- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Utils/Containers/DynamicArray.cpp

    00001
    00002 //
    00003 // Copyright (c) 2004           Model-based Embedded and Robotic Systems Group
    00004 // All Rights Reserved          Massachusetts Institute of Technology
    00005 //
    00006 // This software is provided as is. Model-based Embedded and Robotic Systems
    00007 // (MERS) group does not assume any responsibility.
    00008 //
    00010
    00011 #include "DynamicArray.h"
    00012 #include <cstring>
    00013 #include <cstdio>
    00014 using namespace std;
    00015
    00016 #include <Mers/Utils/Exceptions/ArrayIndexOutOfBoundsException.h>
    00017
    00018 using Mers::Utils::Containers::DynamicArray;
    00019 using Mers::Utils::Exceptions::ArrayIndexOutOfBoundsException;
    00020
    00021 // this should always be NULL so we can return NULL when someone requests
    00022 // an array index that is out of range
    00023 void * DynamicArray::nullPointer = NULL;
    00024
    00026
    00027 DynamicArray::DynamicArray(DynamicArrayType myType, bool myOwnershipStatus,
    00028         BaseModelObject::ObjectType myObjectType)
    00029         : BaseModelObject(myObjectType), dynamicArrayType(myType)
    00030 {
    00031         //cerr << "        DynamicArray: creating " << this << endl;
    00032         mSize = 0;
    00033         maxSize = 0;
    00034         array = NULL;
    00035
    00036         ownsElements = myOwnershipStatus;
    00037 }
    00038
    00040
    00041 DynamicArray::~DynamicArray()
    00042 {
    00043         //cerr << "        DynamicArray: deleting " << this << endl;
    00044         if(NULL != nullPointer){
    00045                 fprintf(stderr, "Error, the nullPointer is no longer NULL, it is 0x%X\n", (unsigned int) nullPointer);
    00046         }
    00047         if(array)
    00048                 delete[] array;
    00049 }
    00050
    00052
    00053 char const * DynamicArray::dynamicArrayTypeToString(DynamicArray::DynamicArrayType daType)
    00054 {
    00055         switch(daType){
    00056         case AssignmentArray:
    00057                 return "Base Model Assignment Array";
    00058         case ClauseArray:
    00059                 return "Base Model Clause Array";
    00060         case DomainArray:
    00061                 return "Base Model Domain Array";
    00062         case ValueArray:
    00063                 return "Base Model Value Array";
    00064         case VariableArray:
    00065                 return "Base Model Variable Array";
    00066         case GIEntryArray:
    00067                 return "Compiled Goal Interpreter Entry Array";
    00068         case IntegerArray:
    00069                 return "Integer Array";
    00070         case oObjectArray:
    00071                 return "Base Model Object Array";
    00072         case oObjectQueue:
    00073                 return "Base Model Object Queue";
    00074         case oHCAAutomatonArray:
    00075                 return "HCA Automaton Array";
    00076         case oHCATransitionArray:
    00077                 return "HCA Transition Array";
    00078         case oMarkedAutomatonArray:
    00079                 return "Marked Automaton Array";
    00080         case oHCAFunctionCallArray:
    00081                 return "HCA Function Call Array";
    00082         case oGIStateHeap:
    00083                 return "GI State Heap";
    00084         case oEstimateHeap:
    00085                 return "Estimate Heap";
    00086         case oDynamicArrayTemplate:
    00087                 return "Dynamic Array Template Class";
    00088         case DAVariableArrayArray:
    00089                 return "Base Model Variable Array Array";
    00090         case DAHBFIGImplicantHeap:
    00091                 return "BFIG Implicant Heap";
    00092         default:
    00093                 return "Unkown Dynamic Array Type";
    00094         }
    00095 }
    00096
    00098
    00099 DynamicArray::DynamicArrayType DynamicArray::getDynamicArrayType() const
    00100 {
    00101         return dynamicArrayType;
    00102 }
    00103
    00105
    00106 void DynamicArray::setOwnershipFlag(bool myOwnershipStatus)
    00107 {
    00108         ownsElements = myOwnershipStatus;
    00109 }
    00110
    00112
    00113 void DynamicArray::makeEmpty()
    00114 {
    00115         if(ownsElements)
    00116                 deleteAll();
    00117         else
    00118                 clearAll();
    00119 }
    00120
    00122
    00123 void DynamicArray::deleteAll()
    00124 {
    00125         unsigned int x;
    00126
    00127         if(array != NULL){
    00128                 for(x = mSize; x > 0; x--){
    00129                         if(NULL != array[x - 1])
    00130                                 deleteElement(array[x - 1]);
    00131                 }
    00132         }else{
    00133                 maxSize = 0;
    00134         }
    00135         mSize = 0;
    00136 }
    00137
    00139
    00140 void DynamicArray::clearAll()
    00141 {
    00142         mSize = 0;
    00143 }
    00144
    00146
    00147 int DynamicArray::resize(unsigned int newSize)
    00148 {
    00149         if(newSize < mSize){
    00150                 // we need to delete some elements to get down to maxSize
    00151                 if(NULL != array && ownsElements){
    00152                         while(mSize > newSize){
    00153                                 mSize--;
    00154                                 if(NULL != array[mSize])
    00155                                         deleteElement(array[mSize]);
    00156                         }
    00157                 }
    00158                 mSize = newSize;
    00159         }else{
    00160                 if(newSize > maxSize){
    00161                         //We need to grow the overall array to support the request
    00162                         void ** newArray;
    00163
    00164                         newArray = new void * [newSize];
    00165                         if(NULL == newArray){
    00166                                 fprintf(stderr, "Error, not enough space to resize this array to %d elements\n", newSize);
    00167                                 return 1;
    00168                         }
    00169                         if(NULL != array){
    00170                                 memcpy(newArray, array, sizeof(void *) * mSize);
    00171                                 delete[] array;
    00172                         }
    00173                         maxSize = newSize;
    00174                         array = newArray;
    00175                 }
    00176                 // we're allocating zero or more new elements but less than maxSize so we can just
    00177                 // initialize the new space to NULL and make mSize = newSize
    00178                 while(mSize < newSize){
    00179                         array[mSize++] = NULL;
    00180                 }
    00181         }
    00182
    00183         // since mSize can be bother equal to or greater than newSize, handle
    00184         // the zero case after we've already deleted all the elements
    00185         // mSize will always be zero here
    00186         if(0 == newSize){
    00187                 if(NULL != array)
    00188                         delete[] array;
    00189                 array = NULL;
    00190                 maxSize = 0;
    00191         }
    00192         return 0;
    00193 }
    00194
    00196
    00197 unsigned int DynamicArray::getLength() const
    00198 {
    00199         return mSize;
    00200 }
    00201
    00203
    00204 bool DynamicArray::isEmpty() const
    00205 {
    00206         return (mSize == 0);
    00207 }
    00208
    00210
    00211 void * DynamicArray::find(char const * elementName)
    00212 {
    00213         unsigned int x;
    00214
    00215         for(x = 0; x < mSize; x++){
    00216                 if(foundMatch(elementName, array[x]))
    00217                         return array[x];
    00218         }
    00219         return NULL;
    00220 }
    00221
    00223
    00224 void const * DynamicArray::find(char const * elementName) const
    00225 {
    00226         unsigned int x;
    00227
    00228         for(x = 0; x < mSize; x++){
    00229                 if(foundMatch(elementName, array[x]))
    00230                         return array[x];
    00231         }
    00232         return NULL;
    00233 }
    00234
    00236
    00237 void * & DynamicArray::peekBack()
    00238 {
    00239         // make sure the index is in range
    00240         if(mSize > 0)
    00241                 return array[mSize - 1];
    00242         // otherwise return null data
    00243         fprintf(stderr, "Attempt to access an element in an empty array\n");
    00244         return nullPointer;
    00245 }
    00246
    00248
    00249 void const * & DynamicArray::peekBack() const
    00250 {
    00251         // make sure the index is in range
    00252         if(mSize > 0)
    00253                 return (void const * &) array[mSize - 1];
    00254         // otherwise return null data
    00255         fprintf(stderr, "Attempt to access an element in an empty array\n");
    00256         return (void const * &) nullPointer;
    00257 }
    00258
    00260
    00261 void DynamicArray::erase(unsigned int elementIndex)
    00262 {
    00263         // Make sure our range is valid.
    00264         if( elementIndex >= mSize )
    00265                 throw new ArrayIndexOutOfBoundsException(0, mSize, elementIndex,
    00266                         __FILE__, __LINE__);
    00267
    00268         // Get the data we're erasing.
    00269         void * data = array[elementIndex];
    00270
    00271         // Update the array (Move any necessary data).
    00272         memmove(array + elementIndex, array + elementIndex + 1, sizeof(void *) * (mSize - elementIndex - 1));
    00273
    00274         // Pop the last element and discard (we don't care what it is).
    00275         popBack();
    00276
    00277         // if we should clean up memory, do so.
    00278         if( ownsElements && data != NULL )
    00279                 deleteElement(data);
    00280 }
    00281
    00283
    00284 void * &DynamicArray::operator[](unsigned int arrayIndex)
    00285 {
    00286         // make sure the index is in range
    00287         if(arrayIndex < mSize)
    00288                 return array[arrayIndex];
    00289         // otherwise return null data
    00290         if(mSize == 0) {
    00291                 fprintf(stderr, "Array index is out of bounds, array was empty: %u\n", arrayIndex);
    00292                 throw new ArrayIndexOutOfBoundsException(0, mSize, arrayIndex, __FILE__, __LINE__);
    00293         } else {
    00294                 fprintf(stderr, "Array index is out of bounds (0-%u): %u\n", mSize - 1, arrayIndex);
    00295                 throw new ArrayIndexOutOfBoundsException(0, mSize - 1, arrayIndex, __FILE__, __LINE__);
    00296         }
    00297         return nullPointer;
    00298 }
    00299
    00301
    00302 void const * & DynamicArray::operator[](unsigned int arrayIndex) const
    00303 {
    00304         // make sure the index is in range
    00305         if(arrayIndex < mSize)
    00306                 return (void const * &)array[arrayIndex];
    00307         // otherwise return null data
    00308         if(mSize == 0) {
    00309                 fprintf(stderr, "Array index is out of bounds, array was empty: %u\n", arrayIndex);
    00310                 throw new ArrayIndexOutOfBoundsException(0, mSize, arrayIndex, __FILE__, __LINE__);
    00311         } else {
    00312                 fprintf(stderr, "Array index is out of bounds (0-%u): %u\n", mSize - 1, arrayIndex);
    00313                 throw new ArrayIndexOutOfBoundsException(0, mSize - 1, arrayIndex, __FILE__, __LINE__);
    00314         }
    00315         return (void const * &)nullPointer;
    00316 }
    00317
    00319
    00320 void * &DynamicArray::operator[](int arrayIndex)
    00321 {
    00322         // make sure we don't have a negative index
    00323         if(arrayIndex >= 0)
    00324                 return DynamicArray::operator []((unsigned int) arrayIndex);
    00325         // out of bounds
    00326         if(mSize == 0) {
    00327                 fprintf(stderr, "Array index is out of bounds, array was empty: %d\n", arrayIndex);
    00328                 throw new ArrayIndexOutOfBoundsException(0, mSize, arrayIndex, __FILE__, __LINE__);
    00329         } else {
    00330                 fprintf(stderr, "Array index is out of bounds (0-%u): %d\n", mSize - 1, arrayIndex);
    00331                 throw new ArrayIndexOutOfBoundsException(0, mSize - 1, arrayIndex, __FILE__, __LINE__);
    00332         }
    00333         return nullPointer;
    00334 }
    00335
    00337
    00338 void const * &DynamicArray::operator[](int arrayIndex) const
    00339 {
    00340         // make sure we don't have a negative index
    00341         if(arrayIndex >= 0)
    00342                 return DynamicArray::operator []((unsigned int) arrayIndex);
    00343         // out of bounds
    00344         if(mSize == 0) {
    00345                 fprintf(stderr, "Array index is out of bounds, array was empty: %d\n", arrayIndex);
    00346                 throw new ArrayIndexOutOfBoundsException(0, mSize, arrayIndex, __FILE__, __LINE__);
    00347         } else {
    00348                 fprintf(stderr, "Array index is out of bounds (0-%u): %d\n", mSize - 1, arrayIndex);
    00349                 throw new ArrayIndexOutOfBoundsException(0, mSize - 1, arrayIndex, __FILE__, __LINE__);
    00350         }
    00351         return (void const * &)nullPointer;
    00352 }
    00353
    00355
    00356 #ifndef EMBEDDED
    00357
    00358 void DynamicArray::print(ostream &out) const
    00359 {
    00360         printArray(out, "\n");
    00361 }
    00362
    00363 #endif
    00364
    00366
    00367 DynamicArray::DynamicArray(DynamicArray const &other)
    00368 : BaseModelObject(other), dynamicArrayType(other.dynamicArrayType)
    00369 {
    00370         mSize = 0;
    00371         maxSize = 0;
    00372         array = NULL;
    00373
    00374         ownsElements = other.ownsElements;
    00375         // note we can't copy here since if we need to call newElement, it won't be defined yet.
    00376 }
    00377
    00379
    00380 #ifndef EMBEDDED
    00381
    00382 /*void DynamicArray::printElement(ostream &out, void const * element) const
    00383 {
    00384         out << "<element " << element << ">";
    00385 }*/
    00386
    00388
    00389 void DynamicArray::printArray(ostream &out, char const * seperator,
    00390                                                                                                                         bool skipNULL)
    00391 {
    00392         ((DynamicArray const *)this)->printArray(out, seperator, skipNULL);
    00393 }
    00394
    00396
    00397 void DynamicArray::printArray(ostream &out, char const * seperator,
    00398                                                                                                                         bool skipNULL) const
    00399 {
    00400         unsigned int x;
    00401
    00402         for(x = 0; x < getLength(); x++){
    00403                 if(x != 0)
    00404                         out << seperator;
    00405                 if(array[x] == NULL && skipNULL)
    00406                         out << "NULL Pointer";
    00407                 else
    00408                         printElement(out, array[x]);
    00409         }
    00410 }
    00411
    00412 #endif
    00413
    00415
    00416 /*void DynamicArray::deleteElement(void * element) const
    00417 {
    00418         fprintf(stderr, "Unable to delete element 0x%X because it is of an unknown class\n", element);
    00419 }*/
    00420
    00422
    00423 /*void * DynamicArray::newElement(void const * element) const
    00424 {
    00425         return NULL;
    00426 }*/
    00427
    00429
    00430 bool DynamicArray::foundMatch(char const * elementName, void const * element) const
    00431 {
    00432         (void) elementName;
    00433         (void) element;
    00434         return false;
    00435 }
    00436
    00438
    00439 bool DynamicArray::isEqual(void const * element1, void const * element2) const
    00440 {
    00441         return (element1 == element2);
    00442 }
    00443
    00445
    00446 void DynamicArray::destroy()
    00447 {
    00448         makeEmpty();
    00449 }
    00450
    00452
    00453 int DynamicArray::copy(DynamicArray const &other)
    00454 {
    00455         unsigned int x;
    00456
    00457         if(this == &other)
    00458                 return 0;
    00459
    00460         makeEmpty();
    00461
    00462         if(FAILED(resize(other.mSize))){
    00463                 fprintf(stderr, "Failed to allocated memory for DynamicArray copy!\n");
    00464                 return 1;
    00465         }
    00466
    00467         for(x = 0; x < mSize; x++){
    00468                 void * element;
    00469
    00470                 if(other.array[x] != NULL){
    00471                         // if we own everything in our array, we need to copy the data,
    00472                         // otherwise we will delete someone else's data.
    00473                         // This maybe easier with reference counting.
    00474                         if(ownsElements){
    00475                                 element = newElement(other.array[x]);
    00476
    00477                                 if(NULL == element){
    00478 #ifndef EMBEDDED
    00479                                         cerr << "Failed to allocate a new copy of:" << endl;
    00480                                         printElement(cerr, other.array[x]);
    00481                                         cerr << endl;
    00482 #else
    00483                                         fprintf(stderr, "Failed to allocate a new copy of a dynamic array element\n");
    00484 #endif
    00485                                         mSize = x;
    00486                                         return 2;
    00487                                 }
    00488                         }else{
    00489                                 element = other.array[x];
    00490                         }
    00491                 }else{
    00492                         element = NULL;
    00493                 }
    00494
    00495                 array[x] = element;
    00496         }
    00497         return 0;
    00498 }
    00499
    00501
    00502 int DynamicArray::grow()
    00503 {
    00504         void ** newArray;
    00505         int newMaxSize;
    00506
    00507         // make sure we grow to a proper size (handle 0 special case)
    00508         if(maxSize > 0)
    00509                 newMaxSize = maxSize << 1;
    00510         else
    00511                 newMaxSize = 1;
    00512
    00513         // create the replacement array
    00514         newArray = new void * [newMaxSize];
    00515         if(NULL != newArray)
    00516         {
    00517                 // copy and then delete the old array, replacing it with the new array
    00518                 memcpy(newArray, array, sizeof(void *) * mSize);
    00519                 if(NULL != array)
    00520                         delete[] array;
    00521                 array = newArray;
    00522                 maxSize = newMaxSize;
    00523                 return 0;
    00524         }else{
    00525                 // allocation failed, return an error
    00526                 fprintf(stderr, "Failed to allocate a new larger array of %d elements", newMaxSize);
    00527                 return 1;
    00528         }
    00529 }
    00530
    00532
    00533 int DynamicArray::shrink()
    00534 {
    00535         void ** newArray;
    00536         unsigned int newMaxSize;
    00537
    00538         // make sure we dont shrink below 2 (we could allow down to 1)
    00539         if(maxSize > 2)
    00540                 newMaxSize = maxSize >> 1;
    00541         else
    00542                 return 0;
    00543
    00544         // delete mSize until it's == newMaxSize
    00545         while(mSize > newMaxSize){
    00546                 mSize--;
    00547                 if(ownsElements && NULL != array[mSize])
    00548                         deleteElement(array[mSize]);
    00549         }
    00550
    00551         // allocate the new smaller array
    00552         newArray = new void * [newMaxSize];
    00553         if(NULL != newArray)
    00554         {
    00555                 // copy of the previous data - mSize should be < newMaxSize/2 so this
    00556                 // shouldn't exceed the newArray's bounds
    00557                 memcpy(newArray, array, sizeof(void *) * mSize);
    00558                 if(NULL != array)
    00559                         delete[] array;
    00560                 array = newArray;
    00561                 maxSize = newMaxSize;
    00562                 return 0;
    00563         }else{
    00564                 // couldn't create the smaller array (no big deal)
    00565                 fprintf(stderr, "Failed to allocate a new smaller array of %d elements", newMaxSize);
    00566                 return 1;
    00567         }
    00568 }
    00569
    00571
    00572 int DynamicArray::pushBack(void * data)
    00573 {
    00574         // make sure we have room for another element, and grow if not
    00575         if(mSize >= maxSize){
    00576                 if(FAILED(grow())){
    00577                         // if grow fails, return and delete this element
    00578                         if(ownsElements && data)
    00579                                 deleteElement(data);
    00580                         return 1;
    00581                 }
    00582         }
    00583         array[mSize++] = data;
    00584         return 0;
    00585 }
    00586
    00588
    00589 void * DynamicArray::popBack()
    00590 {
    00591         void * data = NULL;
    00592
    00593         // make sure we aren't empty first
    00594         if(mSize > 0)
    00595         {
    00596                 // deallocate the last element
    00597                 data = array[--mSize];
    00598                 // shrink if we're less than 1/4 full
    00599                 if(mSize < (maxSize >> 2))
    00600                         shrink();
    00601         }
    00602         return data;
    00603 }
    00604
    00606
    00607 void DynamicArray::insert(unsigned int elementIndex, void * data)
    00608 {
    00609         if(elementIndex >= mSize){
    00610                 pushBack(data);
    00611         }else{
    00612                 pushBack(NULL);
    00613                 memmove(array + elementIndex + 1, array + elementIndex, sizeof(void *) * (mSize - elementIndex - 1));
    00614                 array[elementIndex] = data;
    00615         }
    00616 }
    00617
    00619
    00620 DynamicArray const & DynamicArray::operator =(DynamicArray const &other)
    00621 {
    00622         if(FAILED(copy(other))){
    00623 #ifndef EMBEDDED
    00624                 cerr << "Unable to copy DynamicArray:" << endl << other << endl;
    00625 #else
    00626                 fprintf(stderr, "Unable to copy DynamicArray\n");
    00627 #endif
    00628         }
    00629         return other;
    00630 }
    00631
    00633
    00634 DynamicArray const & DynamicArray::operator +=(DynamicArray const &other)
    00635 {
    00636         unsigned int x;
    00637         unsigned int len, myLen;
    00638
    00639         len = other.getLength();
    00640         myLen = mSize;
    00641
    00642         // make sure we have enough room
    00643         if(FAILED(resize(myLen + len))){
    00644                 fprintf(stderr, "Failed to add enough space to this DynamicArray to add the contents of another DynamicArray\n");
    00645                 return *this;
    00646         }
    00647
    00648         for(x = 0; x < len; x++){
    00649                 void * element;
    00650
    00651                 if(other[x] != NULL){
    00652                         if(ownsElements){
    00653                                 element = other.newElement(other[x]);
    00654                                 if(NULL == element){
    00655 #ifndef EMBEDDED
    00656                                         cerr << "Error, could not duplicate DynamicArray Element:" << endl;
    00657                                         other.printElement(cerr, other[x]);
    00658                                         cerr << endl;
    00659 #else
    00660                                         fprintf(stderr, "Error, could not duplicate DynamicArray Element\n");
    00661 #endif
    00662                                 }
    00663                         }else{
    00664                                 element = other.array[x];
    00665                         }
    00666                 }else{
    00667                         element = NULL;
    00668                 }
    00669                 array[myLen + x] = element;
    00670         }
    00671
    00672         // this is redundant
    00673         //mSize = myLen + len;
    00674
    00675         return *this;
    00676 }
    00677
    00679
    00680 DynamicArray const & DynamicArray::operator +=(void const * element)
    00681 {
    00682         if(NULL == element){
    00683                 pushBack(NULL);
    00684                 return *this;
    00685         }
    00686
    00687         void * newE;
    00688         if(ownsElements){
    00689                 newE = newElement(element);
    00690                 if(NULL == newE){
    00691                         fprintf(stderr, "Error, could not duplicate a dynamic array element, insufficient memory");
    00692                         // already out of memory, might as well not push our luck and try and push back NULL
    00693                         return *this;
    00694                 }
    00695         }else{
    00696                 newE = (void *) element;
    00697         }
    00698         pushBack(newE);
    00699         return *this;
    00700 }
    00701
    00703
    00704 bool DynamicArray::operator ==(DynamicArray const &other) const
    00705 {
    00706         if(mSize != other.mSize)
    00707                 return false;
    00708
    00709         for(unsigned int x = 0; x < mSize; x++){
    00710                 if(!isEqual(array[x], other.array[x]))
    00711                         return false;
    00712         }
    00713         return true;
    00714 }
    00715
    00717
    00718 bool DynamicArray::operator !=(DynamicArray const &other) const
    00719 {
    00720         return !DynamicArray::operator ==(other);
    00721 }
    00722