ROSE  0.9.10.91
Sawyer/Map.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_Map_H
9 #define Sawyer_Map_H
10 
11 #include <Sawyer/Interval.h>
12 #include <Sawyer/Optional.h>
13 #include <Sawyer/Sawyer.h>
14 #include <boost/range/iterator_range.hpp>
15 #include <boost/serialization/access.hpp>
16 #include <boost/serialization/nvp.hpp>
17 #include <boost/serialization/map.hpp>
18 #include <stdexcept>
19 
20 namespace Sawyer {
21 
47 namespace Container {
48 
62 template<class K,
63  class T,
64  class Cmp = std::less<K>,
65  class Alloc = std::allocator<std::pair<const K, T> > >
66 class Map {
67 public:
68  typedef K Key;
69  typedef T Value;
70  typedef Cmp Comparator;
71  typedef Alloc Allocator;
73 private:
74  typedef std::map<Key, Value, Comparator, Alloc> StlMap;
75  StlMap map_;
76 
77 private:
78  friend class boost::serialization::access;
79 
80  template<class S>
81  void serialize(S &s, const unsigned /*version*/) {
82  s & BOOST_SERIALIZATION_NVP(map_);
83  }
84 
85 public:
89  class Node: private std::pair<const Key, Value> {
90  // This class MUST BE binary compatible with its super class (see NodeIterator::operator* below)
91  public:
92  explicit Node(const std::pair<const Key, Value> &pair): std::pair<const Key, Value>(pair) {}
93  Node(const Key &key, Value &value): std::pair<const Key, Value>(key, value) {}
94  public:
98  const Key& key() const { return this->first; }
99 
105  Value& value() { return this->second; }
106  const Value& value() const { return this->second; }
108  };
109 
111  // Iterators
113 private:
114  template<class Derived, class Value, class BaseIterator>
115  class BidirectionalIterator: public std::iterator<std::bidirectional_iterator_tag, Value> {
116  protected:
117  BaseIterator base_;
118  BidirectionalIterator() {}
119  BidirectionalIterator(const BaseIterator &base): base_(base) {}
120  public:
121  Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
122  Derived& operator++() { ++base_; return *derived(); }
123  Derived operator++(int) { Derived old=*derived(); ++*this; return old; }
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 BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> {
140  typedef BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> Super;
141  public:
142  NodeIterator() {}
143  NodeIterator(const NodeIterator &other): Super(other) {}
144  // std::map stores std::pair nodes, but we want to return Node, which must have the same layout.
145  Node& operator*() const { return *(Node*)&*this->base_; }
146  Node* operator->() const { return (Node*)&*this->base_; }
147  private:
148  friend class Map;
149  NodeIterator(const typename StlMap::iterator &base): Super(base) {}
150  };
151 
156  class ConstNodeIterator: public BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> {
157  typedef BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> Super;
158  public:
159  ConstNodeIterator() {}
160  ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
161  ConstNodeIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
162  // std::map stores std::pair nodes, but we want to return Node, which must have the same layout.
163  const Node& operator*() const { return *(const Node*)&*this->base_; }
164  const Node* operator->() const { return (const Node*)&*this->base_; }
165  private:
166  friend class Map;
167  ConstNodeIterator(const typename StlMap::const_iterator &base): Super(base) {}
168  ConstNodeIterator(const typename StlMap::iterator &base): Super(typename StlMap::const_iterator(base)) {}
169  };
170 
175  class ConstKeyIterator: public BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> {
176  typedef BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> Super;
177  public:
178  ConstKeyIterator() {}
179  ConstKeyIterator(const ConstKeyIterator &other): Super(other) {}
180  ConstKeyIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
181  ConstKeyIterator(const ConstNodeIterator &other): Super(other.base()) {}
182  const Key& operator*() const { return this->base()->first; }
183  const Key* operator->() const { return &this->base()->first; }
184  };
185 
190  class ValueIterator: public BidirectionalIterator<ValueIterator, Value, typename StlMap::iterator> {
191  typedef BidirectionalIterator<ValueIterator, Value, typename StlMap::iterator> Super;
192  public:
193  ValueIterator() {}
194  ValueIterator(const ValueIterator &other): Super(other) {}
195  ValueIterator(const NodeIterator &other): Super(other.base()) {}
196  Value& operator*() const { return this->base()->second; }
197  Value* operator->() const { return &this->base()->second; }
198  };
199 
204  class ConstValueIterator: public BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> {
205  typedef BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> Super;
206  public:
207  ConstValueIterator() {}
208  ConstValueIterator(const ConstValueIterator &other): Super(other) {}
209  ConstValueIterator(const ValueIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
210  ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
211  ConstValueIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
212  const Value& operator*() const { return this->base()->second; }
213  const Value* operator->() const { return &this->base()->second; }
214  };
215 
216 
218  // Constructors
220 public:
221 
225  Map() {}
226 
230  explicit Map(const Comparator &comparator, const Allocator &allocator = Allocator())
231  : map_(comparator, allocator) {}
232 
234  Map(const Map& other) {
235  map_ = other.map_;
236  }
237 
242  template<class Key2, class T2, class Cmp2, class Alloc2>
244  typedef typename Map<Key2, T2, Cmp2, Alloc2>::ConstNodeIterator OtherIterator;
245  boost::iterator_range<OtherIterator> otherNodes = other.nodes();
246  for (OtherIterator otherIter=otherNodes.begin(); otherIter!=otherNodes.end(); ++otherIter)
247  map_.insert(map_.end(), std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
248  }
249 
253  template<class Key2, class T2, class Cmp2, class Alloc2>
255  typedef typename Map<Key2, T2, Cmp2, Alloc2>::ConstNodeIterator OtherIterator;
256  clear();
257  boost::iterator_range<OtherIterator> otherNodes = other.nodes();
258  for (OtherIterator otherIter=otherNodes.begin(); otherIter!=otherNodes.end(); ++otherIter)
259  map_.insert(map_.end(), std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
260  return *this;
261  }
262 
263 
265  // Iteration
267 public:
273  boost::iterator_range<NodeIterator> nodes() {
274  return boost::iterator_range<NodeIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
275  }
276  boost::iterator_range<ConstNodeIterator> nodes() const {
277  return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
278  }
286  boost::iterator_range<ConstKeyIterator> keys() {
287  return boost::iterator_range<ConstKeyIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
288  }
289  boost::iterator_range<ConstKeyIterator> keys() const {
290  return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
291  }
300  boost::iterator_range<ValueIterator> values() {
301  return boost::iterator_range<ValueIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
302  }
303  boost::iterator_range<ConstValueIterator> values() const {
304  return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
305  }
309  // Size and capacity
312 public:
313 
317  bool isEmpty() const {
318  return map_.empty();
319  }
320 
324  size_t size() const {
325  return map_.size();
326  }
327 
329  Key least() const {
330  ASSERT_forbid(isEmpty());
331  return map_.begin()->first;
332  }
333 
335  Key greatest() const {
336  ASSERT_forbid(isEmpty());
337  typename StlMap::const_iterator last = map_.end();
338  --last;
339  return last->first;
340  }
341 
349  Interval<Key> hull() const {
351  }
352 
353 
355  // Searching
357 public:
358 
366  NodeIterator find(const Key &key) {
367  return map_.find(key);
368  }
369  ConstNodeIterator find(const Key &key) const {
370  return map_.find(key);
371  }
379  bool exists(const Key &key) const {
380  return map_.find(key)!=map_.end();
381  }
382 
392  NodeIterator lowerBound(const Key &key) {
393  return map_.lower_bound(key);
394  }
395  ConstNodeIterator lowerBound(const Key &key) const {
396  return map_.lower_bound(key);
397  }
409  NodeIterator upperBound(const Key &key) {
410  return map_.upper_bound(key);
411  }
412  ConstNodeIterator upperBound(const Key &key) const {
413  return map_.upper_bound(key);
414  }
418  // Accessors
421 public:
422 
435  Value& operator[](const Key &key) {
436  return get(key);
437  }
438  const Value& operator[](const Key &key) const {
439  return get(key);
440  }
451  Value& get(const Key &key) {
452  typename StlMap::iterator found = map_.find(key);
453  if (found==map_.end())
454  throw std::domain_error("key lookup failure; key is not in map domain");
455  return found->second;
456  }
457  const Value& get(const Key &key) const {
458  typename StlMap::const_iterator found = map_.find(key);
459  if (found==map_.end())
460  throw std::domain_error("key lookup failure; key is not in map domain");
461  return found->second;
462  }
488  Optional<Value> getOptional(const Key &key) const {
489  typename StlMap::const_iterator found = map_.find(key);
490  return found == map_.end() ? Optional<Value>() : Optional<Value>(found->second);
491  }
492 
500  Value& getOrElse(const Key &key, Value &dflt) {
501  typename StlMap::iterator found = map_.find(key);
502  return found == map_.end() ? dflt : found->second;
503  }
504  const Value& getOrElse(const Key &key, const Value &dflt) const {
505  typename StlMap::const_iterator found = map_.find(key);
506  return found == map_.end() ? dflt : found->second;
507  }
515  const Value& getOrDefault(const Key &key) const {
516  static const Value dflt;
517  typename StlMap::const_iterator found = map_.find(key);
518  return found==map_.end() ? dflt : found->second;
519  }
520 
522  // Mutators
524 public:
525 
532  Map& insert(const Key &key, const Value &value) {
533  std::pair<typename StlMap::iterator, bool> inserted = map_.insert(std::make_pair(key, value));
534  if (!inserted.second)
535  inserted.first->second = value;
536  return *this;
537  }
538 
545  Map& insertDefault(const Key &key) {
546  map_[key] = T();
547  return *this;
548  }
549 
567  template<class OtherNodeIterator>
568  Map& insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end) {
569  for (OtherNodeIterator otherIter=begin; otherIter!=end; ++otherIter)
570  insert(Key(otherIter->key()), Value(otherIter->value()));
571  return *this;
572  }
573  template<class OtherNodeIterator>
574  Map& insertMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
575  return insertMultiple(range.begin(), range.end());
576  }
586  Value& insertMaybe(const Key &key, const Value &value) {
587  return map_.insert(std::make_pair(key, value)).first->second;
588  }
589 
597  Value& insertMaybeDefault(const Key &key) {
598  return map_.insert(std::make_pair(key, T())).first->second;
599  }
600 
607  template<class OtherNodeIterator>
608  Map& insertMaybeMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
609  for (OtherNodeIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
610  insertMaybe(Key(otherIter->key()), Value(otherIter->value()));
611  return *this;
612  }
613 
618  Map& clear() {
619  map_.clear();
620  return *this;
621  }
622 
630  Map& erase(const Key &key) {
631  map_.erase(key);
632  return *this;
633  }
634 
643  template<class OtherKeyIterator>
644  Map& eraseMultiple(const boost::iterator_range<OtherKeyIterator> &range) {
645  for (OtherKeyIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
646  map_.erase(Key(*otherIter));
647  return *this;
648  }
649 
657  Map& eraseAt(const NodeIterator &iter) {
658  map_.erase(iter.base());
659  return *this;
660  }
661  Map& eraseAt(const ConstKeyIterator &iter) {
662  // std::map can't erase using a const_iterator
663  ASSERT_require(iter != keys().end());
664  typename StlMap::iterator stdIter = map_.find(*iter);
665  ASSERT_require(stdIter != map_.end());
666  map_.erase(stdIter);
667  return *this;
668  }
669  Map& eraseAt(const ValueIterator &iter) {
670  map_.erase(iter.base());
671  return *this;
672  }
682  template<class Iter>
683  Map& eraseAtMultiple(const Iter &begin, const Iter &end) {
684  map_.erase(begin.base(), end.base());
685  return *this;
686  }
687  template<class Iter>
688  Map& eraseAtMultiple(const boost::iterator_range<Iter> &range) {
689  map_.erase(range.begin().base(), range.end().base());
690  return *this;
691  }
694 };
695 
696 } // namespace
697 } // namespace
698 
699 #endif
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
Definition: Sawyer/Map.h:289
Map(const Map &other)
Copy constructor.
Definition: Sawyer/Map.h:234
bool exists(const Key &key) const
Determine if a key exists.
Definition: Sawyer/Map.h:379
Value & operator[](const Key &key)
Return a reference to an existing value.
Definition: Sawyer/Map.h:435
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: Sawyer/Map.h:488
const Value & operator[](const Key &key) const
Return a reference to an existing value.
Definition: Sawyer/Map.h:438
Map()
Default constructor.
Definition: Sawyer/Map.h:225
Value & value()
Value part of key/value node.
Definition: Sawyer/Map.h:105
ConstNodeIterator upperBound(const Key &key) const
Find a node close to a key.
Definition: Sawyer/Map.h:412
Map(const Comparator &comparator, const Allocator &allocator=Allocator())
Constructs an empty map.
Definition: Sawyer/Map.h:230
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
Definition: Sawyer/Map.h:276
const Value & getOrElse(const Key &key, const Value &dflt) const
Lookup and return a value or something else.
Definition: Sawyer/Map.h:504
ConstNodeIterator lowerBound(const Key &key) const
Find a node close to a key.
Definition: Sawyer/Map.h:395
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Definition: Sawyer/Map.h:597
Map & eraseAt(const ValueIterator &iter)
Remove a node by iterator.
Definition: Sawyer/Map.h:669
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:618
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Definition: Sawyer/Map.h:300
Cmp Comparator
Type of comparator, third template argument.
Definition: Sawyer/Map.h:70
Name space for the entire library.
Definition: Access.h:13
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:139
Alloc Allocator
Type of allocator, fourth template argument.
Definition: Sawyer/Map.h:71
Value & getOrElse(const Key &key, Value &dflt)
Lookup and return a value or something else.
Definition: Sawyer/Map.h:500
bool isEmpty() const
Determines whether this container is empty.
Definition: Sawyer/Map.h:317
Map & insertDefault(const Key &key)
Insert or update a key with a default value.
Definition: Sawyer/Map.h:545
ConstNodeIterator find(const Key &key) const
Find a node by key.
Definition: Sawyer/Map.h:369
Map & insertMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Insert multiple values.
Definition: Sawyer/Map.h:574
NodeIterator lowerBound(const Key &key)
Find a node close to a key.
Definition: Sawyer/Map.h:392
Bidirectional iterator over values.
Definition: Sawyer/Map.h:190
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
Definition: Sawyer/Map.h:303
const Key & key() const
Key part of key/value node.
Definition: Sawyer/Map.h:98
Map & insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end)
Insert multiple values.
Definition: Sawyer/Map.h:568
Bidirectional iterator over values.
Definition: Sawyer/Map.h:204
Map & operator=(const Map< Key2, T2, Cmp2, Alloc2 > &other)
Make this map be a copy of another map.
Definition: Sawyer/Map.h:254
Interval< Key > hull() const
Returns the range of keys in this map.
Definition: Sawyer/Map.h:349
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:515
const Value & value() const
Value part of key/value node.
Definition: Sawyer/Map.h:106
Map & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
Definition: Sawyer/Map.h:657
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition: Sawyer/Map.h:286
Map & insertMaybeMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Conditionally insert multiple key/value pairs.
Definition: Sawyer/Map.h:608
Map & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
Definition: Sawyer/Map.h:683
T Value
Type for values associated with each key.
Definition: Sawyer/Map.h:69
Map & erase(const Key &key)
Remove a node with specified key.
Definition: Sawyer/Map.h:630
Range of values delimited by endpoints.
Definition: Interval.h:33
Map(const Map< Key2, T2, Cmp2, Alloc2 > &other)
Copy constructor.
Definition: Sawyer/Map.h:243
Map & eraseAt(const ConstKeyIterator &iter)
Remove a node by iterator.
Definition: Sawyer/Map.h:661
NodeIterator find(const Key &key)
Find a node by key.
Definition: Sawyer/Map.h:366
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: Sawyer/Map.h:532
Key least() const
Returns the minimum key.
Definition: Sawyer/Map.h:329
Bidirectional iterator over keys.
Definition: Sawyer/Map.h:175
NodeIterator upperBound(const Key &key)
Find a node close to a key.
Definition: Sawyer/Map.h:409
Map & eraseMultiple(const boost::iterator_range< OtherKeyIterator > &range)
Remove keys stored in another Map.
Definition: Sawyer/Map.h:644
Key greatest() const
Returns the maximum key.
Definition: Sawyer/Map.h:335
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Definition: Sawyer/Map.h:273
K Key
Type for keys.
Definition: Sawyer/Map.h:68
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:324
Container associating values with keys.
Definition: Sawyer/Map.h:66
Value & insertMaybe(const Key &key, const Value &value)
Conditionally insert a new key/value pair.
Definition: Sawyer/Map.h:586
Map & eraseAtMultiple(const boost::iterator_range< Iter > &range)
Remove multiple nodes by iterator range.
Definition: Sawyer/Map.h:688
Type for stored nodes.
Definition: Sawyer/Map.h:89
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:156