ROSE  0.9.10.200
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 
124  Derived& operator++() { ++base_; return *derived(); }
125 
127  Derived operator++(int) { Derived old=*derived(); ++*this; return old; }
128 
130  Derived& operator--() { --base_; return *derived(); }
131 
133  Derived operator--(int) { Derived old=*derived(); --*this; return old; }
134 
139  template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base(); }
140 
144  template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base(); }
145 
146  const BaseIterator& base() const { return base_; }
147  protected:
148  Derived* derived() { return static_cast<Derived*>(this); }
149  const Derived* derived() const { return static_cast<const Derived*>(this); }
150  };
151 
152 public:
157  class NodeIterator: public BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> {
158  typedef BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> Super;
159  public:
160  NodeIterator() {}
161 
163  NodeIterator(const NodeIterator &other): Super(other) {}
164 
165  // std::map stores std::pair nodes, but we want to return Node, which must have the same layout.
167  Node& operator*() const { return *(Node*)&*this->base_; }
168 
170  Node* operator->() const { return (Node*)&*this->base_; }
171  private:
172  friend class Map;
173  NodeIterator(const typename StlMap::iterator &base): Super(base) {}
174  };
175 
180  class ConstNodeIterator: public BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> {
181  typedef BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> Super;
182  public:
183  ConstNodeIterator() {}
184 
186  ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
187 
189  ConstNodeIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
190 
191  // std::map stores std::pair nodes, but we want to return Node, which must have the same layout.
193  const Node& operator*() const { return *(const Node*)&*this->base_; }
194 
196  const Node* operator->() const { return (const Node*)&*this->base_; }
197  private:
198  friend class Map;
199  ConstNodeIterator(const typename StlMap::const_iterator &base): Super(base) {}
200  ConstNodeIterator(const typename StlMap::iterator &base): Super(typename StlMap::const_iterator(base)) {}
201  };
202 
207  class ConstKeyIterator: public BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> {
208  typedef BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> Super;
209  public:
210  ConstKeyIterator() {}
211 
213  ConstKeyIterator(const ConstKeyIterator &other): Super(other) {}
214 
216  ConstKeyIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
217 
219  ConstKeyIterator(const ConstNodeIterator &other): Super(other.base()) {}
220 
222  const Key& operator*() const { return this->base()->first; }
223 
225  const Key* operator->() const { return &this->base()->first; }
226  };
227 
232  class ValueIterator: public BidirectionalIterator<ValueIterator, Value, typename StlMap::iterator> {
233  typedef BidirectionalIterator<ValueIterator, Value, typename StlMap::iterator> Super;
234  public:
235  ValueIterator() {}
236 
238  ValueIterator(const ValueIterator &other): Super(other) {}
239 
241  ValueIterator(const NodeIterator &other): Super(other.base()) {}
242 
244  Value& operator*() const { return this->base()->second; }
245 
247  Value* operator->() const { return &this->base()->second; }
248  };
249 
254  class ConstValueIterator: public BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> {
255  typedef BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> Super;
256  public:
257  ConstValueIterator() {}
258 
260  ConstValueIterator(const ConstValueIterator &other): Super(other) {}
261 
263  ConstValueIterator(const ValueIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
264 
266  ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
267 
269  ConstValueIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
270 
272  const Value& operator*() const { return this->base()->second; }
273 
275  const Value* operator->() const { return &this->base()->second; }
276  };
277 
278 
280  // Constructors
282 public:
283 
287  Map() {}
288 
292  explicit Map(const Comparator &comparator, const Allocator &allocator = Allocator())
293  : map_(comparator, allocator) {}
294 
296  Map(const Map& other) {
297  map_ = other.map_;
298  }
299 
304  template<class Key2, class T2, class Cmp2, class Alloc2>
306  typedef typename Map<Key2, T2, Cmp2, Alloc2>::ConstNodeIterator OtherIterator;
307  boost::iterator_range<OtherIterator> otherNodes = other.nodes();
308  for (OtherIterator otherIter=otherNodes.begin(); otherIter!=otherNodes.end(); ++otherIter)
309  map_.insert(map_.end(), std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
310  }
311 
315  template<class Key2, class T2, class Cmp2, class Alloc2>
317  typedef typename Map<Key2, T2, Cmp2, Alloc2>::ConstNodeIterator OtherIterator;
318  clear();
319  boost::iterator_range<OtherIterator> otherNodes = other.nodes();
320  for (OtherIterator otherIter=otherNodes.begin(); otherIter!=otherNodes.end(); ++otherIter)
321  map_.insert(map_.end(), std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
322  return *this;
323  }
324 
325 
327  // Iteration
329 public:
335  boost::iterator_range<NodeIterator> nodes() {
336  return boost::iterator_range<NodeIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
337  }
338  boost::iterator_range<ConstNodeIterator> nodes() const {
339  return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
340  }
348  boost::iterator_range<ConstKeyIterator> keys() {
349  return boost::iterator_range<ConstKeyIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
350  }
351  boost::iterator_range<ConstKeyIterator> keys() const {
352  return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
353  }
362  boost::iterator_range<ValueIterator> values() {
363  return boost::iterator_range<ValueIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
364  }
365  boost::iterator_range<ConstValueIterator> values() const {
366  return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
367  }
371  // Size and capacity
374 public:
375 
379  bool isEmpty() const {
380  return map_.empty();
381  }
382 
386  size_t size() const {
387  return map_.size();
388  }
389 
391  Key least() const {
392  ASSERT_forbid(isEmpty());
393  return map_.begin()->first;
394  }
395 
397  Key greatest() const {
398  ASSERT_forbid(isEmpty());
399  typename StlMap::const_iterator last = map_.end();
400  --last;
401  return last->first;
402  }
403 
411  Interval<Key> hull() const {
413  }
414 
415 
417  // Searching
419 public:
420 
428  NodeIterator find(const Key &key) {
429  return map_.find(key);
430  }
431  ConstNodeIterator find(const Key &key) const {
432  return map_.find(key);
433  }
441  bool exists(const Key &key) const {
442  return map_.find(key)!=map_.end();
443  }
444 
454  NodeIterator lowerBound(const Key &key) {
455  return map_.lower_bound(key);
456  }
457  ConstNodeIterator lowerBound(const Key &key) const {
458  return map_.lower_bound(key);
459  }
471  NodeIterator upperBound(const Key &key) {
472  return map_.upper_bound(key);
473  }
474  ConstNodeIterator upperBound(const Key &key) const {
475  return map_.upper_bound(key);
476  }
480  // Accessors
483 public:
484 
497  Value& operator[](const Key &key) {
498  return get(key);
499  }
500  const Value& operator[](const Key &key) const {
501  return get(key);
502  }
513  Value& get(const Key &key) {
514  typename StlMap::iterator found = map_.find(key);
515  if (found==map_.end())
516  throw std::domain_error("key lookup failure; key is not in map domain");
517  return found->second;
518  }
519  const Value& get(const Key &key) const {
520  typename StlMap::const_iterator found = map_.find(key);
521  if (found==map_.end())
522  throw std::domain_error("key lookup failure; key is not in map domain");
523  return found->second;
524  }
550  Optional<Value> getOptional(const Key &key) const {
551  typename StlMap::const_iterator found = map_.find(key);
552  return found == map_.end() ? Optional<Value>() : Optional<Value>(found->second);
553  }
554 
562  Value& getOrElse(const Key &key, Value &dflt) {
563  typename StlMap::iterator found = map_.find(key);
564  return found == map_.end() ? dflt : found->second;
565  }
566  const Value& getOrElse(const Key &key, const Value &dflt) const {
567  typename StlMap::const_iterator found = map_.find(key);
568  return found == map_.end() ? dflt : found->second;
569  }
577  const Value& getOrDefault(const Key &key) const {
578  static const Value dflt;
579  typename StlMap::const_iterator found = map_.find(key);
580  return found==map_.end() ? dflt : found->second;
581  }
582 
584  // Mutators
586 public:
587 
594  Map& insert(const Key &key, const Value &value) {
595  std::pair<typename StlMap::iterator, bool> inserted = map_.insert(std::make_pair(key, value));
596  if (!inserted.second)
597  inserted.first->second = value;
598  return *this;
599  }
600 
607  Map& insertDefault(const Key &key) {
608  map_[key] = T();
609  return *this;
610  }
611 
629  template<class OtherNodeIterator>
630  Map& insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end) {
631  for (OtherNodeIterator otherIter=begin; otherIter!=end; ++otherIter)
632  insert(Key(otherIter->key()), Value(otherIter->value()));
633  return *this;
634  }
635  template<class OtherNodeIterator>
636  Map& insertMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
637  return insertMultiple(range.begin(), range.end());
638  }
648  Value& insertMaybe(const Key &key, const Value &value) {
649  return map_.insert(std::make_pair(key, value)).first->second;
650  }
651 
659  Value& insertMaybeDefault(const Key &key) {
660  return map_.insert(std::make_pair(key, T())).first->second;
661  }
662 
669  template<class OtherNodeIterator>
670  Map& insertMaybeMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
671  for (OtherNodeIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
672  insertMaybe(Key(otherIter->key()), Value(otherIter->value()));
673  return *this;
674  }
675 
680  Map& clear() {
681  map_.clear();
682  return *this;
683  }
684 
692  Map& erase(const Key &key) {
693  map_.erase(key);
694  return *this;
695  }
696 
705  template<class OtherKeyIterator>
706  Map& eraseMultiple(const boost::iterator_range<OtherKeyIterator> &range) {
707  for (OtherKeyIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
708  map_.erase(Key(*otherIter));
709  return *this;
710  }
711 
719  Map& eraseAt(const NodeIterator &iter) {
720  map_.erase(iter.base());
721  return *this;
722  }
723  Map& eraseAt(const ConstKeyIterator &iter) {
724  // std::map can't erase using a const_iterator
725  ASSERT_require(iter != keys().end());
726  typename StlMap::iterator stdIter = map_.find(*iter);
727  ASSERT_require(stdIter != map_.end());
728  map_.erase(stdIter);
729  return *this;
730  }
731  Map& eraseAt(const ValueIterator &iter) {
732  map_.erase(iter.base());
733  return *this;
734  }
744  template<class Iter>
745  Map& eraseAtMultiple(const Iter &begin, const Iter &end) {
746  map_.erase(begin.base(), end.base());
747  return *this;
748  }
749  template<class Iter>
750  Map& eraseAtMultiple(const boost::iterator_range<Iter> &range) {
751  map_.erase(range.begin().base(), range.end().base());
752  return *this;
753  }
756 };
757 
758 } // namespace
759 } // namespace
760 
761 #endif
const Value * operator->() const
Returns a pointer to the value of the storage node.
Definition: Sawyer/Map.h:275
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
Definition: Sawyer/Map.h:351
Map(const Map &other)
Copy constructor.
Definition: Sawyer/Map.h:296
bool exists(const Key &key) const
Determine if a key exists.
Definition: Sawyer/Map.h:441
Value & operator[](const Key &key)
Return a reference to an existing value.
Definition: Sawyer/Map.h:497
NodeIterator(const NodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:163
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: Sawyer/Map.h:550
const Value & operator[](const Key &key) const
Return a reference to an existing value.
Definition: Sawyer/Map.h:500
Map()
Default constructor.
Definition: Sawyer/Map.h:287
ValueIterator(const ValueIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:238
ConstNodeIterator(const ConstNodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:186
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:474
Map(const Comparator &comparator, const Allocator &allocator=Allocator())
Constructs an empty map.
Definition: Sawyer/Map.h:292
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
Definition: Sawyer/Map.h:338
Value & operator*() const
Dereference iterator to return the value of the storage node.
Definition: Sawyer/Map.h:244
const Value & getOrElse(const Key &key, const Value &dflt) const
Lookup and return a value or something else.
Definition: Sawyer/Map.h:566
ConstNodeIterator lowerBound(const Key &key) const
Find a node close to a key.
Definition: Sawyer/Map.h:457
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Definition: Sawyer/Map.h:659
Map & eraseAt(const ValueIterator &iter)
Remove a node by iterator.
Definition: Sawyer/Map.h:731
const Key & operator*() const
Dereference iterator to return the interval of the storage node.
Definition: Sawyer/Map.h:222
Node * operator->() const
Returns a pointer to a storage node.
Definition: Sawyer/Map.h:170
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:680
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Definition: Sawyer/Map.h:362
Cmp Comparator
Type of comparator, third template argument.
Definition: Sawyer/Map.h:70
Name space for the entire library.
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:157
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:562
bool isEmpty() const
Determines whether this container is empty.
Definition: Sawyer/Map.h:379
Map & insertDefault(const Key &key)
Insert or update a key with a default value.
Definition: Sawyer/Map.h:607
ConstNodeIterator find(const Key &key) const
Find a node by key.
Definition: Sawyer/Map.h:431
Map & insertMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Insert multiple values.
Definition: Sawyer/Map.h:636
NodeIterator lowerBound(const Key &key)
Find a node close to a key.
Definition: Sawyer/Map.h:454
Bidirectional iterator over values.
Definition: Sawyer/Map.h:232
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
Definition: Sawyer/Map.h:365
const Key * operator->() const
Returns a pointer to the interval of the storage node.
Definition: Sawyer/Map.h:225
ConstKeyIterator(const NodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:216
ConstKeyIterator(const ConstKeyIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:213
ConstValueIterator(const ConstNodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:266
Node & operator*() const
Dereference iterator to return a storage node.
Definition: Sawyer/Map.h:167
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:630
Bidirectional iterator over values.
Definition: Sawyer/Map.h:254
Map & operator=(const Map< Key2, T2, Cmp2, Alloc2 > &other)
Make this map be a copy of another map.
Definition: Sawyer/Map.h:316
ConstNodeIterator(const NodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:189
Interval< Key > hull() const
Returns the range of keys in this map.
Definition: Sawyer/Map.h:411
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:577
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:719
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition: Sawyer/Map.h:348
Map & insertMaybeMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Conditionally insert multiple key/value pairs.
Definition: Sawyer/Map.h:670
Map & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
Definition: Sawyer/Map.h:745
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:692
Range of values delimited by endpoints.
Definition: Interval.h:33
Map(const Map< Key2, T2, Cmp2, Alloc2 > &other)
Copy constructor.
Definition: Sawyer/Map.h:305
Map & eraseAt(const ConstKeyIterator &iter)
Remove a node by iterator.
Definition: Sawyer/Map.h:723
NodeIterator find(const Key &key)
Find a node by key.
Definition: Sawyer/Map.h:428
ConstValueIterator(const ConstValueIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:260
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: Sawyer/Map.h:594
Key least() const
Returns the minimum key.
Definition: Sawyer/Map.h:391
ConstKeyIterator(const ConstNodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:219
ConstValueIterator(const ValueIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:263
const Node * operator->() const
Returns a pointer to a storage node.
Definition: Sawyer/Map.h:196
Bidirectional iterator over keys.
Definition: Sawyer/Map.h:207
NodeIterator upperBound(const Key &key)
Find a node close to a key.
Definition: Sawyer/Map.h:471
Map & eraseMultiple(const boost::iterator_range< OtherKeyIterator > &range)
Remove keys stored in another Map.
Definition: Sawyer/Map.h:706
ConstValueIterator(const NodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:269
Key greatest() const
Returns the maximum key.
Definition: Sawyer/Map.h:397
const Node & operator*() const
Dereference iterator to return a storage node.
Definition: Sawyer/Map.h:193
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Definition: Sawyer/Map.h:335
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:386
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:272
Value & insertMaybe(const Key &key, const Value &value)
Conditionally insert a new key/value pair.
Definition: Sawyer/Map.h:648
Map & eraseAtMultiple(const boost::iterator_range< Iter > &range)
Remove multiple nodes by iterator range.
Definition: Sawyer/Map.h:750
Type for stored nodes.
Definition: Sawyer/Map.h:89
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:180
Value * operator->() const
Returns a pointer to the value of the storage node.
Definition: Sawyer/Map.h:247
ValueIterator(const NodeIterator &other)
Copy constructor.
Definition: Sawyer/Map.h:241