ROSE  0.11.109.0
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 {
116 
117  public:
118  // Five standard iterator types
119  using iterator_category = std::bidirectional_iterator_tag;
120  using value_type = Value;
121  using difference_type = std::ptrdiff_t;
122  using pointer = Value*;
123  using reference = Value&;
124 
125  protected:
126  BaseIterator base_;
127  BidirectionalIterator() {}
128  BidirectionalIterator(const BaseIterator &base): base_(base) {}
129  public:
130  Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
131 
133  Derived& operator++() { ++base_; return *derived(); }
134 
136  Derived operator++(int) { Derived old=*derived(); ++*this; return old; }
137 
139  Derived& operator--() { --base_; return *derived(); }
140 
142  Derived operator--(int) { Derived old=*derived(); --*this; return old; }
143 
148  template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base(); }
149 
153  template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base(); }
154 
155  const BaseIterator& base() const { return base_; }
156  protected:
157  Derived* derived() { return static_cast<Derived*>(this); }
158  const Derived* derived() const { return static_cast<const Derived*>(this); }
159  };
160 
161 public:
166  class NodeIterator: public BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> {
167  typedef BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> Super;
168  public:
169  NodeIterator() {}
170 
172  NodeIterator(const NodeIterator &other): Super(other) {}
173 
174  // std::map stores std::pair nodes, but we want to return Node, which must have the same layout.
176  Node& operator*() const { return *(Node*)&*this->base_; }
177 
179  Node* operator->() const { return (Node*)&*this->base_; }
180  private:
181  friend class Map;
182  NodeIterator(const typename StlMap::iterator &base): Super(base) {}
183  };
184 
189  class ConstNodeIterator: public BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> {
190  typedef BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> Super;
191  public:
192  ConstNodeIterator() {}
193 
195  ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
196 
198  ConstNodeIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
199 
200  // std::map stores std::pair nodes, but we want to return Node, which must have the same layout.
202  const Node& operator*() const { return *(const Node*)&*this->base_; }
203 
205  const Node* operator->() const { return (const Node*)&*this->base_; }
206  private:
207  friend class Map;
208  ConstNodeIterator(const typename StlMap::const_iterator &base): Super(base) {}
209  ConstNodeIterator(const typename StlMap::iterator &base): Super(typename StlMap::const_iterator(base)) {}
210  };
211 
216  class ConstKeyIterator: public BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> {
217  typedef BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> Super;
218  public:
219  ConstKeyIterator() {}
220 
222  ConstKeyIterator(const ConstKeyIterator &other): Super(other) {}
223 
225  ConstKeyIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
226 
228  ConstKeyIterator(const ConstNodeIterator &other): Super(other.base()) {}
229 
231  const Key& operator*() const { return this->base()->first; }
232 
234  const Key* operator->() const { return &this->base()->first; }
235  };
236 
241  class ValueIterator: public BidirectionalIterator<ValueIterator, Value, typename StlMap::iterator> {
242  typedef BidirectionalIterator<ValueIterator, Value, typename StlMap::iterator> Super;
243  public:
244  ValueIterator() {}
245 
247  ValueIterator(const ValueIterator &other): Super(other) {}
248 
250  ValueIterator(const NodeIterator &other): Super(other.base()) {}
251 
253  Value& operator*() const { return this->base()->second; }
254 
256  Value* operator->() const { return &this->base()->second; }
257  };
258 
263  class ConstValueIterator: public BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> {
264  typedef BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> Super;
265  public:
266  ConstValueIterator() {}
267 
269  ConstValueIterator(const ConstValueIterator &other): Super(other) {}
270 
272  ConstValueIterator(const ValueIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
273 
275  ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
276 
278  ConstValueIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
279 
281  const Value& operator*() const { return this->base()->second; }
282 
284  const Value* operator->() const { return &this->base()->second; }
285  };
286 
287 
289  // Constructors
291 public:
292 
296  Map() {}
297 
301  explicit Map(const Comparator &comparator, const Allocator &allocator = Allocator())
302  : map_(comparator, allocator) {}
303 
305  Map(const Map& other) {
306  map_ = other.map_;
307  }
308 
313  template<class Key2, class T2, class Cmp2, class Alloc2>
315  typedef typename Map<Key2, T2, Cmp2, Alloc2>::ConstNodeIterator OtherIterator;
316  boost::iterator_range<OtherIterator> otherNodes = other.nodes();
317  for (OtherIterator otherIter=otherNodes.begin(); otherIter!=otherNodes.end(); ++otherIter)
318  map_.insert(map_.end(), std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
319  }
320 
324  template<class Key2, class T2, class Cmp2, class Alloc2>
326  typedef typename Map<Key2, T2, Cmp2, Alloc2>::ConstNodeIterator OtherIterator;
327  clear();
328  boost::iterator_range<OtherIterator> otherNodes = other.nodes();
329  for (OtherIterator otherIter=otherNodes.begin(); otherIter!=otherNodes.end(); ++otherIter)
330  map_.insert(map_.end(), std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
331  return *this;
332  }
333 
334 
336  // Iteration
338 public:
344  boost::iterator_range<NodeIterator> nodes() {
345  return boost::iterator_range<NodeIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
346  }
347  boost::iterator_range<ConstNodeIterator> nodes() const {
348  return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
349  }
357  boost::iterator_range<ConstKeyIterator> keys() {
358  return boost::iterator_range<ConstKeyIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
359  }
360  boost::iterator_range<ConstKeyIterator> keys() const {
361  return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
362  }
371  boost::iterator_range<ValueIterator> values() {
372  return boost::iterator_range<ValueIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
373  }
374  boost::iterator_range<ConstValueIterator> values() const {
375  return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
376  }
380  // Size and capacity
383 public:
384 
388  bool isEmpty() const {
389  return map_.empty();
390  }
391 
395  size_t size() const {
396  return map_.size();
397  }
398 
400  Key least() const {
401  ASSERT_forbid(isEmpty());
402  return map_.begin()->first;
403  }
404 
406  Key greatest() const {
407  ASSERT_forbid(isEmpty());
408  typename StlMap::const_iterator last = map_.end();
409  --last;
410  return last->first;
411  }
412 
420  Interval<Key> hull() const {
422  }
423 
424 
426  // Searching
428 public:
429 
437  NodeIterator find(const Key &key) {
438  return map_.find(key);
439  }
440  ConstNodeIterator find(const Key &key) const {
441  return map_.find(key);
442  }
450  bool exists(const Key &key) const {
451  return map_.find(key)!=map_.end();
452  }
453 
463  NodeIterator lowerBound(const Key &key) {
464  return map_.lower_bound(key);
465  }
466  ConstNodeIterator lowerBound(const Key &key) const {
467  return map_.lower_bound(key);
468  }
480  NodeIterator upperBound(const Key &key) {
481  return map_.upper_bound(key);
482  }
483  ConstNodeIterator upperBound(const Key &key) const {
484  return map_.upper_bound(key);
485  }
489  // Accessors
492 public:
493 
506  Value& operator[](const Key &key) {
507  return get(key);
508  }
509  const Value& operator[](const Key &key) const {
510  return get(key);
511  }
522  Value& get(const Key &key) {
523  typename StlMap::iterator found = map_.find(key);
524  if (found==map_.end())
525  throw std::domain_error("key lookup failure; key is not in map domain");
526  return found->second;
527  }
528  const Value& get(const Key &key) const {
529  typename StlMap::const_iterator found = map_.find(key);
530  if (found==map_.end())
531  throw std::domain_error("key lookup failure; key is not in map domain");
532  return found->second;
533  }
559  Optional<Value> getOptional(const Key &key) const {
560  typename StlMap::const_iterator found = map_.find(key);
561  return found == map_.end() ? Optional<Value>() : Optional<Value>(found->second);
562  }
563 
571  Value& getOrElse(const Key &key, Value &dflt) {
572  typename StlMap::iterator found = map_.find(key);
573  return found == map_.end() ? dflt : found->second;
574  }
575  const Value& getOrElse(const Key &key, const Value &dflt) const {
576  typename StlMap::const_iterator found = map_.find(key);
577  return found == map_.end() ? dflt : found->second;
578  }
586  const Value& getOrDefault(const Key &key) const {
587  static const Value dflt;
588  typename StlMap::const_iterator found = map_.find(key);
589  return found==map_.end() ? dflt : found->second;
590  }
591 
593  // Mutators
595 public:
596 
603  Map& insert(const Key &key, const Value &value) {
604  std::pair<typename StlMap::iterator, bool> inserted = map_.insert(std::make_pair(key, value));
605  if (!inserted.second)
606  inserted.first->second = value;
607  return *this;
608  }
609 
616  Map& insertDefault(const Key &key) {
617  map_[key] = T();
618  return *this;
619  }
620 
638  template<class OtherNodeIterator>
639  Map& insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end) {
640  for (OtherNodeIterator otherIter=begin; otherIter!=end; ++otherIter)
641  insert(Key(otherIter->key()), Value(otherIter->value()));
642  return *this;
643  }
644  template<class OtherNodeIterator>
645  Map& insertMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
646  return insertMultiple(range.begin(), range.end());
647  }
657  Value& insertMaybe(const Key &key, const Value &value) {
658  return map_.insert(std::make_pair(key, value)).first->second;
659  }
660 
668  Value& insertMaybeDefault(const Key &key) {
669  return map_.insert(std::make_pair(key, T())).first->second;
670  }
671 
678  template<class OtherNodeIterator>
679  Map& insertMaybeMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
680  for (OtherNodeIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
681  insertMaybe(Key(otherIter->key()), Value(otherIter->value()));
682  return *this;
683  }
684 
689  Map& clear() {
690  map_.clear();
691  return *this;
692  }
693 
701  Map& erase(const Key &key) {
702  map_.erase(key);
703  return *this;
704  }
705 
714  template<class OtherKeyIterator>
715  Map& eraseMultiple(const boost::iterator_range<OtherKeyIterator> &range) {
716  for (OtherKeyIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
717  map_.erase(Key(*otherIter));
718  return *this;
719  }
720 
728  Map& eraseAt(const NodeIterator &iter) {
729  map_.erase(iter.base());
730  return *this;
731  }
732  Map& eraseAt(const ConstKeyIterator &iter) {
733  // std::map can't erase using a const_iterator
734  ASSERT_require(iter != keys().end());
735  typename StlMap::iterator stdIter = map_.find(*iter);
736  ASSERT_require(stdIter != map_.end());
737  map_.erase(stdIter);
738  return *this;
739  }
740  Map& eraseAt(const ValueIterator &iter) {
741  map_.erase(iter.base());
742  return *this;
743  }
753  template<class Iter>
754  Map& eraseAtMultiple(const Iter &begin, const Iter &end) {
755  map_.erase(begin.base(), end.base());
756  return *this;
757  }
758  template<class Iter>
759  Map& eraseAtMultiple(const boost::iterator_range<Iter> &range) {
760  map_.erase(range.begin().base(), range.end().base());
761  return *this;
762  }
765 };
766 
767 } // namespace
768 } // namespace
769 
770 #endif
const Value * operator->() const
Returns a pointer to the value of the storage node.
Definition: Sawyer/Map.h:284
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
Definition: Sawyer/Map.h:360
Map(const Map &other)
Copy constructor.
Definition: Sawyer/Map.h:305
bool exists(const Key &key) const
Determine if a key exists.
Definition: Sawyer/Map.h:450
Value & operator[](const Key &key)
Return a reference to an existing value.
Definition: Sawyer/Map.h:506
NodeIterator(const NodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:172
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: Sawyer/Map.h:559
const Value & operator[](const Key &key) const
Return a reference to an existing value.
Definition: Sawyer/Map.h:509
Map()
Default constructor.
Definition: Sawyer/Map.h:296
ValueIterator(const ValueIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:247
ConstNodeIterator(const ConstNodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:195
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:483
Map(const Comparator &comparator, const Allocator &allocator=Allocator())
Constructs an empty map.
Definition: Sawyer/Map.h:301
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
Definition: Sawyer/Map.h:347
Value & operator*() const
Dereference iterator to return the value of the storage node.
Definition: Sawyer/Map.h:253
const Value & getOrElse(const Key &key, const Value &dflt) const
Lookup and return a value or something else.
Definition: Sawyer/Map.h:575
ConstNodeIterator lowerBound(const Key &key) const
Find a node close to a key.
Definition: Sawyer/Map.h:466
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Definition: Sawyer/Map.h:668
Map & eraseAt(const ValueIterator &iter)
Remove a node by iterator.
Definition: Sawyer/Map.h:740
const Key & operator*() const
Dereference iterator to return the interval of the storage node.
Definition: Sawyer/Map.h:231
Node * operator->() const
Returns a pointer to a storage node.
Definition: Sawyer/Map.h:179
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:689
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Definition: Sawyer/Map.h:371
Cmp Comparator
Type of comparator, third template argument.
Definition: Sawyer/Map.h:70
Name space for the entire library.
Definition: FeasiblePath.h:767
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:166
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:571
bool isEmpty() const
Determines whether this container is empty.
Definition: Sawyer/Map.h:388
Map & insertDefault(const Key &key)
Insert or update a key with a default value.
Definition: Sawyer/Map.h:616
ConstNodeIterator find(const Key &key) const
Find a node by key.
Definition: Sawyer/Map.h:440
Map & insertMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Insert multiple values.
Definition: Sawyer/Map.h:645
NodeIterator lowerBound(const Key &key)
Find a node close to a key.
Definition: Sawyer/Map.h:463
Bidirectional iterator over values.
Definition: Sawyer/Map.h:241
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
Definition: Sawyer/Map.h:374
const Key * operator->() const
Returns a pointer to the interval of the storage node.
Definition: Sawyer/Map.h:234
ConstKeyIterator(const NodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:225
ConstKeyIterator(const ConstKeyIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:222
ConstValueIterator(const ConstNodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:275
Node & operator*() const
Dereference iterator to return a storage node.
Definition: Sawyer/Map.h:176
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:639
Bidirectional iterator over values.
Definition: Sawyer/Map.h:263
Map & operator=(const Map< Key2, T2, Cmp2, Alloc2 > &other)
Make this map be a copy of another map.
Definition: Sawyer/Map.h:325
ConstNodeIterator(const NodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:198
Interval< Key > hull() const
Returns the range of keys in this map.
Definition: Sawyer/Map.h:420
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:586
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:728
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition: Sawyer/Map.h:357
Map & insertMaybeMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Conditionally insert multiple key/value pairs.
Definition: Sawyer/Map.h:679
Map & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
Definition: Sawyer/Map.h:754
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:701
Range of values delimited by endpoints.
Definition: Interval.h:33
Map(const Map< Key2, T2, Cmp2, Alloc2 > &other)
Copy constructor.
Definition: Sawyer/Map.h:314
Map & eraseAt(const ConstKeyIterator &iter)
Remove a node by iterator.
Definition: Sawyer/Map.h:732
NodeIterator find(const Key &key)
Find a node by key.
Definition: Sawyer/Map.h:437
ConstValueIterator(const ConstValueIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:269
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: Sawyer/Map.h:603
Key least() const
Returns the minimum key.
Definition: Sawyer/Map.h:400
ConstKeyIterator(const ConstNodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:228
ConstValueIterator(const ValueIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:272
const Node * operator->() const
Returns a pointer to a storage node.
Definition: Sawyer/Map.h:205
Bidirectional iterator over keys.
Definition: Sawyer/Map.h:216
NodeIterator upperBound(const Key &key)
Find a node close to a key.
Definition: Sawyer/Map.h:480
Map & eraseMultiple(const boost::iterator_range< OtherKeyIterator > &range)
Remove keys stored in another Map.
Definition: Sawyer/Map.h:715
ConstValueIterator(const NodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:278
Key greatest() const
Returns the maximum key.
Definition: Sawyer/Map.h:406
const Node & operator*() const
Dereference iterator to return a storage node.
Definition: Sawyer/Map.h:202
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Definition: Sawyer/Map.h:344
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:395
Container associating values with keys.
Definition: Sawyer/Map.h:66
const Value & operator*() const
Dereference iterator to return the value of the storage node.
Definition: Sawyer/Map.h:281
Value & insertMaybe(const Key &key, const Value &value)
Conditionally insert a new key/value pair.
Definition: Sawyer/Map.h:657
Map & eraseAtMultiple(const boost::iterator_range< Iter > &range)
Remove multiple nodes by iterator range.
Definition: Sawyer/Map.h:759
Type for stored nodes.
Definition: Sawyer/Map.h:89
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:189
Value * operator->() const
Returns a pointer to the value of the storage node.
Definition: Sawyer/Map.h:256
ValueIterator(const NodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:250