ROSE  0.11.109.0
HashMap.h
1 // WARNING: Changes to this file must be contributed back to Sawyer or else they will
2 // be clobbered by the next update from Sawyer. The Sawyer repository is at
3 // https://github.com/matzke1/sawyer.
4 
5 
6 
7 
8 #ifndef Sawyer_HashMap_H
9 #define Sawyer_HashMap_H
10 
11 #include <Sawyer/Optional.h>
12 #include <Sawyer/Sawyer.h>
13 
14 #include <boost/range/iterator_range.hpp>
15 #include <boost/serialization/access.hpp>
16 #include <boost/serialization/nvp.hpp>
17 #include <boost/serialization/split_member.hpp>
18 #include <boost/unordered_map.hpp>
19 #include <stdexcept>
20 
21 namespace Sawyer {
22 namespace Container {
23 
31 template<class K, class T, class H = boost::hash<K>, class C = std::equal_to<K>,
32  class A = std::allocator<std::pair<const K, T> > >
33 class HashMap {
34 public:
35  typedef K Key;
36  typedef T Value;
37  typedef H Hasher;
38  typedef C Comparator;
39  typedef A Allocator;
41 private:
42  typedef boost::unordered_map<Key, Value, Hasher, Comparator, Allocator> ImplMap;
43  ImplMap map_;
44 
45 private:
46  friend class boost::serialization::access;
47 
48  // Apparently no serialization functions for boost::unordered_map, so do it the hard way.
49  template<class S>
50  void save(S &s, const unsigned /*verion*/) const {
51  size_t nElmts = map_.size();
52  s & BOOST_SERIALIZATION_NVP(nElmts);
53  for (typename ImplMap::const_iterator iter = map_.begin(); iter != map_.end(); ++iter) {
54  const Key &key = iter->first;
55  s & BOOST_SERIALIZATION_NVP(key);
56  const Value &value = iter->second;
57  s & BOOST_SERIALIZATION_NVP(value);
58  }
59  }
60 
61  template<class S>
62  void load(S & s, const unsigned /*version*/) {
63  size_t nElmts;
64  s & BOOST_SERIALIZATION_NVP(nElmts);
65  for (size_t i=0; i<nElmts; ++i) {
66  Key key;
67  s & BOOST_SERIALIZATION_NVP(key);
68  Value value;
69  s & BOOST_SERIALIZATION_NVP(value);
70  map_.insert(std::make_pair(key, value));
71  }
72  }
73 
74  BOOST_SERIALIZATION_SPLIT_MEMBER();
75 
76 public:
80  class Node: private ImplMap::value_type {
81  // This class MUST be binary compatible with ImplMap::value_type
82  public:
83  explicit Node(const std::pair<const Key, Value> &pair)
84  : std::pair<const Key, Value>(pair) {}
85 
86  Node(const Key &key, Value &value)
87  : std::pair<const Key, Value>(key, value) {}
88 
92  const Key& key() const { return this->first; }
93 
99  Value& value() { return this->second; }
100  const Value& value() const { return this->second; }
102  };
103 
105  // Iterators
107 private:
108  template<class Derived, class Value, class BaseIterator>
109  class ForwardIterator {
110  public:
111  // Five standard iterator types
112  using iterator_category = std::forward_iterator_tag;
113  using value_type = Value;
114  using difference_type = std::ptrdiff_t;
115  using pointer = Value*;
116  using reference = Value&;
117 
118  protected:
119  BaseIterator base_;
120  ForwardIterator() {}
121  ForwardIterator(const BaseIterator &base): base_(base) {}
122  public:
123  Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
124  Derived& operator++() { ++base_; return *derived(); }
125  Derived operator++(int) { Derived old = *derived(); ++*this; return old; }
126  template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base(); }
127  template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base(); }
128  const BaseIterator& base() const { return base_; }
129  protected:
130  Derived* derived() { return static_cast<Derived*>(this); }
131  const Derived* derived() const { return static_cast<const Derived*>(this); }
132  };
133 
134 public:
139  class NodeIterator: public ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> {
140  typedef ForwardIterator<NodeIterator, Node, typename ImplMap::iterator> Super;
141  public:
142  NodeIterator() {}
143  NodeIterator(const NodeIterator &other): Super(other) {}
144  Node& operator*() const { return *(Node*)&*this->base_; } // boost iter's value cast to our own node type
145  Node* operator->() const { return (Node*)&*this->base_; }
146  private:
147  friend class HashMap;
148  NodeIterator(const typename ImplMap::iterator &base): Super(base) {}
149  };
150 
155  class ConstNodeIterator: public ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> {
156  typedef ForwardIterator<ConstNodeIterator, const Node, typename ImplMap::const_iterator> Super;
157  public:
158  ConstNodeIterator() {}
159  ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
160  ConstNodeIterator(const NodeIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
161  const Node& operator*() const { return *(const Node*)&*this->base_; }
162  const Node* operator->() const { return (const Node*)&*this->base_; }
163  private:
164  friend class HashMap;
165  ConstNodeIterator(const typename ImplMap::const_iterator &base): Super(base) {}
166  ConstNodeIterator(const typename ImplMap::iterator &base): Super(typename ImplMap::const_iterator(base)) {}
167  };
168 
173  class ConstKeyIterator: public ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> {
174  typedef ForwardIterator<ConstKeyIterator, const Key, typename ImplMap::const_iterator> Super;
175  public:
176  ConstKeyIterator() {}
177  ConstKeyIterator(const ConstKeyIterator &other): Super(other) {}
178  ConstKeyIterator(const NodeIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
179  ConstKeyIterator(const ConstNodeIterator &other): Super(other.base()) {}
180  const Key& operator*() const { return this->base()->first; }
181  const Key* operator->() const { return &this->base()->first; }
182  };
183 
188  class ValueIterator: public ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> {
189  typedef ForwardIterator<ValueIterator, Value, typename ImplMap::iterator> Super;
190  public:
191  ValueIterator() {}
192  ValueIterator(const ValueIterator &other): Super(other) {}
193  ValueIterator(const NodeIterator &other): Super(other.base()) {}
194  Value& operator*() const { return this->base()->second; }
195  Value* operator->() const { return &this->base()->second; }
196  };
197 
202  class ConstValueIterator: public ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> {
203  typedef ForwardIterator<ConstValueIterator, const Value, typename ImplMap::const_iterator> Super;
204  public:
205  ConstValueIterator() {}
206  ConstValueIterator(const ConstValueIterator &other): Super(other) {}
207  ConstValueIterator(const ValueIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
208  ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
209  ConstValueIterator(const NodeIterator &other): Super(typename ImplMap::const_iterator(other.base())) {}
210  const Value& operator*() const { return this->base()->second; }
211  const Value* operator->() const { return &this->base()->second; }
212  };
213 
215  // Constructors
217 public:
218 
222  HashMap() {}
223 
225  HashMap(size_t n, const Hasher &hasher = Hasher(), const Comparator &cmp = Comparator(), const Allocator& alloc = Allocator())
226  : map_(n, hasher, cmp, alloc) {}
227 
229  HashMap(const HashMap& other)
230  : map_(other.map_) {}
231 
236  template<class K2, class T2, class H2, class C2, class A2>
238  typedef typename HashMap<K2, T2, H2, C2, A2>::ConstNodeIterator OtherIterator;
239  boost::iterator_range<OtherIterator> otherNodes = other.nodes();
240  for (OtherIterator otherIter = otherNodes.begin(); otherIter != otherNodes.end(); ++otherIter)
241  map_.insert(std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
242  }
243 
245  template<class K2, class T2, class H2, class C2, class A2>
247  typedef typename HashMap<K2, T2, H2, C2, A2>::ConstNodeIterator OtherIterator;
248  clear();
249  boost::iterator_range<OtherIterator> otherNodes = other.nodes();
250  for (OtherIterator otherIter = otherNodes.begin(); otherIter != otherNodes.end(); ++otherIter)
251  map_.insert(std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
252  return *this;
253  }
254 
256  // Iteration
258 public:
259 
265  boost::iterator_range<NodeIterator> nodes() {
266  return boost::iterator_range<NodeIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
267  }
268  boost::iterator_range<ConstNodeIterator> nodes() const {
269  return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
270  }
278  boost::iterator_range<ConstKeyIterator> keys() {
279  return boost::iterator_range<ConstKeyIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
280  }
281  boost::iterator_range<ConstKeyIterator> keys() const {
282  return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
283  }
292  boost::iterator_range<ValueIterator> values() {
293  return boost::iterator_range<ValueIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
294  }
295  boost::iterator_range<ConstValueIterator> values() const {
296  return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
297  }
300  // Size and capacity
303 public:
304 
308  bool isEmpty() const {
309  return map_.empty();
310  }
311 
316  size_t size() const {
317  return map_.size();
318  }
319 
321  size_t nBuckets() const {
322  return map_.bucket_count();
323  }
324 
326  double loadFactor() const {
327  return map_.load_factor();
328  }
329 
333  double maxLoadFactor() const {
334  return map_.max_load_factor();
335  }
336  void maxLoadFactor(double mlf) {
337  map_.max_load_factor(mlf);
338  }
342  void rehash(size_t nBuckets) {
343  map_.rehash(nBuckets);
344  }
345 
347  // Searching
349 public:
350 
357  NodeIterator find(const Key &key) {
358  return map_.find(key);
359  }
360  ConstNodeIterator find(const Key &key) const {
361  return map_.find(key);
362  }
369  bool exists(const Key &key) const {
370  return map_.find(key) != map_.end();
371  }
372 
374  // Accessors
376 public:
377 
390  Value& operator[](const Key &key) {
391  return get(key);
392  }
393  const Value& operator[](const Key &key) const {
394  return get(key);
395  }
406  Value& get(const Key &key) {
407  typename ImplMap::iterator found = map_.find(key);
408  if (found == map_.end())
409  throw std::domain_error("key lookup failure; key is not in map domain");
410  return found->second;
411  }
412  const Value& get(const Key &key) const {
413  typename ImplMap::const_iterator found = map_.find(key);
414  if (found == map_.end())
415  throw std::domain_error("key lookup failure; key is not in map domain");
416  return found->second;
417  }
442  Optional<Value> getOptional(const Key &key) const {
443  typename ImplMap::const_iterator found = map_.find(key);
444  return found == map_.end() ? Optional<Value>() : Optional<Value>(found->second);
445  }
446 
454  Value& getOrElse(const Key &key, Value &dflt) {
455  typename ImplMap::iterator found = map_.find(key);
456  return found == map_.end() ? dflt : found->second;
457  }
458  const Value& getOrElse(const Key &key, const Value &dflt) const {
459  typename ImplMap::const_iterator found = map_.find(key);
460  return found == map_.end() ? dflt : found->second;
461  }
468  const Value& getOrDefault(const Key &key) const {
469  static const Value dflt;
470  typename ImplMap::const_iterator found = map_.find(key);
471  return found==map_.end() ? dflt : found->second;
472  }
473 
475  // Mutators
477 public:
478 
485  HashMap& insert(const Key &key, const Value &value) {
486  std::pair<typename ImplMap::iterator, bool> inserted = map_.insert(std::make_pair(key, value));
487  if (!inserted.second)
488  inserted.first->second = value;
489  return *this;
490  }
491 
498  HashMap& insertDefault(const Key &key) {
499  return insert(key, Value());
500  }
501 
519  template<class OtherNodeIterator>
520  HashMap& insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end) {
521  for (OtherNodeIterator otherIter = begin; otherIter != end; ++otherIter)
522  insert(Key(otherIter->key()), Value(otherIter->value()));
523  return *this;
524  }
525  template<class OtherNodeIterator>
526  HashMap& insertMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
527  return insertMultiple(range.begin(), range.end());
528  }
538  Value& insertMaybe(const Key &key, const Value &value) {
539  return map_.insert(std::make_pair(key, value)).first->second;
540  }
541 
549  Value& insertMaybeDefault(const Key &key) {
550  return insertMaybe(key, Value());
551  }
552 
559  template<class OtherNodeIterator>
560  HashMap& insertMaybeMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
561  for (OtherNodeIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
562  insertMaybe(Key(otherIter->key()), Value(otherIter->value()));
563  return *this;
564  }
565 
571  map_.clear();
572  return *this;
573  }
574 
581  HashMap& erase(const Key &key) {
582  map_.erase(key);
583  return *this;
584  }
585 
593  template<class OtherKeyIterator>
594  HashMap& eraseMultiple(const boost::iterator_range<OtherKeyIterator> &range) {
595  for (OtherKeyIterator otherIter = range.begin(); otherIter != range.end(); ++otherIter)
596  map_.erase(Key(*otherIter));
597  return *this;
598  }
599 
607  HashMap& eraseAt(const NodeIterator &iter) {
608  map_.erase(iter.base());
609  return *this;
610  }
611  HashMap& eraseAt(const ConstKeyIterator &iter) {
612  map_.erase(iter.base());
613  return *this;
614  }
615  HashMap& eraseAt(const ValueIterator &iter) {
616  map_.erase(iter.base());
617  return *this;
618  }
628  template<class Iter>
629  HashMap& eraseAtMultiple(const Iter &begin, const Iter &end) {
630  map_.erase(begin.base(), end.base());
631  return *this;
632  }
633  template<class Iter>
634  HashMap& eraseAtMultiple(const boost::iterator_range<Iter> &range) {
635  map_.erase(range.begin().base(), range.end().base());
636  return *this;
637  }
639 };
640 
641 } // namespace
642 } // namespace
643 
644 #endif
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
Definition: HashMap.h:268
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition: HashMap.h:278
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Definition: HashMap.h:549
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Definition: HashMap.h:292
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Definition: HashMap.h:265
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
Definition: HashMap.h:281
const Value & operator[](const Key &key) const
Return a reference to an existing value.
Definition: HashMap.h:393
H Hasher
Functor for hashing keys.
Definition: HashMap.h:37
HashMap & insertMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Insert multiple values.
Definition: HashMap.h:526
Value & getOrElse(const Key &key, Value &dflt)
Lookup and return a value or something else.
Definition: HashMap.h:454
const Key & key() const
Key part of key/value node.
Definition: HashMap.h:92
HashMap(const HashMap< K2, T2, H2, C2, A2 > &other)
Copy constructor.
Definition: HashMap.h:237
ConstNodeIterator find(const Key &key) const
Find a node by key.
Definition: HashMap.h:360
HashMap & insertMaybeMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Conditionally insert multiple key/value pairs.
Definition: HashMap.h:560
Value & value()
Value part of key/value node.
Definition: HashMap.h:99
Forward iterator over key/value nodes.
Definition: HashMap.h:139
Forward iterator over values.
Definition: HashMap.h:188
const Value & getOrElse(const Key &key, const Value &dflt) const
Lookup and return a value or something else.
Definition: HashMap.h:458
bool isEmpty() const
Determine whether this container is empty.
Definition: HashMap.h:308
HashMap & operator=(const HashMap< K2, T2, H2, C2, A2 > &other)
Assignment operator.
Definition: HashMap.h:246
double maxLoadFactor() const
Property: Maximum allowed load faster before automatic rehash.
Definition: HashMap.h:333
Name space for the entire library.
Definition: FeasiblePath.h:767
void maxLoadFactor(double mlf)
Property: Maximum allowed load faster before automatic rehash.
Definition: HashMap.h:336
size_t size() const
Number of nodes, keys, or values in this container.
Definition: HashMap.h:316
HashMap()
Default constructor.
Definition: HashMap.h:222
HashMap & insertDefault(const Key &key)
Insert or update a key with a default value.
Definition: HashMap.h:498
Type for stored nodes.
Definition: HashMap.h:80
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: HashMap.h:442
A Allocator
Functor for allocating node memory.
Definition: HashMap.h:39
HashMap & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: HashMap.h:485
HashMap & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
Definition: HashMap.h:629
HashMap & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
Definition: HashMap.h:607
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
Definition: HashMap.h:295
NodeIterator find(const Key &key)
Find a node by key.
Definition: HashMap.h:357
HashMap & eraseMultiple(const boost::iterator_range< OtherKeyIterator > &range)
Remove keys stored in another HashMap.
Definition: HashMap.h:594
HashMap(size_t n, const Hasher &hasher=Hasher(), const Comparator &cmp=Comparator(), const Allocator &alloc=Allocator())
Constructs a hash map with at least n buckets.
Definition: HashMap.h:225
HashMap & eraseAt(const ValueIterator &iter)
Remove a node by iterator.
Definition: HashMap.h:615
Value & insertMaybe(const Key &key, const Value &value)
Conditionally insert a new key/value pair.
Definition: HashMap.h:538
Container associating values with keys.
Definition: HashMap.h:33
void rehash(size_t nBuckets)
Change number of buckets.
Definition: HashMap.h:342
Forward iterator over key/value nodes.
Definition: HashMap.h:155
const Value & value() const
Value part of key/value node.
Definition: HashMap.h:100
HashMap(const HashMap &other)
Copy constructor.
Definition: HashMap.h:229
HashMap & clear()
Remove all nodes.
Definition: HashMap.h:570
Forward iterator over values.
Definition: HashMap.h:202
K Key
Type of keys.
Definition: HashMap.h:35
Value & operator[](const Key &key)
Return a reference to an existing value.
Definition: HashMap.h:390
C Comparator
Functor for comparing keys.
Definition: HashMap.h:38
double loadFactor() const
Average number of nodes per bucket.
Definition: HashMap.h:326
HashMap & eraseAtMultiple(const boost::iterator_range< Iter > &range)
Remove multiple nodes by iterator range.
Definition: HashMap.h:634
HashMap & eraseAt(const ConstKeyIterator &iter)
Remove a node by iterator.
Definition: HashMap.h:611
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: HashMap.h:468
Forward iterator over keys.
Definition: HashMap.h:173
size_t nBuckets() const
Number of buckets.
Definition: HashMap.h:321
bool exists(const Key &key) const
Determine if a key exists.
Definition: HashMap.h:369
T Value
Type of values.
Definition: HashMap.h:36
HashMap & erase(const Key &key)
Remove a node with specified key.
Definition: HashMap.h:581
HashMap & insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end)
Insert multiple values.
Definition: HashMap.h:520