SHOGUN
v1.1.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 */ 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 //in case of shrinking we must adjust last element idx 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 /* check if orig array is larger than current, create new array */ 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 /* _DYNARRAY_H_ */