csutil/array.h
00001 /* 00002 Crystal Space Generic Array Template 00003 Copyright (C) 2003 by Matze Braun 00004 00005 This library is free software; you can redistribute it and/or 00006 modify it under the terms of the GNU Library General Public 00007 License as published by the Free Software Foundation; either 00008 version 2 of the License, or (at your option) any later version. 00009 00010 This library is distributed in the hope that it will be useful, 00011 but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 Library General Public License for more details. 00014 00015 You should have received a copy of the GNU Library General Public 00016 License along with this library; if not, write to the Free 00017 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00018 */ 00019 #ifndef __CSUTIL_ARRAY_H__ 00020 #define __CSUTIL_ARRAY_H__ 00021 00022 // hack: work around problems caused by #defining 'new' 00023 #ifdef CS_EXTENSIVE_MEMDEBUG 00024 # undef new 00025 #endif 00026 #include <new> 00027 00029 typedef int ArraySortCompareFunction (void const* item1, 00030 void const* item2); 00031 00035 template <class T> 00036 class csArrayElementHandler 00037 { 00038 public: 00039 static void Construct (T* address, T const& src) 00040 { 00041 new (static_cast<void*>(address)) T(src); 00042 } 00043 00044 static void Destroy (T* address) 00045 { 00046 address->~T(); 00047 } 00048 00049 static void InitRegion (T* address, int count) 00050 { 00051 for (int i = 0 ; i < count ; i++) 00052 Construct (address + i, T ()); 00053 } 00054 }; 00055 00059 template <class T> 00060 class csArrayMemoryAllocator 00061 { 00062 public: 00063 static T* Alloc (int count) 00064 { 00065 return (T*)malloc (count * sizeof(T)); 00066 } 00067 00068 static void Free (T* mem) 00069 { 00070 free (mem); 00071 } 00072 00073 // The 'relevantcount' parameter should be the number of items 00074 // in the old array that are initialized. 00075 static T* Realloc (T* mem, int relevantcount, int oldcount, int newcount) 00076 { 00077 (void)relevantcount; (void)oldcount; 00078 return (T*)realloc (mem, newcount * sizeof(T)); 00079 } 00080 }; 00081 00090 template <class T, class ElementHandler = csArrayElementHandler<T> > 00091 class csSafeCopyArrayMemoryAllocator 00092 { 00093 public: 00094 static T* Alloc (int count) 00095 { 00096 return (T*)malloc (count * sizeof(T)); 00097 } 00098 00099 static void Free (T* mem) 00100 { 00101 free (mem); 00102 } 00103 00104 static T* Realloc (T* mem, int relevantcount, int oldcount, int newcount) 00105 { 00106 if (newcount <= oldcount) 00107 { 00108 // Realloc is safe. 00109 T* newmem = (T*)realloc (mem, newcount * sizeof (T)); 00110 CS_ASSERT (newmem == mem); 00111 return newmem; 00112 } 00113 00114 T* newmem = Alloc (newcount); 00115 int i; 00116 for (i = 0 ; i < relevantcount ; i++) 00117 { 00118 ElementHandler::Construct (newmem + i, mem[i]); 00119 ElementHandler::Destroy (mem + i); 00120 } 00121 Free (mem); 00122 return newmem; 00123 } 00124 }; 00125 00126 00134 template <class T, 00135 class ElementHandler = csArrayElementHandler<T>, 00136 class MemoryAllocator = csArrayMemoryAllocator<T> > 00137 class csArray 00138 { 00139 private: 00140 int count; 00141 int capacity; 00142 int threshold; 00143 T* root; 00144 00145 protected: 00150 void InitRegion (int start, int count) 00151 { 00152 ElementHandler::InitRegion (root+start, count); 00153 } 00154 00155 private: 00157 void CopyFrom (const csArray& source) 00158 { 00159 if (&source != this) 00160 { 00161 DeleteAll (); 00162 threshold = source.threshold; 00163 SetLengthUnsafe (source.Length ()); 00164 for (int i=0 ; i<source.Length() ; i++) 00165 ElementHandler::Construct (root + i, source[i]); 00166 } 00167 } 00168 00169 // Adjust internal capacity of this array. 00170 void AdjustCapacity (int n) 00171 { 00172 if (n > capacity || (capacity > threshold && n < capacity - threshold)) 00173 { 00174 n = ((n + threshold - 1) / threshold ) * threshold; 00175 if (root == 0) 00176 root = MemoryAllocator::Alloc (n); 00177 else 00178 root = MemoryAllocator::Realloc (root, count, capacity, n); 00179 capacity = n; 00180 } 00181 } 00182 00183 // Set array length. NOTE: Do not make this public since it does not 00184 // properly construct/destroy elements. To safely truncate the array, use 00185 // Truncate(). To safely set the capacity, use SetCapacity(). 00186 void SetLengthUnsafe (int n) 00187 { 00188 if (n > capacity) 00189 AdjustCapacity (n); 00190 count = n; 00191 } 00192 00193 public: 00195 typedef int ArrayCompareFunction (T const& item1, T const& item2); 00197 typedef int ArrayCompareKeyFunction (T const& item1, void* item2); 00198 00203 csArray (int icapacity = 0, int ithreshold = 0) 00204 { 00205 count = 0; 00206 capacity = (icapacity > 0 ? icapacity : 0); 00207 threshold = (ithreshold > 0 ? ithreshold : 16); 00208 if (capacity != 0) 00209 root = MemoryAllocator::Alloc (capacity); 00210 else 00211 root = 0; 00212 } 00213 00214 ~csArray () 00215 { 00216 DeleteAll (); 00217 } 00218 00220 csArray (const csArray& source) 00221 { 00222 root = 0; 00223 capacity = 0; 00224 count = 0; 00225 CopyFrom (source); 00226 } 00227 00229 csArray<T>& operator= (const csArray& other) 00230 { 00231 CopyFrom (other); 00232 return *this; 00233 } 00234 00236 int Length () const 00237 { 00238 return count; 00239 } 00240 00242 int Capacity () const 00243 { 00244 return capacity; 00245 } 00246 00253 void TransferTo (csArray& destination) 00254 { 00255 if (&destination != this) 00256 { 00257 destination.DeleteAll (); 00258 destination.root = root; 00259 destination.count = count; 00260 destination.capacity = capacity; 00261 destination.threshold = threshold; 00262 root = 0; 00263 capacity = count = 0; 00264 } 00265 } 00266 00274 void SetLength (int n, T const& what) 00275 { 00276 if (n <= count) 00277 { 00278 Truncate (n); 00279 } 00280 else 00281 { 00282 int old_len = Length (); 00283 SetLengthUnsafe (n); 00284 for (int i = old_len ; i < n ; i++) 00285 ElementHandler::Construct (root + i, what); 00286 } 00287 } 00288 00290 void SetLength (int n) 00291 { 00292 if (n <= count) 00293 { 00294 Truncate (n); 00295 } 00296 else 00297 { 00298 int old_len = Length (); 00299 SetLengthUnsafe (n); 00300 ElementHandler::InitRegion (root + old_len, n-old_len); 00301 } 00302 } 00303 00305 T& Get (int n) 00306 { 00307 CS_ASSERT (n >= 0 && n < count); 00308 return root[n]; 00309 } 00310 00312 T const& Get (int n) const 00313 { 00314 CS_ASSERT (n >= 0 && n < count); 00315 return root[n]; 00316 } 00317 00322 T& GetExtend (int n) 00323 { 00324 CS_ASSERT (n >= 0); 00325 if (n >= count) 00326 SetLength (n+1); 00327 return root[n]; 00328 } 00329 00331 T& operator [] (int n) 00332 { 00333 return Get(n); 00334 } 00335 00337 T const& operator [] (int n) const 00338 { 00339 return Get(n); 00340 } 00341 00343 void Put (int n, T const& what) 00344 { 00345 CS_ASSERT (n >= 0); 00346 if (n >= count) 00347 SetLength (n+1); 00348 ElementHandler::Destroy (root + n); 00349 ElementHandler::Construct (root + n, what); 00350 } 00351 00355 int FindKey (void* key, ArrayCompareKeyFunction* comparekey) const 00356 { 00357 for (int i = 0 ; i < Length () ; i++) 00358 if (comparekey (root[i], key) == 0) 00359 return i; 00360 return -1; 00361 } 00362 00363 00365 int Push (T const& what) 00366 { 00367 SetLengthUnsafe (count + 1); 00368 ElementHandler::Construct (root + count - 1, what); 00369 return count - 1; 00370 } 00371 00372 /* 00373 * Push a element onto the tail end of the array if not already present. 00374 * Returns index of newly pushed element or index of already present element. 00375 */ 00376 int PushSmart (T const& what) 00377 { 00378 int const n = Find (what); 00379 return (n < 0) ? Push (what) : n; 00380 } 00381 00383 T Pop () 00384 { 00385 CS_ASSERT (count > 0); 00386 T ret(root [count - 1]); 00387 ElementHandler::Destroy (root + count - 1); 00388 SetLengthUnsafe (count - 1); 00389 return ret; 00390 } 00391 00393 T const& Top () const 00394 { 00395 CS_ASSERT (count > 0); 00396 return root [count - 1]; 00397 } 00398 00400 T& Top () 00401 { 00402 CS_ASSERT (count > 0); 00403 return root [count - 1]; 00404 } 00405 00407 bool Insert (int n, T const& item) 00408 { 00409 if (n <= count) 00410 { 00411 SetLengthUnsafe (count + 1); // Increments 'count' as a side-effect. 00412 int const nmove = (count - n - 1); 00413 if (nmove > 0) 00414 memmove (root + n + 1, root + n, nmove * sizeof(T)); 00415 ElementHandler::Construct (root + n, item); 00416 return true; 00417 } 00418 else 00419 return false; 00420 } 00421 00425 csArray<T> Section (int low, int high) const 00426 { 00427 CS_ASSERT (low >= 0 && high < count && high >= low); 00428 csArray<T> sect (high - low + 1); 00429 for (int i = low; i <= high; i++) sect.Push (root[i]); 00430 return sect; 00431 } 00432 00434 static int DefaultCompare (T const &item1, T const &item2) 00435 { 00436 if (item1 < item2) return -1; 00437 else if (item1 > item2) return 1; 00438 else return 0; 00439 } 00440 00442 static int DefaultCompareKey (T const &item1, void* p) 00443 { 00444 T const& item2 = *(T const*)p; 00445 if (item1 < item2) return -1; 00446 else if (item1 > item2) return 1; 00447 else return 0; 00448 } 00449 00454 int FindSortedKey (void* key, ArrayCompareKeyFunction* comparekey 00455 = DefaultCompareKey, int* candidate = 0) const 00456 { 00457 int m = 0, l = 0, r = Length () - 1; 00458 while (l <= r) 00459 { 00460 m = (l + r) / 2; 00461 int cmp = comparekey (root [m], key); 00462 00463 if (cmp == 0) 00464 { 00465 if (candidate) *candidate = -1; 00466 return m; 00467 } 00468 else if (cmp < 0) 00469 l = m + 1; 00470 else 00471 r = m - 1; 00472 } 00473 if (candidate) *candidate = m; 00474 return -1; 00475 } 00476 00481 int InsertSorted (const T &item, ArrayCompareFunction* compare 00482 = DefaultCompare, int* equal_index = 0) 00483 { 00484 int m = 0, l = 0, r = Length () - 1; 00485 while (l <= r) 00486 { 00487 m = (l + r) / 2; 00488 int cmp = compare (root [m], item); 00489 00490 if (cmp == 0) 00491 { 00492 if (equal_index) *equal_index = m; 00493 Insert (++m, item); 00494 return m; 00495 } 00496 else if (cmp < 0) 00497 l = m + 1; 00498 else 00499 r = m - 1; 00500 } 00501 if (r == m) 00502 m++; 00503 if (equal_index) *equal_index = -1; 00504 Insert (m, item); 00505 return m; 00506 } 00507 00509 int Find (T const& which) const 00510 { 00511 for (int i = 0 ; i < Length () ; i++) 00512 if (root[i] == which) 00513 return i; 00514 return -1; 00515 } 00516 00520 void Sort (ArraySortCompareFunction* compare) 00521 { 00522 qsort (root, Length (), sizeof (T), compare); 00523 } 00524 00528 void DeleteAll () 00529 { 00530 if (root) 00531 { 00532 int i; 00533 for (i = 0 ; i < count ; i++) 00534 ElementHandler::Destroy (root + i); 00535 MemoryAllocator::Free (root); 00536 root = 0; 00537 capacity = count = 0; 00538 } 00539 } 00540 00546 void Truncate (int n) 00547 { 00548 CS_ASSERT(n >= 0); 00549 CS_ASSERT(n <= count); 00550 if (n < count) 00551 { 00552 for (int i = n; i < count; i++) 00553 ElementHandler::Destroy (root + i); 00554 SetLengthUnsafe(n); 00555 } 00556 } 00557 00563 void Empty () 00564 { 00565 Truncate (0); 00566 } 00567 00574 void SetCapacity (int n) 00575 { 00576 if (n > Length ()) 00577 AdjustCapacity (n); 00578 } 00579 00585 void ShrinkBestFit () 00586 { 00587 if (count == 0) 00588 { 00589 DeleteAll (); 00590 } 00591 else if (count != capacity) 00592 { 00593 root = MemoryAllocator::Realloc (root, count, capacity, count); 00594 capacity = count; 00595 } 00596 } 00597 00599 bool DeleteIndex (int n) 00600 { 00601 if (n >= 0 && n < count) 00602 { 00603 int const ncount = count - 1; 00604 int const nmove = ncount - n; 00605 ElementHandler::Destroy (root + n); 00606 if (nmove > 0) 00607 memmove (root + n, root + n + 1, nmove * sizeof(T)); 00608 SetLengthUnsafe (ncount); 00609 return true; 00610 } 00611 else 00612 return false; 00613 } 00614 00619 void DeleteRange (int start, int end) 00620 { 00621 if (start >= count) return; 00622 if (end < 0) return; 00623 if (start < 0) start = 0; 00624 if (end >= count) end = count-1; 00625 int i; 00626 for (i = start ; i < end ; i++) 00627 ElementHandler::Destroy (root + i); 00628 00629 int const range_size = end-start+1; 00630 int const ncount = count - range_size; 00631 int const nmove = count - end - 1; 00632 if (nmove > 0) 00633 memmove (root + start, root + start + range_size, nmove * sizeof(T)); 00634 SetLengthUnsafe (ncount); 00635 } 00636 00638 bool Delete (T const& item) 00639 { 00640 int const n = Find (item); 00641 if (n >= 0) 00642 return DeleteIndex (n); 00643 return false; 00644 } 00645 00647 class Iterator 00648 { 00649 public: 00651 Iterator(Iterator const& r) : 00652 currentelem(r.currentelem), array(r.array) {} 00653 00655 Iterator& operator=(Iterator const& r) 00656 { currentelem = r.currentelem; array = r.array; return *this; } 00657 00659 bool HasNext() 00660 { return currentelem < array.Length(); } 00661 00663 const T& Next() 00664 { return array.Get(currentelem++); } 00665 00667 void Reset() 00668 { currentelem = 0; } 00669 protected: 00670 Iterator(const csArray<T, ElementHandler>& newarray) 00671 : currentelem(0), array(newarray) 00672 { } 00673 friend class csArray<T, ElementHandler>; 00674 00675 private: 00676 int currentelem; 00677 const csArray<T, ElementHandler>& array; 00678 }; 00679 00681 Iterator GetIterator() const 00682 { return Iterator(*this); } 00683 }; 00684 00690 template <class T> 00691 class csSafeCopyArray 00692 : public csArray<T, 00693 csArrayElementHandler<T>, 00694 csSafeCopyArrayMemoryAllocator<T> > 00695 { 00696 public: 00701 csSafeCopyArray (int ilimit = 0, int ithreshold = 0) 00702 : csArray<T, csArrayElementHandler<T>, 00703 csSafeCopyArrayMemoryAllocator<T> > (ilimit, ithreshold) 00704 { 00705 } 00706 }; 00707 00708 #ifdef CS_EXTENSIVE_MEMDEBUG 00709 # define new CS_EXTENSIVE_MEMDEBUG_NEW 00710 #endif 00711 00712 #endif
Generated for Crystal Space by doxygen 1.2.18