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 <shogun/lib/common.h>
00015 #include <shogun/lib/memory.h>
00016 #include <shogun/mathematics/Math.h>
00017
00018 namespace shogun
00019 {
00020 template <class T> class CDynamicArray;
00021 template <class T> class CDynamicObjectArray;
00022
00031 template <class T> class DynArray
00032 {
00033 template<class U> friend class CDynamicArray;
00034 template<class U> friend class CDynamicObjectArray;
00035 friend class CCommUlongStringKernel;
00036
00037 public:
00043 DynArray(int32_t p_resize_granularity=128, bool tracable=true)
00044 {
00045 this->resize_granularity=p_resize_granularity;
00046 use_sg_mallocs=tracable;
00047
00048 if (use_sg_mallocs)
00049 array=SG_CALLOC(T, p_resize_granularity);
00050 else
00051 array=(T*) calloc(p_resize_granularity, sizeof(T));
00052
00053 num_elements=p_resize_granularity;
00054 last_element_idx=-1;
00055 }
00056
00058 virtual ~DynArray()
00059 {
00060 if (use_sg_mallocs)
00061 SG_FREE(array);
00062 else
00063 free(array);
00064 }
00065
00071 inline int32_t set_granularity(int32_t g)
00072 {
00073 g=CMath::max(g,128);
00074 this->resize_granularity = g;
00075 return g;
00076 }
00077
00082 inline int32_t get_array_size() const
00083 {
00084 return num_elements;
00085 }
00086
00091 inline int32_t get_num_elements() const
00092 {
00093 return last_element_idx+1;
00094 }
00095
00103 inline T get_element(int32_t index) const
00104 {
00105 return array[index];
00106 }
00107
00115 inline T* get_element_ptr(int32_t index)
00116 {
00117 return &array[index];
00118 }
00119
00127 inline T get_element_safe(int32_t index) const
00128 {
00129 if (index>=get_num_elements())
00130 {
00131 SG_SERROR("array index out of bounds (%d >= %d)\n",
00132 index, get_num_elements());
00133 }
00134 return array[index];
00135 }
00136
00143 inline bool set_element(T element, int32_t index)
00144 {
00145 if (index < 0)
00146 {
00147 return false;
00148 }
00149 else if (index <= last_element_idx)
00150 {
00151 array[index]=element;
00152 return true;
00153 }
00154 else if (index < num_elements)
00155 {
00156 array[index]=element;
00157 last_element_idx=index;
00158 return true;
00159 }
00160 else
00161 {
00162 if (resize_array(index))
00163 return set_element(element, index);
00164 else
00165 return false;
00166 }
00167 }
00168
00175 inline bool insert_element(T element, int32_t index)
00176 {
00177 if (append_element(get_element(last_element_idx)))
00178 {
00179 for (int32_t i=last_element_idx-1; i>index; i--)
00180 {
00181 array[i]=array[i-1];
00182 }
00183 array[index]=element;
00184
00185 return true;
00186 }
00187
00188 return false;
00189 }
00190
00196 inline bool append_element(T element)
00197 {
00198 return set_element(element, last_element_idx+1);
00199 }
00200
00206 inline void push_back(T element)
00207 {
00208 if (get_num_elements() < 0) set_element(element, 0);
00209 else set_element(element, get_num_elements());
00210 }
00211
00215 inline void pop_back()
00216 {
00217 if (get_num_elements() <= 0) return;
00218 delete_element(get_num_elements()-1);
00219 }
00220
00226 inline T back() const
00227 {
00228 if (get_num_elements() <= 0) return get_element(0);
00229 return get_element(get_num_elements()-1);
00230 }
00231
00238 int32_t find_element(T element) const
00239 {
00240 int32_t idx=-1;
00241 int32_t num=get_num_elements();
00242
00243 for (int32_t i=0; i<num; i++)
00244 {
00245 if (array[i] == element)
00246 {
00247 idx=i;
00248 break;
00249 }
00250 }
00251
00252 return idx;
00253 }
00254
00261 inline bool delete_element(int32_t idx)
00262 {
00263 if (idx>=0 && idx<=last_element_idx)
00264 {
00265 for (int32_t i=idx; i<last_element_idx; i++)
00266 array[i]=array[i+1];
00267
00268 memset(&array[last_element_idx], 0, sizeof(T));
00269 last_element_idx--;
00270
00271 if (num_elements - last_element_idx
00272 > resize_granularity)
00273 resize_array(last_element_idx+1);
00274
00275 return true;
00276 }
00277
00278 return false;
00279 }
00280
00286 bool resize_array(int32_t n)
00287 {
00288 int32_t new_num_elements= ((n/resize_granularity)+1)
00289 *resize_granularity;
00290
00291 T* p;
00292
00293 if (use_sg_mallocs)
00294 p = SG_REALLOC(T, array, new_num_elements);
00295 else
00296 p = (T*) realloc(array, new_num_elements*sizeof(T));
00297 if (p)
00298 {
00299 array=p;
00300 if (new_num_elements > num_elements)
00301 {
00302 memset(&array[num_elements], 0,
00303 (new_num_elements-num_elements)*sizeof(T));
00304 }
00305 else if (n+1<new_num_elements)
00306 {
00307 memset(&array[n+1], 0,
00308 (new_num_elements-n-1)*sizeof(T));
00309 }
00310
00311
00312 if (n-1<last_element_idx)
00313 last_element_idx=n-1;
00314
00315 num_elements=new_num_elements;
00316 return true;
00317 }
00318 else
00319 return false;
00320 }
00321
00329 inline T* get_array() const
00330 {
00331 return array;
00332 }
00333
00340 inline void set_array(T* p_array, int32_t p_num_elements,
00341 int32_t array_size)
00342 {
00343 SG_FREE(this->array);
00344 this->array=p_array;
00345 this->num_elements=array_size;
00346 this->last_element_idx=p_num_elements-1;
00347 }
00348
00350 inline void clear_array()
00351 {
00352 if (last_element_idx >= 0)
00353 memset(array, 0, (last_element_idx+1)*sizeof(T));
00354 }
00355
00357 void shuffle()
00358 {
00359 for (index_t i=0; i<=last_element_idx; ++i)
00360 CMath::swap(array[i], array[CMath::random(i, last_element_idx)]);
00361 }
00362
00372 inline T operator[](int32_t index) const
00373 {
00374 return array[index];
00375 }
00376
00383 DynArray<T>& operator=(DynArray<T>& orig)
00384 {
00385 resize_granularity=orig.resize_granularity;
00386
00387
00388 if (orig.num_elements>num_elements)
00389 {
00390 SG_FREE(array);
00391
00392 if (use_sg_mallocs)
00393 array=SG_MALLOC(T, orig.num_elements);
00394 else
00395 array=(T*) malloc(sizeof(T)*orig.num_elements);
00396 }
00397
00398 memcpy(array, orig.array, sizeof(T)*orig.num_elements);
00399 num_elements=orig.num_elements;
00400 last_element_idx=orig.last_element_idx;
00401
00402 return *this;
00403 }
00404
00406 inline virtual const char* get_name() const { return "DynArray"; }
00407
00408 protected:
00410 int32_t resize_granularity;
00411
00413 T* array;
00414
00416 int32_t num_elements;
00417
00419 int32_t last_element_idx;
00420
00422 bool use_sg_mallocs;
00423 };
00424 }
00425 #endif