SHOGUN
v3.2.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/mathematics/Math.h> 00017 00018 namespace shogun 00019 { 00020 template <class T> class CDynamicArray; 00021 00030 template <class T> class DynArray 00031 { 00032 template<class U> friend class CDynamicArray; 00033 friend class CDynamicObjectArray; 00034 friend class CCommUlongStringKernel; 00035 00036 public: 00042 DynArray(int32_t p_resize_granularity=128, bool tracable=true) 00043 { 00044 resize_granularity=p_resize_granularity; 00045 free_array=true; 00046 use_sg_mallocs=tracable; 00047 00048 if (use_sg_mallocs) 00049 array=SG_MALLOC(T, p_resize_granularity); 00050 else 00051 array=(T*) malloc(size_t(p_resize_granularity)*sizeof(T)); 00052 00053 num_elements=p_resize_granularity; 00054 current_num_elements=0; 00055 } 00056 00065 DynArray(T* p_array, int32_t p_array_size, bool p_free_array, bool p_copy_array, bool tracable=true) 00066 { 00067 resize_granularity=p_array_size; 00068 free_array=false; 00069 use_sg_mallocs=tracable; 00070 00071 array=NULL; 00072 set_array(p_array, p_array_size, p_array_size, p_free_array, p_copy_array); 00073 } 00074 00081 DynArray(const T* p_array, int32_t p_array_size, bool tracable=true) 00082 { 00083 resize_granularity=p_array_size; 00084 free_array=false; 00085 use_sg_mallocs=tracable; 00086 00087 array=NULL; 00088 set_array(p_array, p_array_size, p_array_size); 00089 } 00090 00092 virtual ~DynArray() 00093 { 00094 if (array!=NULL && free_array) 00095 { 00096 if (use_sg_mallocs) 00097 SG_FREE(array); 00098 else 00099 free(array); 00100 } 00101 } 00102 00108 inline int32_t set_granularity(int32_t g) 00109 { 00110 g=CMath::max(g,1); 00111 this->resize_granularity = g; 00112 return g; 00113 } 00114 00119 inline int32_t get_array_size() const 00120 { 00121 return num_elements; 00122 } 00123 00128 inline int32_t get_num_elements() const 00129 { 00130 return current_num_elements; 00131 } 00132 00140 inline T get_element(int32_t index) const 00141 { 00142 return array[index]; 00143 } 00144 00149 inline T get_last_element() const 00150 { 00151 return array[current_num_elements-1]; 00152 } 00153 00161 inline T* get_element_ptr(int32_t index) 00162 { 00163 return &array[index]; 00164 } 00165 00173 inline T get_element_safe(int32_t index) const 00174 { 00175 if (index>=get_num_elements()) 00176 { 00177 SG_SERROR("array index out of bounds (%d >= %d)\n", 00178 index, get_num_elements()); 00179 } 00180 return array[index]; 00181 } 00182 00189 inline bool set_element(T element, int32_t index) 00190 { 00191 if (index < 0) 00192 { 00193 return false; 00194 } 00195 else if (index <= current_num_elements-1) 00196 { 00197 array[index]=element; 00198 return true; 00199 } 00200 else if (index < num_elements) 00201 { 00202 array[index]=element; 00203 current_num_elements=index+1; 00204 return true; 00205 } 00206 else 00207 { 00208 if (free_array && resize_array(index)) 00209 return set_element(element, index); 00210 else 00211 return false; 00212 } 00213 } 00214 00221 inline bool insert_element(T element, int32_t index) 00222 { 00223 if (append_element(get_element(current_num_elements-1))) 00224 { 00225 for (int32_t i=current_num_elements-2; i>index; i--) 00226 { 00227 array[i]=array[i-1]; 00228 } 00229 array[index]=element; 00230 00231 return true; 00232 } 00233 00234 return false; 00235 } 00236 00242 inline bool append_element(T element) 00243 { 00244 return set_element(element, current_num_elements); 00245 } 00246 00252 inline void push_back(T element) 00253 { 00254 if (get_num_elements() < 0) 00255 set_element(element, 0); 00256 else 00257 set_element(element, get_num_elements()); 00258 } 00259 00263 inline void pop_back() 00264 { 00265 if (get_num_elements() <= 0) 00266 return; 00267 00268 delete_element(get_num_elements()-1); 00269 } 00270 00276 inline T back() const 00277 { 00278 if (get_num_elements() <= 0) 00279 return get_element(0); 00280 00281 return get_element(get_num_elements()-1); 00282 } 00283 00290 int32_t find_element(T element) const 00291 { 00292 int32_t idx=-1; 00293 int32_t num=get_num_elements(); 00294 00295 for (int32_t i=0; i<num; i++) 00296 { 00297 if (array[i] == element) 00298 { 00299 idx=i; 00300 break; 00301 } 00302 } 00303 00304 return idx; 00305 } 00306 00313 inline bool delete_element(int32_t idx) 00314 { 00315 if (idx>=0 && idx<=current_num_elements-1) 00316 { 00317 for (int32_t i=idx; i<current_num_elements-1; i++) 00318 array[i]=array[i+1]; 00319 00320 current_num_elements--; 00321 00322 if (num_elements - current_num_elements - 1 00323 > resize_granularity) 00324 resize_array(current_num_elements); 00325 00326 return true; 00327 } 00328 00329 return false; 00330 } 00331 00338 bool resize_array(int32_t n, bool exact_resize=false) 00339 { 00340 int32_t new_num_elements=n; 00341 00342 if (!exact_resize) 00343 { 00344 new_num_elements=((n/resize_granularity)+1)*resize_granularity; 00345 } 00346 00347 00348 if (use_sg_mallocs) 00349 array = SG_REALLOC(T, array, num_elements, new_num_elements); 00350 else 00351 array = (T*) realloc(array, new_num_elements*sizeof(T)); 00352 00353 //in case of shrinking we must adjust last element idx 00354 if (n-1<current_num_elements-1) 00355 current_num_elements=n; 00356 00357 num_elements=new_num_elements; 00358 return true; 00359 00360 return array || new_num_elements==0; 00361 } 00362 00370 inline T* get_array() const 00371 { 00372 return array; 00373 } 00374 00383 inline void set_array(T* p_array, int32_t p_num_elements, 00384 int32_t p_array_size, bool p_free_array, bool p_copy_array) 00385 { 00386 if (array!=NULL && free_array) 00387 SG_FREE(array); 00388 00389 if (p_copy_array) 00390 { 00391 if (use_sg_mallocs) 00392 array=SG_MALLOC(T, p_array_size); 00393 else 00394 array=(T*) malloc(p_array_size*sizeof(T)); 00395 memcpy(array, p_array, p_array_size*sizeof(T)); 00396 } 00397 else 00398 array=p_array; 00399 00400 num_elements=p_array_size; 00401 current_num_elements=p_num_elements; 00402 free_array=p_free_array; 00403 } 00404 00411 inline void set_array(const T* p_array, int32_t p_num_elements, 00412 int32_t p_array_size) 00413 { 00414 if (array!=NULL && free_array) 00415 SG_FREE(array); 00416 00417 if (use_sg_mallocs) 00418 array=SG_MALLOC(T, p_array_size); 00419 else 00420 array=(T*) malloc(p_array_size*sizeof(T)); 00421 memcpy(array, p_array, p_array_size*sizeof(T)); 00422 00423 num_elements=p_array_size; 00424 current_num_elements=p_num_elements; 00425 free_array=true; 00426 } 00427 00429 inline void clear_array(T value) 00430 { 00431 if (current_num_elements-1 >= 0) 00432 { 00433 for (int32_t i=0; i<current_num_elements; i++) 00434 array[i]=value; 00435 } 00436 } 00437 00439 void reset(T value) 00440 { 00441 clear_array(value); 00442 current_num_elements=0; 00443 } 00444 00446 void shuffle() 00447 { 00448 for (index_t i=0; i<=current_num_elements-1; ++i) 00449 CMath::swap(array[i], array[CMath::random(i, current_num_elements-1)]); 00450 } 00451 00453 void shuffle(CRandom * rand) 00454 { 00455 for (index_t i=0; i<=current_num_elements-1; ++i) 00456 CMath::swap(array[i], array[rand->random(i, current_num_elements-1)]); 00457 } 00458 00460 void set_const(const T& const_element) 00461 { 00462 for (int32_t i=0; i<num_elements; i++) 00463 array[i]=const_element; 00464 } 00465 00475 inline T operator[](int32_t index) const 00476 { 00477 return array[index]; 00478 } 00479 00486 DynArray<T>& operator=(DynArray<T>& orig) 00487 { 00488 resize_granularity=orig.resize_granularity; 00489 00490 /* check if orig array is larger than current, create new array */ 00491 if (orig.num_elements>num_elements) 00492 { 00493 SG_FREE(array); 00494 00495 if (use_sg_mallocs) 00496 array=SG_MALLOC(T, orig.num_elements); 00497 else 00498 array=(T*) malloc(sizeof(T)*orig.num_elements); 00499 } 00500 00501 memcpy(array, orig.array, sizeof(T)*orig.num_elements); 00502 num_elements=orig.num_elements; 00503 current_num_elements=orig.current_num_elements; 00504 00505 return *this; 00506 } 00507 00509 virtual const char* get_name() const { return "DynArray"; } 00510 00511 protected: 00513 int32_t resize_granularity; 00514 00516 T* array; 00517 00519 int32_t num_elements; 00520 00522 int32_t current_num_elements; 00523 00525 bool use_sg_mallocs; 00526 00528 bool free_array; 00529 }; 00530 } 00531 #endif /* _DYNARRAY_H_ */