WHashMap.h
Go to the documentation of this file.
1 /* $Id: HashMap.h 1198 2011-06-14 21:08:27Z bhagman $
2 ||
3 || @author Alexander Brevig <abrevig@wiring.org.co>
4 || @url http://wiring.org.co/
5 || @url http://alexanderbrevig.com/
6 || @contribution Brett Hagman <bhagman@wiring.org.co>
7 ||
8 || @description
9 || | Implementation of a HashMap data structure.
10 || |
11 || | Wiring Cross-platform Library
12 || #
13 ||
14 || @license Please see cores/Common/License.txt.
15 ||
16 */
17 
18 /*
19  * @author: 3 Oct 2018 - mikee47 <mike@sillyhouse.net>
20  *
21  * Modified to use references (const or otherwise) to avoid object copies when used with classes, e.g. String.
22  *
23  * Note that if the value is a primitive then setNullValue should be called to provide a default value to be
24  * used when adding a new unspecified entry, or if a key value is not present. This should not be necessary
25  * for object values as the default constructor will be used.
26  *
27  */
28 
29 #pragma once
30 
31 #include <cstdint>
32 #include <iterator>
33 #include <cstdlib>
34 
39 template <typename K, typename V> class HashMap
40 {
41 public:
42  using Comparator = bool (*)(const K&, const K&);
43 
44  template <bool is_const> struct BaseElement {
45  public:
46  using Value = typename std::conditional<is_const, const V, V>::type;
47 
48  BaseElement(const K& key, Value& value) : k(key), v(value)
49  {
50  }
51 
52  const K& key() const
53  {
54  return k;
55  }
56 
58  {
59  return v;
60  }
61 
62  const V& value() const
63  {
64  return v;
65  }
66 
68  {
69  v = value;
70  return *this;
71  }
72 
73  private:
74  const K& k;
75  Value& v;
76  };
77 
78  using Element = BaseElement<false>;
79  using ElementConst = BaseElement<true>;
80 
81  template <bool is_const>
82  class Iterator : public std::iterator<std::random_access_iterator_tag, BaseElement<is_const>>
83  {
84  public:
85  using Map = typename std::conditional<is_const, const HashMap, HashMap>::type;
86  using Value = typename std::conditional<is_const, const V, V>::type;
87 
88  Iterator(const Iterator&) = default;
89 
90  Iterator(Map& map, unsigned index) : map(map), index(index)
91  {
92  }
93 
95  {
96  ++index;
97  return *this;
98  }
99 
101  {
102  Iterator tmp(*this);
103  ++index;
104  return tmp;
105  }
106 
107  Iterator operator+=(size_t distance)
108  {
109  Iterator tmp(*this);
110  index += distance;
111  return tmp;
112  }
113 
114  bool operator==(const Iterator& rhs) const
115  {
116  return &map == &rhs.map && index == rhs.index;
117  }
118 
119  bool operator!=(const Iterator& rhs) const
120  {
121  return !operator==(rhs);
122  }
123 
125  {
126  return BaseElement<is_const>{map.keyAt(index), map.valueAt(index)};
127  }
128 
130  {
131  return ElementConst{map.keyAt(index), map.valueAt(index)};
132  }
133 
134  private:
135  Map& map;
136  unsigned index{0};
137  };
138 
139  /*
140  || @constructor
141  || | Default constructor
142  || #
143  */
145  {
146  }
147 
148  /*
149  || @constructor
150  || | Initialize this HashMap
151  || #
152  ||
153  || @parameter compare optional function for comparing a key against another (for complex types)
154  */
155  HashMap(Comparator compare) : cb_comparator(compare)
156  {
157  }
158 
160  {
161  clear();
162  }
163 
164  /*
165  || @description
166  || | Get the size of this HashMap
167  || #
168  ||
169  || @return The size of this HashMap
170  */
171  unsigned int count() const
172  {
173  return currentIndex;
174  }
175 
176  /*
177  || @description
178  || | Get a key at a specified index
179  || #
180  ||
181  || @parameter idx the index to get the key at
182  ||
183  || @return The key at index idx
184  */
185  const K& keyAt(unsigned int idx) const
186  {
187  if(idx >= count()) {
188  abort();
189  }
190  return *keys[idx];
191  }
192 
193  K& keyAt(unsigned int idx)
194  {
195  if(idx >= count()) {
196  abort();
197  }
198  return *keys[idx];
199  }
200 
201  /*
202  || @description
203  || | Get a value at a specified index
204  || #
205  ||
206  || @parameter idx the index to get the value at
207  ||
208  || @return The value at index idx
209  */
210  const V& valueAt(unsigned int idx) const
211  {
212  if(idx >= count()) {
213  abort();
214  }
215  return *values[idx];
216  }
217 
218  V& valueAt(unsigned int idx)
219  {
220  if(idx >= count()) {
221  abort();
222  }
223  return *values[idx];
224  }
225 
226  /*
227  || @description
228  || | An indexer for accessing and assigning a value to a key
229  || | If a key is used that exists, it returns the value for that key
230  || | If there exists no value for that key, a nil value is returned
231  || |
232  || | Note that if the HashMap object is not const, the non-const version
233  || | of this operator will be called which will create a default value
234  || | for this key. If that behaviour is not desired, then check for the
235  || | existence of the key first, using either contains() or indexOf().
236  || #
237  ||
238  || @parameter key the key to get the value for
239  ||
240  || @return The const value for key
241  */
242  const V& operator[](const K& key) const
243  {
244  // Don't create non-existent values
245  auto i = indexOf(key);
246  return (i >= 0) ? *values[i] : nil;
247  }
248 
249  /*
250  || @description
251  || | An indexer for accessing and assigning a value to a key
252  || | If a key is used that exists, it returns the value for that key
253  || | If there exists no value for that key, the key is added
254  || #
255  ||
256  || @parameter key the key to get the value for
257  ||
258  || @return The value for key
259  */
260  V& operator[](const K& key);
261 
262  void allocate(unsigned int newSize);
263 
264  /*
265  || @description
266  || | Get the index of a key
267  || #
268  ||
269  || @parameter key the key to get the index for
270  ||
271  || @return The index of the key, or -1 if key does not exist
272  */
273  int indexOf(const K& key) const;
274 
275  /*
276  || @description
277  || | Check if a key is contained within this HashMap
278  || #
279  ||
280  || @parameter key the key to check if is contained within this HashMap
281  ||
282  || @return true if it is contained in this HashMap
283  */
284  bool contains(const K& key) const
285  {
286  return indexOf(key) >= 0;
287  }
288 
289  /*
290  || @description
291  || | Remove entry at given index
292  || #
293  ||
294  || @parameter index location to remove from this HashMap
295  */
296  void removeAt(unsigned index);
297 
298  /*
299  || @description
300  || | Remove a key from this HashMap
301  || #
302  ||
303  || @parameter key the key to remove from this HashMap
304  */
305  void remove(const K& key)
306  {
307  int index = indexOf(key);
308  if(index >= 0) {
309  removeAt(index);
310  }
311  }
312 
313  void clear();
314 
315  void setMultiple(const HashMap<K, V>& map);
316 
317  void setNullValue(const V& nullv)
318  {
319  nil = nullv;
320  }
321 
322  Iterator<false> begin()
323  {
324  return Iterator<false>(*this, 0);
325  }
326 
327  Iterator<false> end()
328  {
329  return Iterator<false>(*this, count());
330  }
331 
332  Iterator<true> begin() const
333  {
334  return Iterator<true>(*this, 0);
335  }
336 
337  Iterator<true> end() const
338  {
339  return Iterator<true>(*this, count());
340  }
341 
342 protected:
343  K** keys = nullptr;
344  V** values = nullptr;
345  V nil;
349 
350 private:
351  HashMap(const HashMap<K, V>& that);
352 };
353 
354 template <typename K, typename V> V& HashMap<K, V>::operator[](const K& key)
355 {
356  int i = indexOf(key);
357  if(i >= 0) {
358  return *values[i];
359  }
360  if(currentIndex >= size) {
361  allocate(currentIndex + 1);
362  }
363  *keys[currentIndex] = key;
364  *values[currentIndex] = nil;
365  currentIndex++;
366  return *values[currentIndex - 1];
367 }
368 
369 template <typename K, typename V> void HashMap<K, V>::allocate(unsigned int newSize)
370 {
371  if(newSize <= size)
372  return;
373 
374  K** nkeys = new K*[newSize];
375  V** nvalues = new V*[newSize];
376 
377  if(keys != nullptr) {
378  for(unsigned i = 0; i < size; i++) {
379  nkeys[i] = keys[i];
380  nvalues[i] = values[i];
381  }
382 
383  delete[] keys;
384  delete[] values;
385  }
386  for(unsigned i = size; i < newSize; i++) {
387  nkeys[i] = new K();
388  nvalues[i] = new V();
389  }
390 
391  keys = nkeys;
392  values = nvalues;
393  size = newSize;
394 }
395 
396 template <typename K, typename V> int HashMap<K, V>::indexOf(const K& key) const
397 {
398  for(unsigned i = 0; i < currentIndex; i++) {
399  if(cb_comparator) {
400  if(cb_comparator(key, *keys[i])) {
401  return i;
402  }
403  } else {
404  if(key == *keys[i]) {
405  return i;
406  }
407  }
408  }
409  return -1;
410 }
411 
412 template <typename K, typename V> void HashMap<K, V>::removeAt(unsigned index)
413 {
414  if(index >= currentIndex)
415  return;
416 
417  for(unsigned i = index + 1; i < size; i++) {
418  *keys[i - 1] = *keys[i];
419  *values[i - 1] = *values[i];
420  }
421 
422  currentIndex--;
423 }
424 
425 template <typename K, typename V> void HashMap<K, V>::clear()
426 {
427  if(keys != nullptr) {
428  for(unsigned i = 0; i < size; i++) {
429  delete keys[i];
430  delete values[i];
431  }
432  delete[] keys;
433  delete[] values;
434  keys = nullptr;
435  values = nullptr;
436  }
437  currentIndex = 0;
438  size = 0;
439 }
440 
441 template <typename K, typename V> void HashMap<K, V>::setMultiple(const HashMap<K, V>& map)
442 {
443  for(unsigned i = 0; i < map.count(); i++) {
444  (*this)[map.keyAt(i)] = *(map.values)[i];
445  }
446 }
Iterator(Map &map, unsigned index)
Definition: WHashMap.h:90
bool operator==(const Iterator &rhs) const
Definition: WHashMap.h:114
void allocate(unsigned int newSize)
Definition: WHashMap.h:369
const V & operator[](const K &key) const
Definition: WHashMap.h:242
Iterator< true > end() const
Definition: WHashMap.h:337
HashMap class template.
Definition: WHashMap.h:39
typename std::conditional< is_const, const HashMap, HashMap >::type Map
Definition: WHashMap.h:85
BaseElement< false > Element
Definition: WHashMap.h:78
void clear()
Definition: WHashMap.h:425
const K & keyAt(unsigned int idx) const
Definition: WHashMap.h:185
ElementConst operator*() const
Definition: WHashMap.h:129
Iterator & operator++()
Definition: WHashMap.h:94
long map(long, long, long, long, long)
BaseElement(const K &key, Value &value)
Definition: WHashMap.h:48
Iterator< true > begin() const
Definition: WHashMap.h:332
const V & valueAt(unsigned int idx) const
Definition: WHashMap.h:210
Iterator< false > end()
Definition: WHashMap.h:327
Value & value()
Definition: WHashMap.h:57
Iterator< false > begin()
Definition: WHashMap.h:322
const V & value() const
Definition: WHashMap.h:62
~HashMap()
Definition: WHashMap.h:159
Comparator cb_comparator
Definition: WHashMap.h:348
void setNullValue(const V &nullv)
Definition: WHashMap.h:317
Iterator operator+=(size_t distance)
Definition: WHashMap.h:107
const K & key() const
Definition: WHashMap.h:52
uint16_t size
Definition: WHashMap.h:347
typename std::conditional< is_const, const V, V >::type Value
Definition: WHashMap.h:86
V nil
Definition: WHashMap.h:345
uint16_t currentIndex
Definition: WHashMap.h:346
BaseElement & operator=(const V &value)
Definition: WHashMap.h:67
K & keyAt(unsigned int idx)
Definition: WHashMap.h:193
Definition: WHashMap.h:44
void setMultiple(const HashMap< K, V > &map)
Definition: WHashMap.h:441
Iterator operator++(int)
Definition: WHashMap.h:100
typename std::conditional< is_const, const V, V >::type Value
Definition: WHashMap.h:46
K ** keys
Definition: WHashMap.h:343
BaseElement< is_const > operator*()
Definition: WHashMap.h:124
bool operator!=(const Iterator &rhs) const
Definition: WHashMap.h:119
V & valueAt(unsigned int idx)
Definition: WHashMap.h:218
HashMap()
Definition: WHashMap.h:144
Definition: WHashMap.h:82
int indexOf(const K &key) const
Definition: WHashMap.h:396
BaseElement< true > ElementConst
Definition: WHashMap.h:79
V ** values
Definition: WHashMap.h:344
bool contains(const K &key) const
Definition: WHashMap.h:284
void removeAt(unsigned index)
Definition: WHashMap.h:412
HashMap(Comparator compare)
Definition: WHashMap.h:155
bool(*)(const mqtt_type_t &, const mqtt_type_t &) Comparator
Definition: WHashMap.h:42
unsigned int count() const
Definition: WHashMap.h:171