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 namespace shogun
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 int32_t find_element(T element)
00178 {
00179 int32_t idx=-1;
00180 int32_t num=get_num_elements();
00181
00182 for (int32_t i=0; i<num; i++)
00183 {
00184 if (array[i] == element)
00185 {
00186 idx=i;
00187 break;
00188 }
00189 }
00190
00191 return idx;
00192 }
00193
00200 inline bool delete_element(int32_t idx)
00201 {
00202 if (idx>=0 && idx<=last_element_idx)
00203 {
00204 for (int32_t i=idx; i<last_element_idx; i++)
00205 array[i]=array[i+1];
00206
00207 array[last_element_idx]=0;
00208 last_element_idx--;
00209
00210 if ( num_elements - last_element_idx >= resize_granularity)
00211 resize_array(last_element_idx);
00212
00213 return true;
00214 }
00215
00216 return false;
00217 }
00218
00224 bool resize_array(int32_t n)
00225 {
00226 int32_t new_num_elements= ((n/resize_granularity)+1)*resize_granularity;
00227
00228 T* p= (T*) realloc(array, sizeof(T)*new_num_elements);
00229 if (p)
00230 {
00231 array=p;
00232 if (new_num_elements > num_elements)
00233 memset(&array[num_elements], 0, (new_num_elements-num_elements)*sizeof(T));
00234 else if (n+1<new_num_elements)
00235 memset(&array[n+1], 0, (new_num_elements-n-1)*sizeof(T));
00236
00237
00238 if (n-1<last_element_idx)
00239 last_element_idx=n-1;
00240
00241 num_elements=new_num_elements;
00242 return true;
00243 }
00244 else
00245 return false;
00246 }
00247
00255 inline T* get_array()
00256 {
00257 return array;
00258 }
00259
00266 inline void set_array(T* p_array, int32_t p_num_elements, int32_t array_size)
00267 {
00268 free(this->array);
00269 this->array=p_array;
00270 this->num_elements=array_size;
00271 this->last_element_idx=p_num_elements-1;
00272 }
00273
00275 inline void clear_array()
00276 {
00277 if (last_element_idx >= 0)
00278 memset(array, 0, (last_element_idx+1)*sizeof(T));
00279 }
00280
00290 inline T operator[](int32_t index) const
00291 {
00292 return array[index];
00293 }
00294
00300 CDynamicArray<T>& operator=(CDynamicArray<T>& orig)
00301 {
00302 resize_granularity=orig.resize_granularity;
00303 memcpy(array, orig.array, sizeof(T)*orig.num_elements);
00304 num_elements=orig.num_elements;
00305 last_element_idx=orig.last_element_idx;
00306
00307 return *this;
00308 }
00309
00311 inline virtual const char* get_name() const { return "DynamicArray"; }
00312
00313 protected:
00315 int32_t resize_granularity;
00316
00318 T* array;
00319
00321 int32_t num_elements;
00322
00324 int32_t last_element_idx;
00325 };
00326 }
00327 #endif