 |
+
+
+
+ Irrlicht 3D Engine
+
+
+
+ |
+
+
+
+
+
+
+
+
+
+
+ 
+
+ |
+
+
+
00001 // Copyright (C) 2002-2012 Nikolaus Gebhardt +00002 // This file is part of the "Irrlicht Engine" and the "irrXML" project. +00003 // For conditions of distribution and use, see copyright notice in irrlicht.h and irrXML.h +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 #include "irrMath.h" +00012 +00013 namespace irr +00014 { +00015 namespace core +00016 { +00017 +00019 +00021 template <class T, typename TAlloc = irrAllocator<T> > +00022 class array +00023 { +00024 +00025 public: +00026 +00028 array() +00029 : data(0), allocated(0), used(0), +00030 strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true) +00031 { +00032 } +00033 +00034 +00036 +00037 array(u32 start_count) +00038 : data(0), allocated(0), used(0), +00039 strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true) +00040 { +00041 reallocate(start_count); +00042 } +00043 +00044 +00046 array(const array<T, TAlloc>& other) : data(0) +00047 { +00048 *this = other; +00049 } +00050 +00051 +00053 +00055 ~array() +00056 { +00057 clear(); +00058 } +00059 +00060 +00062 +00067 void reallocate(u32 new_size, bool canShrink=true) +00068 { +00069 if (allocated==new_size) +00070 return; +00071 if (!canShrink && (new_size < allocated)) +00072 return; +00073 +00074 T* old_data = data; +00075 +00076 data = allocator.allocate(new_size); //new T[new_size]; +00077 allocated = new_size; +00078 +00079 // copy old data +00080 s32 end = used < new_size ? used : new_size; +00081 +00082 for (s32 i=0; i<end; ++i) +00083 { +00084 // data[i] = old_data[i]; +00085 allocator.construct(&data[i], old_data[i]); +00086 } +00087 +00088 // destruct old data +00089 for (u32 j=0; j<used; ++j) +00090 allocator.destruct(&old_data[j]); +00091 +00092 if (allocated < used) +00093 used = allocated; +00094 +00095 allocator.deallocate(old_data); //delete [] old_data; +00096 } +00097 +00098 +00100 +00103 void setAllocStrategy ( eAllocStrategy newStrategy = ALLOC_STRATEGY_DOUBLE ) +00104 { +00105 strategy = newStrategy; +00106 } +00107 +00108 +00110 +00112 void push_back(const T& element) +00113 { +00114 insert(element, used); +00115 } +00116 +00117 +00119 +00123 void push_front(const T& element) +00124 { +00125 insert(element); +00126 } +00127 +00128 +00130 +00135 void insert(const T& element, u32 index=0) +00136 { +00137 _IRR_DEBUG_BREAK_IF(index>used) // access violation +00138 +00139 if (used + 1 > allocated) +00140 { +00141 // this doesn't work if the element is in the same +00142 // array. So we'll copy the element first to be sure +00143 // we'll get no data corruption +00144 const T e(element); +00145 +00146 // increase data block +00147 u32 newAlloc; +00148 switch ( strategy ) +00149 { +00150 case ALLOC_STRATEGY_DOUBLE: +00151 newAlloc = used + 1 + (allocated < 500 ? +00152 (allocated < 5 ? 5 : used) : used >> 2); +00153 break; +00154 default: +00155 case ALLOC_STRATEGY_SAFE: +00156 newAlloc = used + 1; +00157 break; +00158 } +00159 reallocate( newAlloc); +00160 +00161 // move array content and construct new element +00162 // first move end one up +00163 for (u32 i=used; i>index; --i) +00164 { +00165 if (i<used) +00166 allocator.destruct(&data[i]); +00167 allocator.construct(&data[i], data[i-1]); // data[i] = data[i-1]; +00168 } +00169 // then add new element +00170 if (used > index) +00171 allocator.destruct(&data[index]); +00172 allocator.construct(&data[index], e); // data[index] = e; +00173 } +00174 else +00175 { +00176 // element inserted not at end +00177 if ( used > index ) +00178 { +00179 // create one new element at the end +00180 allocator.construct(&data[used], data[used-1]); +00181 +00182 // move the rest of the array content +00183 for (u32 i=used-1; i>index; --i) +00184 { +00185 data[i] = data[i-1]; +00186 } +00187 // insert the new element +00188 data[index] = element; +00189 } +00190 else +00191 { +00192 // insert the new element to the end +00193 allocator.construct(&data[index], element); +00194 } +00195 } +00196 // set to false as we don't know if we have the comparison operators +00197 is_sorted = false; +00198 ++used; +00199 } +00200 +00201 +00203 void clear() +00204 { +00205 if (free_when_destroyed) +00206 { +00207 for (u32 i=0; i<used; ++i) +00208 allocator.destruct(&data[i]); +00209 +00210 allocator.deallocate(data); // delete [] data; +00211 } +00212 data = 0; +00213 used = 0; +00214 allocated = 0; +00215 is_sorted = true; +00216 } +00217 +00218 +00220 +00228 void set_pointer(T* newPointer, u32 size, bool _is_sorted=false, bool _free_when_destroyed=true) +00229 { +00230 clear(); +00231 data = newPointer; +00232 allocated = size; +00233 used = size; +00234 is_sorted = _is_sorted; +00235 free_when_destroyed=_free_when_destroyed; +00236 } +00237 +00238 +00240 +00247 void set_free_when_destroyed(bool f) +00248 { +00249 free_when_destroyed = f; +00250 } +00251 +00252 +00254 +00257 void set_used(u32 usedNow) +00258 { +00259 if (allocated < usedNow) +00260 reallocate(usedNow); +00261 +00262 used = usedNow; +00263 } +00264 +00265 +00267 const array<T, TAlloc>& operator=(const array<T, TAlloc>& other) +00268 { +00269 if (this == &other) +00270 return *this; +00271 strategy = other.strategy; +00272 +00273 if (data) +00274 clear(); +00275 +00276 //if (allocated < other.allocated) +00277 if (other.allocated == 0) +00278 data = 0; +00279 else +00280 data = allocator.allocate(other.allocated); // new T[other.allocated]; +00281 +00282 used = other.used; +00283 free_when_destroyed = true; +00284 is_sorted = other.is_sorted; +00285 allocated = other.allocated; +00286 +00287 for (u32 i=0; i<other.used; ++i) +00288 allocator.construct(&data[i], other.data[i]); // data[i] = other.data[i]; +00289 +00290 return *this; +00291 } +00292 +00293 +00295 bool operator == (const array<T, TAlloc>& other) const +00296 { +00297 if (used != other.used) +00298 return false; +00299 +00300 for (u32 i=0; i<other.used; ++i) +00301 if (data[i] != other[i]) +00302 return false; +00303 return true; +00304 } +00305 +00306 +00308 bool operator != (const array<T, TAlloc>& other) const +00309 { +00310 return !(*this==other); +00311 } +00312 +00313 +00315 T& operator [](u32 index) +00316 { +00317 _IRR_DEBUG_BREAK_IF(index>=used) // access violation +00318 +00319 return data[index]; +00320 } +00321 +00322 +00324 const T& operator [](u32 index) const +00325 { +00326 _IRR_DEBUG_BREAK_IF(index>=used) // access violation +00327 +00328 return data[index]; +00329 } +00330 +00331 +00333 T& getLast() +00334 { +00335 _IRR_DEBUG_BREAK_IF(!used) // access violation +00336 +00337 return data[used-1]; +00338 } +00339 +00340 +00342 const T& getLast() const +00343 { +00344 _IRR_DEBUG_BREAK_IF(!used) // access violation +00345 +00346 return data[used-1]; +00347 } +00348 +00349 +00351 +00352 T* pointer() +00353 { +00354 return data; +00355 } +00356 +00357 +00359 +00360 const T* const_pointer() const +00361 { +00362 return data; +00363 } +00364 +00365 +00367 +00368 u32 size() const +00369 { +00370 return used; +00371 } +00372 +00373 +00375 +00377 u32 allocated_size() const +00378 { +00379 return allocated; +00380 } +00381 +00382 +00384 +00385 bool empty() const +00386 { +00387 return used == 0; +00388 } +00389 +00390 +00392 +00394 void sort() +00395 { +00396 if (!is_sorted && used>1) +00397 heapsort(data, used); +00398 is_sorted = true; +00399 } +00400 +00401 +00403 +00409 s32 binary_search(const T& element) +00410 { +00411 sort(); +00412 return binary_search(element, 0, used-1); +00413 } +00414 +00415 +00417 +00422 s32 binary_search(const T& element) const +00423 { +00424 if (is_sorted) +00425 return binary_search(element, 0, used-1); +00426 else +00427 return linear_search(element); +00428 } +00429 +00430 +00432 +00437 s32 binary_search(const T& element, s32 left, s32 right) const +00438 { +00439 if (!used) +00440 return -1; +00441 +00442 s32 m; +00443 +00444 do +00445 { +00446 m = (left+right)>>1; +00447 +00448 if (element < data[m]) +00449 right = m - 1; +00450 else +00451 left = m + 1; +00452 +00453 } while((element < data[m] || data[m] < element) && left<=right); +00454 // this last line equals to: +00455 // " while((element != array[m]) && left<=right);" +00456 // but we only want to use the '<' operator. +00457 // the same in next line, it is "(element == array[m])" +00458 +00459 +00460 if (!(element < data[m]) && !(data[m] < element)) +00461 return m; +00462 +00463 return -1; +00464 } +00465 +00466 +00469 +00475 s32 binary_search_multi(const T& element, s32 &last) +00476 { +00477 sort(); +00478 s32 index = binary_search(element, 0, used-1); +00479 if ( index < 0 ) +00480 return index; +00481 +00482 // The search can be somewhere in the middle of the set +00483 // look linear previous and past the index +00484 last = index; +00485 +00486 while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) ) +00487 { +00488 index -= 1; +00489 } +00490 // look linear up +00491 while ( last < (s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) ) +00492 { +00493 last += 1; +00494 } +00495 +00496 return index; +00497 } +00498 +00499 +00501 +00506 s32 linear_search(const T& element) const +00507 { +00508 for (u32 i=0; i<used; ++i) +00509 if (element == data[i]) +00510 return (s32)i; +00511 +00512 return -1; +00513 } +00514 +00515 +00517 +00522 s32 linear_reverse_search(const T& element) const +00523 { +00524 for (s32 i=used-1; i>=0; --i) +00525 if (data[i] == element) +00526 return i; +00527 +00528 return -1; +00529 } +00530 +00531 +00533 +00536 void erase(u32 index) +00537 { +00538 _IRR_DEBUG_BREAK_IF(index>=used) // access violation +00539 +00540 for (u32 i=index+1; i<used; ++i) +00541 { +00542 allocator.destruct(&data[i-1]); +00543 allocator.construct(&data[i-1], data[i]); // data[i-1] = data[i]; +00544 } +00545 +00546 allocator.destruct(&data[used-1]); +00547 +00548 --used; +00549 } +00550 +00551 +00553 +00557 void erase(u32 index, s32 count) +00558 { +00559 if (index>=used || count<1) +00560 return; +00561 if (index+count>used) +00562 count = used-index; +00563 +00564 u32 i; +00565 for (i=index; i<index+count; ++i) +00566 allocator.destruct(&data[i]); +00567 +00568 for (i=index+count; i<used; ++i) +00569 { +00570 if (i-count >= index+count) // not already destructed before loop +00571 allocator.destruct(&data[i-count]); +00572 +00573 allocator.construct(&data[i-count], data[i]); // data[i-count] = data[i]; +00574 +00575 if (i >= used-count) // those which are not overwritten +00576 allocator.destruct(&data[i]); +00577 } +00578 +00579 used-= count; +00580 } +00581 +00582 +00584 void set_sorted(bool _is_sorted) +00585 { +00586 is_sorted = _is_sorted; +00587 } +00588 +00589 +00591 +00594 void swap(array<T, TAlloc>& other) +00595 { +00596 core::swap(data, other.data); +00597 core::swap(allocated, other.allocated); +00598 core::swap(used, other.used); +00599 core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation +00600 eAllocStrategy helper_strategy(strategy); // can't use core::swap with bitfields +00601 strategy = other.strategy; +00602 other.strategy = helper_strategy; +00603 bool helper_free_when_destroyed(free_when_destroyed); +00604 free_when_destroyed = other.free_when_destroyed; +00605 other.free_when_destroyed = helper_free_when_destroyed; +00606 bool helper_is_sorted(is_sorted); +00607 is_sorted = other.is_sorted; +00608 other.is_sorted = helper_is_sorted; +00609 } +00610 +00611 +00612 private: +00613 T* data; +00614 u32 allocated; +00615 u32 used; +00616 TAlloc allocator; +00617 eAllocStrategy strategy:4; +00618 bool free_when_destroyed:1; +00619 bool is_sorted:1; +00620 }; +00621 +00622 +00623 } // end namespace core +00624 } // end namespace irr +00625 +00626 #endif +00627 +