SHOGUN v0.9.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 "lib/common.h" 00015 #include "lib/Mathematics.h" 00016 00017 namespace shogun 00018 { 00019 extern IO* sg_io; 00020 00029 template <class T> class DynArray 00030 { 00031 public: 00033 int32_t resize_granularity; 00034 00036 T* array; 00037 00039 int32_t num_elements; 00040 00042 int32_t last_element_idx; 00043 00048 DynArray(int32_t p_resize_granularity=128) 00049 { 00050 this->resize_granularity=p_resize_granularity; 00051 00052 array=(T*) calloc(p_resize_granularity, sizeof(T)); 00053 ASSERT(array); 00054 00055 num_elements=p_resize_granularity; 00056 last_element_idx=-1; 00057 } 00058 00059 virtual ~DynArray(void) 00060 { free(array); } 00061 00067 inline int32_t set_granularity(int32_t g) 00068 { 00069 g=CMath::max(g,128); 00070 this->resize_granularity = g; 00071 return g; 00072 } 00073 00078 inline int32_t get_array_size(void) 00079 { 00080 return num_elements; 00081 } 00082 00087 inline int32_t get_num_elements(void) const 00088 { 00089 return last_element_idx+1; 00090 } 00091 00099 inline T get_element(int32_t index) const 00100 { 00101 return array[index]; 00102 } 00103 00111 inline T get_element_safe(int32_t index) const 00112 { 00113 IO* io = sg_io; 00114 00115 if (index>=get_num_elements()) 00116 { 00117 SG_ERROR("array index out of bounds (%d >= %d)\n", 00118 index, get_num_elements()); 00119 } 00120 return array[index]; 00121 } 00122 00129 inline bool set_element(T element, int32_t index) 00130 { 00131 if (index < 0) 00132 { 00133 return false; 00134 } 00135 else if (index <= last_element_idx) 00136 { 00137 array[index]=element; 00138 return true; 00139 } 00140 else if (index < num_elements) 00141 { 00142 array[index]=element; 00143 last_element_idx=index; 00144 return true; 00145 } 00146 else 00147 { 00148 if (resize_array(index)) 00149 return set_element(element, index); 00150 else 00151 return false; 00152 } 00153 } 00154 00161 inline bool insert_element(T element, int32_t index) 00162 { 00163 if (append_element(get_element(last_element_idx))) 00164 { 00165 for (int32_t i=last_element_idx-1; i>index; i--) 00166 { 00167 array[i]=array[i-1]; 00168 } 00169 array[index]=element; 00170 00171 return true; 00172 } 00173 00174 return false; 00175 } 00176 00182 inline bool append_element(T element) 00183 { 00184 return set_element(element, last_element_idx+1); 00185 } 00186 00192 inline void push_back(T element) 00193 { 00194 if (get_num_elements() < 0) set_element(element, 0); 00195 else set_element(element, get_num_elements()); 00196 } 00197 00201 inline void pop_back(void) 00202 { 00203 if (get_num_elements() <= 0) return; 00204 delete_element(get_num_elements()-1); 00205 } 00206 00212 inline T back(void) 00213 { 00214 if (get_num_elements() <= 0) return get_element(0); 00215 return get_element(get_num_elements()-1); 00216 } 00217 00224 int32_t find_element(T element) 00225 { 00226 int32_t idx=-1; 00227 int32_t num=get_num_elements(); 00228 00229 for (int32_t i=0; i<num; i++) 00230 { 00231 if (array[i] == element) 00232 { 00233 idx=i; 00234 break; 00235 } 00236 } 00237 00238 return idx; 00239 } 00240 00247 inline bool delete_element(int32_t idx) 00248 { 00249 if (idx>=0 && idx<=last_element_idx) 00250 { 00251 for (int32_t i=idx; i<last_element_idx; i++) 00252 array[i]=array[i+1]; 00253 00254 array[last_element_idx]=0; 00255 last_element_idx--; 00256 00257 if (num_elements - last_element_idx 00258 > resize_granularity) 00259 resize_array(last_element_idx+1); 00260 00261 return true; 00262 } 00263 00264 return false; 00265 } 00266 00272 bool resize_array(int32_t n) 00273 { 00274 int32_t new_num_elements= ((n/resize_granularity)+1) 00275 *resize_granularity; 00276 00277 T* p= (T*) realloc(array, sizeof(T)*new_num_elements); 00278 if (p) 00279 { 00280 array=p; 00281 if (new_num_elements > num_elements) 00282 memset(&array[num_elements], 0, 00283 (new_num_elements-num_elements)*sizeof(T)); 00284 else if (n+1<new_num_elements) 00285 memset(&array[n+1], 0, 00286 (new_num_elements-n-1)*sizeof(T)); 00287 00288 //in case of shrinking we must adjust last element idx 00289 if (n-1<last_element_idx) 00290 last_element_idx=n-1; 00291 00292 num_elements=new_num_elements; 00293 return true; 00294 } 00295 else 00296 return false; 00297 } 00298 00306 inline T* get_array(void) 00307 { 00308 return array; 00309 } 00310 00317 inline void set_array(T* p_array, int32_t p_num_elements, 00318 int32_t array_size) 00319 { 00320 free(this->array); 00321 this->array=p_array; 00322 this->num_elements=array_size; 00323 this->last_element_idx=p_num_elements-1; 00324 } 00325 00327 inline void clear_array(void) 00328 { 00329 if (last_element_idx >= 0) 00330 memset(array, 0, (last_element_idx+1)*sizeof(T)); 00331 } 00332 00342 inline T operator[](int32_t index) const 00343 { 00344 return array[index]; 00345 } 00346 00352 DynArray<T>& operator=(DynArray<T>& orig) 00353 { 00354 resize_granularity=orig.resize_granularity; 00355 memcpy(array, orig.array, sizeof(T)*orig.num_elements); 00356 num_elements=orig.num_elements; 00357 last_element_idx=orig.last_element_idx; 00358 00359 return *this; 00360 } 00361 00363 inline virtual const char* get_name() const 00364 { return "DynamicArray"; } 00365 }; 00366 } 00367 #endif /* _DYNARRAY_H_ */