SHOGUN  v1.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
HashSet.cpp
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) 2011 Evgeniy Andreev (gsomix)
8  *
9  * Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society
10  */
11 
12 #include <shogun/lib/HashSet.h>
13 
14 using namespace shogun;
15 
17 {
18  array_size = 0;
19  hash_array = NULL;
20 }
21 
22 CHashSet::CHashSet(int32_t size)
23 {
24  array_size = size;
25  hash_array = SG_MALLOC(HashSetNode*, array_size);
26  for(int32_t i = 0; i < array_size; i++)
27  {
28  hash_array[i] = NULL;
29  }
30 }
31 
33 {
34  if(hash_array != NULL)
35  {
36  for(int32_t i = 0; i < array_size; i++)
37  {
38  delete hash_array[i];
39  }
41  }
42 }
43 
44 bool CHashSet::insert_key(int32_t key, float64_t data)
45 {
46  int32_t index = hash(key);
47  if(chain_search(index, key) != NULL)
48  {
49  // this key is already in set
50  return false;
51  }
52 
53  // init new node
54  HashSetNode* new_node = new HashSetNode;
55  new_node->key = key;
56  new_node->data = data;
57  new_node->left = NULL;
58  new_node->right = NULL;
59 
60  // add new node in start of list
61  if(hash_array[index] == NULL)
62  {
63  hash_array[index] = new_node;
64  }
65  else
66  {
67  hash_array[index]->left = new_node;
68  new_node->right = hash_array[index];
69 
70  hash_array[index] = new_node;
71  }
72 
73  return true;
74 }
75 
76 bool CHashSet::search_key(int32_t key, float64_t &ret_data)
77 {
78  int index = hash(key);
79 
80  HashSetNode* result = chain_search(index, key);
81  if(result == NULL)
82  {
83  return false;
84  }
85  else
86  {
87  ret_data = result->data;
88  return true;
89  }
90 }
91 
92 HashSetNode* CHashSet::chain_search(int32_t index, int32_t key)
93 {
94  if(hash_array[index] == NULL)
95  {
96  return NULL;
97  }
98  else
99  {
100  HashSetNode* current = hash_array[index];
101 
102 
103  do // iterating all items in the list
104  {
105  if(current->key == key)
106  {
107  return current; // it's a search key
108  }
109 
110  current = current->right;
111 
112  } while(current != NULL);
113 
114  return NULL;
115  }
116 }
117 
118 void CHashSet::delete_key(int32_t key)
119 {
120  int index = hash(key);
121  HashSetNode* result = chain_search(index, key);
122 
123  if(result == NULL)
124  {
125  return;
126  }
127 
128  if(result->right != NULL)
129  {
130  result->right->left = result->left;
131  }
132 
133  if(result->left != NULL)
134  {
135  result->left->right = result->right;
136  }
137  else
138  {
139  hash_array[index] = result->right;
140  }
141 
142  result->left = NULL;
143  result->right = NULL;
144 
145  delete result;
146 }
147 
149 {
150  for(int32_t i = 0; i < array_size; i++)
151  {
152  HashSetNode* current = hash_array[i];
153 
154  if(current == NULL)
155  {
156  SG_SPRINT("NULL\n");
157  continue;
158  }
159 
160  do
161  {
162  SG_SPRINT("%d ", current->key);
163  current = current->right;
164  }
165  while(current != NULL);
166  printf("\n");
167  }
168 }
169 
170 int32_t CHashSet::hash(int32_t key)
171 {
172  return CHash::MurmurHash2((uint8_t*)(&key), 4, 1) % array_size;
173 }
174 

SHOGUN Machine Learning Toolbox - Documentation