00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef __CS_REFARR_H__
00021 #define __CS_REFARR_H__
00022
00023 #include "csutil/ref.h"
00024
00028 template <class T>
00029 class csRefArray
00030 {
00031 private:
00032 int count, limit, threshold;
00033 csRef<T>* root;
00034
00035 public:
00036 typedef int ArrayCompareFunction (T* item1, T* item2);
00037 typedef int ArrayCompareKeyFunction (T* item, void* key);
00038
00043 csRefArray (int ilimit = 0, int ithreshold = 0)
00044 {
00045 count = 0;
00046 limit = (ilimit > 0 ? ilimit : 0);
00047 threshold = (ithreshold > 0 ? ithreshold : 16);
00048 if (limit != 0)
00049 root = (csRef<T>*)calloc (limit, sizeof(csRef<T>));
00050 else
00051 root = NULL;
00052 }
00053
00060 void TransferTo (csRefArray<T>& destination)
00061 {
00062 destination.DeleteAll ();
00063 destination.root = root;
00064 destination.count = count;
00065 destination.limit = limit;
00066 destination.threshold = threshold;
00067 root = NULL;
00068 limit = count = 0;
00069 }
00070
00074 void DeleteAll ()
00075 {
00076 if (root)
00077 {
00078 int i;
00079 for (i = 0 ; i < limit ; i++)
00080 root[i] = NULL;
00081 free (root);
00082 root = NULL;
00083 limit = count = 0;
00084 }
00085 }
00086
00090 ~csRefArray ()
00091 {
00092 DeleteAll ();
00093 }
00094
00096 void SetLength (int n)
00097 {
00098
00099 int i;
00100 for (i = n ; i < count ; i++) root[i] = NULL;
00101
00102 int old_count = count;
00103 count = n;
00104
00105 if (n > limit || (limit > threshold && n < limit - threshold))
00106 {
00107 n = ((n + threshold - 1) / threshold ) * threshold;
00108 if (!n)
00109 {
00110 DeleteAll ();
00111 }
00112 else if (root == NULL)
00113 root = (csRef<T>*)calloc (n, sizeof(csRef<T>));
00114 else
00115 {
00116 csRef<T>* newroot = (csRef<T>*)calloc (n, sizeof(csRef<T>));
00117 memcpy (newroot, root, old_count * sizeof (csRef<T>));
00118 free (root);
00119 root = newroot;
00120 }
00121 limit = n;
00122 }
00123 }
00124
00126 int Length () const
00127 {
00128 return count;
00129 }
00130
00132 int Limit () const
00133 {
00134 return limit;
00135 }
00136
00138 const csRef<T>& Get (int n) const
00139 {
00140 CS_ASSERT (n >= 0 && n < count);
00141 return root[n];
00142 }
00143
00145 const csRef<T>& operator [] (int n) const
00146 {
00147 CS_ASSERT (n >= 0 && n < count);
00148 return root[n];
00149 }
00150
00152 csRef<T>& operator [] (int n)
00153 {
00154 CS_ASSERT (n >= 0);
00155 if (n >= count)
00156 SetLength (n + 1);
00157 return root[n];
00158 }
00159
00161 int Find (T* which) const
00162 {
00163 int i;
00164 for (i = 0 ; i < Length () ; i++)
00165 if (root[i] == which)
00166 return i;
00167 return -1;
00168 }
00169
00171 int Push (T* what)
00172 {
00173 SetLength (count + 1);
00174 root [count - 1] = what;
00175 return (count - 1);
00176 }
00177
00179 int PushSmart (T* what)
00180 {
00181 int n = Find (what);
00182 return (n == -1) ? Push (what) : n;
00183 }
00184
00186 csPtr<T> Pop ()
00187 {
00188 csRef<T> ret = root [count - 1];
00189 SetLength (count - 1);
00190 return csPtr<T> (ret);
00191 }
00192
00194 T* Top () const
00195 {
00196 return root [count - 1];
00197 }
00198
00200 bool Delete (int n)
00201 {
00202 if (n >= 0 && n < count)
00203 {
00204 root[n] = NULL;
00205 const int ncount = count - 1;
00206 const int nmove = ncount - n;
00207 if (nmove > 0)
00208 {
00209 memmove (&root [n], &root [n + 1], nmove * sizeof (csRef<T>));
00210
00211
00212 if (root[ncount])
00213 root[ncount]->IncRef ();
00214 }
00215 SetLength (ncount);
00216 return true;
00217 }
00218 else
00219 return false;
00220 }
00221
00223 bool Delete (T* item)
00224 {
00225 int n = Find (item);
00226 if (n == -1) return false;
00227 else return Delete (n);
00228 }
00229
00231 bool Insert (int n, T* item)
00232 {
00233 if (n <= count)
00234 {
00235 SetLength (count + 1);
00236 const int nmove = (count - n - 1);
00237 if (nmove > 0)
00238 {
00239 memmove (&root [n + 1], &root [n], nmove * sizeof (csRef<T>));
00240
00241
00242
00243
00244 if (root[n])
00245 root[n]->IncRef ();
00246 }
00247 root [n] = item;
00248 return true;
00249 }
00250 else
00251 return false;
00252 }
00253
00257 int FindSortedKey (void* key, ArrayCompareKeyFunction* comparekey) const
00258 {
00259 int l = 0, r = Length () - 1;
00260 while (l <= r)
00261 {
00262 int m = (l + r) / 2;
00263 int cmp = comparekey (root [m], key);
00264
00265 if (cmp == 0)
00266 return m;
00267 else if (cmp < 0)
00268 l = m + 1;
00269 else
00270 r = m - 1;
00271 }
00272 return -1;
00273 }
00274
00279 int InsertSorted (T* item, ArrayCompareFunction* compare)
00280 {
00281 int m = 0, l = 0, r = Length () - 1;
00282 while (l <= r)
00283 {
00284 m = (l + r) / 2;
00285 int cmp = compare (root [m], item);
00286
00287 if (cmp == 0)
00288 {
00289 Insert (++m, item);
00290 return m;
00291 }
00292 else if (cmp < 0)
00293 l = m + 1;
00294 else
00295 r = m - 1;
00296 }
00297 if (r == m)
00298 m++;
00299 Insert (m, item);
00300 return m;
00301 }
00302
00304 void QuickSort (ArrayCompareFunction* compare)
00305 {
00306 if (count > 0)
00307 QuickSort (0, count - 1, compare);
00308 }
00309
00311 void QuickSort (int Left, int Right, ArrayCompareFunction* compare)
00312 {
00313 recurse:
00314 int i = Left, j = Right;
00315 int x = (Left + Right) / 2;
00316 do
00317 {
00318 while ((i != x) && (compare (root[i], root[x]) < 0))
00319 i++;
00320 while ((j != x) && (compare (root[j], root[x]) > 0))
00321 j--;
00322 if (i < j)
00323 {
00324 csRef<T> swap;
00325 swap = root[i];
00326 root[i] = root[j];
00327 root[j] = swap;
00328 if (x == i)
00329 x = j;
00330 else if (x == j)
00331 x = i;
00332 }
00333 if (i <= j)
00334 {
00335 i++;
00336 if (j > Left)
00337 j--;
00338 }
00339 } while (i <= j);
00340
00341 if (j - Left < Right - i)
00342 {
00343 if (Left < j)
00344 QuickSort (Left, j, compare);
00345 if (i < Right)
00346 {
00347 Left = i;
00348 goto recurse;
00349 }
00350 }
00351 else
00352 {
00353 if (i < Right)
00354 QuickSort (i, Right, compare);
00355 if (Left < j)
00356 {
00357 Right = j;
00358 goto recurse;
00359 }
00360 }
00361 }
00362
00363 };
00364
00365 #endif // __CS_REFARR_H__
00366