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
00035 template <class T>
00036 class csArray
00037 {
00038 private:
00039 int count;
00040 int capacity;
00041 int threshold;
00042 T* root;
00043
00044 void ConstructElement (int n, T const& src)
00045 {
00046 new (static_cast<void*>(root + n)) T(src);
00047 }
00048
00049 void DestroyElement (int n)
00050 {
00051 (root + n)->T::~T();
00052 }
00053
00054
00055 void AdjustCapacity (int n)
00056 {
00057 if (n > capacity || (capacity > threshold && n < capacity - threshold))
00058 {
00059 n = ((n + threshold - 1) / threshold ) * threshold;
00060 if (root == 0)
00061 root = (T*)malloc (n * sizeof(T));
00062 else
00063 root = (T*)realloc (root, n * sizeof(T));
00064 capacity = n;
00065 }
00066 }
00067
00068
00069
00070
00071 void SetLengthUnsafe (int n)
00072 {
00073 if (n > capacity)
00074 AdjustCapacity (n);
00075 count = n;
00076 }
00077
00078 public:
00083 csArray (int icapacity = 0, int ithreshold = 0)
00084 {
00085 count = 0;
00086 capacity = (icapacity > 0 ? icapacity : 0);
00087 threshold = (ithreshold > 0 ? ithreshold : 16);
00088 if (capacity != 0)
00089 root = (T*)malloc (capacity * sizeof(T));
00090 else
00091 root = 0;
00092 }
00093
00095 csArray (const csArray& other)
00096 {
00097 count = 0;
00098 capacity = 0;
00099 threshold = other.threshold;
00100 root = 0;
00101 for (int i=0;i<other.Length();i++)
00102 Push (other[i]);
00103 }
00104
00111 void TransferTo (csArray<T>& destination)
00112 {
00113 destination.DeleteAll ();
00114 destination.root = root;
00115 destination.count = count;
00116 destination.capacity = capacity;
00117 destination.threshold = threshold;
00118 root = NULL;
00119 capacity = count = 0;
00120 }
00121
00122 csArray<T>& operator = (const csArray& other)
00123 {
00124 if (&other == this)
00125 return *this;
00126
00127
00128 DeleteAll ();
00129
00130 for (int i=0;i<other.Length();i++)
00131 Push(other[i]);
00132 return *this;
00133 }
00134
00136 void DeleteAll ()
00137 {
00138 for (int i = 0; i < count; i++)
00139 DestroyElement (i);
00140 if (root != 0)
00141 {
00142 free (root);
00143 root = 0;
00144 capacity = 0;
00145 count = 0;
00146 }
00147 }
00148
00154 void Truncate (int n)
00155 {
00156 CS_ASSERT(n >= 0);
00157 CS_ASSERT(n <= count);
00158 if (n < count)
00159 {
00160 for (int i = n; i < count; i++)
00161 DestroyElement(i);
00162 SetLengthUnsafe(n);
00163 }
00164 }
00165
00173 void SetLength (int n, T const& what)
00174 {
00175 if (n <= count)
00176 {
00177 Truncate (n);
00178 }
00179 else
00180 {
00181 int old_len = Length ();
00182 SetLengthUnsafe (n);
00183 for (int i = old_len ; i < n ; i++)
00184 ConstructElement (i, what);
00185 }
00186 }
00187
00193 void Empty()
00194 { Truncate(0); }
00195
00196
00198 ~csArray ()
00199 {
00200 DeleteAll ();
00201 }
00202
00204 int Length () const
00205 {
00206 return count;
00207 }
00208
00210 int Capacity () const
00211 {
00212 return capacity;
00213 }
00214
00221 void SetCapacity (int n)
00222 {
00223 if (n > Length ())
00224 AdjustCapacity (n);
00225 }
00226
00232 void ShrinkBestFit ()
00233 {
00234 if (count == 0)
00235 {
00236 DeleteAll ();
00237 }
00238 else if (count != capacity)
00239 {
00240 capacity = count;
00241 root = (T*)realloc (root, capacity * sizeof(T));
00242 }
00243 }
00244
00246 T const& Get (int n) const
00247 {
00248 CS_ASSERT (n >= 0 && n < count);
00249 return root[n];
00250 }
00251
00253 T& Get (int n)
00254 {
00255 CS_ASSERT (n >= 0 && n < count);
00256 return root[n];
00257 }
00258
00260 T const& operator [] (int n) const
00261 {
00262 return Get(n);
00263 }
00264
00266 T& operator [] (int n)
00267 {
00268 return Get(n);
00269 }
00270
00272 int Find (T const& which) const
00273 {
00274 for (int i = 0, n = Length(); i < n; i++)
00275 if (root[i] == which)
00276 return i;
00277 return -1;
00278 }
00279
00281 int Push (T const& what)
00282 {
00283 SetLengthUnsafe (count + 1);
00284 ConstructElement (count - 1, what);
00285 return (count - 1);
00286 }
00287
00288
00289
00290
00291
00292 int PushSmart (T const& what)
00293 {
00294 int const n = Find (what);
00295 return (n < 0) ? Push (what) : n;
00296 }
00297
00299 T Pop ()
00300 {
00301 CS_ASSERT (count > 0);
00302 T ret(root [count - 1]);
00303 DestroyElement (count - 1);
00304 SetLengthUnsafe (count - 1);
00305 return ret;
00306 }
00307
00309 T const& Top () const
00310 {
00311 CS_ASSERT (count > 0);
00312 return root [count - 1];
00313 }
00314
00316 bool DeleteIndex (int n)
00317 {
00318 if (n >= 0 && n < count)
00319 {
00320 int const ncount = count - 1;
00321 int const nmove = ncount - n;
00322 DestroyElement (n);
00323 if (nmove > 0)
00324 memmove (root + n, root + n + 1, nmove * sizeof(T));
00325 SetLengthUnsafe (ncount);
00326 return true;
00327 }
00328 else
00329 return false;
00330 }
00331
00336 void DeleteRange (int start, int end)
00337 {
00338 if (start >= count) return;
00339 if (end < 0) return;
00340 if (start < 0) start = 0;
00341 if (end >= count) end = count-1;
00342 int i;
00343 for (i = start ; i < end ; i++)
00344 DestroyElement (i);
00345
00346 int const range_size = end-start+1;
00347 int const ncount = count - range_size;
00348 int const nmove = count - end - 1;
00349 if (nmove > 0)
00350 memmove (root + start, root + start + range_size, nmove * sizeof(T));
00351 SetLengthUnsafe (ncount);
00352 }
00353
00355 bool Delete (T const& item)
00356 {
00357 int const n = Find (item);
00358 if (n >= 0)
00359 return DeleteIndex (n);
00360 return false;
00361 }
00362
00364 bool Insert (int n, T const& item)
00365 {
00366 if (n <= count)
00367 {
00368 SetLengthUnsafe (count + 1);
00369 int const nmove = (count - n - 1);
00370 if (nmove > 0)
00371 memmove (root + n + 1, root + n, nmove * sizeof(T));
00372 ConstructElement (n, item);
00373 return true;
00374 }
00375 else
00376 return false;
00377 }
00378 };
00379
00380 #ifdef CS_EXTENSIVE_MEMDEBUG
00381 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00382 #endif
00383
00384 #endif