SHOGUN  v2.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DynArray.h
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 1999-2009 Soeren Sonnenburg
8  * Copyright (C) 1999-2009 Fraunhofer Institute FIRST and Max-Planck-Society
9  * Copyright (C) 2012 Engeniy Andreev (gsomix)
10  */
11 
12 #ifndef _DYNARRAY_H_
13 #define _DYNARRAY_H_
14 
15 #include <shogun/lib/common.h>
16 #include <shogun/lib/memory.h>
18 
19 namespace shogun
20 {
21 template <class T> class CDynamicArray;
22 
31 template <class T> class DynArray
32 {
33  template<class U> friend class CDynamicArray;
34  friend class CDynamicObjectArray;
35  friend class CCommUlongStringKernel;
36 
37  public:
43  DynArray(int32_t p_resize_granularity=128, bool tracable=true)
44  {
45  resize_granularity=p_resize_granularity;
46  free_array=true;
47  use_sg_mallocs=tracable;
48 
49  if (use_sg_mallocs)
50  array=SG_CALLOC(T, p_resize_granularity);
51  else
52  array=(T*) calloc(p_resize_granularity, sizeof(T));
53 
54  num_elements=p_resize_granularity;
56  }
57 
66  DynArray(T* p_array, int32_t p_array_size, bool p_free_array, bool p_copy_array, bool tracable=true)
67  {
68  resize_granularity=p_array_size;
69  free_array=false;
70  use_sg_mallocs=tracable;
71 
72  array=NULL;
73  set_array(p_array, p_array_size, p_array_size, p_free_array, p_copy_array);
74  }
75 
82  DynArray(const T* p_array, int32_t p_array_size, bool tracable=true)
83  {
84  resize_granularity=p_array_size;
85  free_array=false;
86  use_sg_mallocs=tracable;
87 
88  array=NULL;
89  set_array(p_array, p_array_size, p_array_size);
90  }
91 
93  virtual ~DynArray()
94  {
95  if (array!=NULL && free_array)
96  {
97  if (use_sg_mallocs)
98  SG_FREE(array);
99  else
100  free(array);
101  }
102  }
103 
109  inline int32_t set_granularity(int32_t g)
110  {
111  g=CMath::max(g,128);
112  this->resize_granularity = g;
113  return g;
114  }
115 
120  inline int32_t get_array_size() const
121  {
122  return num_elements;
123  }
124 
129  inline int32_t get_num_elements() const
130  {
131  return last_element_idx+1;
132  }
133 
141  inline T get_element(int32_t index) const
142  {
143  return array[index];
144  }
145 
150  inline T get_last_element() const
151  {
152  return array[last_element_idx];
153  }
154 
162  inline T* get_element_ptr(int32_t index)
163  {
164  return &array[index];
165  }
166 
174  inline T get_element_safe(int32_t index) const
175  {
176  if (index>=get_num_elements())
177  {
178  SG_SERROR("array index out of bounds (%d >= %d)\n",
179  index, get_num_elements());
180  }
181  return array[index];
182  }
183 
190  inline bool set_element(T element, int32_t index)
191  {
192  if (index < 0)
193  {
194  return false;
195  }
196  else if (index <= last_element_idx)
197  {
198  array[index]=element;
199  return true;
200  }
201  else if (index < num_elements)
202  {
203  array[index]=element;
204  last_element_idx=index;
205  return true;
206  }
207  else
208  {
209  if (free_array && resize_array(index))
210  return set_element(element, index);
211  else
212  return false;
213  }
214  }
215 
222  inline bool insert_element(T element, int32_t index)
223  {
225  {
226  for (int32_t i=last_element_idx-1; i>index; i--)
227  {
228  array[i]=array[i-1];
229  }
230  array[index]=element;
231 
232  return true;
233  }
234 
235  return false;
236  }
237 
243  inline bool append_element(T element)
244  {
245  return set_element(element, last_element_idx+1);
246  }
247 
253  inline void push_back(T element)
254  {
255  if (get_num_elements() < 0) set_element(element, 0);
256  else set_element(element, get_num_elements());
257  }
258 
262  inline void pop_back()
263  {
264  if (get_num_elements() <= 0) return;
266  }
267 
273  inline T back() const
274  {
275  if (get_num_elements() <= 0) return get_element(0);
276  return get_element(get_num_elements()-1);
277  }
278 
285  int32_t find_element(T element) const
286  {
287  int32_t idx=-1;
288  int32_t num=get_num_elements();
289 
290  for (int32_t i=0; i<num; i++)
291  {
292  if (array[i] == element)
293  {
294  idx=i;
295  break;
296  }
297  }
298 
299  return idx;
300  }
301 
308  inline bool delete_element(int32_t idx)
309  {
310  if (idx>=0 && idx<=last_element_idx)
311  {
312  for (int32_t i=idx; i<last_element_idx; i++)
313  array[i]=array[i+1];
314 
315  memset(&array[last_element_idx], 0, sizeof(T));
316  last_element_idx--;
317 
318  if (num_elements - last_element_idx
320  resize_array(last_element_idx+1);
321 
322  return true;
323  }
324 
325  return false;
326  }
327 
333  bool resize_array(int32_t n)
334  {
335  int32_t new_num_elements=((n/resize_granularity)+1)
337 
338  T* p;
339 
340  if (use_sg_mallocs)
341  p = SG_REALLOC(T, array, new_num_elements);
342  else
343  p = (T*) realloc(array, new_num_elements*sizeof(T));
344  if (p)
345  {
346  array=p;
347  if (new_num_elements > num_elements)
348  {
349  memset(&array[num_elements], 0,
350  (new_num_elements-num_elements)*sizeof(T));
351  }
352  else if (n+1<new_num_elements)
353  {
354  memset(&array[n+1], 0,
355  (new_num_elements-n-1)*sizeof(T));
356  }
357 
358  //in case of shrinking we must adjust last element idx
359  if (n-1<last_element_idx)
360  last_element_idx=n-1;
361 
362  num_elements=new_num_elements;
363  return true;
364  }
365  else
366  return false;
367  }
368 
376  inline T* get_array() const
377  {
378  return array;
379  }
380 
389  inline void set_array(T* p_array, int32_t p_num_elements,
390  int32_t p_array_size, bool p_free_array, bool p_copy_array)
391  {
392  if (array!=NULL && free_array)
393  SG_FREE(array);
394 
395  if (p_copy_array)
396  {
397  if (use_sg_mallocs)
398  array=SG_MALLOC(T, p_array_size);
399  else
400  array=(T*) malloc(p_array_size*sizeof(T));
401  memcpy(array, p_array, p_array_size*sizeof(T));
402  }
403  else
404  array=p_array;
405 
406  num_elements=p_array_size;
407  last_element_idx=p_num_elements-1;
408  free_array=p_free_array;
409  }
410 
417  inline void set_array(const T* p_array, int32_t p_num_elements,
418  int32_t p_array_size)
419  {
420  if (array!=NULL && free_array)
421  SG_FREE(array);
422 
423  if (use_sg_mallocs)
424  array=SG_MALLOC(T, p_array_size);
425  else
426  array=(T*) malloc(p_array_size*sizeof(T));
427  memcpy(array, p_array, p_array_size*sizeof(T));
428 
429  num_elements=p_array_size;
430  last_element_idx=p_num_elements-1;
431  free_array=true;
432  }
433 
435  inline void clear_array()
436  {
437  if (last_element_idx >= 0)
438  memset(array, 0, (last_element_idx+1)*sizeof(T));
439  }
440 
442  void reset()
443  {
444  clear_array();
445  last_element_idx=-1;
446  }
447 
449  void shuffle()
450  {
451  for (index_t i=0; i<=last_element_idx; ++i)
453  }
454 
456  void set_const(const T& const_element)
457  {
458  for (int32_t i=0; i<num_elements; i++)
459  array[i]=const_element;
460  }
461 
471  inline T operator[](int32_t index) const
472  {
473  return array[index];
474  }
475 
483  {
485 
486  /* check if orig array is larger than current, create new array */
487  if (orig.num_elements>num_elements)
488  {
489  SG_FREE(array);
490 
491  if (use_sg_mallocs)
492  array=SG_MALLOC(T, orig.num_elements);
493  else
494  array=(T*) malloc(sizeof(T)*orig.num_elements);
495  }
496 
497  memcpy(array, orig.array, sizeof(T)*orig.num_elements);
500 
501  return *this;
502  }
503 
505  inline virtual const char* get_name() const { return "DynArray"; }
506 
507  protected:
510 
512  T* array;
513 
515  int32_t num_elements;
516 
519 
522 
525 };
526 }
527 #endif /* _DYNARRAY_H_ */

SHOGUN Machine Learning Toolbox - Documentation