DynamicArray.h
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #ifndef _DYNARRAY_H_
00012 #define _DYNARRAY_H_
00013
00014 #include "lib/common.h"
00015 #include "lib/Mathematics.h"
00016 #include "base/SGObject.h"
00017
00018 template <class T> class CDynamicArray;
00019
00027 template <class T> class CDynamicArray : public CSGObject
00028 {
00029 public:
00034 CDynamicArray(int32_t p_resize_granularity=128)
00035 : CSGObject()
00036 {
00037 this->resize_granularity=p_resize_granularity;
00038
00039 array=(T*) calloc(p_resize_granularity, sizeof(T));
00040 ASSERT(array);
00041
00042 num_elements=p_resize_granularity;
00043 last_element_idx=-1;
00044 }
00045
00046 virtual ~CDynamicArray() { free(array); }
00047
00053 inline int32_t set_granularity(int32_t g)
00054 {
00055 g=CMath::max(g,128);
00056 this->resize_granularity = g;
00057 return g;
00058 }
00059
00064 inline int32_t get_array_size()
00065 {
00066 return num_elements;
00067 }
00068
00073 inline int32_t get_num_elements() const
00074 {
00075 return last_element_idx+1;
00076 }
00077
00085 inline T get_element(int32_t index) const
00086 {
00087 return array[index];
00088 }
00089
00097 inline T get_element_safe(int32_t index) const
00098 {
00099 if (index>=get_num_elements())
00100 {
00101 SG_ERROR("array index out of bounds (%d >= %d)\n",
00102 index, get_num_elements());
00103 }
00104 return array[index];
00105 }
00106
00113 inline bool set_element(T element, int32_t index)
00114 {
00115 if (index < 0)
00116 {
00117 return false;
00118 }
00119 else if (index <= last_element_idx)
00120 {
00121 array[index]=element;
00122 return true;
00123 }
00124 else if (index < num_elements)
00125 {
00126 array[index]=element;
00127 last_element_idx=index;
00128 return true;
00129 }
00130 else
00131 {
00132 if (resize_array(index))
00133 return set_element(element, index);
00134 else
00135 return false;
00136 }
00137 }
00138
00145 inline bool insert_element(T element, int32_t index)
00146 {
00147 if (append_element(get_element(last_element_idx)))
00148 {
00149 for (int32_t i=last_element_idx-1; i>index; i--)
00150 {
00151 array[i]=array[i-1];
00152 }
00153 array[index]=element;
00154
00155 return true;
00156 }
00157
00158 return false;
00159 }
00160
00166 inline bool append_element(T element)
00167 {
00168 return set_element(element, last_element_idx+1);
00169 }
00170
00177 inline bool delete_element(int32_t idx)
00178 {
00179 if (idx>=0 && idx<=last_element_idx)
00180 {
00181 for (int32_t i=idx; i<last_element_idx; i++)
00182 array[i]=array[i+1];
00183
00184 array[last_element_idx]=0;
00185 last_element_idx--;
00186
00187 if ( num_elements - last_element_idx >= resize_granularity)
00188 resize_array(last_element_idx);
00189
00190 return true;
00191 }
00192
00193 return false;
00194 }
00195
00201 bool resize_array(int32_t n)
00202 {
00203 int32_t new_num_elements= ((n/resize_granularity)+1)*resize_granularity;
00204
00205 T* p= (T*) realloc(array, sizeof(T)*new_num_elements);
00206 if (p)
00207 {
00208 array=p;
00209 if (new_num_elements > num_elements)
00210 memset(&array[num_elements], 0, (new_num_elements-num_elements)*sizeof(T));
00211 else if (n+1<new_num_elements)
00212 memset(&array[n+1], 0, (new_num_elements-n-1)*sizeof(T));
00213
00214
00215 if (n-1<last_element_idx)
00216 last_element_idx=n-1;
00217
00218 num_elements=new_num_elements;
00219 return true;
00220 }
00221 else
00222 return false;
00223 }
00224
00232 inline T* get_array()
00233 {
00234 return array;
00235 }
00236
00243 inline void set_array(T* p_array, int32_t p_num_elements, int32_t array_size)
00244 {
00245 free(this->array);
00246 this->array=p_array;
00247 this->num_elements=array_size;
00248 this->last_element_idx=p_num_elements-1;
00249 }
00250
00252 inline void clear_array()
00253 {
00254 if (last_element_idx >= 0)
00255 memset(array, 0, (last_element_idx+1)*sizeof(T));
00256 }
00257
00267 inline T operator[](int32_t index) const
00268 {
00269 return array[index];
00270 }
00271
00277 CDynamicArray<T>& operator=(CDynamicArray<T>& orig)
00278 {
00279 resize_granularity=orig.resize_granularity;
00280 memcpy(array, orig.array, sizeof(T)*orig.num_elements);
00281 num_elements=orig.num_elements;
00282 last_element_idx=orig.last_element_idx;
00283
00284 return *this;
00285 }
00286
00288 inline virtual const char* get_name() const { return "DynamicArray"; }
00289
00290 protected:
00292 int32_t resize_granularity;
00293
00295 T* array;
00296
00298 int32_t num_elements;
00299
00301 int32_t last_element_idx;
00302 };
00303 #endif