SHOGUN  4.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
Set.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) 2012 Evgeniy Andreev (gsomix)
8  *
9  * Copyright (C) 2012 Evgeniy Andreev (gsomix)
10  */
11 
12 #ifndef _SET_H_
13 #define _SET_H_
14 
15 #include <shogun/lib/config.h>
16 
17 #include <shogun/base/SGObject.h>
18 #include <shogun/lib/common.h>
19 #include <shogun/lib/Hash.h>
20 #include <shogun/base/DynArray.h>
21 
22 #include <cstdio>
23 
24 namespace shogun
25 {
26 
27 #ifndef DOXYGEN_SHOULD_SKIP_THIS
28 
29 template<class T> struct CSetNode
30 {
32  int32_t index;
33 
35  bool free;
36 
38  T element;
39 
41  CSetNode<T> *left;
42 
44  CSetNode<T> *right;
45 };
46 #endif
47 
51 template<class T> class CSet: public CSGObject
52 {
53 public:
55  CSet(int32_t size=41, int32_t reserved=128, bool tracable=true)
56  {
57  hash_size=size;
58  free_index=0;
59  num_elements=0;
60  use_sg_mallocs=tracable;
61 
62  if (use_sg_mallocs)
63  hash_array=SG_CALLOC(CSetNode<T>*, size);
64  else
65  hash_array=(CSetNode<T>**) calloc(size, sizeof(CSetNode<T>*));
66 
67  for (int32_t i=0; i<size; i++)
68  {
69  hash_array[i]=NULL;
70  }
71 
72  array=new DynArray<CSetNode<T>* >(reserved, tracable);
73  }
74 
76  virtual ~CSet()
77  {
78  if (array!=NULL)
79  {
80  for(int32_t i=0; i<array->get_num_elements(); i++)
81  {
82  if (array->get_element(i)!=NULL)
83  {
84  if (use_sg_mallocs)
85  SG_FREE(array->get_element(i));
86  else
87  free(array->get_element(i));
88  }
89  }
90  delete array;
91  }
92 
93  if (hash_array!=NULL)
94  {
95  if (use_sg_mallocs)
96  SG_FREE(hash_array);
97  else
98  free(hash_array);
99  }
100  }
101 
103  virtual const char* get_name() const { return "Set"; }
104 
109  void add(const T& element)
110  {
111  int32_t index=hash(element);
112  if (chain_search(index, element)==NULL)
113  {
114  insert_key(index, element);
115  num_elements++;
116  }
117  }
118 
123  bool contains(const T& element)
124  {
125  int32_t index=hash(element);
126  if (chain_search(index, element)!=NULL)
127  return true;
128 
129  return false;
130  }
131 
136  void remove(const T& element)
137  {
138  int32_t index=hash(element);
139  CSetNode<T>* result=chain_search(index, element);
140 
141  if (result!=NULL)
142  {
143  delete_key(index, result);
144  num_elements--;
145  }
146  }
147 
153  int32_t index_of(const T& element)
154  {
155  int32_t index=hash(element);
156  CSetNode<T>* result=chain_search(index, element);
157 
158  if (result!=NULL)
159  return result->index;
160 
161  return -1;
162  }
163 
168  int32_t get_num_elements() const
169  {
170  return num_elements;
171  }
172 
177  int32_t get_array_size() const
178  {
179  return array->get_num_elements();
180  }
181 
189  T* get_element_ptr(int32_t index)
190  {
191  if (array->get_element(index)!=NULL)
192  return &(array->get_element(index)->element);
193  return NULL;
194  }
195 
203  CSetNode<T>* get_node_ptr(int32_t index)
204  {
205  return array->get_element(index);
206  }
207 
209  CSetNode<T>** get_array()
210  {
211  return array->get_array();
212  }
213 
214 private:
218  int32_t hash(const T& element)
219  {
220  return CHash::MurmurHash3((uint8_t*)(&element), sizeof(element), 0xDEADBEEF) % hash_size;
221  }
222 
224  bool is_free(CSetNode<T>* node)
225  {
226  if (node->free==true)
227  return true;
228 
229  return false;
230  }
231 
233  CSetNode<T>* chain_search(int32_t index, const T& element)
234  {
235  if (hash_array[index]==NULL)
236  {
237  return NULL;
238  }
239  else
240  {
241  CSetNode<T>* current=hash_array[index];
242 
243  do // iterating all items in the list
244  {
245  if (current->element==element)
246  return current; // it's a search key
247 
248  current=current->right;
249 
250  } while (current!=NULL);
251 
252  return NULL;
253  }
254  }
255 
257  void insert_key(int32_t index, const T& element)
258  {
259  int32_t new_index;
260  CSetNode<T>* new_node;
261 
263  {
264  // init new node
265  if (use_sg_mallocs)
266  new_node=SG_CALLOC(CSetNode<T>, 1);
267  else
268  new_node=(CSetNode<T>*) calloc(1, sizeof(CSetNode<T>));
269 
270  array->append_element(new_node);
271 
272  new_index=free_index;
273  free_index++;
274  }
275  else
276  {
277  new_node=array->get_element(free_index);
278  ASSERT(is_free(new_node))
279 
280  new_index=free_index;
281  free_index=new_node->index;
282  }
283 
284  new_node->index=new_index;
285  new_node->free=false;
286  new_node->element=element;
287  new_node->left=NULL;
288  new_node->right=NULL;
289 
290  // add new node in start of list
291  if (hash_array[index]==NULL)
292  {
293  hash_array[index]=new_node;
294  }
295  else
296  {
297  hash_array[index]->left=new_node;
298  new_node->right=hash_array[index];
299 
300  hash_array[index]=new_node;
301  }
302  }
303 
305  void delete_key(int32_t index, CSetNode<T>* node)
306  {
307  int32_t temp=0;
308 
309  if (node==NULL)
310  return;
311 
312  if (node->right!=NULL)
313  node->right->left = node->left;
314 
315  if (node->left!=NULL)
316  node->left->right = node->right;
317  else
318  hash_array[index] = node->right;
319 
320  temp=node->index;
321 
322  node->index=free_index;
323  node->free=true;
324  node->left=NULL;
325  node->right=NULL;
326 
327  free_index=temp;
328  }
329 
330 
331 protected:
334 
336  int32_t hash_size;
337 
339  int32_t free_index;
340 
342  int32_t num_elements;
343 
345  CSetNode<T>** hash_array;
346 
349 };
350 
351 }
352 
353 #endif /* _MAP_H_ */
bool contains(const T &element)
Definition: Set.h:123
T get_element(int32_t index) const
Definition: DynArray.h:142
int32_t index_of(const T &element)
Definition: Set.h:153
bool append_element(T element)
Definition: DynArray.h:244
node< P > new_node(const P &p)
Definition: JLCoverTree.h:100
DynArray< CSetNode< T > * > * array
Definition: Set.h:348
CSetNode< T > ** get_array()
Definition: Set.h:209
int32_t get_num_elements() const
Definition: DynArray.h:130
CSet(int32_t size=41, int32_t reserved=128, bool tracable=true)
Definition: Set.h:55
static uint32_t MurmurHash3(uint8_t *data, int32_t len, uint32_t seed)
Definition: Hash.cpp:366
int32_t free_index
Definition: Set.h:339
#define ASSERT(x)
Definition: SGIO.h:201
Class SGObject is the base class of all shogun objects.
Definition: SGObject.h:112
the class CSet, a set based on the hash-table. w: http://en.wikipedia.org/wiki/Hash_table ...
Definition: Set.h:51
CSetNode< T > ** hash_array
Definition: Set.h:345
virtual const char * get_name() const
Definition: Set.h:103
int32_t hash_size
Definition: Set.h:336
Template Dynamic array class that creates an array that can be used like a list or an array...
Definition: DynArray.h:32
CSetNode< T > * get_node_ptr(int32_t index)
Definition: Set.h:203
T * get_element_ptr(int32_t index)
Definition: Set.h:189
all of classes and functions are contained in the shogun namespace
Definition: class_list.h:18
T * get_array() const
Definition: DynArray.h:372
virtual ~CSet()
Definition: Set.h:76
int32_t get_num_elements() const
Definition: Set.h:168
void add(const T &element)
Definition: Set.h:109
bool use_sg_mallocs
Definition: Set.h:333
int32_t get_array_size() const
Definition: Set.h:177
int32_t num_elements
Definition: Set.h:342

SHOGUN Machine Learning Toolbox - Documentation