00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef __CS_PTRARR_H__
00021 #define __CS_PTRARR_H__
00022
00023 #include "csutil/ref.h"
00024
00025 typedef int csArrayCompareFunction (void* item1, void* item2);
00026 typedef int csArrayCompareKeyFunction (void* item, void* key);
00027
00037 template <class T>
00038 class csPArray
00039 {
00040 private:
00041 int count, limit, threshold;
00042 T** root;
00043
00044 public:
00049 csPArray (int ilimit = 0, int ithreshold = 0)
00050 {
00051 count = 0;
00052 limit = (ilimit > 0 ? ilimit : 0);
00053 threshold = (ithreshold > 0 ? ithreshold : 16);
00054 if (limit != 0)
00055 root = (T**)malloc (limit * sizeof(T*));
00056 else
00057 root = NULL;
00058 }
00059
00063 void DeleteAll ()
00064 {
00065 if (root)
00066 {
00067 free (root);
00068 root = NULL;
00069 limit = count = 0;
00070 }
00071 }
00072
00076 ~csPArray ()
00077 {
00078 DeleteAll ();
00079 }
00080
00087 void TransferTo (csPArray<T>& destination)
00088 {
00089 destination.DeleteAll ();
00090 destination.root = root;
00091 destination.count = count;
00092 destination.limit = limit;
00093 destination.threshold = threshold;
00094 root = NULL;
00095 limit = count = 0;
00096 }
00097
00099 void SetLength (int n)
00100 {
00101 count = n;
00102
00103 if (n > limit || (limit > threshold && n < limit - threshold))
00104 {
00105 n = ((n + threshold - 1) / threshold ) * threshold;
00106 if (!n)
00107 DeleteAll ();
00108 else if (root == NULL)
00109 root = (T**)malloc (n * sizeof(T*));
00110 else
00111 root = (T**)realloc (root, n * sizeof(T*));
00112 limit = n;
00113 }
00114 }
00115
00117 int Length () const
00118 {
00119 return count;
00120 }
00121
00123 int Limit () const
00124 {
00125 return limit;
00126 }
00127
00129 T* Get (int n) const
00130 {
00131 CS_ASSERT (n >= 0 && n < count);
00132 return root[n];
00133 }
00134
00136 const T*& operator [] (int n) const
00137 {
00138 CS_ASSERT (n >= 0 && n < count);
00139 return root[n];
00140 }
00141
00143 T*& operator [] (int n)
00144 {
00145 CS_ASSERT (n >= 0);
00146 if (n >= count)
00147 SetLength (n + 1);
00148 return root[n];
00149 }
00150
00152 int Find (T* which) const
00153 {
00154 int i;
00155 for (i = 0 ; i < Length () ; i++)
00156 if (root[i] == which)
00157 return i;
00158 return -1;
00159 }
00160
00162 int Push (T* what)
00163 {
00164 SetLength (count + 1);
00165 root [count - 1] = what;
00166 return (count - 1);
00167 }
00168
00170 int PushSmart (T* what)
00171 {
00172 int n = Find (what);
00173 return (n == -1) ? Push (what) : n;
00174 }
00175
00177 T* Pop ()
00178 {
00179 T* ret = root [count - 1];
00180 SetLength (count - 1);
00181 return ret;
00182 }
00183
00185 T* Top () const
00186 {
00187 return root [count - 1];
00188 }
00189
00191 bool Delete (int n)
00192 {
00193 if (n >= 0 && n < count)
00194 {
00195 const int ncount = count - 1;
00196 const int nmove = ncount - n;
00197 if (nmove > 0)
00198 {
00199 memmove (&root [n], &root [n + 1], nmove * sizeof (T*));
00200 }
00201 SetLength (ncount);
00202 return true;
00203 }
00204 else
00205 return false;
00206 }
00207
00209 bool Delete (T* item)
00210 {
00211 int n = Find (item);
00212 if (n == -1) return false;
00213 else return Delete (n);
00214 }
00215
00217 bool Insert (int n, T* item)
00218 {
00219 if (n <= count)
00220 {
00221 SetLength (count + 1);
00222 const int nmove = (count - n - 1);
00223 if (nmove > 0)
00224 {
00225 memmove (&root [n + 1], &root [n], nmove * sizeof (T*));
00226 }
00227 root [n] = item;
00228 return true;
00229 }
00230 else
00231 return false;
00232 }
00233
00237 int FindSortedKey (void* key, csArrayCompareKeyFunction* comparekey) const
00238 {
00239 int l = 0, r = Length () - 1;
00240 while (l <= r)
00241 {
00242 int m = (l + r) / 2;
00243 int cmp = comparekey (root [m], key);
00244
00245 if (cmp == 0)
00246 return m;
00247 else if (cmp < 0)
00248 l = m + 1;
00249 else
00250 r = m - 1;
00251 }
00252 return -1;
00253 }
00254
00259 int InsertSorted (T* item, csArrayCompareFunction* compare)
00260 {
00261 int m = 0, l = 0, r = Length () - 1;
00262 while (l <= r)
00263 {
00264 m = (l + r) / 2;
00265 int cmp = compare (root [m], item);
00266
00267 if (cmp == 0)
00268 {
00269 Insert (++m, item);
00270 return m;
00271 }
00272 else if (cmp < 0)
00273 l = m + 1;
00274 else
00275 r = m - 1;
00276 }
00277 if (r == m)
00278 m++;
00279 Insert (m, item);
00280 return m;
00281 }
00282 };
00283
00291 template <class T>
00292 class csPDelArray
00293 {
00294 private:
00295 int count, limit, threshold;
00296 T** root;
00297
00298 public:
00303 csPDelArray (int ilimit = 0, int ithreshold = 0)
00304 {
00305 count = 0;
00306 limit = (ilimit > 0 ? ilimit : 0);
00307 threshold = (ithreshold > 0 ? ithreshold : 16);
00308 if (limit != 0)
00309 root = (T**)calloc (limit, sizeof(T*));
00310 else
00311 root = NULL;
00312 }
00313
00317 void DeleteAll ()
00318 {
00319 if (root)
00320 {
00321 int i;
00322 for (i = 0 ; i < limit ; i++)
00323 delete root[i];
00324 free (root);
00325 root = NULL;
00326 limit = count = 0;
00327 }
00328 }
00329
00333 ~csPDelArray ()
00334 {
00335 DeleteAll ();
00336 }
00337
00344 void TransferTo (csPDelArray<T>& destination)
00345 {
00346 destination.DeleteAll ();
00347 destination.root = root;
00348 destination.count = count;
00349 destination.limit = limit;
00350 destination.threshold = threshold;
00351 root = NULL;
00352 limit = count = 0;
00353 }
00354
00356 void SetLength (int n)
00357 {
00358
00359 int i;
00360 for (i = n ; i < count ; i++) { delete root[i]; root[i] = NULL; }
00361
00362 int old_count = count;
00363 count = n;
00364
00365 if (n > limit || (limit > threshold && n < limit - threshold))
00366 {
00367 n = ((n + threshold - 1) / threshold ) * threshold;
00368 if (!n)
00369 {
00370 DeleteAll ();
00371 }
00372 else if (root == NULL)
00373 {
00374 root = (T**)calloc (n, sizeof(T*));
00375 }
00376 else
00377 {
00378 T** newroot = (T**)calloc (n, sizeof(T*));
00379 memcpy (newroot, root, old_count * sizeof (T*));
00380 free (root);
00381 root = newroot;
00382 }
00383 limit = n;
00384 }
00385 }
00386
00388 int Length () const
00389 {
00390 return count;
00391 }
00392
00394 int Limit () const
00395 {
00396 return limit;
00397 }
00398
00400 T* Get (int n) const
00401 {
00402 CS_ASSERT (n >= 0 && n < count);
00403 return root[n];
00404 }
00405
00407 T* operator [] (int n) const
00408 {
00409 CS_ASSERT (n >= 0 && n < count);
00410 return root[n];
00411 }
00412
00414 void Put (int n, T* ptr)
00415 {
00416 CS_ASSERT (n >= 0);
00417 if (n >= count)
00418 SetLength (n + 1);
00419 delete root[n];
00420 root[n] = ptr;
00421 }
00422
00424 int Find (T* which) const
00425 {
00426 int i;
00427 for (i = 0 ; i < Length () ; i++)
00428 if (root[i] == which)
00429 return i;
00430 return -1;
00431 }
00432
00434 int Push (T* what)
00435 {
00436 SetLength (count + 1);
00437 root [count - 1] = what;
00438 return (count - 1);
00439 }
00440
00442 int PushSmart (T* what)
00443 {
00444 int n = Find (what);
00445 return (n == -1) ? Push (what) : n;
00446 }
00447
00452 T* Pop ()
00453 {
00454 T* ret = root [count - 1];
00455 root [count-1] = NULL;
00456 SetLength (count - 1);
00457 return ret;
00458 }
00459
00461 T* Top () const
00462 {
00463 return root [count - 1];
00464 }
00465
00471 T* GetAndClear (int n)
00472 {
00473 CS_ASSERT (n >= 0 && n < count);
00474 T* ret = root[n];
00475 root[n] = NULL;
00476 return ret;
00477 }
00478
00484 T* Extract (int n)
00485 {
00486 T* rc = NULL;
00487 if (n >= 0 && n < count)
00488 {
00489 rc = root[n]; root[n] = NULL;
00490 const int ncount = count - 1;
00491 const int nmove = ncount - n;
00492 if (nmove > 0)
00493 {
00494 memmove (&root [n], &root [n + 1], nmove * sizeof (T*));
00495 root[count-1] = NULL;
00496 }
00497 SetLength (ncount);
00498 }
00499 return rc;
00500 }
00501
00503 bool Delete (int n)
00504 {
00505 T* p = Extract (n);
00506 if (p)
00507 {
00508 delete p;
00509 return true;
00510 }
00511 else
00512 {
00513 return false;
00514 }
00515 }
00516
00518 bool Delete (T* item)
00519 {
00520 int n = Find (item);
00521 if (n == -1) return false;
00522 else return Delete (n);
00523 }
00524
00526 bool Insert (int n, T* item)
00527 {
00528 if (n <= count)
00529 {
00530 SetLength (count + 1);
00531 const int nmove = (count - n - 1);
00532 if (nmove > 0)
00533 {
00534 memmove (&root [n + 1], &root [n], nmove * sizeof (T*));
00535 }
00536 root [n] = item;
00537 return true;
00538 }
00539 else
00540 return false;
00541 }
00542
00546 int FindSortedKey (void* key, csArrayCompareKeyFunction* comparekey) const
00547 {
00548 int l = 0, r = Length () - 1;
00549 while (l <= r)
00550 {
00551 int m = (l + r) / 2;
00552 int cmp = comparekey (root [m], key);
00553
00554 if (cmp == 0)
00555 return m;
00556 else if (cmp < 0)
00557 l = m + 1;
00558 else
00559 r = m - 1;
00560 }
00561 return -1;
00562 }
00563
00568 int InsertSorted (T* item, csArrayCompareFunction* compare)
00569 {
00570 int m = 0, l = 0, r = Length () - 1;
00571 while (l <= r)
00572 {
00573 m = (l + r) / 2;
00574 int cmp = compare (root [m], item);
00575
00576 if (cmp == 0)
00577 {
00578 Insert (++m, item);
00579 return m;
00580 }
00581 else if (cmp < 0)
00582 l = m + 1;
00583 else
00584 r = m - 1;
00585 }
00586 if (r == m)
00587 m++;
00588 Insert (m, item);
00589 return m;
00590 }
00591 };
00592
00593 #endif // __CS_PTRARR_H__
00594