Home | Namespaces | Hierarchy | Alphabetical List | Class list | Files | Namespace Members | Class members | File members | Tutorials

# irrArray.h

Go to the documentation of this file.

    00001 // Copyright (C) 2002-2009 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
    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); //new T[new_size];
    00074                 allocated = new_size;
    00075
    00076                 // copy old data
    00077                 s32 end = used < new_size ? used : new_size;
    00078
    00079                 for (s32 i=0; i<end; ++i)
    00080                 {
    00081                         // data[i] = old_data[i];
    00082                         allocator.construct(&data[i], old_data[i]);
    00083                 }
    00084
    00085                 // destruct old data
    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); //delete [] 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                         // this doesn't work if the element is in the same array. So
    00113                         // we'll copy the element first to be sure we'll get no data
    00114                         // corruption
    00115
    00116                         T e(element);
    00117                         //reallocate(used * 2 +1); // increase data block
    00118                         // TA: okt, 2008. it's only allowed to alloc one element, if
    00119                         // default constructor has to be called
    00120
    00121                         // increase data block
    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                         // construct new element
    00136                         // Attention!. in missing default constructors for faster alloc methods
    00137                         allocator.construct(&data[used++], e); // data[used++] = e; // push_back
    00138                 }
    00139                 else
    00140                 {
    00141                         //data[used++] = element;
    00142                         // instead of using this here, we copy it the safe way:
    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) // access violation
    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]); // data[i] = data[i-1];
    00179                 }
    00180
    00181                 if (used > index)
    00182                         allocator.destruct(&data[index]);
    00183                 allocator.construct(&data[index], element); // 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); // delete [] 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); // delete [] 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); // delete [] data;
    00252                 }
    00253
    00254                 //if (allocated < other.allocated)
    00255                 if (other.allocated == 0)
    00256                         data = 0;
    00257                 else
    00258                         data = allocator.allocate(other.allocated); // new T[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]); // 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) // access violation
    00293
    00294                 return data[index];
    00295         }
    00296
    00297
    00299         const T& operator [](u32 index) const
    00300         {
    00301                 _IRR_DEBUG_BREAK_IF(index>=used) // access violation
    00302
    00303                 return data[index];
    00304         }
    00305
    00306
    00308         T& getLast()
    00309         {
    00310                 _IRR_DEBUG_BREAK_IF(!used) // access violation
    00311
    00312                 return data[used-1];
    00313         }
    00314
    00315
    00317         const T& getLast() const
    00318         {
    00319                 _IRR_DEBUG_BREAK_IF(!used) // access violation
    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                 // this last line equals to:
    00432                 // " while((element != array[m]) && left<=right);"
    00433                 // but we only want to use the '<' operator.
    00434                 // the same in next line, it is "(element == array[m])"
    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                 // The search can be somewhere in the middle of the set
    00460                 // look linear previous and past the index
    00461                 last = index;
    00462
    00463                 while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) )
    00464                 {
    00465                         index -= 1;
    00466                 }
    00467                 // look linear up
    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) // access violation
    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]); // 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) // access violation
    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]); // 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 } // end namespace core
    00575 } // end namespace irr
    00576
    00577
    00578 #endif
    00579

| The Irrlicht Engine Documentation © 2003-2009 by Nikolaus Gebhardt. Generated on Sun Jan 10 09:24:04 2010 by Doxygen (1.5.6)