DynamicArray.h

Go to the documentation of this file.
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 #include "base/SGObject.h"
00017 
00018 namespace shogun
00019 {
00027 template <class T> class CDynamicArray : public CSGObject
00028 {
00029     public:
00034         CDynamicArray(int32_t p_resize_granularity=128)
00035         : CSGObject()
00036         {
00037             this->resize_granularity=p_resize_granularity;
00038 
00039             array=(T*) calloc(p_resize_granularity, sizeof(T));
00040             ASSERT(array);
00041 
00042             num_elements=p_resize_granularity;
00043             last_element_idx=-1;
00044         }
00045 
00046         virtual ~CDynamicArray() { free(array); }
00047 
00053         inline int32_t set_granularity(int32_t g)
00054         {
00055             g=CMath::max(g,128);
00056             this->resize_granularity = g;
00057             return g;
00058         }
00059 
00064         inline int32_t get_array_size()
00065         {
00066             return num_elements;
00067         }
00068 
00073         inline int32_t get_num_elements() const
00074         {
00075             return last_element_idx+1;
00076         }
00077 
00085         inline T get_element(int32_t index) const
00086         {
00087             return array[index];
00088         }
00089 
00097         inline T get_element_safe(int32_t index) const
00098         {
00099             if (index>=get_num_elements())
00100             {
00101                 SG_ERROR("array index out of bounds (%d >= %d)\n",
00102                         index, get_num_elements());
00103             }
00104             return array[index];
00105         }
00106 
00113         inline bool set_element(T element, int32_t index)
00114         {
00115             if (index < 0)
00116             {
00117                 return false;
00118             }
00119             else if (index <= last_element_idx)
00120             {
00121                 array[index]=element;
00122                 return true;
00123             }
00124             else if (index < num_elements)
00125             {
00126                 array[index]=element;
00127                 last_element_idx=index;
00128                 return true;
00129             }
00130             else
00131             {
00132                 if (resize_array(index))
00133                     return set_element(element, index);
00134                 else
00135                     return false;
00136             }
00137         }
00138 
00145         inline bool insert_element(T element, int32_t index)
00146         {
00147             if (append_element(get_element(last_element_idx)))
00148             {
00149                 for (int32_t i=last_element_idx-1; i>index; i--)
00150                 {
00151                     array[i]=array[i-1];
00152                 }
00153                 array[index]=element;
00154 
00155                 return true;
00156             }
00157 
00158             return false;
00159         }
00160 
00166         inline bool append_element(T element)
00167         {
00168             return set_element(element, last_element_idx+1);
00169         }
00170 
00177         int32_t find_element(T element)
00178         {
00179             int32_t idx=-1;
00180             int32_t num=get_num_elements();
00181 
00182             for (int32_t i=0; i<num; i++)
00183             {
00184                 if (array[i] == element)
00185                 {
00186                     idx=i;
00187                     break;
00188                 }
00189             }
00190 
00191             return idx;
00192         }
00193 
00200         inline bool delete_element(int32_t idx)
00201         {
00202             if (idx>=0 && idx<=last_element_idx)
00203             {
00204                 for (int32_t i=idx; i<last_element_idx; i++)
00205                     array[i]=array[i+1];
00206 
00207                 array[last_element_idx]=0;
00208                 last_element_idx--;
00209 
00210                 if ( num_elements - last_element_idx >= resize_granularity)
00211                     resize_array(last_element_idx);
00212 
00213                 return true;
00214             }
00215 
00216             return false;
00217         }
00218 
00224         bool resize_array(int32_t n)
00225         {
00226             int32_t new_num_elements= ((n/resize_granularity)+1)*resize_granularity;
00227 
00228             T* p= (T*) realloc(array, sizeof(T)*new_num_elements);
00229             if (p)
00230             {
00231                 array=p;
00232                 if (new_num_elements > num_elements)
00233                     memset(&array[num_elements], 0, (new_num_elements-num_elements)*sizeof(T));
00234                 else if (n+1<new_num_elements)
00235                     memset(&array[n+1], 0, (new_num_elements-n-1)*sizeof(T));
00236 
00237                 //in case of shrinking we must adjust last element idx
00238                 if (n-1<last_element_idx)
00239                     last_element_idx=n-1;
00240 
00241                 num_elements=new_num_elements;
00242                 return true;
00243             }
00244             else
00245                 return false;
00246         }
00247 
00255         inline T* get_array()
00256         {
00257             return array;
00258         }
00259 
00266         inline void set_array(T* p_array, int32_t p_num_elements, int32_t array_size)
00267         {
00268             free(this->array);
00269             this->array=p_array;
00270             this->num_elements=array_size;
00271             this->last_element_idx=p_num_elements-1;
00272         }
00273 
00275         inline void clear_array()
00276         {
00277             if (last_element_idx >= 0)
00278                 memset(array, 0, (last_element_idx+1)*sizeof(T));
00279         }
00280 
00290         inline T operator[](int32_t index) const
00291         {
00292             return array[index];
00293         }
00294 
00300         CDynamicArray<T>& operator=(CDynamicArray<T>& orig)
00301         {
00302             resize_granularity=orig.resize_granularity;
00303             memcpy(array, orig.array, sizeof(T)*orig.num_elements);
00304             num_elements=orig.num_elements;
00305             last_element_idx=orig.last_element_idx;
00306 
00307             return *this;
00308         }
00309 
00311         inline virtual const char* get_name() const { return "DynamicArray"; }
00312 
00313     protected:
00315         int32_t resize_granularity;
00316 
00318         T* array;
00319 
00321         int32_t num_elements;
00322 
00324         int32_t last_element_idx;
00325 };
00326 }
00327 #endif

SHOGUN Machine Learning Toolbox - Documentation