00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #ifndef _DYNARRAY_H_
00013 #define _DYNARRAY_H_
00014
00015 #include <shogun/lib/common.h>
00016 #include <shogun/lib/memory.h>
00017 #include <shogun/mathematics/Math.h>
00018
00019 namespace shogun
00020 {
00021 template <class T> class CDynamicArray;
00022
00031 template <class T> class DynArray
00032 {
00033 template<class U> friend class CDynamicArray;
00034 friend class CDynamicObjectArray;
00035 friend class CCommUlongStringKernel;
00036
00037 public:
00043 DynArray(int32_t p_resize_granularity=128, bool tracable=true)
00044 {
00045 resize_granularity=p_resize_granularity;
00046 free_array=true;
00047 use_sg_mallocs=tracable;
00048
00049 if (use_sg_mallocs)
00050 array=SG_CALLOC(T, p_resize_granularity);
00051 else
00052 array=(T*) calloc(p_resize_granularity, sizeof(T));
00053
00054 num_elements=p_resize_granularity;
00055 last_element_idx=-1;
00056 }
00057
00066 DynArray(T* p_array, int32_t p_array_size, bool p_free_array, bool p_copy_array, bool tracable=true)
00067 {
00068 resize_granularity=p_array_size;
00069 free_array=false;
00070 use_sg_mallocs=tracable;
00071
00072 array=NULL;
00073 set_array(p_array, p_array_size, p_array_size, p_free_array, p_copy_array);
00074 }
00075
00082 DynArray(const T* p_array, int32_t p_array_size, bool tracable=true)
00083 {
00084 resize_granularity=p_array_size;
00085 free_array=false;
00086 use_sg_mallocs=tracable;
00087
00088 array=NULL;
00089 set_array(p_array, p_array_size, p_array_size);
00090 }
00091
00093 virtual ~DynArray()
00094 {
00095 if (array!=NULL && free_array)
00096 {
00097 if (use_sg_mallocs)
00098 SG_FREE(array);
00099 else
00100 free(array);
00101 }
00102 }
00103
00109 inline int32_t set_granularity(int32_t g)
00110 {
00111 g=CMath::max(g,128);
00112 this->resize_granularity = g;
00113 return g;
00114 }
00115
00120 inline int32_t get_array_size() const
00121 {
00122 return num_elements;
00123 }
00124
00129 inline int32_t get_num_elements() const
00130 {
00131 return last_element_idx+1;
00132 }
00133
00141 inline T get_element(int32_t index) const
00142 {
00143 return array[index];
00144 }
00145
00150 inline T get_last_element() const
00151 {
00152 return array[last_element_idx];
00153 }
00154
00162 inline T* get_element_ptr(int32_t index)
00163 {
00164 return &array[index];
00165 }
00166
00174 inline T get_element_safe(int32_t index) const
00175 {
00176 if (index>=get_num_elements())
00177 {
00178 SG_SERROR("array index out of bounds (%d >= %d)\n",
00179 index, get_num_elements());
00180 }
00181 return array[index];
00182 }
00183
00190 inline bool set_element(T element, int32_t index)
00191 {
00192 if (index < 0)
00193 {
00194 return false;
00195 }
00196 else if (index <= last_element_idx)
00197 {
00198 array[index]=element;
00199 return true;
00200 }
00201 else if (index < num_elements)
00202 {
00203 array[index]=element;
00204 last_element_idx=index;
00205 return true;
00206 }
00207 else
00208 {
00209 if (free_array && resize_array(index))
00210 return set_element(element, index);
00211 else
00212 return false;
00213 }
00214 }
00215
00222 inline bool insert_element(T element, int32_t index)
00223 {
00224 if (append_element(get_element(last_element_idx)))
00225 {
00226 for (int32_t i=last_element_idx-1; i>index; i--)
00227 {
00228 array[i]=array[i-1];
00229 }
00230 array[index]=element;
00231
00232 return true;
00233 }
00234
00235 return false;
00236 }
00237
00243 inline bool append_element(T element)
00244 {
00245 return set_element(element, last_element_idx+1);
00246 }
00247
00253 inline void push_back(T element)
00254 {
00255 if (get_num_elements() < 0) set_element(element, 0);
00256 else set_element(element, get_num_elements());
00257 }
00258
00262 inline void pop_back()
00263 {
00264 if (get_num_elements() <= 0) return;
00265 delete_element(get_num_elements()-1);
00266 }
00267
00273 inline T back() const
00274 {
00275 if (get_num_elements() <= 0) return get_element(0);
00276 return get_element(get_num_elements()-1);
00277 }
00278
00285 int32_t find_element(T element) const
00286 {
00287 int32_t idx=-1;
00288 int32_t num=get_num_elements();
00289
00290 for (int32_t i=0; i<num; i++)
00291 {
00292 if (array[i] == element)
00293 {
00294 idx=i;
00295 break;
00296 }
00297 }
00298
00299 return idx;
00300 }
00301
00308 inline bool delete_element(int32_t idx)
00309 {
00310 if (idx>=0 && idx<=last_element_idx)
00311 {
00312 for (int32_t i=idx; i<last_element_idx; i++)
00313 array[i]=array[i+1];
00314
00315 memset(&array[last_element_idx], 0, sizeof(T));
00316 last_element_idx--;
00317
00318 if (num_elements - last_element_idx
00319 > resize_granularity)
00320 resize_array(last_element_idx+1);
00321
00322 return true;
00323 }
00324
00325 return false;
00326 }
00327
00333 bool resize_array(int32_t n)
00334 {
00335 int32_t new_num_elements=((n/resize_granularity)+1)
00336 *resize_granularity;
00337
00338 T* p;
00339
00340 if (use_sg_mallocs)
00341 p = SG_REALLOC(T, array, new_num_elements);
00342 else
00343 p = (T*) realloc(array, new_num_elements*sizeof(T));
00344 if (p)
00345 {
00346 array=p;
00347 if (new_num_elements > num_elements)
00348 {
00349 memset(&array[num_elements], 0,
00350 (new_num_elements-num_elements)*sizeof(T));
00351 }
00352 else if (n+1<new_num_elements)
00353 {
00354 memset(&array[n+1], 0,
00355 (new_num_elements-n-1)*sizeof(T));
00356 }
00357
00358
00359 if (n-1<last_element_idx)
00360 last_element_idx=n-1;
00361
00362 num_elements=new_num_elements;
00363 return true;
00364 }
00365 else
00366 return false;
00367 }
00368
00376 inline T* get_array() const
00377 {
00378 return array;
00379 }
00380
00389 inline void set_array(T* p_array, int32_t p_num_elements,
00390 int32_t p_array_size, bool p_free_array, bool p_copy_array)
00391 {
00392 if (array!=NULL && free_array)
00393 SG_FREE(array);
00394
00395 if (p_copy_array)
00396 {
00397 if (use_sg_mallocs)
00398 array=SG_MALLOC(T, p_array_size);
00399 else
00400 array=(T*) malloc(p_array_size*sizeof(T));
00401 memcpy(array, p_array, p_array_size*sizeof(T));
00402 }
00403 else
00404 array=p_array;
00405
00406 num_elements=p_array_size;
00407 last_element_idx=p_num_elements-1;
00408 free_array=p_free_array;
00409 }
00410
00417 inline void set_array(const T* p_array, int32_t p_num_elements,
00418 int32_t p_array_size)
00419 {
00420 if (array!=NULL && free_array)
00421 SG_FREE(array);
00422
00423 if (use_sg_mallocs)
00424 array=SG_MALLOC(T, p_array_size);
00425 else
00426 array=(T*) malloc(p_array_size*sizeof(T));
00427 memcpy(array, p_array, p_array_size*sizeof(T));
00428
00429 num_elements=p_array_size;
00430 last_element_idx=p_num_elements-1;
00431 free_array=true;
00432 }
00433
00435 inline void clear_array()
00436 {
00437 if (last_element_idx >= 0)
00438 memset(array, 0, (last_element_idx+1)*sizeof(T));
00439 }
00440
00442 void reset()
00443 {
00444 clear_array();
00445 last_element_idx=-1;
00446 }
00447
00449 void shuffle()
00450 {
00451 for (index_t i=0; i<=last_element_idx; ++i)
00452 CMath::swap(array[i], array[CMath::random(i, last_element_idx)]);
00453 }
00454
00456 void set_const(const T& const_element)
00457 {
00458 for (int32_t i=0; i<num_elements; i++)
00459 array[i]=const_element;
00460 }
00461
00471 inline T operator[](int32_t index) const
00472 {
00473 return array[index];
00474 }
00475
00482 DynArray<T>& operator=(DynArray<T>& orig)
00483 {
00484 resize_granularity=orig.resize_granularity;
00485
00486
00487 if (orig.num_elements>num_elements)
00488 {
00489 SG_FREE(array);
00490
00491 if (use_sg_mallocs)
00492 array=SG_MALLOC(T, orig.num_elements);
00493 else
00494 array=(T*) malloc(sizeof(T)*orig.num_elements);
00495 }
00496
00497 memcpy(array, orig.array, sizeof(T)*orig.num_elements);
00498 num_elements=orig.num_elements;
00499 last_element_idx=orig.last_element_idx;
00500
00501 return *this;
00502 }
00503
00505 virtual const char* get_name() const { return "DynArray"; }
00506
00507 protected:
00509 int32_t resize_granularity;
00510
00512 T* array;
00513
00515 int32_t num_elements;
00516
00518 int32_t last_element_idx;
00519
00521 bool use_sg_mallocs;
00522
00524 bool free_array;
00525 };
00526 }
00527 #endif