00001
00002
00003
00004
00005 #ifndef _GARRAY_H_
00006 #define _GARRAY_H_
00007
00008 #include <stdlib.h>
00009 #include <assert.h>
00010 #include "LgiDefs.h"
00011 #include "GMem.h"
00012
00013 #define GARRAY_MIN_SIZE 16
00014
00031 template <class Type>
00032 class GArray
00033 {
00034 Type *p;
00035 uint32 len;
00036 uint32 alloc;
00037
00038 protected:
00039 bool fixed;
00040
00041 public:
00043 GArray(int PreAlloc = 0)
00044 {
00045 p = 0;
00046 len = 0;
00047 fixed = false;
00048
00049 alloc = PreAlloc;
00050 if (alloc)
00051 {
00052 int Bytes = sizeof(Type) * alloc;
00053 p = (Type*) malloc(Bytes);
00054 if (p)
00055 {
00056 memset(p, 0, Bytes);
00057 }
00058 else
00059 {
00060 alloc = 0;
00061 }
00062 }
00063 }
00064
00065 GArray(const GArray<Type> &c)
00066 {
00067 p = 0;
00068 alloc = len = 0;
00069 fixed = false;
00070 *this = c;
00071 }
00072
00074 ~GArray()
00075 {
00076 Length(0);
00077 }
00078
00080 uint32 Length() const
00081 {
00082 return len;
00083 }
00084
00086 void SetFixedLength()
00087 {
00088 fixed = true;
00089 }
00090
00092 bool Length(uint32 i)
00093 {
00094 if (i > 0)
00095 {
00096 if (i > len && fixed)
00097 {
00098 LgiAssert(!"Attempt to enlarged fixed array.");
00099 return false;
00100 }
00101
00102 uint nalloc = alloc;
00103 if (i < len)
00104 {
00105
00106 }
00107 else
00108 {
00109
00110 int b;
00111 for (b = 4; (1 << b) < i; b++)
00112 ;
00113 nalloc = 1 << b;
00114 LgiAssert(nalloc >= i);
00115 }
00116
00117 if (nalloc != alloc)
00118 {
00119 Type *np = (Type*)malloc(sizeof(Type) * nalloc);
00120 if (!np)
00121 {
00122 return false;
00123 }
00124
00125 if (p)
00126 {
00127
00128 memcpy(np, p, min(len, i) * sizeof(Type));
00129 free(p);
00130 }
00131 p = np;
00132 alloc = nalloc;
00133 }
00134
00135 if (i > len)
00136 {
00137
00138 memset(p + len, 0, sizeof(Type) * (nalloc - len));
00139 }
00140
00141 len = i;
00142 }
00143 else
00144 {
00145 if (p)
00146 {
00147 int Length = len;
00148 for (uint i=0; i<Length; i++)
00149 {
00150 p[i].~Type();
00151 }
00152 free(p);
00153 p = 0;
00154 }
00155 len = alloc = 0;
00156 }
00157
00158 return true;
00159 }
00160
00161 GArray<Type> &operator =(const GArray<Type> &a)
00162 {
00163 Length(a.Length());
00164 if (p && a.p)
00165 {
00166 for (int i=0; i<len; i++)
00167 {
00168 p[i] = a.p[i];
00169 }
00170 }
00171 return *this;
00172 }
00173
00178 Type &operator [](uint32 i)
00179 {
00180 static Type t;
00181 if
00182 (
00183 i < 0
00184 ||
00185 (fixed && i >= len)
00186 )
00187 {
00188 ZeroObj(t);
00189 if (fixed && i >= len)
00190 LgiAssert(!"Attempt to enlarged fixed array.");
00191 return t;
00192 }
00193
00194 #if 1
00195 if (i > 64<<20)
00196 {
00197 #if defined(_DEBUG) && defined(_MSC_VER)
00198 LgiAssert(0);
00199 #endif
00200
00201 ZeroObj(t);
00202 return t;
00203 }
00204 #endif
00205
00206 if (i >= alloc)
00207 {
00208
00209 uint nalloc = max(alloc, GARRAY_MIN_SIZE);
00210 while (nalloc <= i)
00211 {
00212 nalloc <<= 1;
00213 }
00214
00215
00216 Type *np = (Type*) malloc(sizeof(Type) * nalloc);
00217 if (np)
00218 {
00219
00220 memset(np + len, 0, (nalloc - len) * sizeof(Type));
00221 if (p)
00222 {
00223
00224 memcpy(np, p, len * sizeof(Type));
00225
00226
00227 free(p);
00228 }
00229
00230
00231 p = np;
00232 alloc = nalloc;
00233 }
00234 else
00235 {
00236 static Type *t = 0;
00237 return *t;
00238 }
00239 }
00240
00241
00242 if (i + 1 > len)
00243 {
00244 len = i + 1;
00245 }
00246
00247 return p[i];
00248 }
00249
00251 void DeleteObjects()
00252 {
00253 for (uint i=0; i<len; i++)
00254 {
00255 DeleteObj(p[i]);
00256 }
00257 Length(0);
00258 }
00259
00261 void DeleteArrays()
00262 {
00263 for (int i=0; i<len; i++)
00264 {
00265 DeleteArray(p[i]);
00266 }
00267 Length(0);
00268 }
00269
00271 int IndexOf(Type n)
00272 {
00273 for (uint i=0; i<len; i++)
00274 {
00275 if (p[i] == n) return i;
00276 }
00277
00278 return -1;
00279 }
00280
00282 bool HasItem(Type n)
00283 {
00284 return IndexOf(n) >= 0;
00285 }
00286
00288 bool DeleteAt
00289 (
00291 uint Index,
00293 bool Ordered = false
00294 )
00295 {
00296 if (p && Index >= 0 && Index < len)
00297 {
00298
00299 p[Index].~Type();
00300
00301
00302 if (Index < len - 1)
00303 {
00304 if (Ordered)
00305 {
00306 memmove(p + Index, p + Index + 1, (len - Index - 1) * sizeof(Type) );
00307 }
00308 else
00309 {
00310 p[Index] = p[len-1];
00311 }
00312 }
00313
00314
00315 len--;
00316
00317
00318 memset(p + len, 0, sizeof(Type));
00319 return true;
00320 }
00321
00322 return false;
00323 }
00324
00326 bool Delete
00327 (
00329 Type n,
00331 bool Ordered = false
00332 )
00333 {
00334 int i = IndexOf(n);
00335 if (p && i >= 0)
00336 {
00337 return DeleteAt(i, Ordered);
00338 }
00339
00340 return false;
00341 }
00342
00344 void Add
00345 (
00347 const Type &n
00348 )
00349 {
00350 (*this)[len] = n;
00351 }
00352
00354 void Add
00355 (
00357 Type *s,
00359 int count
00360
00361 )
00362 {
00363 if (!s || count < 1)
00364 return;
00365
00366 int i = len;
00367 Length(len + count);
00368 Type *d = p + i;
00369 while (count--)
00370 {
00371 *d++ = *s++;
00372 }
00373 }
00374
00376 void Add
00377 (
00379 GArray<Type> &a
00380
00381 )
00382 {
00383 int old = len;
00384 if (Length(len + a.Length()))
00385 {
00386 for (int i=0; i<a.Length(); i++, old++)
00387 p[old] = a[i];
00388 }
00389 }
00390 GArray<Type> &operator +(GArray<Type> &a)
00391 {
00392 Add(a);
00393 return *this;
00394 }
00395
00397 bool AddAt
00398 (
00400 int Index,
00402 Type n
00403 )
00404 {
00405
00406 if (Length(len + 1))
00407 {
00408 if (Index < len - 1)
00409 {
00410
00411 memmove(p + Index + 1, p + Index, (len - Index - 1) * sizeof(Type) );
00412 }
00413 else if (Index >= len)
00414 {
00415
00416 Index = len - 1;
00417 }
00418
00419
00420 p[Index] = n;
00421
00422 return true;
00423 }
00424
00425 return false;
00426 }
00427
00429 void Sort(int (*Compare)(Type*, Type*))
00430 {
00431 typedef int (*qsort_compare)(const void *, const void *);
00432 qsort(p, len, sizeof(Type), (qsort_compare)Compare);
00433 }
00434
00436 Type &New()
00437 {
00438 return (*this)[len];
00439 }
00440
00442 Type *Release()
00443 {
00444 Type *Ptr = p;
00445 p = 0;
00446 len = alloc = 0;
00447 return Ptr;
00448 }
00449
00450 template <class T>
00451 class Iter
00452 {
00453 int i;
00454 int8 each_dir;
00455 GArray<T> *a;
00456
00457 public:
00458 Iter(GArray<T> *arr, int pos)
00459 {
00460 i = pos;
00461 a = arr;
00462 each_dir = 0;
00463 }
00464
00465 bool Each()
00466 {
00467 if (each_dir) i += each_dir;
00468 else each_dir = i == 0 ? 1 : -1;
00469 return In();
00470 }
00471
00472 operator bool() { return In(); }
00473 bool In() { return i >= 0 && i < a->Length(); }
00474 bool End() { return i < 0 || i >= a->Length(); }
00475 T &operator *() { return (*a)[i]; }
00476 Iter<T> &operator ++() { i++; return *this; }
00477 Iter<T> &operator --() { i--; return *this; }
00478 Iter<T> &operator ++(int) { i++; return *this; }
00479 Iter<T> &operator --(int) { i--; return *this; }
00480 };
00481
00482 typedef Iter<Type> I;
00483 I Start() { return I(this, 0); }
00484 I End() { return I(this, Length()-1); }
00485 };
00486
00487 #endif