CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

parray.h

00001 /*
00002   Crystal Space Smart Pointers
00003   Copyright (C) 2003 by Jorrit Tyberghein
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 
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); // Increments 'count' as a side-effect.
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     // Free all items between new count and old count.
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;   // Clear last element to prevent deletion.
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); // Increments 'count' as a side-effect.
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 

Generated for Crystal Space by doxygen 1.2.14