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-2010 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 
00063         void reallocate(u32 new_size)
00064         {
00065                 T* old_data = data;
00066 
00067                 data = allocator.allocate(new_size); //new T[new_size];
00068                 allocated = new_size;
00069 
00070                 // copy old data
00071                 s32 end = used < new_size ? used : new_size;
00072 
00073                 for (s32 i=0; i<end; ++i)
00074                 {
00075                         // data[i] = old_data[i];
00076                         allocator.construct(&data[i], old_data[i]);
00077                 }
00078 
00079                 // destruct old data
00080                 for (u32 j=0; j<used; ++j)
00081                         allocator.destruct(&old_data[j]);
00082 
00083                 if (allocated < used)
00084                         used = allocated;
00085 
00086                 allocator.deallocate(old_data); //delete [] old_data;
00087         }
00088 
00089 
00091 
00094         void setAllocStrategy ( eAllocStrategy newStrategy = ALLOC_STRATEGY_DOUBLE )
00095         {
00096                 strategy = newStrategy;
00097         }
00098 
00099 
00101 
00103         void push_back(const T& element)
00104         {
00105                 insert(element, used);
00106         }
00107 
00108 
00110 
00114         void push_front(const T& element)
00115         {
00116                 insert(element);
00117         }
00118 
00119 
00121 
00126         void insert(const T& element, u32 index=0)
00127         {
00128                 _IRR_DEBUG_BREAK_IF(index>used) // access violation
00129 
00130                 if (used + 1 > allocated)
00131                 {
00132                         // this doesn't work if the element is in the same
00133                         // array. So we'll copy the element first to be sure
00134                         // we'll get no data corruption
00135                         const T e(element);
00136 
00137                         // increase data block
00138                         u32 newAlloc;
00139                         switch ( strategy )
00140                         {
00141                                 case ALLOC_STRATEGY_DOUBLE:
00142                                         newAlloc = used + 1 + (allocated < 500 ?
00143                                                         (allocated < 5 ? 5 : used) : used >> 2);
00144                                         break;
00145                                 default:
00146                                 case ALLOC_STRATEGY_SAFE:
00147                                         newAlloc = used + 1;
00148                                         break;
00149                         }
00150                         reallocate( newAlloc);
00151 
00152                         // move array content and construct new element
00153                         // first move end one up
00154                         for (u32 i=used; i>index; --i)
00155                         {
00156                                 if (i<used)
00157                                         allocator.destruct(&data[i]);
00158                                 allocator.construct(&data[i], data[i-1]); // data[i] = data[i-1];
00159                         }
00160                         // then add new element
00161                         if (used > index)
00162                                 allocator.destruct(&data[index]);
00163                         allocator.construct(&data[index], e); // data[index] = e;
00164                 }
00165                 else
00166                 {
00167                         // element inserted not at end
00168                         if ( used > index )
00169                         {
00170                                 // create one new element at the end
00171                                 allocator.construct(&data[used], data[used-1]);
00172 
00173                                 // move the rest of the array content
00174                                 for (u32 i=used-1; i>index; --i)
00175                                 {
00176                                         data[i] = data[i-1];
00177                                 }
00178                                 // insert the new element
00179                                 data[index] = element;
00180                         }
00181                         else
00182                         {
00183                                 // insert the new element to the end
00184                                 allocator.construct(&data[index], element);
00185                         }
00186                 }
00187                 // set to false as we don't know if we have the comparison operators
00188                 is_sorted = false;
00189                 ++used;
00190         }
00191 
00192 
00194         void clear()
00195         {
00196                 if (free_when_destroyed)
00197                 {
00198                         for (u32 i=0; i<used; ++i)
00199                                 allocator.destruct(&data[i]);
00200 
00201                         allocator.deallocate(data); // delete [] data;
00202                 }
00203                 data = 0;
00204                 used = 0;
00205                 allocated = 0;
00206                 is_sorted = true;
00207         }
00208 
00209 
00211 
00219         void set_pointer(T* newPointer, u32 size, bool _is_sorted=false, bool _free_when_destroyed=true)
00220         {
00221                 clear();
00222                 data = newPointer;
00223                 allocated = size;
00224                 used = size;
00225                 is_sorted = _is_sorted;
00226                 free_when_destroyed=_free_when_destroyed;
00227         }
00228 
00229 
00231 
00238         void set_free_when_destroyed(bool f)
00239         {
00240                 free_when_destroyed = f;
00241         }
00242 
00243 
00245 
00248         void set_used(u32 usedNow)
00249         {
00250                 if (allocated < usedNow)
00251                         reallocate(usedNow);
00252 
00253                 used = usedNow;
00254         }
00255 
00256 
00258         const array<T, TAlloc>& operator=(const array<T, TAlloc>& other)
00259         {
00260                 if (this == &other)
00261                         return *this;
00262                 strategy = other.strategy;
00263 
00264                 if (data)
00265                         clear();
00266 
00267                 //if (allocated < other.allocated)
00268                 if (other.allocated == 0)
00269                         data = 0;
00270                 else
00271                         data = allocator.allocate(other.allocated); // new T[other.allocated];
00272 
00273                 used = other.used;
00274                 free_when_destroyed = true;
00275                 is_sorted = other.is_sorted;
00276                 allocated = other.allocated;
00277 
00278                 for (u32 i=0; i<other.used; ++i)
00279                         allocator.construct(&data[i], other.data[i]); // data[i] = other.data[i];
00280 
00281                 return *this;
00282         }
00283 
00284 
00286         bool operator == (const array<T, TAlloc>& other) const
00287         {
00288                 if (used != other.used)
00289                         return false;
00290 
00291                 for (u32 i=0; i<other.used; ++i)
00292                         if (data[i] != other[i])
00293                                 return false;
00294                 return true;
00295         }
00296 
00297 
00299         bool operator != (const array<T, TAlloc>& other) const
00300         {
00301                 return !(*this==other);
00302         }
00303 
00304 
00306         T& operator [](u32 index)
00307         {
00308                 _IRR_DEBUG_BREAK_IF(index>=used) // access violation
00309 
00310                 return data[index];
00311         }
00312 
00313 
00315         const T& operator [](u32 index) const
00316         {
00317                 _IRR_DEBUG_BREAK_IF(index>=used) // access violation
00318 
00319                 return data[index];
00320         }
00321 
00322 
00324         T& getLast()
00325         {
00326                 _IRR_DEBUG_BREAK_IF(!used) // access violation
00327 
00328                 return data[used-1];
00329         }
00330 
00331 
00333         const T& getLast() const
00334         {
00335                 _IRR_DEBUG_BREAK_IF(!used) // access violation
00336 
00337                 return data[used-1];
00338         }
00339 
00340 
00342 
00343         T* pointer()
00344         {
00345                 return data;
00346         }
00347 
00348 
00350 
00351         const T* const_pointer() const
00352         {
00353                 return data;
00354         }
00355 
00356 
00358 
00359         u32 size() const
00360         {
00361                 return used;
00362         }
00363 
00364 
00366 
00368         u32 allocated_size() const
00369         {
00370                 return allocated;
00371         }
00372 
00373 
00375 
00376         bool empty() const
00377         {
00378                 return used == 0;
00379         }
00380 
00381 
00383 
00385         void sort()
00386         {
00387                 if (!is_sorted && used>1)
00388                         heapsort(data, used);
00389                 is_sorted = true;
00390         }
00391 
00392 
00394 
00400         s32 binary_search(const T& element)
00401         {
00402                 sort();
00403                 return binary_search(element, 0, used-1);
00404         }
00405 
00406 
00408 
00413         s32 binary_search(const T& element) const
00414         {
00415                 if (is_sorted)
00416                         return binary_search(element, 0, used-1);
00417                 else
00418                         return linear_search(element);
00419         }
00420 
00421 
00423 
00428         s32 binary_search(const T& element, s32 left, s32 right) const
00429         {
00430                 if (!used)
00431                         return -1;
00432 
00433                 s32 m;
00434 
00435                 do
00436                 {
00437                         m = (left+right)>>1;
00438 
00439                         if (element < data[m])
00440                                 right = m - 1;
00441                         else
00442                                 left = m + 1;
00443 
00444                 } while((element < data[m] || data[m] < element) && left<=right);
00445                 // this last line equals to:
00446                 // " while((element != array[m]) && left<=right);"
00447                 // but we only want to use the '<' operator.
00448                 // the same in next line, it is "(element == array[m])"
00449 
00450 
00451                 if (!(element < data[m]) && !(data[m] < element))
00452                         return m;
00453 
00454                 return -1;
00455         }
00456 
00457 
00460 
00466         s32 binary_search_multi(const T& element, s32 &last)
00467         {
00468                 sort();
00469                 s32 index = binary_search(element, 0, used-1);
00470                 if ( index < 0 )
00471                         return index;
00472 
00473                 // The search can be somewhere in the middle of the set
00474                 // look linear previous and past the index
00475                 last = index;
00476 
00477                 while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) )
00478                 {
00479                         index -= 1;
00480                 }
00481                 // look linear up
00482                 while ( last < (s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) )
00483                 {
00484                         last += 1;
00485                 }
00486 
00487                 return index;
00488         }
00489 
00490 
00492 
00497         s32 linear_search(const T& element) const
00498         {
00499                 for (u32 i=0; i<used; ++i)
00500                         if (element == data[i])
00501                                 return (s32)i;
00502 
00503                 return -1;
00504         }
00505 
00506 
00508 
00513         s32 linear_reverse_search(const T& element) const
00514         {
00515                 for (s32 i=used-1; i>=0; --i)
00516                         if (data[i] == element)
00517                                 return i;
00518 
00519                 return -1;
00520         }
00521 
00522 
00524 
00527         void erase(u32 index)
00528         {
00529                 _IRR_DEBUG_BREAK_IF(index>=used) // access violation
00530 
00531                 for (u32 i=index+1; i<used; ++i)
00532                 {
00533                         allocator.destruct(&data[i-1]);
00534                         allocator.construct(&data[i-1], data[i]); // data[i-1] = data[i];
00535                 }
00536 
00537                 allocator.destruct(&data[used-1]);
00538 
00539                 --used;
00540         }
00541 
00542 
00544 
00548         void erase(u32 index, s32 count)
00549         {
00550                 if (index>=used || count<1)
00551                         return;
00552                 if (index+count>used)
00553                         count = used-index;
00554 
00555                 u32 i;
00556                 for (i=index; i<index+count; ++i)
00557                         allocator.destruct(&data[i]);
00558 
00559                 for (i=index+count; i<used; ++i)
00560                 {
00561                         if (i > index+count)
00562                                 allocator.destruct(&data[i-count]);
00563 
00564                         allocator.construct(&data[i-count], data[i]); // data[i-count] = data[i];
00565 
00566                         if (i >= used-count)
00567                                 allocator.destruct(&data[i]);
00568                 }
00569 
00570                 used-= count;
00571         }
00572 
00573 
00575         void set_sorted(bool _is_sorted)
00576         {
00577                 is_sorted = _is_sorted;
00578         }
00579 
00580 
00582 
00585         void swap(array<T, TAlloc>& other)
00586         {
00587                 core::swap(data, other.data);
00588                 core::swap(allocated, other.allocated);
00589                 core::swap(used, other.used);
00590                 core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation
00591                 eAllocStrategy helper_strategy(strategy);       // can't use core::swap with bitfields
00592                 strategy = other.strategy;
00593                 other.strategy = helper_strategy;
00594                 bool helper_free_when_destroyed(free_when_destroyed);
00595                 free_when_destroyed = other.free_when_destroyed;
00596                 other.free_when_destroyed = helper_free_when_destroyed;
00597                 bool helper_is_sorted(is_sorted);
00598                 is_sorted = other.is_sorted;
00599                 other.is_sorted = helper_is_sorted;
00600         }
00601 
00602 
00603 private:
00604         T* data;
00605         u32 allocated;
00606         u32 used;
00607         TAlloc allocator;
00608         eAllocStrategy strategy:4;
00609         bool free_when_destroyed:1;
00610         bool is_sorted:1;
00611 };
00612 
00613 
00614 } // end namespace core
00615 } // end namespace irr
00616 
00617 #endif
00618 

The Irrlicht Engine
The Irrlicht Engine Documentation © 2003-2010 by Nikolaus Gebhardt. Generated on Sun Oct 24 12:41:57 2010 by Doxygen (1.6.2)