doc/html/irr_array_8h_source.html

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
-