00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CSUTIL_ARRAY_H__
00020 #define __CSUTIL_ARRAY_H__
00021
00022
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
00032 template <class T>
00033 class csArrayElementHandler
00034 {
00035 public:
00036 static void Construct (T* address, T const& src)
00037 {
00038 new (static_cast<void*>(address)) T(src);
00039 }
00040
00041 static void Destroy (T* address)
00042 {
00043 address->T::~T();
00044 }
00045
00046 static void InitRegion (T* address, int count)
00047 {
00048 for (int i = 0 ; i < count ; i++)
00049 Construct (address + i, T ());
00050 }
00051 };
00052
00060 template <class T, class ElementHandler = csArrayElementHandler<T> >
00061 class csArray
00062 {
00063 private:
00064 int count;
00065 int capacity;
00066 int threshold;
00067 T* root;
00068
00069 protected:
00074 void InitRegion (int start, int count)
00075 {
00076 ElementHandler::InitRegion (root+start, count);
00077 }
00078
00079 private:
00081 void CopyFrom (const csArray& source)
00082 {
00083 if (&source != this)
00084 {
00085 DeleteAll ();
00086 threshold = source.threshold;
00087 SetLengthUnsafe (source.Length ());
00088 for (int i=0 ; i<source.Length() ; i++)
00089 ElementHandler::Construct (root + i, source[i]);
00090 }
00091 }
00092
00093
00094 void AdjustCapacity (int n)
00095 {
00096 if (n > capacity || (capacity > threshold && n < capacity - threshold))
00097 {
00098 n = ((n + threshold - 1) / threshold ) * threshold;
00099 capacity = n;
00100 if (root == 0)
00101 root = (T*)malloc (capacity * sizeof(T));
00102 else
00103 root = (T*)realloc (root, capacity * sizeof(T));
00104 }
00105 }
00106
00107
00108
00109
00110 void SetLengthUnsafe (int n)
00111 {
00112 if (n > capacity)
00113 AdjustCapacity (n);
00114 count = n;
00115 }
00116
00117 public:
00119 typedef int ArrayCompareFunction (T const& item1, T const& item2);
00121 typedef int ArrayCompareKeyFunction (T const& item1, void* item2);
00122
00127 csArray (int icapacity = 0, int ithreshold = 0)
00128 {
00129 count = 0;
00130 capacity = (icapacity > 0 ? icapacity : 0);
00131 threshold = (ithreshold > 0 ? ithreshold : 16);
00132 if (capacity != 0)
00133 root = (T*)malloc (capacity * sizeof(T));
00134 else
00135 root = 0;
00136 }
00137
00138 ~csArray ()
00139 {
00140 DeleteAll ();
00141 }
00142
00144 csArray (const csArray& source)
00145 {
00146 root = 0;
00147 capacity = 0;
00148 count = 0;
00149 CopyFrom (source);
00150 }
00151
00153 csArray<T>& operator= (const csArray& other)
00154 {
00155 CopyFrom (other);
00156 return *this;
00157 }
00158
00160 int Length () const
00161 {
00162 return count;
00163 }
00164
00166 int Capacity () const
00167 {
00168 return capacity;
00169 }
00170
00177 void TransferTo (csArray& destination)
00178 {
00179 if (&destination != this)
00180 {
00181 destination.DeleteAll ();
00182 destination.root = root;
00183 destination.count = count;
00184 destination.capacity = capacity;
00185 destination.threshold = threshold;
00186 root = 0;
00187 capacity = count = 0;
00188 }
00189 }
00190
00198 void SetLength (int n, T const& what)
00199 {
00200 if (n <= count)
00201 {
00202 Truncate (n);
00203 }
00204 else
00205 {
00206 int old_len = Length ();
00207 SetLengthUnsafe (n);
00208 for (int i = old_len ; i < n ; i++)
00209 ElementHandler::Construct (root + i, what);
00210 }
00211 }
00212
00214 void SetLength (int n)
00215 {
00216 if (n <= count)
00217 {
00218 Truncate (n);
00219 }
00220 else
00221 {
00222 int old_len = Length ();
00223 SetLengthUnsafe (n);
00224 ElementHandler::InitRegion (root + old_len, n-old_len);
00225 }
00226 }
00227
00229 T& Get (int n)
00230 {
00231 CS_ASSERT (n >= 0 && n < count);
00232 return root[n];
00233 }
00234
00239 T& GetExtend (int n)
00240 {
00241 CS_ASSERT (n >= 0);
00242 if (n >= count)
00243 SetLength (n+1);
00244 return root[n];
00245 }
00246
00248 T& operator [] (int n)
00249 {
00250 return Get(n);
00251 }
00252
00254 void Put (int n, T const& what)
00255 {
00256 CS_ASSERT (n >= 0);
00257 if (n >= count)
00258 SetLength (n+1);
00259 ElementHandler::Destroy (root + n);
00260 ElementHandler::Construct (root + n, what);
00261 }
00262
00266 int FindKey (void* key, ArrayCompareKeyFunction* comparekey) const
00267 {
00268 for (int i = 0 ; i < Length () ; i++)
00269 if (comparekey (root[i], key) == 0)
00270 return i;
00271 return -1;
00272 }
00273
00274
00276 int Push (T const& what)
00277 {
00278 SetLengthUnsafe (count + 1);
00279 ElementHandler::Construct (root + count - 1, what);
00280 return count - 1;
00281 }
00282
00283
00284
00285
00286
00287 int PushSmart (T const& what)
00288 {
00289 int const n = Find (what);
00290 return (n < 0) ? Push (what) : n;
00291 }
00292
00294 T Pop ()
00295 {
00296 CS_ASSERT (count > 0);
00297 T ret(root [count - 1]);
00298 ElementHandler::Destroy (root + count - 1);
00299 SetLengthUnsafe (count - 1);
00300 return ret;
00301 }
00302
00304 T const& Top () const
00305 {
00306 CS_ASSERT (count > 0);
00307 return root [count - 1];
00308 }
00309
00311 bool Insert (int n, T const& item)
00312 {
00313 if (n <= count)
00314 {
00315 SetLengthUnsafe (count + 1);
00316 int const nmove = (count - n - 1);
00317 if (nmove > 0)
00318 memmove (root + n + 1, root + n, nmove * sizeof(T));
00319 ElementHandler::Construct (root + n, item);
00320 return true;
00321 }
00322 else
00323 return false;
00324 }
00325
00329 csArray<T> Section (int low, int high) const
00330 {
00331 CS_ASSERT (low >= 0 && high < count && high >= low);
00332 csArray<T> sect (high - low + 1);
00333 for (int i = low; i <= high; i++) sect.Push (root[i]);
00334 return sect;
00335 }
00336
00338 static int DefaultCompare (T const &item1, T const &item2)
00339 {
00340 if (item1 < item2) return -1;
00341 else if (item1 > item2) return 1;
00342 else return 0;
00343 }
00344
00346 static int DefaultCompareKey (T const &item1, void* p)
00347 {
00348 T const& item2 = *(T const*)p;
00349 if (item1 < item2) return -1;
00350 else if (item1 > item2) return 1;
00351 else return 0;
00352 }
00353
00358 int FindSortedKey (void* key, ArrayCompareKeyFunction* comparekey
00359 = DefaultCompareKey, int* candidate = 0) const
00360 {
00361 int m = 0, l = 0, r = Length () - 1;
00362 while (l <= r)
00363 {
00364 m = (l + r) / 2;
00365 int cmp = comparekey (root [m], key);
00366
00367 if (cmp == 0)
00368 {
00369 if (candidate) *candidate = -1;
00370 return m;
00371 }
00372 else if (cmp < 0)
00373 l = m + 1;
00374 else
00375 r = m - 1;
00376 }
00377 if (candidate) *candidate = m;
00378 return -1;
00379 }
00380
00385 int InsertSorted (const T &item, ArrayCompareFunction* compare
00386 = DefaultCompare, int* equal_index = 0)
00387 {
00388 int m = 0, l = 0, r = Length () - 1;
00389 while (l <= r)
00390 {
00391 m = (l + r) / 2;
00392 int cmp = compare (root [m], item);
00393
00394 if (cmp == 0)
00395 {
00396 if (equal_index) *equal_index = m;
00397 Insert (++m, item);
00398 return m;
00399 }
00400 else if (cmp < 0)
00401 l = m + 1;
00402 else
00403 r = m - 1;
00404 }
00405 if (r == m)
00406 m++;
00407 if (equal_index) *equal_index = -1;
00408 Insert (m, item);
00409 return m;
00410 }
00411
00413 int Find (T const& which) const
00414 {
00415 for (int i = 0 ; i < Length () ; i++)
00416 if (root[i] == which)
00417 return i;
00418 return -1;
00419 }
00420
00424 void Sort (ArraySortCompareFunction* compare)
00425 {
00426 qsort (root, Length (), sizeof (T), compare);
00427 }
00428
00430 T const& Get (int n) const
00431 {
00432 CS_ASSERT (n >= 0 && n < count);
00433 return root[n];
00434 }
00435
00437 T const& operator [] (int n) const
00438 {
00439 CS_ASSERT (n >= 0 && n < count);
00440 return root[n];
00441 }
00442
00446 void DeleteAll ()
00447 {
00448 if (root)
00449 {
00450 int i;
00451 for (i = 0 ; i < count ; i++)
00452 ElementHandler::Destroy (root + i);
00453 free (root);
00454 root = 0;
00455 capacity = count = 0;
00456 }
00457 }
00458
00464 void Truncate (int n)
00465 {
00466 CS_ASSERT(n >= 0);
00467 CS_ASSERT(n <= count);
00468 if (n < count)
00469 {
00470 for (int i = n; i < count; i++)
00471 ElementHandler::Destroy (root + i);
00472 SetLengthUnsafe(n);
00473 }
00474 }
00475
00481 void Empty ()
00482 {
00483 Truncate (0);
00484 }
00485
00492 void SetCapacity (int n)
00493 {
00494 if (n > Length ())
00495 AdjustCapacity (n);
00496 }
00497
00503 void ShrinkBestFit ()
00504 {
00505 if (count == 0)
00506 {
00507 DeleteAll ();
00508 }
00509 else if (count != capacity)
00510 {
00511 capacity = count;
00512 root = (T*)realloc (root, capacity * sizeof(T));
00513 }
00514 }
00515
00517 bool DeleteIndex (int n)
00518 {
00519 if (n >= 0 && n < count)
00520 {
00521 int const ncount = count - 1;
00522 int const nmove = ncount - n;
00523 ElementHandler::Destroy (root + n);
00524 if (nmove > 0)
00525 memmove (root + n, root + n + 1, nmove * sizeof(T));
00526 SetLengthUnsafe (ncount);
00527 return true;
00528 }
00529 else
00530 return false;
00531 }
00532
00537 void DeleteRange (int start, int end)
00538 {
00539 if (start >= count) return;
00540 if (end < 0) return;
00541 if (start < 0) start = 0;
00542 if (end >= count) end = count-1;
00543 int i;
00544 for (i = start ; i < end ; i++)
00545 ElementHandler::Destroy (root + i);
00546
00547 int const range_size = end-start+1;
00548 int const ncount = count - range_size;
00549 int const nmove = count - end - 1;
00550 if (nmove > 0)
00551 memmove (root + start, root + start + range_size, nmove * sizeof(T));
00552 SetLengthUnsafe (ncount);
00553 }
00554
00556 bool Delete (T const& item)
00557 {
00558 int const n = Find (item);
00559 if (n >= 0)
00560 return DeleteIndex (n);
00561 return false;
00562 }
00563
00565 class Iterator
00566 {
00567 public:
00569 bool HasNext()
00570 { return currentelem < array.Length(); }
00571
00573 const T& Next()
00574 { return array.Get(currentelem++); }
00575
00577 void Reset()
00578 { currentelem = 0; }
00579 protected:
00580 Iterator(const csArray<T, ElementHandler>& newarray)
00581 : currentelem(0), array(newarray)
00582 { }
00583 friend class csArray<T, ElementHandler>;
00584
00585 private:
00586 int currentelem;
00587 const csArray<T, ElementHandler>& array;
00588 };
00589
00591 Iterator GetIterator() const
00592 { return Iterator(*this); }
00593 };
00594
00595 #ifdef CS_EXTENSIVE_MEMDEBUG
00596 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00597 #endif
00598
00599 #endif