Main Page Modules Namespace List Class Hierarchy Alphabetical List Compound List File List Namespace Members Compound Members File Members Related Pages

# deArray.hpp

Go to the documentation of this file.

    00001 ///////////////////////////////////////////////////////////////////////////////
    00002 /// @file deArray.hpp
    00003 ///
    00004 /// @brief templated array class
    00005 ///
    00006 /// @author Assassin
    00007 ///
    00008 /// This file is the intellectual property of Novus Delta, LLC.. Usage of the
    00009 /// contents of this file is subject to the Destiny3D Member License which
    00010 /// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
    00011 ///
    00012 /// This file is distributed "AS IS" without warranty of any kind.  Novus
    00013 /// Delta, LLC. does not guarantee the fitness of the contents of this file
    00014 /// for any particular purpose.
    00015 ///
    00016 /// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
    00017 ///
    00018 /// <hr>
    00019 ///                                 Change History
    00020 /// <hr>
    00021 ///
    00022 /// @date Sept 2001
    00023 /// @author Assassin
    00024 /// @remarks Creation
    00025 ///
    00026 /// @date Jan 2002
    00027 /// @author Assassin
    00028 /// @remarks Bug fixes
    00029 ///
    00030 ///////////////////////////////////////////////////////////////////////////////
    00031
    00032 #ifndef DEARRAY_HPP
    00033 #define DEARRAY_HPP
    00034
    00035 #include "deGlobalTypes.hpp"
    00036
    00037 #ifndef NULL
    00038 #define NULL (0)
    00039 #endif
    00040 #pragma warning (disable : 4284) // return type for 'identifier::operator –>' is not a UDT or reference to a UDT. Will produce errors if applied using infix notation
    00041 #pragma warning (disable : 4710) // function not inlined
    00042
    00043 template <typename T>
    00044 class deTWrapper
    00045 {
    00046 private:
    00047     T m_data;
    00048 public:
    00049     deTWrapper() : m_data() {}
    00050     deTWrapper(const T & ref) : m_data(ref) {}
    00051     virtual ~deTWrapper() {}
    00052     deTWrapper<T>& operator=(const T& ref) { m_data = ref; return *this; }
    00053     deTWrapper<T>& operator=(const deTWrapper<T>& ref) { m_data = ref.m_data; return *this; }
    00054     operator T& () { return m_data; }
    00055     T* operator&() { return &m_data; }
    00056 };
    00057
    00058 /// templated resizable linear array storage class
    00059 template <class T>
    00060 class deTArray
    00061 {
    00062 private:
    00063     size_t  m_Length;
    00064     size_t  m_Capacity;
    00065     T*      m_Items;
    00066 public:
    00067     static u32 SmallestLargerPow2(u32 x)
    00068     {
    00069         int retval = 1;
    00070         if (x & 0xffff0000)
    00071         { retval += 16; x >>= 16; }
    00072         if (x & 0x0000ff00)
    00073         { retval += 8; x >>= 8; }
    00074         if (x & 0x000000f0)
    00075         { retval += 4; x >>= 4; }
    00076         if (x & 0x0000000c)
    00077         { retval += 2; x >>= 2; }
    00078         if (x & 0x00000002)
    00079         { retval += 1; x >>= 1; }
    00080         return (1 << retval);
    00081     }
    00082 #ifdef _DEBUG
    00083     class iterator
    00084     {
    00085     private:
    00086         const deTArray<T>* m_Holder;
    00087         T* m_Ref;
    00088     protected:
    00089         friend class deTArray<T>;
    00090         iterator(T* ref, const deTArray<T>* holder) : m_Ref(ref), m_Holder(holder) {}
    00091     public:
    00092         iterator() : m_Ref(0), m_Holder(0) {}
    00093         ~iterator() {}
    00094         T& operator*() const
    00095         {
    00096             DE_ASSERT (m_Ref >= m_Holder->begin().m_Ref && m_Ref < m_Holder->end().m_Ref);
    00097             return *m_Ref;
    00098         }
    00099         T* operator->() const
    00100         { return &operator*(); }
    00101         void operator++() { ++m_Ref; }
    00102         void operator--() { --m_Ref; }
    00103         bool operator==(const iterator & other) const
    00104         { return m_Ref == other.m_Ref; }
    00105         bool operator!=(const iterator & other) const
    00106         { return m_Ref != other.m_Ref; }
    00107     };
    00108 private:
    00109     inline iterator make_iterator(size_t index) const
    00110     {
    00111         return iterator(&m_Items[index], this);
    00112     }
    00113     inline size_t iterator_index(const iterator& it)
    00114     {
    00115         return it.m_Ref - m_Items;
    00116     }
    00117 public:
    00118 #else
    00119     typedef T* iterator;
    00120 private:
    00121     inline iterator make_iterator(size_t index) const
    00122     {
    00123         return &m_Items[index];
    00124     }
    00125     inline size_t iterator_index(const iterator& it)
    00126     {
    00127         return it - m_Items;
    00128     }
    00129 public:
    00130 #endif
    00131
    00132     deTArray(void)
    00133     :m_Length(0), m_Capacity(0), m_Items(NULL)  {}
    00134     deTArray(const deTArray & RHS)
    00135     :m_Length(RHS.m_Length),m_Capacity(RHS.m_Capacity)
    00136     {
    00137         if (m_Capacity > 0)
    00138         {
    00139             size_t i;
    00140             m_Items = new T[m_Capacity];
    00141             for (i = 0; i < m_Length; i++)
    00142                 m_Items[i] = RHS.m_Items[i];
    00143         }
    00144         else
    00145             m_Items = NULL;
    00146     }
    00147     deTArray(size_t InitialSize)
    00148     :m_Length(InitialSize),m_Capacity(InitialSize)
    00149     {
    00150         if (m_Capacity > 0)
    00151             m_Items = new T[m_Capacity];
    00152         else
    00153             m_Items = NULL;
    00154     }
    00155     deTArray(size_t InitialSize,const T & Value)
    00156     :m_Length(InitialSize),m_Capacity(InitialSize)
    00157     {
    00158         if (m_Capacity > 0)
    00159         {
    00160             u32 i;
    00161             m_Items = new T[m_Capacity];
    00162             for (i = 0; i < m_Length; i++)
    00163                 m_Items[i] = Value;
    00164         }
    00165         else
    00166             m_Items = NULL;
    00167     }
    00168     ~deTArray()
    00169     {
    00170         if (m_Items != NULL)
    00171         {
    00172             delete [] m_Items;
    00173             m_Items = NULL;
    00174         }
    00175     }
    00176
    00177     deTArray <T> & operator=(const deTArray <T> & ref)
    00178     {
    00179         Resize(0);
    00180         Resize(ref.m_Length);
    00181         for (u32 i = 0; i < m_Length; ++i)
    00182             m_Items[i] = ref.m_Items[i];
    00183
    00184         return *this;
    00185     }
    00186
    00187     inline T& operator[](size_t ArrayItemIndex)         // L-value
    00188     {
    00189         #ifdef _DEBUG
    00190         if (ArrayItemIndex < 0 || ArrayItemIndex >= m_Length)
    00191         {
    00192             // you've tried to access an invalid array element
    00193             BREAK_EXECUTION();
    00194         }
    00195         #endif
    00196         return m_Items[ArrayItemIndex];
    00197     }
    00198     inline const T& operator[](size_t ArrayItemIndex) const // R-value
    00199     {
    00200         #ifdef _DEBUG
    00201         if (ArrayItemIndex < 0 || ArrayItemIndex >= m_Length)
    00202         {
    00203             // you've tried to access an invalid array element
    00204             BREAK_EXECUTION();
    00205         }
    00206         #endif
    00207         return m_Items[ArrayItemIndex];
    00208     }
    00209     inline iterator get_iterator(size_t ArrayItemIndex) const
    00210     {
    00211         return make_iterator(ArrayItemIndex);
    00212     }
    00213
    00214     inline deBoolean PushBack(const T& element)
    00215     {
    00216         int i = m_Length;
    00217         if (m_Length >= m_Capacity)
    00218         {
    00219             // this will increment m_Length internally
    00220             if (!Resize(m_Length+1))
    00221                 return deFALSE;
    00222         }
    00223         else
    00224         {
    00225             ++m_Length;
    00226         }
    00227         m_Items[i] = element;
    00228         return deTRUE;
    00229     }
    00230
    00231     inline deBoolean InsertArrayQuick(const T* Array, size_t StartIndex, size_t NumElements)
    00232     {
    00233         if (StartIndex + NumElements > m_Length)
    00234             return deFALSE;
    00235         if (Array == NULL)
    00236             return deFALSE;
    00237         memcpy(&(m_Items[StartIndex]), Array, NumElements*sizeof(T));
    00238         return deTRUE;
    00239     }
    00240
    00241     inline iterator IncrementSize()
    00242     {
    00243         if (Resize(m_Length+1))
    00244             return make_iterator(m_Length-1);
    00245         return end();
    00246     }
    00247
    00248     inline iterator IncrementSizeQuick(deBoolean ZeroMem = deFALSE)
    00249     {
    00250         if (ResizeQuick(m_Length+1, ZeroMem))
    00251             return make_iterator(m_Length-1);
    00252         return end();
    00253     }
    00254
    00255     deBoolean Reserve(size_t NewSize, deBoolean PrimitiveType = deFALSE)
    00256     {
    00257         size_t NewCapacity;
    00258         NewCapacity = SmallestLargerPow2(NewSize);
    00259
    00260         // if smaller but not by much, keep current capacity
    00261         if (NewCapacity <= m_Capacity && NewCapacity >= m_Capacity/2)
    00262             return deTRUE;
    00263
    00264         T *NewItems;
    00265         NewItems = new T[NewCapacity];
    00266
    00267         if (NewItems == NULL)
    00268             return deFALSE;
    00269
    00270         if (m_Items)
    00271         {
    00272             if (PrimitiveType)
    00273             {
    00274                 int i = min(m_Length, NewSize);
    00275                 memcpy(NewItems, m_Items, i * sizeof(T));
    00276             }
    00277             else
    00278             {
    00279                 int k = min(m_Length, NewSize);
    00280                 for (int i=0; i < k; i++)
    00281                 {
    00282                     NewItems[i] = m_Items[i];
    00283                 }
    00284             }
    00285             delete[] m_Items;
    00286         }
    00287         m_Capacity = NewCapacity;
    00288         m_Items = NewItems;
    00289         return deTRUE;
    00290     }
    00291
    00292     deBoolean Resize(size_t NewSize)
    00293     {
    00294         if (NewSize < 0)
    00295             return deFALSE;
    00296
    00297         if (NewSize == m_Length)
    00298             return deTRUE;
    00299
    00300         if (NewSize == 0)
    00301         {
    00302             m_Length = m_Capacity = 0;
    00303             delete[] m_Items;
    00304             m_Items = NULL;
    00305             return deTRUE;
    00306         }
    00307
    00308         if (m_Capacity < NewSize)
    00309         {
    00310             if (!Reserve(NewSize))
    00311                 return deFALSE;
    00312         }
    00313         m_Length = NewSize;
    00314         return deTRUE;
    00315     }
    00316
    00317     // WARNING!!!
    00318     // Only use this method on primitive types in the array
    00319     // such as int, char, etc. If you use this on a class that
    00320     // maintains special information, it will most likely break.
    00321     // Use Resize in those cases, as it deals with classes properly.
    00322     // WARNING!!
    00323     deBoolean ResizeQuick(size_t NewSize, deBoolean ZeroMem = deFALSE)
    00324     {
    00325         if (NewSize < 0)
    00326             return deFALSE;
    00327
    00328         if (NewSize == m_Length)
    00329             return deTRUE;
    00330
    00331         if (NewSize == 0)
    00332         {
    00333             m_Length = m_Capacity = 0;
    00334             delete[] m_Items;
    00335             m_Items = NULL;
    00336             return deTRUE;
    00337         }
    00338
    00339         if (m_Capacity < NewSize)
    00340         {
    00341             if (!Reserve(NewSize, deTRUE))
    00342                 return deFALSE;
    00343         }
    00344         if (ZeroMem && NewSize > m_Length)
    00345         {
    00346             memset(m_Items + m_Length, 0, (NewSize - m_Length)*sizeof(T));
    00347         }
    00348         m_Length = NewSize;
    00349         return deTRUE;
    00350     }
    00351
    00352     deBoolean RemoveElementAt(size_t index)
    00353     {
    00354         if (index < 0 || index >= m_Length)
    00355         {
    00356             DEBUGRETURN(deFALSE, "RemoveElementAt: Invalid array index");
    00357         }
    00358
    00359         int i;
    00360         int NewSize = m_Length - 1;
    00361
    00362         if (NewSize == 0)
    00363         {
    00364             m_Length = 0;
    00365             return deTRUE;
    00366         }
    00367
    00368         for (i = index; i < NewSize; i++)
    00369         {
    00370             m_Items[i] = m_Items[i+1];
    00371         }
    00372         m_Length = NewSize;
    00373         return deTRUE;
    00374     }
    00375
    00376     inline T* GetCArray() const { return m_Items; }
    00377
    00378     inline size_t Length() const    { return m_Length; }
    00379
    00380 public:
    00381     // STL compliance
    00382     inline size_t size() const  { return m_Length; }
    00383     inline size_t capacity()const   { return m_Capacity; }
    00384     inline iterator begin() const { return make_iterator(0); }
    00385     inline iterator end() const { return make_iterator(m_Length); }
    00386     inline deBoolean resize(size_t NewSize) { return Resize(NewSize); }
    00387     inline iterator push_back(const T& element) { PushBack(element); return get_iterator(m_Length-1); }
    00388     inline iterator erase(iterator& it) { int index = iterator_index(it); RemoveElementAt(index); return make_iterator(index); }
    00389 };
    00390
    00391 #endif