lldarray.h

Go to the documentation of this file.
00001 
00032 #ifndef LL_LLDARRAY_H
00033 #define LL_LLDARRAY_H
00034 
00035 #include "llmath.h"
00036 #include "llerror.h"
00037 
00038 #include <vector>
00039 #include <map>
00040 
00041 // class LLDynamicArray<>; // = std::vector + reserves <BlockSize> elements
00042 // class LLDynamicArrayIndexed<>; // = std::vector + std::map if indices, only supports operator[] and begin(),end()
00043 
00044 //--------------------------------------------------------
00045 // LLDynamicArray declaration
00046 //--------------------------------------------------------
00047 // NOTE: BlockSize is used to reserve a minimal initial amount
00048 template <typename Type, int BlockSize = 32> 
00049 class LLDynamicArray : public std::vector<Type>
00050 {
00051 public:
00052         enum
00053         {
00054                 OKAY = 0,
00055                 FAIL = -1
00056         };
00057         
00058         LLDynamicArray(S32 size=0) : std::vector<Type>(size) { if (size < BlockSize) std::vector<Type>::reserve(BlockSize); }
00059 
00060         void reset() { std::vector<Type>::resize(0); }
00061 
00062         // ACCESSORS
00063         const Type& get(S32 index) const                                { return std::vector<Type>::operator[](index); }
00064         Type&       get(S32 index)                                              { return std::vector<Type>::operator[](index); }
00065         S32                     find(const Type &obj) const;
00066 
00067         S32                     count() const                                           { return std::vector<Type>::size(); }
00068         S32                     getLength() const                                       { return std::vector<Type>::size(); }
00069         S32                     getMax() const                                          { return std::vector<Type>::capacity(); }
00070 
00071         // MANIPULATE
00072         S32         put(const Type &obj);                                       // add to end of array, returns index
00073 //      Type*           reserve(S32 num);                                       // reserve a block of indices in advance
00074         Type*           reserve_block(U32 num);                 // reserve a block of indices in advance
00075 
00076         S32                     remove(S32 index);                              // remove by index, no bounds checking
00077         S32                     removeObj(const Type &obj);                             // remove by object
00078         S32                     removeLast();
00079 
00080         void            operator+=(const LLDynamicArray<Type,BlockSize> &other);
00081 };
00082 
00083 //--------------------------------------------------------
00084 // LLDynamicArray implementation
00085 //--------------------------------------------------------
00086 
00087 template <typename Type,int BlockSize>
00088 inline S32 LLDynamicArray<Type,BlockSize>::find(const Type &obj) const
00089 {
00090         typename std::vector<Type>::const_iterator iter = std::find(this->begin(), this->end(), obj);
00091         if (iter != this->end())
00092         {
00093                 return iter - this->begin();
00094         }
00095         return FAIL;
00096 }
00097 
00098 
00099 template <typename Type,int BlockSize>
00100 inline S32 LLDynamicArray<Type,BlockSize>::remove(S32 i)
00101 {
00102         // This is a fast removal by swapping with the last element
00103         S32 sz = this->size();
00104         if (i < 0 || i >= sz)
00105         {
00106                 return FAIL;
00107         }
00108         if (i < sz-1)
00109         {
00110                 this->operator[](i) = this->back();
00111         }
00112         this->pop_back();
00113         return i;
00114 }
00115 
00116 template <typename Type,int BlockSize>
00117 inline S32 LLDynamicArray<Type,BlockSize>::removeObj(const Type& obj)
00118 {
00119         typename std::vector<Type>::iterator iter = std::find(this->begin(), this->end(), obj);
00120         if (iter != this->end())
00121         {
00122                 typename std::vector<Type>::iterator last = this->end(); 
00123                 --last;
00124                 *iter = *last;
00125                 this->pop_back();
00126                 return iter - this->begin();
00127         }
00128         return FAIL;
00129 }
00130 
00131 template <typename Type,int BlockSize>
00132 inline S32      LLDynamicArray<Type,BlockSize>::removeLast()
00133 {
00134         if (!this->empty())
00135         {
00136                 this->pop_back();
00137                 return OKAY;
00138         }
00139         return FAIL;
00140 }
00141 
00142 template <typename Type,int BlockSize>
00143 inline Type* LLDynamicArray<Type,BlockSize>::reserve_block(U32 num)
00144 {
00145         U32 sz = this->size();
00146         this->resize(sz+num);
00147         return &(this->operator[](sz));
00148 }
00149 
00150 template <typename Type,int BlockSize>
00151 inline S32      LLDynamicArray<Type,BlockSize>::put(const Type &obj) 
00152 {
00153         this->push_back(obj);
00154         return this->size() - 1;
00155 }
00156 
00157 template <typename Type,int BlockSize>
00158 inline void LLDynamicArray<Type,BlockSize>::operator+=(const LLDynamicArray<Type,BlockSize> &other)
00159 {
00160         insert(this->end(), other.begin(), other.end());
00161 }
00162 
00163 //--------------------------------------------------------
00164 // LLDynamicArrayIndexed declaration
00165 //--------------------------------------------------------
00166 
00167 template <typename Type, typename Key, int BlockSize = 32> 
00168 class LLDynamicArrayIndexed
00169 {
00170 public:
00171         typedef typename std::vector<Type>::iterator iterator;
00172         typedef typename std::vector<Type>::const_iterator const_iterator;
00173         typedef typename std::vector<Type>::reverse_iterator reverse_iterator;
00174         typedef typename std::vector<Type>::const_reverse_iterator const_reverse_iterator;
00175         typedef typename std::vector<Type>::size_type size_type;
00176 protected:
00177         std::vector<Type> mVector;
00178         std::map<Key, U32> mIndexMap;
00179         
00180 public:
00181         LLDynamicArrayIndexed() { mVector.reserve(BlockSize); }
00182         
00183         iterator begin() { return mVector.begin(); }
00184         const_iterator begin() const { return mVector.begin(); }
00185         iterator end() { return mVector.end(); }
00186         const_iterator end() const { return mVector.end(); }
00187 
00188         reverse_iterator rbegin() { return mVector.rbegin(); }
00189         const_reverse_iterator rbegin() const { return mVector.rbegin(); }
00190         reverse_iterator rend() { return mVector.rend(); }
00191         const_reverse_iterator rend() const { return mVector.rend(); }
00192 
00193         void reset() { mVector.resize(0); mIndexMap.resize(0); }
00194         bool empty() const { return mVector.empty(); }
00195         size_type size() const { return mVector.size(); }
00196         
00197         Type& operator[](const Key& k)
00198         {
00199                 typename std::map<Key, U32>::const_iterator iter = mIndexMap.find(k);
00200                 if (iter == mIndexMap.end())
00201                 {
00202                         U32 n = mVector.size();
00203                         mIndexMap[k] = n;
00204                         mVector.resize(n+1);
00205                         llassert(mVector.size() == mIndexMap.size());
00206                         return mVector[n];
00207                 }
00208                 else
00209                 {
00210                         return mVector[iter->second];
00211                 }
00212         }
00213 
00214         const_iterator find(const Key& k) const
00215         {
00216                 typename std::map<Key, U32>::const_iterator iter = mIndexMap.find(k);
00217                 if(iter == mIndexMap.end())
00218                 {
00219                         return mVector.end();
00220                 }
00221                 else
00222                 {
00223                         return mVector.begin() + iter->second;
00224                 }
00225         }
00226 };
00227 
00228 #endif

Generated on Thu Jul 1 06:08:23 2010 for Second Life Viewer by  doxygen 1.4.7