DynArray.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 
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_  */
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation