(C) An X-Ryl669 project 2007
This document describes Unlimited Zooming Interface source code. UZI stands for Unlimited Zooming Interface, and source code license is
00001 #ifndef hpp_CPP_Container_CPP_hpp 00002 #define hpp_CPP_Container_CPP_hpp 00003 00004 // We need Bool2Type declaration 00005 #include "../Types/Bool2Type.hpp" 00006 00007 00009 namespace Container 00010 { 00011 namespace PrivateGenericImplementation 00012 { 00014 template <typename T> 00015 struct MemoryPolicy 00016 { 00018 static void Copy(T & dest, const T & src); 00020 static void CopyArray(T * dest, const T * src, const size_t & destSize, const size_t & srcSize); 00024 static void CopyArray(T *& dest, const T * src, size_t & destSize, const size_t & srcSize); 00026 static T & DefaultElement(); // This method can throw 00028 static size_t Search(const T* array, const size_t & arraySize, const T & valueToLookFor); 00030 static size_t ReverseSearch(const T* array, const size_t & arraySize, const T & valueToLookFor); 00032 static T * NonDestructiveAlloc(const T* array, const size_t & currentSize, const size_t & newSize, const T & fillWith); 00034 static T * Insert(const T* array, const size_t & currentSize, const size_t & newSize, const size_t & index, const T & elementToInsert); 00036 static void DeleteArray(const T * array, const size_t & currentSize); 00038 static bool CompareArray(const T * array1, const T * array2, const size_t & commonSize); 00039 }; 00040 00050 template <typename T, class Policy = MemoryPolicy<T>, bool ExactSize = false> 00051 class Array 00052 { 00053 private: 00054 enum { elementSize = sizeof(T) }; 00055 public: 00057 inline Array() : array(NULL), currentSize(0), allocatedSize(0) { } 00059 inline Array(const Array & other) : array(NULL), currentSize(0), allocatedSize(0) { *this = other; } 00061 ~Array() { Clear(); } 00062 00063 00064 // Interface 00065 public: 00067 inline void Clear() { Clear(NULL); } 00068 00070 inline void Append(const T & ref) throw() { Add(ref, (Bool2Type<ExactSize> * )0); } 00074 inline void insertBefore(uint32 index, const T & ref) throw() { Insert(index, ref, (Bool2Type<ExactSize> * )0); } 00078 inline void Remove(uint32 index) throw() { Remove(index, (Bool2Type<ExactSize> * )0); } 00079 00080 00082 inline const Array& operator = ( const Array & other) 00083 { 00084 if (&other == this) return *this; 00085 Policy::CopyArray(array, other.array, allocatedSize, other.currentSize); 00086 currentSize = other.currentSize; 00087 return *this; 00088 } 00089 00091 inline size_t getSize() const { return currentSize; } 00096 inline T & operator [] (uint32 index) { return index < currentSize ? array[index] : Policy::DefaultElement(); } 00101 inline const T & operator [] (uint32 index) const { return index < currentSize ? array[index] : Policy::DefaultElement(); } 00106 inline uint32 indexOf(const T & objectToSearch) { return Policy::Search(array, currentSize, objectToSearch); } 00111 inline uint32 lastIndexOf(const T & objectToSearch) { return Policy::ReverseSearch(array, currentSize, objectToSearch); } 00113 inline T & getElementAtUncheckedPosition(uint32 index) { return array[index]; } 00115 inline const T & getElementAtUncheckedPosition(uint32 index) const { return array[index]; } 00117 inline bool operator == (const Array & other) { return other.currentSize == currentSize && Policy::CompareArray(array, other.array, currentSize); } 00118 00119 00120 private: 00122 inline void Add(const T & ref, Bool2Type<true> *) throw() 00123 { 00124 array = Policy::NonDestructiveAlloc(array, currentSize, currentSize+1, ref); 00125 if (array == NULL) { Reset(); return; } 00126 allocatedSize = ++currentSize; 00127 } 00129 inline void Add(const T & ref, Bool2Type<false> *) throw() 00130 { 00131 // Check if the array needs reallocation 00132 if (currentSize >= allocatedSize) 00133 { 00134 // Need to realloc the data 00135 if (allocatedSize == 0) allocatedSize = 2; else allocatedSize *= 2; 00136 array = Policy::NonDestructiveAlloc(array, currentSize, allocatedSize, Policy::DefaultElement()); 00137 if (array == NULL) { Reset(); return; } 00138 } 00139 // Copy the data 00140 Policy::Copy(array[currentSize],ref); 00141 currentSize ++; 00142 } 00143 00145 inline void Insert(uint32 index, const T & ref, Bool2Type<true> * t) throw() 00146 { 00147 if (index >= currentSize) { Add(ref, t); return; } 00148 array = Policy::Insert(array, currentSize, currentSize+1, index, ref); 00149 if (array == NULL) { Reset(); return; } 00150 allocatedSize = ++currentSize; 00151 } 00153 inline void Insert(uint32 index, const T & ref, Bool2Type<false> * t) throw() 00154 { 00155 if (index >= currentSize) { Add(ref, t); return; } 00156 // Check if the array needs reallocation 00157 if (currentSize >= allocatedSize) 00158 { 00159 // Need to realloc the data 00160 if (allocatedSize == 0) allocatedSize = 2; else allocatedSize *= 2; 00161 array = Policy::Insert(array, currentSize, allocatedSize, index, ref); 00162 if (array == NULL) { Reset(); return; } 00163 } else 00164 { // Need to move the data 00165 uint32 i = currentSize; 00166 for (; i > index; i--) 00167 Policy::Copy(array[i], array[i - 1]); 00168 Policy::Copy(array[i], ref); 00169 } 00170 currentSize ++; 00171 } 00172 00174 inline void Remove(uint32 index, Bool2Type<true> *) throw() 00175 { 00176 if (index < currentSize) 00177 { 00178 T * newArray = Policy::NonDestructiveAlloc(NULL, 0, currentSize - 1, Policy::DefaultElement()); 00179 if (newArray == NULL) return; 00180 // Copy the data before the index 00181 Policy::CopyArray(newArray, array, currentSize - 1, index); 00182 // Copy the data after the index 00183 Policy::CopyArray(&newArray[index], &array[index+1], currentSize - 1, currentSize - index - 1); 00184 // Then switch the pointers 00185 allocatedSize = --currentSize; 00186 // Delete the previous array 00187 Policy::DeleteArray(array, allocatedSize + 1); 00188 00189 array = newArray; 00190 } 00191 } 00192 00194 inline void Remove(uint32 index, Bool2Type<false> *) throw() 00195 { 00196 if (index < currentSize) 00197 { 00198 // Copy the data after the index 00199 Policy::CopyArray(&array[index], &array[index+1], currentSize - 1, currentSize - index - 1); 00200 // Then switch the pointers 00201 --currentSize; 00202 } 00203 } 00204 00205 00207 inline void Reset() { currentSize = 0; allocatedSize = 0; array = NULL; } 00211 inline void Clear(T * ref) 00212 { Policy::DeleteArray(array, allocatedSize); Reset(); } 00213 private: 00215 T * array; 00217 size_t currentSize; 00219 size_t allocatedSize; 00220 }; 00221 00222 00224 template <typename T> 00225 struct MemoryListPolicy 00226 { 00228 static void CopyPtr(T* & dest, T* const & src); 00230 static void CopyArray(T** dest, T** const src, const size_t & destSize, const size_t & srcSize); 00234 static void CopyArray(T**& dest, T** const src, size_t & destSize, const size_t & srcSize); 00238 static void DuplicateArray(T**& dest, T** const src, size_t & destSize, const size_t & srcSize); 00242 static size_t Search(T** const array, const size_t & arraySize, T* const & valueToLookFor); 00244 static size_t ReverseSearch(T** const array, const size_t & arraySize, T* const & valueToLookFor); 00246 static size_t SearchRef(const T** array, const size_t & arraySize, const T & valueToLookFor); 00248 static T& DefaultSubElement(); 00250 static T* DefaultElement(); 00251 static T** NonDestructiveAlloc(T** const array, const size_t & currentSize, const size_t & newSize, T* const & fillWith); 00252 static T* * Insert(T** const array, const size_t & currentSize, const size_t & newSize, const size_t & index, T* const & elementToInsert); 00254 static void DeleteArray(T* * const array, const size_t & currentSize); 00256 static void Remove(T * const data); 00258 static bool CompareArray(T** const array1, T** const array2, const size_t & commonSize); 00259 }; 00260 00287 template <typename TElem, class Policy = MemoryListPolicy<TElem>, bool ExactSize = false> 00288 class IndexList 00289 { 00290 private: 00291 enum { elementSize = sizeof(TElem) }; 00292 typedef TElem * TPtr; 00293 public: 00295 inline IndexList() : array(NULL), currentSize(0), allocatedSize(0) { } 00297 inline IndexList(const IndexList & other) : array(NULL), currentSize(0), allocatedSize(0) { *this = other; } 00299 ~IndexList() { Clear(); } 00300 00301 00302 // Interface 00303 public: 00305 inline void Clear() { Clear(NULL); } 00306 00308 inline void Append(const TPtr & ref) throw() { Add(ref, (Bool2Type<ExactSize> * )0); } 00313 inline void insertBefore(uint32 index, const TPtr & ref) throw() { Insert(index, ref, (Bool2Type<ExactSize> * )0); } 00317 inline void Remove(uint32 index) throw() { Remove(index, (Bool2Type<ExactSize> * )0); } 00318 00319 00321 inline const IndexList& operator = ( const IndexList & other) 00322 { 00323 if (&other == this) return *this; 00324 Policy::DuplicateArray(array, other.array, allocatedSize, other.currentSize); 00325 currentSize = other.currentSize; 00326 return *this; 00327 } 00328 00330 inline size_t getSize() const { return currentSize; } 00335 inline TElem & operator [] (uint32 index) { return index < currentSize ? *array[index] : Policy::DefaultSubElement(); } 00340 inline uint32 indexOf(const TPtr & objectToSearch) { return Policy::Search(array, currentSize, objectToSearch); } 00345 inline uint32 lastIndexOf(const TPtr & objectToSearch) { return Policy::ReverseSearch(array, currentSize, objectToSearch); } 00350 inline uint32 indexOfMatching(const TElem & objectToSearch) { return Policy::SearchRef(array, currentSize, objectToSearch); } 00352 inline TPtr & getElementAtUncheckedPosition(uint32 index) { return array[index]; } 00354 inline bool operator == (const IndexList & other) { return other.currentSize == currentSize && Policy::CompareArray(array, other.array, currentSize); } 00355 00356 00357 private: 00359 inline void Add(const TPtr & ref, Bool2Type<true> *) throw() 00360 { 00361 array = Policy::NonDestructiveAlloc(array, currentSize, currentSize+1, ref); 00362 if (array == NULL) { Reset(); return; } 00363 allocatedSize = ++currentSize; 00364 } 00366 inline void Add(const TPtr & ref, Bool2Type<false> *) throw() 00367 { 00368 // Check if the array needs reallocation 00369 if (currentSize >= allocatedSize) 00370 { 00371 // Need to realloc the data 00372 if (allocatedSize == 0) allocatedSize = 2; else allocatedSize *= 2; 00373 array = Policy::NonDestructiveAlloc(array, currentSize, allocatedSize, Policy::DefaultElement()); 00374 if (array == NULL) { Reset(); return; } 00375 } 00376 // Copy the data 00377 Policy::CopyPtr(array[currentSize], ref); 00378 currentSize ++; 00379 } 00380 00382 inline void Insert(uint32 index, const TPtr & ref, Bool2Type<true> * t) throw() 00383 { 00384 if (index >= currentSize) { Add(ref, t); return; } 00385 array = Policy::Insert(array, currentSize, currentSize+1, index, ref); 00386 if (array == NULL) { Reset(); return; } 00387 allocatedSize = ++currentSize; 00388 } 00390 inline void Insert(uint32 index, const TPtr & ref, Bool2Type<false> * t) throw() 00391 { 00392 if (index >= currentSize) { Add(ref, t); return; } 00393 // Check if the array needs reallocation 00394 if (currentSize >= allocatedSize) 00395 { 00396 // Need to realloc the data 00397 if (allocatedSize == 0) allocatedSize = 2; else allocatedSize *= 2; 00398 array = Policy::Insert(array, currentSize, allocatedSize, index, ref); 00399 if (array == NULL) { Reset(); return; } 00400 } else 00401 { // Need to move the data 00402 uint32 i = currentSize; 00403 for (; i > index; i--) 00404 Policy::CopyPtr(array[i], array[i - 1]); 00405 Policy::CopyPtr(array[i], ref); 00406 } 00407 currentSize ++; 00408 } 00409 00411 inline void Remove(uint32 index, Bool2Type<true> *) throw() 00412 { 00413 if (index < currentSize) 00414 { 00415 TPtr * newArray = Policy::NonDestructiveAlloc(NULL, 0, currentSize - 1, Policy::DefaultElement()); 00416 if (newArray == NULL) return; 00417 // Copy the data before the index 00418 Policy::CopyArray(newArray, array, currentSize - 1, index); 00419 // Copy the data after the index 00420 Policy::CopyArray(&newArray[index], &array[index+1], currentSize - 1, currentSize - index - 1); 00421 // Then switch the pointers 00422 allocatedSize = --currentSize; 00423 // Delete the previous array 00424 Policy::DeleteArray(array, allocatedSize + 1); 00425 00426 array = newArray; 00427 } 00428 } 00429 00431 inline void Remove(uint32 index, Bool2Type<false> *) throw() 00432 { 00433 if (index < currentSize) 00434 { 00435 // Remove the given data 00436 Policy::Remove(array[index]); 00437 // Copy the data after the index 00438 Policy::CopyArray(&array[index], &array[index+1], currentSize - 1, currentSize - index - 1); 00439 // Then switch the pointers 00440 --currentSize; 00441 // Zero the last element 00442 array[currentSize] = Policy::DefaultElement(); 00443 } 00444 } 00445 00446 00448 inline void Reset() { currentSize = 0; allocatedSize = 0; array = NULL; } 00452 inline void Clear(TPtr *) 00453 { Policy::DeleteArray(array, allocatedSize); Reset(); } 00454 private: 00456 TElem ** array; 00458 size_t currentSize; 00460 size_t allocatedSize; 00461 }; 00462 00463 00464 00466 template <typename T> 00467 struct SearchPolicyInterface 00468 { 00469 typedef T & Result; 00471 static Result DefaultValue(); 00473 static Result From(T * x); 00475 static bool Compare(const T & a, const T & b); 00476 00478 enum { DefaultConstructibleAndCopyable }; 00479 }; 00480 00483 template <bool flag> 00484 struct SelectImpl 00485 { 00486 template <class T, class U> 00487 struct In 00488 { 00489 typedef T Result; 00490 }; 00491 }; 00492 00495 template <> 00496 struct SelectImpl<false> 00497 { 00498 template <class T, class U> 00499 struct In 00500 { 00501 typedef U Result; 00502 }; 00503 }; 00506 template <bool flag, typename T, typename U> 00507 struct Select 00508 { 00509 typedef typename SelectImpl<flag>::template In<T, U>::Result Result; 00510 }; 00511 00512 00596 template <class U, unsigned int pow2 = 4, class SearchPolicy = SearchPolicyInterface<U> > 00597 class ChainedList 00598 { 00599 public: 00601 enum 00602 { 00603 ChainedEnd = -1, 00604 ChainedError = ChainedEnd, 00605 ChainedStart = 0, 00606 ChainedBS = 1<<pow2, 00607 }; 00608 00609 private: 00611 class NodeNotCopyable 00612 { 00613 public: 00615 NodeNotCopyable * mpxPrevious; 00617 NodeNotCopyable * mpxNext; 00619 U * mpuElement; 00620 00621 00623 NodeNotCopyable(U* t = NULL) : mpxPrevious(NULL), mpxNext(NULL), mpuElement(t) {} 00625 ~NodeNotCopyable() 00626 { 00627 if (mpuElement!=NULL) delete mpuElement; 00628 } 00629 00631 void Set(U* t) { mpuElement = t; } 00633 U& Get() { return (*mpuElement); } 00634 }; 00635 00637 class NodeCopyable 00638 { 00639 public: 00641 NodeCopyable * mpxPrevious; 00643 NodeCopyable * mpxNext; 00645 U * mpuElement; 00646 public: 00648 NodeCopyable(U* t = NULL) : mpxPrevious(NULL), mpxNext(NULL), mpuElement(t) {} 00650 ~NodeCopyable() 00651 { 00652 if (mpuElement!=NULL) delete mpuElement; 00653 } 00654 00656 void Set(U* t) { mpuElement = t; } 00658 U& Get() { return (*mpuElement); } 00659 00660 // Add the copy interface 00661 public: 00663 NodeCopyable(const U& t) : mpxPrevious(NULL), mpxNext(NULL) { mpuElement = new U(t); } 00665 void Set(const U& t) { mpuElement = new U(t); } 00666 00667 }; 00668 00669 typedef typename Select<SearchPolicy::DefaultConstructibleAndCopyable, NodeCopyable, NodeNotCopyable>::Result Node; 00670 00672 typedef typename Select<SearchPolicy::DefaultConstructibleAndCopyable, U&, U*>::Result DefaultParamType; 00673 typedef typename Select<SearchPolicy::DefaultConstructibleAndCopyable, const U&, const U*>::Result DefaultConstParamType; 00674 00675 private: 00677 template <unsigned int size> 00678 class LinearBlock 00679 { 00680 // Members 00681 private: 00683 LinearBlock * spxNext; 00685 LinearBlock * spxPrevious; 00687 Node sapxBlock[size]; 00689 unsigned char soUsed; 00690 00691 // Construction 00692 public: 00694 LinearBlock(LinearBlock * previous = NULL, LinearBlock * next = NULL) : spxPrevious(previous), spxNext(next) , soUsed(0) {} 00696 ~LinearBlock() 00697 { 00698 if ( spxNext!=NULL || spxPrevious!=NULL) 00699 { 00700 if (spxNext!=NULL) 00701 spxNext->spxPrevious = spxPrevious; 00702 if (spxPrevious!=NULL) 00703 spxPrevious->spxNext = spxNext; 00704 00705 spxNext = spxPrevious = NULL; 00706 } 00707 } 00708 00709 // Interface 00710 public: 00712 inline void Connect(LinearBlock * previous, LinearBlock * next) { spxPrevious = previous; spxNext = next; } 00714 inline void Delete() 00715 { 00716 if (spxNext!=NULL) 00717 spxNext->spxPrevious = spxPrevious; 00718 if (spxPrevious!=NULL) 00719 spxPrevious->spxNext = spxNext; 00720 00721 spxNext = spxPrevious = NULL; 00722 delete this; 00723 } 00724 00726 inline LinearBlock<size> * GoFirst() { LinearBlock<size>* pNode = this; while (pNode->spxPrevious != NULL) pNode = spxPrevious; return pNode; } 00728 inline LinearBlock<size> * GoLast() { LinearBlock<size>* pNode = this; while (pNode->spxNext != NULL) pNode = spxNext; return pNode; } 00729 00730 00732 inline bool CreateNewBlock() 00733 { 00734 if (spxNext!=NULL) return false; 00735 LinearBlock<size>* pNode = new LinearBlock<size>(this, NULL); 00736 if (pNode == NULL) return false; 00737 else spxNext = pNode; 00738 return true; 00739 } 00740 00742 inline Node * GetData() { return &sapxBlock[0]; } 00744 LinearBlock<size> * Find(Node * pNode) 00745 { 00746 if (pNode==NULL) return NULL; 00747 LinearBlock<size> * pBlock = GoFirst(); 00748 LinearBlock<size> * pEnd = GoLast(); 00749 for (; pBlock != pEnd; pBlock = pBlock->spxNext) 00750 if ( pNode >= pBlock->GetData() && pNode <= pBlock->GetData() + size) return pBlock; 00751 return NULL; 00752 } 00753 00754 private: 00761 bool DeleteAll() 00762 { 00763 LinearBlock<size>* pNode2, *pNode = GoFirst(); 00764 if (pNode == NULL) return false; 00765 if (pNode->spxNext == NULL) 00766 { 00767 pNode->Delete(); 00768 pNode = NULL; 00769 return true; 00770 } 00771 00772 // Goto second pointer until next pointer is different from null , advance to next 00773 for (; pNode != NULL; ) 00774 { 00775 pNode2 = pNode->spxNext; 00776 pNode->Delete(); 00777 pNode = pNode2; 00778 } 00779 return true; 00780 } 00781 public: 00782 friend class ChainedList<U, pow2, SearchPolicy>; 00783 }; 00784 00785 // Members 00786 private: 00788 Node * mpxFirst; 00790 Node * mpxLast; 00792 mutable Node * mpxCurrent; 00794 unsigned int mlNumberOfNodes; 00795 00797 unsigned int mlNumberOfBlocks; 00799 // unsigned int mlBlockSize; 00801 LinearBlock<ChainedBS> * mpxBlock; 00803 LinearBlock<ChainedBS> * mpxBLast; 00804 00805 private: 00809 bool mbUseBlocks; 00811 bool mbIntegrity; 00812 00813 // Properties 00814 public: 00816 inline unsigned int getSize() const { return mlNumberOfNodes; } 00817 00818 // Interface 00819 public: 00829 bool Add(DefaultConstParamType, const unsigned int& = ChainedEnd); 00833 bool Add(U*, const unsigned int& = ChainedEnd); 00834 00838 bool Insert(DefaultConstParamType, const unsigned int& = ChainedStart); 00845 bool Sub(const unsigned int& = ChainedEnd); 00850 bool Remove(const unsigned int& = ChainedStart); 00851 00856 unsigned int indexOf(DefaultConstParamType); 00861 unsigned int lastIndexOf(DefaultConstParamType); 00864 bool Swap(const unsigned int &, const unsigned int &); 00865 00866 // Helpers functions 00867 private: 00869 inline Node * CreateNode(); 00871 inline Node * Goto(const unsigned int &); 00873 inline bool UseBlocks(const bool &); 00875 bool Connect(Node *, Node *, Node *); 00876 00877 public: 00881 bool Add(const ChainedList&, const unsigned int & = ChainedEnd); 00882 00886 bool Free(); 00889 bool Change(DefaultConstParamType, const unsigned int &); 00890 00891 00896 U * parseList(const bool & bInit = false) const; 00900 U * parseListStart(const unsigned int & uiPos = ChainedEnd) const; 00901 00906 U * reverseParseList(const bool & bInit = false) const; 00910 U * reverseParseListStart(const unsigned int & uiPos = ChainedEnd) const; 00911 00912 00913 // Operators 00914 public: 00919 inline typename SearchPolicy::Result operator [] (const unsigned int &i) 00920 { Node * pNode = Goto(i); 00921 if (pNode == NULL) return SearchPolicy::DefaultValue(); 00922 return SearchPolicy::From(pNode->mpuElement); 00923 } 00924 00926 inline ChainedList& operator += (DefaultConstParamType a) { this->Add(a); return (*this); } 00928 inline ChainedList& operator -= (DefaultConstParamType a) { unsigned int i = this->lastIndexOf(a); if (i!=ChainedEnd) this->Sub(i); return (*this); } 00929 00931 inline ChainedList operator + (DefaultConstParamType a) const { return ChainedList(*this)+= a; } 00932 inline ChainedList operator - (DefaultConstParamType a) const { return ChainedList(*this)-= a; } 00933 00935 inline ChainedList& operator = (const ChainedList& ); 00937 inline ChainedList& operator += (const ChainedList& a) { this->Add(a); return (*this); } 00938 00940 inline ChainedList& operator + (const ChainedList& a) const { return ChainedList(*this)+= a; } 00941 00945 inline bool moveAppendedList(ChainedList & a) 00946 { 00947 if (mlNumberOfNodes) 00948 { 00949 if (!a.Add(*this, ChainedStart)) return false; 00950 } 00951 mpxBlock = a.mpxBlock; 00952 mpxBLast = a.mpxBLast; 00953 mpxFirst = a.mpxFirst; 00954 mpxLast = a.mpxLast; 00955 mpxCurrent = a.mpxCurrent; 00956 mlNumberOfNodes = a.mlNumberOfNodes; 00957 mlNumberOfBlocks = a.mlNumberOfBlocks; 00958 mbUseBlocks = a.mbUseBlocks; 00959 mbIntegrity = a.mbIntegrity; 00960 00961 a.mpxBlock = a.mpxBLast = NULL; 00962 a.mpxFirst = a.mpxLast = a.mpxCurrent = NULL; 00963 a.mlNumberOfNodes = a.mlNumberOfBlocks = 0; 00964 a.mbIntegrity = true; 00965 return true; 00966 } 00967 00968 // Construction 00969 public: 00971 ChainedList(); 00973 ~ChainedList(); 00974 00976 ChainedList(const ChainedList &); 00977 00978 }; 00979 00980 00981 // Inclusion for template definition, and implementation (it's too big to be implemented here) 00982 #include "template/ChainedList.hpp" 00983 } 00984 00985 00986 00987 00988 00989 00990 00994 00995 00997 namespace PlainOldDataPolicy 00998 { 01000 template <typename T> 01001 struct DefaultMemoryPolicy 01002 { 01004 inline static size_t min(size_t a, size_t b) { return a < b ? a : b; } 01006 inline static void Copy(T & dest, const T & src) { dest = src; } 01008 inline static void CopyArray(T * dest, const T * src, const size_t & destSize, const size_t & srcSize) { memcpy(dest, src, min(srcSize, destSize) * sizeof(T)); } 01010 inline static void CopyArray(T *& dest, const T * src, size_t & destSize, const size_t & srcSize) 01011 { 01012 if (destSize < srcSize) 01013 { 01014 // Need to resize the array 01015 T* tmp = (T*)realloc(NULL, srcSize * sizeof(T)); 01016 if (tmp == NULL) { DeleteArray(dest, destSize); dest = NULL; destSize = 0; return; } 01017 01018 memcpy(tmp, src, srcSize * sizeof(T)); 01019 01020 // Erase the previous array 01021 DeleteArray(dest, destSize); 01022 dest = tmp; 01023 01024 destSize = srcSize; 01025 } else memcpy(dest, src, srcSize * sizeof(T)); 01026 } 01028 inline static T& DefaultElement() { static T t(0); return t; } 01030 inline static size_t Search(const T* array, const size_t & arraySize, const T & valueToLookFor) { size_t i = 0; while (i < arraySize && array[i] != valueToLookFor) i++; return i; } 01032 inline static size_t ReverseSearch(const T* array, const size_t & arraySize, const T & valueToLookFor) { size_t i = arraySize; while (i && array[i-1] != valueToLookFor) i--; return i ? i - 1 : arraySize; } 01034 inline static T * NonDestructiveAlloc(const T* array, const size_t & currentSize, const size_t & newSize, const T & fillWith) 01035 { 01036 T * ret = (T*)realloc((void*)array, newSize * sizeof(T)); 01037 if (ret == NULL) { free((void*)array); return NULL; } 01038 size_t i = currentSize; 01039 for (; i < newSize; i++) 01040 ret[i] = fillWith; 01041 01042 return ret; 01043 } 01046 static T * Insert(const T* array, const size_t & currentSize, const size_t & newSize, const size_t & index, const T & elementToInsert) 01047 { 01048 T * ret = (T*)realloc((void*)array, newSize * sizeof(T)); 01049 if (ret == NULL) { free((void*)array); return NULL; } 01050 01051 size_t i = newSize - 1; 01052 for (; i > currentSize; i--) 01053 ret[i] = DefaultElement(); 01054 for (; i > index; i--) 01055 ret[i] = ret[i-1]; 01056 01057 ret[index] = elementToInsert; 01058 01059 return ret; 01060 } 01062 inline static void DeleteArray(const T * array, const size_t & currentSize) { free((void*)array); } 01064 inline static bool CompareArray(const T * array1, const T * array2, const size_t & commonSize) { return memcmp(array1, array2, commonSize * sizeof(T)) == 0; } 01065 01066 }; 01067 01068 template <typename T> 01069 struct CloneAsNew 01070 { 01071 inline static void Clone(T ** const dest, T ** const src, size_t size) 01072 { 01073 while (size --) 01074 dest[size] = new T(*src[size]); 01075 } 01076 01077 inline static void Delete(T * data) 01078 { 01079 delete data; 01080 } 01081 }; 01082 01084 template <typename T, typename CloneMixin = CloneAsNew<T> > 01085 struct DefaultMemoryListPolicy 01086 { 01087 01088 typedef T * Tptr; 01089 typedef const Tptr * constPtr; 01090 01091 inline static void CopyPtr(T* & dest, T* const & src) { DefaultMemoryPolicy<T*>::Copy(dest, src); } 01092 inline static void CopyArray(T** dest, T** const src, const size_t & destSize, const size_t & srcSize) { DefaultMemoryPolicy<T*>::CopyArray(dest, src, destSize, srcSize); } 01093 inline static void CopyArray(T**& dest, T** const src, size_t & destSize, const size_t & srcSize) { DefaultMemoryPolicy<T*>::CopyArray(dest, src, destSize, srcSize); } 01094 inline static void DuplicateArray(T**& dest, T** const src, size_t & destSize, const size_t & srcSize) 01095 { 01096 if (destSize < srcSize) 01097 { 01098 // Need to resize the array 01099 T** tmp = (T**)realloc(NULL, srcSize * sizeof(T*)); 01100 if (tmp == NULL) { DeleteArray(dest, destSize); dest = NULL; destSize = 0; return; } 01101 01102 CloneMixin::Clone(tmp, src, srcSize); 01103 01104 // Erase the previous array 01105 DeleteArray(dest, destSize); 01106 dest = tmp; 01107 01108 destSize = srcSize; 01109 } else CloneMixin::Clone(dest, src, srcSize); 01110 } 01111 01115 inline static size_t Search(T** const array, const size_t & arraySize, T* const & valueToLookFor) { size_t i = 0; while (i < arraySize && !(array[i] == valueToLookFor)) i++; return i; } 01119 inline static size_t ReverseSearch(T** const array, const size_t & arraySize, T* const & valueToLookFor) { size_t i = arraySize; while (i && !(array[i-1] == valueToLookFor)) i--; return i ? i - 1 : arraySize; } 01121 inline static size_t SearchRef(const Tptr* array, const size_t & arraySize, const T & valueToLookFor) { size_t i = 0; while (i < arraySize && *array[i] != valueToLookFor) i++; return i; } 01123 inline static T& DefaultSubElement() { static T t; return t; } 01125 inline static Tptr DefaultElement() { return 0; } 01126 inline static T** NonDestructiveAlloc(T** const array, const size_t & currentSize, const size_t & newSize, T* const & fillWith) { return DefaultMemoryPolicy<T*>::NonDestructiveAlloc(array, currentSize, newSize, fillWith); } 01127 inline static T* * Insert(T** const array, const size_t & currentSize, const size_t & newSize, const size_t & index, T* const & elementToInsert) { return DefaultMemoryPolicy<T*>::Insert(array, currentSize, newSize, index, elementToInsert); } 01129 inline static void DeleteArray(Tptr * const array, const size_t & currentSize) 01130 { 01131 // Delete all pointers in the array 01132 for (size_t i = 0; i < currentSize; i++) 01133 { 01134 Remove(array[i]); array[i] = NULL; 01135 } 01136 free((void*)array); 01137 } 01139 inline static void Remove(T * const data) { CloneMixin::Delete(data); } 01140 01143 inline static bool CompareArray(T** const array1, T** const array2, const size_t & commonSize) { constPtr end = array1 + commonSize; constPtr it = array1, it2 = array2; while (it != end) { if (!(*(*it++) == *(*it2++))) return false; } return true; } 01144 }; 01145 01146 template <typename T> 01147 struct SearchPolicy 01148 { 01149 typedef T & Result; 01150 inline static Result DefaultValue() { static T t(0); return t; } 01151 inline static Result From(T * x) { return *x; } 01152 inline static bool Compare(const T & a, const T & b) { return a == b; } 01153 01154 enum { DefaultConstructibleAndCopyable = true }; 01155 }; 01156 01157 } 01158 01160 template <typename T, class Policy = PlainOldDataPolicy::DefaultMemoryPolicy<T> > 01161 struct PlainOldData 01162 { 01166 typedef ::Container::PrivateGenericImplementation::Array<T, Policy, false> Array; 01170 typedef ::Container::PrivateGenericImplementation::IndexList<T, PlainOldDataPolicy::DefaultMemoryListPolicy<T>, false> IndexList; 01174 typedef ::Container::PrivateGenericImplementation::ChainedList<T, 4, PlainOldDataPolicy::SearchPolicy<T> > ChainedList; 01175 01176 01177 }; 01178 01179 01180 01181 01182 01183 01184 01185 01186 01187 01188 01189 01193 01194 01195 01196 01198 namespace WithCopyConstructorPolicy 01199 { 01201 template <typename T> 01202 struct DefaultMemoryPolicy 01203 { 01204 typedef const T * constPtr; 01205 typedef const T constT; 01207 inline static void Copy(T & dest, const T & src) { dest.~T(); new(&dest) T(src); } 01209 inline static void CopyArray(T * dest, const T * src, const size_t & destSize, const size_t & srcSize) 01210 { 01211 constPtr it = src, end = src + min(srcSize, destSize); 01212 T * itd = dest; 01213 while (it != end) 01214 { // Destruct itd 01215 itd->~T(); 01216 // Construct it again 01217 new(itd) T(*it); 01218 itd++, it++; 01219 } 01220 } 01222 inline static void CopyArray(T *& dest, const T * src, size_t & destSize, const size_t & srcSize) 01223 { 01224 if (destSize < srcSize) 01225 { 01226 // Need to resize the array 01227 T* tmp = (T*)realloc(NULL, srcSize * sizeof(T)); 01228 if (tmp == NULL) { DeleteArray(dest, destSize); dest = NULL; destSize = 0; return; } 01229 01230 size_t i = 0; 01231 for (; i < srcSize; i++) 01232 new (&tmp[i]) T(src[i]); 01233 01234 // Erase the previous array 01235 DeleteArray(dest, destSize); 01236 dest = tmp; 01237 01238 destSize = srcSize; 01239 } else CopyArray((T*)dest, src, srcSize, srcSize); 01240 } 01242 inline static T & DefaultElement() { static T t; return t; } 01246 inline static size_t Search(const T* array, const size_t & arraySize, const T & valueToLookFor) { size_t i = 0; while (i < arraySize && array[i] != valueToLookFor) i++; return i; } 01250 inline static size_t ReverseSearch(const T * array, const size_t & arraySize, const T & valueToLookFor) { size_t i = arraySize; while (i && array[i-1] != valueToLookFor) i--; return i ? i - 1 : arraySize; } 01252 inline static T * NonDestructiveAlloc(const T* array, const size_t & currentSize, const size_t & newSize, const T & fillWith) 01253 { 01254 // Realloc here will not work. So let's do it the old way. 01255 T * ret = (T*)malloc(newSize * sizeof(T)); 01256 if (ret == NULL) { DeleteArray(array, currentSize); return NULL; } 01257 01258 size_t i = 0; 01259 for (; i < currentSize; i++) 01260 new (&ret[i]) T(array[i]); 01261 01262 for (; i < newSize; i++) 01263 new (&ret[i]) T(fillWith); 01264 01265 // Ok, let's delete the previous array 01266 DeleteArray(array, currentSize); 01267 return ret; 01268 } 01271 static T * Insert(const T* array, const size_t & currentSize, const size_t & newSize, const size_t & index, const T & elementToInsert) 01272 { 01273 T * ret = (T*)malloc(newSize * sizeof(T)); 01274 if (ret == NULL) { DeleteArray(array, currentSize); return NULL; } 01275 01276 size_t i = 0; 01277 for (; i < index; i++) 01278 new (&ret[i]) T(array[i]); 01279 01280 new (&ret[index]) T(elementToInsert); 01281 01282 for (; i < currentSize; i++) 01283 new (&ret[i+1]) T(array[i]); 01284 for (; i < newSize - 1; i++) 01285 new (&ret[i+1]) T(DefaultElement()); 01286 01287 // Ok, let's delete the previous array 01288 DeleteArray(array, currentSize); 01289 return ret; 01290 } 01291 01293 inline static void DeleteArray(const T * array, const size_t & currentSize) 01294 { 01295 if (!currentSize) return; 01296 constPtr end = array + currentSize, it = array; 01297 for (; it != end; it++) 01298 it->~T(); 01299 01300 free((void*)array); 01301 } 01304 inline static bool CompareArray(const T * array1, const T * array2, const size_t & commonSize) { constPtr end = array1 + commonSize; constPtr it = array1, it2 = array2; while (it != end) { if (*it++ != *it2++) return false; } return true; } 01305 }; 01306 01308 template <typename T> 01309 struct SimplerMemoryPolicy 01310 { 01311 typedef const T * constPtr; 01312 inline static void Copy(T & dest, const T & src) { DefaultMemoryPolicy<T>::Copy(dest, src); } 01313 inline static void CopyArray(T * dest, const T * src, const size_t & destSize, const size_t & srcSize) { DefaultMemoryPolicy<T>::CopyArray(dest, src, destSize, srcSize); } 01314 inline static void CopyArray(T *& dest, const T * src, size_t & destSize, const size_t & srcSize) { DefaultMemoryPolicy<T>::CopyArray(dest, src, destSize, srcSize); } 01315 inline static T & DefaultElement() { return DefaultMemoryPolicy<T>::DefaultElement(); } 01319 inline static size_t Search(const T* array, const size_t & arraySize, const T & valueToLookFor) { size_t i = 0; while (i < arraySize && !(array[i] == valueToLookFor)) i++; return i; } 01323 inline static size_t ReverseSearch(const T* array, const size_t & arraySize, const T & valueToLookFor) { size_t i = arraySize; while (i && !(array[i-1] == valueToLookFor)) i--; return i ? i - 1 : arraySize; } 01324 01325 inline static T * NonDestructiveAlloc(const T* array, const size_t & currentSize, const size_t & newSize, const T & fillWith) { return DefaultMemoryPolicy<T>::NonDestructiveAlloc(array, currentSize, newSize, fillWith); } 01326 inline static T * Insert(const T* array, const size_t & currentSize, const size_t & newSize, const size_t & index, const T & elementToInsert) { return DefaultMemoryPolicy<T>::Insert(array, currentSize, newSize, index, elementToInsert); } 01327 inline static void DeleteArray(const T * array, const size_t & currentSize) { DefaultMemoryPolicy<T>::DeleteArray(array, currentSize); } 01330 inline static bool CompareArray(const T * array1, const T * array2, const size_t & commonSize) { constPtr end = array1 + commonSize; constPtr it = array1, it2 = array2; while (it != end) { if (!(*it++ == *it2++)) return false; } return true; } 01331 }; 01332 01333 template <typename T> 01334 struct CloneAsNew 01335 { 01336 inline static void Clone(T ** const dest, T ** const src, size_t size) 01337 { 01338 while (size --) 01339 dest[size] = new T(*src[size]); 01340 } 01341 01342 inline static void Delete(T * data) 01343 { 01344 delete data; 01345 } 01346 }; 01347 01349 template <typename T, typename CloneMixin = CloneAsNew<T> > 01350 struct DefaultMemoryListPolicy 01351 { 01352 01353 typedef T * Tptr; 01354 typedef const Tptr * constPtr; 01355 01356 inline static void CopyPtr(T* & dest, T* const & src) { DefaultMemoryPolicy<T*>::Copy(dest, src); } 01357 inline static void CopyArray(T** dest, T** const src, const size_t & destSize, const size_t & srcSize) { DefaultMemoryPolicy<T*>::CopyArray(dest, src, destSize, srcSize); } 01358 inline static void CopyArray(T**& dest, T** const src, size_t & destSize, const size_t & srcSize) { DefaultMemoryPolicy<T*>::CopyArray(dest, src, destSize, srcSize); } 01359 inline static void DuplicateArray(T**& dest, T** const src, size_t & destSize, const size_t & srcSize) 01360 { 01361 if (destSize < srcSize) 01362 { 01363 // Need to resize the array 01364 T** tmp = (T**)realloc(NULL, srcSize * sizeof(T*)); 01365 if (tmp == NULL) { DeleteArray(dest, destSize); dest = NULL; destSize = 0; return; } 01366 01367 CloneMixin::Clone(tmp, src, srcSize); 01368 01369 // Erase the previous array 01370 DeleteArray(dest, destSize); 01371 dest = tmp; 01372 01373 destSize = srcSize; 01374 } else CloneMixin::Clone(dest, src, srcSize); 01375 } 01376 01380 inline static size_t Search(T** const array, const size_t & arraySize, T* const & valueToLookFor) { size_t i = 0; while (i < arraySize && !(array[i] == valueToLookFor)) i++; return i; } 01384 inline static size_t ReverseSearch(T** const array, const size_t & arraySize, T* const & valueToLookFor) { size_t i = arraySize; while (i && !(array[i-1] == valueToLookFor)) i--; return i ? i - 1 : arraySize; } 01386 inline static size_t SearchRef(const Tptr* array, const size_t & arraySize, const T & valueToLookFor) { size_t i = 0; while (i < arraySize && *array[i] != valueToLookFor) i++; return i; } 01388 inline static T& DefaultSubElement() { static T t; return t; } 01390 inline static Tptr DefaultElement() { return 0; } 01391 inline static T** NonDestructiveAlloc(T** const array, const size_t & currentSize, const size_t & newSize, T* const & fillWith) { return DefaultMemoryPolicy<T*>::NonDestructiveAlloc(array, currentSize, newSize, fillWith); } 01392 inline static T* * Insert(T** const array, const size_t & currentSize, const size_t & newSize, const size_t & index, T* const & elementToInsert) { return DefaultMemoryPolicy<T*>::Insert(array, currentSize, newSize, index, elementToInsert); } 01394 inline static void DeleteArray(Tptr * const array, const size_t & currentSize) 01395 { 01396 // Delete all pointers in the array 01397 for (size_t i = 0; i < currentSize; i++) 01398 { 01399 Remove(array[i]); array[i] = NULL; 01400 } 01401 free((void*)array); 01402 } 01404 inline static void Remove(T * const data) { CloneMixin::Delete(data); } 01407 inline static bool CompareArray(T** const array1, T** const array2, const size_t & commonSize) { constPtr end = array1 + commonSize; constPtr it = array1, it2 = array2; while (it != end) { if (!(*(*it++) == *(*it2++))) return false; } return true; } 01408 }; 01409 01410 01411 template <typename T> 01412 struct SearchPolicy 01413 { 01414 typedef T & Result; 01415 inline static Result DefaultValue() { static T t; return t; } 01416 inline static Result From(T * x) { return *x; } 01417 inline static bool Compare(const T & a, const T & b) { return a == b; } 01418 01419 enum { DefaultConstructibleAndCopyable = true }; 01420 }; 01421 01422 } 01423 01425 namespace NotConstructiblePolicy 01426 { 01427 template <typename T> 01428 struct SearchPolicy 01429 { 01430 typedef T * Result; 01431 inline static Result DefaultValue() { return NULL; } 01432 inline static Result From(T * x) { return x; } 01433 inline static bool Compare(const T & a, const T * b) { return &a == b; } 01434 01435 enum { DefaultConstructibleAndCopyable = false }; 01436 }; 01437 } 01438 01447 template <typename T, class Policy = WithCopyConstructorPolicy::DefaultMemoryPolicy<T> > 01448 struct WithCopyConstructorAndOperators 01449 { 01453 typedef ::Container::PrivateGenericImplementation::Array<T, Policy, true> Array; 01457 typedef ::Container::PrivateGenericImplementation::IndexList<T, WithCopyConstructorPolicy::DefaultMemoryListPolicy<T>, false> IndexList; 01461 typedef ::Container::PrivateGenericImplementation::ChainedList<T, 4, WithCopyConstructorPolicy::SearchPolicy<T> > ChainedList; 01462 }; 01463 01468 template <typename T, class Policy = WithCopyConstructorPolicy::SimplerMemoryPolicy<T> > 01469 struct WithCopyConstructor 01470 { 01474 typedef ::Container::PrivateGenericImplementation::Array<T, Policy, true> Array; 01478 typedef ::Container::PrivateGenericImplementation::IndexList<T, WithCopyConstructorPolicy::DefaultMemoryListPolicy<T>, false> IndexList; 01482 typedef ::Container::PrivateGenericImplementation::ChainedList<T, 4, WithCopyConstructorPolicy::SearchPolicy<T> > ChainedList; 01483 }; 01484 01485 01486 namespace PrivateNotConstructibleImplementation 01487 { 01492 template <class U, unsigned int pow2 = 4, class SearchPolicy = NotConstructiblePolicy::SearchPolicy<U> > 01493 class ChainedList 01494 { 01495 public: 01497 enum 01498 { 01499 ChainedEnd = -1, 01500 ChainedError = ChainedEnd, 01501 ChainedStart = 0, 01502 ChainedBS = 1<<pow2, 01503 }; 01504 01505 private: 01507 class NodeNotCopyable 01508 { 01509 public: 01511 NodeNotCopyable * mpxPrevious; 01513 NodeNotCopyable * mpxNext; 01515 U * mpuElement; 01516 01517 01519 NodeNotCopyable(U* t = NULL) : mpxPrevious(NULL), mpxNext(NULL), mpuElement(t) {} 01521 ~NodeNotCopyable() 01522 { 01523 if (mpuElement!=NULL) delete mpuElement; 01524 } 01525 01527 void Set(U* t) { mpuElement = t; } 01529 U& Get() { return (*mpuElement); } 01530 }; 01531 01533 class NodeCopyable 01534 { 01535 public: 01537 NodeCopyable * mpxPrevious; 01539 NodeCopyable * mpxNext; 01541 U * mpuElement; 01542 public: 01544 NodeCopyable(U* t = NULL) : mpxPrevious(NULL), mpxNext(NULL), mpuElement(t) {} 01546 ~NodeCopyable() 01547 { 01548 if (mpuElement!=NULL) delete mpuElement; 01549 } 01550 01552 void Set(U* t) { mpuElement = t; } 01554 U& Get() { return (*mpuElement); } 01555 01556 // Add the copy interface 01557 public: 01559 NodeCopyable(const U& t) : mpxPrevious(NULL), mpxNext(NULL) { mpuElement = new U(t); } 01561 void Set(const U& t) { mpuElement = new U(t); } 01562 01563 }; 01564 01565 typedef typename PrivateGenericImplementation::Select<SearchPolicy::DefaultConstructibleAndCopyable, NodeCopyable, NodeNotCopyable>::Result Node; 01566 01568 typedef typename PrivateGenericImplementation::Select<SearchPolicy::DefaultConstructibleAndCopyable, U&, U*>::Result DefaultParamType; 01569 typedef typename PrivateGenericImplementation::Select<SearchPolicy::DefaultConstructibleAndCopyable, const U&, U* const>::Result DefaultConstParamType; 01570 private: 01572 template <unsigned int size> 01573 class LinearBlock 01574 { 01575 // Members 01576 private: 01578 LinearBlock * spxNext; 01580 LinearBlock * spxPrevious; 01582 Node sapxBlock[size]; 01584 unsigned char soUsed; 01585 01586 // Construction 01587 public: 01589 LinearBlock(LinearBlock * previous = NULL, LinearBlock * next = NULL) : spxPrevious(previous), spxNext(next) , soUsed(0) {} 01591 ~LinearBlock() 01592 { 01593 if ( spxNext!=NULL || spxPrevious!=NULL) 01594 { 01595 if (spxNext!=NULL) 01596 spxNext->spxPrevious = spxPrevious; 01597 if (spxPrevious!=NULL) 01598 spxPrevious->spxNext = spxNext; 01599 01600 spxNext = spxPrevious = NULL; 01601 } 01602 } 01603 01604 // Interface 01605 public: 01607 inline void Connect(LinearBlock * previous, LinearBlock * next) { spxPrevious = previous; spxNext = next; } 01609 inline void Delete() 01610 { 01611 if (spxNext!=NULL) 01612 spxNext->spxPrevious = spxPrevious; 01613 if (spxPrevious!=NULL) 01614 spxPrevious->spxNext = spxNext; 01615 01616 spxNext = spxPrevious = NULL; 01617 delete this; 01618 } 01619 01621 inline LinearBlock<size> * GoFirst() { LinearBlock<size>* pNode = this; while (pNode->spxPrevious != NULL) pNode = spxPrevious; return pNode; } 01623 inline LinearBlock<size> * GoLast() { LinearBlock<size>* pNode = this; while (pNode->spxNext != NULL) pNode = spxNext; return pNode; } 01624 01625 01627 inline bool CreateNewBlock() 01628 { 01629 if (spxNext!=NULL) return false; 01630 LinearBlock<size>* pNode = new LinearBlock<size>(this, NULL); 01631 if (pNode == NULL) return false; 01632 else spxNext = pNode; 01633 return true; 01634 } 01635 01637 inline Node * GetData() { return &sapxBlock[0]; } 01639 LinearBlock<size> * Find(Node * pNode) 01640 { 01641 if (pNode==NULL) return NULL; 01642 LinearBlock<size> * pBlock = GoFirst(); 01643 LinearBlock<size> * pEnd = GoLast(); 01644 for (; pBlock != pEnd; pBlock = pBlock->spxNext) 01645 if ( pNode >= pBlock->GetData() && pNode <= pBlock->GetData() + size) return pBlock; 01646 return NULL; 01647 } 01648 01649 private: 01656 bool DeleteAll() 01657 { 01658 LinearBlock<size>* pNode2, *pNode = GoFirst(); 01659 if (pNode == NULL) return false; 01660 if (pNode->spxNext == NULL) 01661 { 01662 pNode->Delete(); 01663 pNode = NULL; 01664 return true; 01665 } 01666 01667 // Goto second pointer until next pointer is different from null , advance to next 01668 for (; pNode != NULL; ) 01669 { 01670 pNode2 = pNode->spxNext; 01671 pNode->Delete(); 01672 pNode = pNode2; 01673 } 01674 return true; 01675 } 01676 public: 01677 friend class ChainedList<U, pow2, SearchPolicy>; 01678 }; 01679 01680 // Members 01681 private: 01683 Node * mpxFirst; 01685 Node * mpxLast; 01687 mutable Node * mpxCurrent; 01689 unsigned int mlNumberOfNodes; 01690 01692 unsigned int mlNumberOfBlocks; 01694 // unsigned int mlBlockSize; 01696 LinearBlock<ChainedBS> * mpxBlock; 01698 LinearBlock<ChainedBS> * mpxBLast; 01699 01700 private: 01704 bool mbUseBlocks; 01706 bool mbIntegrity; 01707 01708 // Properties 01709 public: 01711 inline unsigned int getSize() const { return mlNumberOfNodes; } 01712 01713 // Interface 01714 public: 01724 bool Add(U*, const unsigned int& = ChainedEnd); 01725 01729 bool Insert(DefaultConstParamType, const unsigned int& = ChainedStart); 01736 bool Sub(const unsigned int& = ChainedEnd); 01741 bool Remove(const unsigned int& = ChainedStart); 01742 01747 unsigned int indexOf(DefaultConstParamType); 01752 unsigned int lastIndexOf(DefaultConstParamType); 01755 bool Swap(const unsigned int &, const unsigned int &); 01756 01757 // Helpers functions 01758 private: 01760 inline Node * CreateNode(); 01762 inline Node * Goto(const unsigned int &); 01764 inline bool UseBlocks(const bool &); 01766 bool Connect(Node *, Node *, Node *); 01767 01768 public: 01772 bool Add(const ChainedList&, const unsigned int & = ChainedEnd); 01773 01777 bool Free(); 01780 bool Change(DefaultConstParamType, const unsigned int &); 01781 01782 01787 U * parseList(const bool & bInit = false) const; 01791 U * parseListStart(const unsigned int & uiPos = ChainedEnd) const; 01792 01797 U * reverseParseList(const bool & bInit = false) const; 01801 U * reverseParseListStart(const unsigned int & uiPos = ChainedEnd) const; 01802 01806 inline bool moveList(ChainedList & a) 01807 { 01808 if (mlNumberOfNodes) return false; 01809 mpxBlock = a.mpxBlock; 01810 mpxBLast = a.mpxBLast; 01811 mpxFirst = a.mpxFirst; 01812 mpxLast = a.mpxLast; 01813 mpxCurrent = a.mpxCurrent; 01814 mlNumberOfNodes = a.mlNumberOfNodes; 01815 mlNumberOfBlocks = a.mlNumberOfBlocks; 01816 mbUseBlocks = a.mbUseBlocks; 01817 mbIntegrity = a.mbIntegrity; 01818 01819 a.mpxBlock = a.mpxBLast = NULL; 01820 a.mpxFirst = a.mpxLast = a.mpxCurrent = NULL; 01821 a.mlNumberOfNodes = a.mlNumberOfBlocks = 0; 01822 a.mbIntegrity = true; 01823 return true; 01824 } 01828 inline bool moveAppendedList(ChainedList & a) 01829 { 01830 if (mlNumberOfNodes) 01831 { 01832 if (!a.Add(*this, ChainedStart)) return false; 01833 } 01834 mpxBlock = a.mpxBlock; 01835 mpxBLast = a.mpxBLast; 01836 mpxFirst = a.mpxFirst; 01837 mpxLast = a.mpxLast; 01838 mpxCurrent = a.mpxCurrent; 01839 mlNumberOfNodes = a.mlNumberOfNodes; 01840 mlNumberOfBlocks = a.mlNumberOfBlocks; 01841 mbUseBlocks = a.mbUseBlocks; 01842 mbIntegrity = a.mbIntegrity; 01843 01844 a.mpxBlock = a.mpxBLast = NULL; 01845 a.mpxFirst = a.mpxLast = a.mpxCurrent = NULL; 01846 a.mlNumberOfNodes = a.mlNumberOfBlocks = 0; 01847 a.mbIntegrity = true; 01848 return true; 01849 } 01850 01851 01852 // Operators 01853 public: 01858 inline typename SearchPolicy::Result operator [] (const unsigned int &i) 01859 { Node * pNode = Goto(i); 01860 if (pNode == NULL) return SearchPolicy::DefaultValue(); 01861 return SearchPolicy::From(pNode->mpuElement); 01862 } 01863 01865 inline ChainedList& operator += (DefaultConstParamType a) { this->Add(a); return (*this); } 01867 inline ChainedList& operator -= (DefaultConstParamType a) { unsigned int i = this->lastIndexOf(a); if (i!=ChainedEnd) this->Sub(i); return (*this); } 01868 01869 01871 inline ChainedList& operator += (const ChainedList& a) { this->Add(a); return (*this); } 01872 01873 01874 // Disallowed here 01875 private: 01877 ChainedList(const ChainedList &); 01879 inline ChainedList& operator = (const ChainedList& ); 01881 inline ChainedList& operator + (const ChainedList& a) const; 01883 inline ChainedList operator + (const U & a) const; 01884 inline ChainedList operator - (const U & a) const; 01885 bool Add(const U&, const unsigned int& = ChainedEnd); 01886 01887 01888 // Construction 01889 public: 01891 ChainedList(); 01893 ~ChainedList(); 01894 }; 01895 01896 01897 // Inclusion for template definition, and implementation (it's too big to be implemented here) 01898 #define NotCopyable 01899 #include "template/ChainedList.hpp" 01900 #undef NotCopyable 01901 } 01902 01903 01905 template <typename T> 01906 struct NotConstructible 01907 { 01908 01914 typedef ::Container::PrivateNotConstructibleImplementation::ChainedList<T, 0, NotConstructiblePolicy::SearchPolicy<T> > ChainedList; 01915 }; 01916 01917 01918 } 01919 01920 01921 #endif 01922