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