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

SHOGUN Machine Learning Toolbox - Documentation