00001
00002
00003
00004
00005 #ifndef __IRR_ARRAY_H_INCLUDED__
00006 #define __IRR_ARRAY_H_INCLUDED__
00007
00008 #include "irrTypes.h"
00009 #include "heapsort.h"
00010 #include "irrAllocator.h"
00011
00012 namespace irr
00013 {
00014 namespace core
00015 {
00016
00018
00020 template <class T, typename TAlloc = irrAllocator<T> >
00021 class array
00022 {
00023
00024 public:
00025
00027 array()
00028 : data(0), allocated(0), used(0),
00029 strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true)
00030 {
00031 }
00032
00034
00035 array(u32 start_count)
00036 : data(0), allocated(0), used(0),
00037 strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true)
00038 {
00039 reallocate(start_count);
00040 }
00041
00042
00044 array(const array<T>& other)
00045 : data(0)
00046 {
00047 *this = other;
00048 }
00049
00050
00051
00053
00055 ~array()
00056 {
00057 if (free_when_destroyed)
00058 {
00059 for (u32 i=0; i<used; ++i)
00060 allocator.destruct(&data[i]);
00061
00062 allocator.deallocate(data);
00063 }
00064 }
00065
00066
00068
00069 void reallocate(u32 new_size)
00070 {
00071 T* old_data = data;
00072
00073 data = allocator.allocate(new_size);
00074 allocated = new_size;
00075
00076
00077 s32 end = used < new_size ? used : new_size;
00078
00079 for (s32 i=0; i<end; ++i)
00080 {
00081
00082 allocator.construct(&data[i], old_data[i]);
00083 }
00084
00085
00086 for (u32 j=0; j<used; ++j)
00087 allocator.destruct(&old_data[j]);
00088
00089 if (allocated < used)
00090 used = allocated;
00091
00092 allocator.deallocate(old_data);
00093 }
00094
00095
00097
00100 void setAllocStrategy ( eAllocStrategy newStrategy = ALLOC_STRATEGY_DOUBLE )
00101 {
00102 strategy = newStrategy;
00103 }
00104
00106
00108 void push_back(const T& element)
00109 {
00110 if (used + 1 > allocated)
00111 {
00112
00113
00114
00115
00116 T e(element);
00117
00118
00119
00120
00121
00122 u32 newAlloc;
00123 switch ( strategy )
00124 {
00125 case ALLOC_STRATEGY_DOUBLE:
00126 newAlloc = used + 1 + (allocated < 500 ?
00127 (allocated < 5 ? 5 : used) : used >> 2);
00128 break;
00129 default:
00130 case ALLOC_STRATEGY_SAFE:
00131 newAlloc = used + 1;
00132 break;
00133 }
00134 reallocate( newAlloc);
00135
00136
00137 allocator.construct(&data[used++], e);
00138 }
00139 else
00140 {
00141
00142
00143 allocator.construct(&data[used++], element);
00144 }
00145
00146 is_sorted = false;
00147 }
00148
00149
00151
00155 void push_front(const T& element)
00156 {
00157 insert(element);
00158 }
00159
00160
00162
00167 void insert(const T& element, u32 index=0)
00168 {
00169 _IRR_DEBUG_BREAK_IF(index>used)
00170
00171 if (used + 1 > allocated)
00172 reallocate(used +1);
00173
00174 for (u32 i=used; i>index; --i)
00175 {
00176 if (i<used)
00177 allocator.destruct(&data[i]);
00178 allocator.construct(&data[i], data[i-1]);
00179 }
00180
00181 if (used > index)
00182 allocator.destruct(&data[index]);
00183 allocator.construct(&data[index], element);
00184 is_sorted = false;
00185 ++used;
00186 }
00187
00188
00190 void clear()
00191 {
00192 for (u32 i=0; i<used; ++i)
00193 allocator.destruct(&data[i]);
00194
00195 allocator.deallocate(data);
00196 data = 0;
00197 used = 0;
00198 allocated = 0;
00199 is_sorted = true;
00200 }
00201
00202
00204
00206 void set_pointer(T* newPointer, u32 size)
00207 {
00208 for (u32 i=0; i<used; ++i)
00209 allocator.destruct(&data[i]);
00210
00211 allocator.deallocate(data);
00212 data = newPointer;
00213 allocated = size;
00214 used = size;
00215 is_sorted = false;
00216 }
00217
00218
00220
00222 void set_free_when_destroyed(bool f)
00223 {
00224 free_when_destroyed = f;
00225 }
00226
00227
00229
00232 void set_used(u32 usedNow)
00233 {
00234 if (allocated < usedNow)
00235 reallocate(usedNow);
00236
00237 used = usedNow;
00238 }
00239
00240
00242 void operator=(const array<T>& other)
00243 {
00244 strategy = other.strategy;
00245
00246 if (data)
00247 {
00248 for (u32 i=0; i<used; ++i)
00249 allocator.destruct(&data[i]);
00250
00251 allocator.deallocate(data);
00252 }
00253
00254
00255 if (other.allocated == 0)
00256 data = 0;
00257 else
00258 data = allocator.allocate(other.allocated);
00259
00260 used = other.used;
00261 free_when_destroyed = other.free_when_destroyed;
00262 is_sorted = other.is_sorted;
00263 allocated = other.allocated;
00264
00265 for (u32 i=0; i<other.used; ++i)
00266 allocator.construct(&data[i], other.data[i]);
00267 }
00268
00269
00271 bool operator == (const array<T>& other) const
00272 {
00273 if (used != other.used)
00274 return false;
00275
00276 for (u32 i=0; i<other.used; ++i)
00277 if (data[i] != other[i])
00278 return false;
00279 return true;
00280 }
00281
00283 bool operator != (const array<T>& other) const
00284 {
00285 return !(*this==other);
00286 }
00287
00288
00290 T& operator [](u32 index)
00291 {
00292 _IRR_DEBUG_BREAK_IF(index>=used)
00293
00294 return data[index];
00295 }
00296
00297
00299 const T& operator [](u32 index) const
00300 {
00301 _IRR_DEBUG_BREAK_IF(index>=used)
00302
00303 return data[index];
00304 }
00305
00306
00308 T& getLast()
00309 {
00310 _IRR_DEBUG_BREAK_IF(!used)
00311
00312 return data[used-1];
00313 }
00314
00315
00317 const T& getLast() const
00318 {
00319 _IRR_DEBUG_BREAK_IF(!used)
00320
00321 return data[used-1];
00322 }
00323
00324
00326
00327 T* pointer()
00328 {
00329 return data;
00330 }
00331
00332
00334
00335 const T* const_pointer() const
00336 {
00337 return data;
00338 }
00339
00340
00342
00343 u32 size() const
00344 {
00345 return used;
00346 }
00347
00348
00350
00352 u32 allocated_size() const
00353 {
00354 return allocated;
00355 }
00356
00357
00359
00360 bool empty() const
00361 {
00362 return used == 0;
00363 }
00364
00365
00367
00369 void sort()
00370 {
00371 if (is_sorted || used<2)
00372 return;
00373
00374 heapsort(data, used);
00375 is_sorted = true;
00376 }
00377
00378
00380
00386 s32 binary_search(const T& element)
00387 {
00388 sort();
00389 return binary_search(element, 0, used-1);
00390 }
00391
00392
00394
00399 s32 binary_search(const T& element) const
00400 {
00401 if (is_sorted)
00402 return binary_search(element, 0, used-1);
00403 else
00404 return linear_search(element);
00405 }
00406
00407
00409
00414 s32 binary_search(const T& element, s32 left, s32 right) const
00415 {
00416 if (!used)
00417 return -1;
00418
00419 s32 m;
00420
00421 do
00422 {
00423 m = (left+right)>>1;
00424
00425 if (element < data[m])
00426 right = m - 1;
00427 else
00428 left = m + 1;
00429
00430 } while((element < data[m] || data[m] < element) && left<=right);
00431
00432
00433
00434
00435
00436
00437 if (!(element < data[m]) && !(data[m] < element))
00438 return m;
00439
00440 return -1;
00441 }
00442
00443
00446
00452 s32 binary_search_multi(const T& element, s32 &last)
00453 {
00454 sort();
00455 s32 index = binary_search(element, 0, used-1);
00456 if ( index < 0 )
00457 return index;
00458
00459
00460
00461 last = index;
00462
00463 while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) )
00464 {
00465 index -= 1;
00466 }
00467
00468 while ( last < (s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) )
00469 {
00470 last += 1;
00471 }
00472
00473 return index;
00474 }
00475
00477
00482 s32 linear_search(const T& element) const
00483 {
00484 for (u32 i=0; i<used; ++i)
00485 if (element == data[i])
00486 return (s32)i;
00487
00488 return -1;
00489 }
00490
00491
00493
00498 s32 linear_reverse_search(const T& element) const
00499 {
00500 for (s32 i=used-1; i>=0; --i)
00501 if (data[i] == element)
00502 return i;
00503
00504 return -1;
00505 }
00506
00507
00509
00512 void erase(u32 index)
00513 {
00514 _IRR_DEBUG_BREAK_IF(index>=used)
00515
00516 for (u32 i=index+1; i<used; ++i)
00517 {
00518 allocator.destruct(&data[i-1]);
00519 allocator.construct(&data[i-1], data[i]);
00520 }
00521
00522 allocator.destruct(&data[used-1]);
00523
00524 --used;
00525 }
00526
00527
00529
00533 void erase(u32 index, s32 count)
00534 {
00535 _IRR_DEBUG_BREAK_IF(index>=used || count<1 || index+count>used)
00536
00537 u32 i;
00538 for (i=index; i<index+count; ++i)
00539 allocator.destruct(&data[i]);
00540
00541 for (i=index+count; i<used; ++i)
00542 {
00543 if (i > index+count)
00544 allocator.destruct(&data[i-count]);
00545
00546 allocator.construct(&data[i-count], data[i]);
00547
00548 if (i >= used-count)
00549 allocator.destruct(&data[i]);
00550 }
00551
00552 used-= count;
00553 }
00554
00555
00557 void set_sorted(bool _is_sorted)
00558 {
00559 is_sorted = _is_sorted;
00560 }
00561
00562 private:
00563
00564 T* data;
00565 TAlloc allocator;
00566 u32 allocated;
00567 u32 used;
00568 eAllocStrategy strategy;
00569 bool free_when_destroyed:1;
00570 bool is_sorted:1;
00571 };
00572
00573
00574 }
00575 }
00576
00577
00578 #endif
00579