SHOGUN
v2.0.0
|
00001 /* 00002 * This program is free software; you can redistribute it and/or modify 00003 * it under the terms of the GNU General Public License as published by 00004 * the Free Software Foundation; either version 3 of the License, or 00005 * (at your option) any later version. 00006 * 00007 * Written (W) 1999-2009 Soeren Sonnenburg 00008 * Copyright (C) 1999-2009 Fraunhofer Institute FIRST and Max-Planck-Society 00009 * Copyright (C) 2012 Engeniy Andreev (gsomix) 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 //in case of shrinking we must adjust last element idx 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 /* check if orig array is larger than current, create new array */ 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 inline 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 /* _DYNARRAY_H_ */