ROSE  0.9.9.139
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 
60 template<class K,
61  class T,
62  class Cmp = std::less<K>,
63  class Alloc = std::allocator<std::pair<const K, T> > >
64 class Map {
65 public:
66  typedef K Key;
67  typedef T Value;
68  typedef Cmp Comparator;
69  typedef Alloc Allocator;
71 private:
72  typedef std::map<Key, Value, Comparator, Alloc> StlMap;
73  StlMap map_;
74 
75 private:
76  friend class boost::serialization::access;
77 
78  template<class S>
79  void serialize(S &s, const unsigned /*version*/) {
80  s & BOOST_SERIALIZATION_NVP(map_);
81  }
82 
83 public:
87  class Node: private std::pair<const Key, Value> {
88  // This class MUST BE binary compatible with its super class (see NodeIterator::operator* below)
89  public:
90  explicit Node(const std::pair<const Key, Value> &pair): std::pair<const Key, Value>(pair) {}
91  Node(const Key &key, Value &value): std::pair<const Key, Value>(key, value) {}
92  public:
96  const Key& key() const { return this->first; }
97 
103  Value& value() { return this->second; }
104  const Value& value() const { return this->second; }
106  };
107 
109  // Iterators
111 private:
112  template<class Derived, class Value, class BaseIterator>
113  class BidirectionalIterator: public std::iterator<std::bidirectional_iterator_tag, Value> {
114  protected:
115  BaseIterator base_;
116  BidirectionalIterator() {}
117  BidirectionalIterator(const BaseIterator &base): base_(base) {}
118  public:
119  Derived& operator=(const Derived &other) { base_ = other.base_; return *derived(); }
120  Derived& operator++() { ++base_; return *derived(); }
121  Derived operator++(int) { Derived old=*derived(); ++*this; return old; }
122  Derived& operator--() { --base_; return *derived(); }
123  Derived operator--(int) { Derived old=*derived(); --*this; return old; }
124  template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base(); }
125  template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base(); }
126  const BaseIterator& base() const { return base_; }
127  protected:
128  Derived* derived() { return static_cast<Derived*>(this); }
129  const Derived* derived() const { return static_cast<const Derived*>(this); }
130  };
131 
132 public:
137  class NodeIterator: public BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> {
138  typedef BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> Super;
139  public:
140  NodeIterator() {}
141  NodeIterator(const NodeIterator &other): Super(other) {}
142  // std::map stores std::pair nodes, but we want to return Node, which must have the same layout.
143  Node& operator*() const { return *(Node*)&*this->base_; }
144  Node* operator->() const { return (Node*)&*this->base_; }
145  private:
146  friend class Map;
147  NodeIterator(const typename StlMap::iterator &base): Super(base) {}
148  };
149 
154  class ConstNodeIterator: public BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> {
155  typedef BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> Super;
156  public:
157  ConstNodeIterator() {}
158  ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
159  ConstNodeIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
160  // std::map stores std::pair nodes, but we want to return Node, which must have the same layout.
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 Map;
165  ConstNodeIterator(const typename StlMap::const_iterator &base): Super(base) {}
166  ConstNodeIterator(const typename StlMap::iterator &base): Super(typename StlMap::const_iterator(base)) {}
167  };
168 
173  class ConstKeyIterator: public BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> {
174  typedef BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> Super;
175  public:
176  ConstKeyIterator() {}
177  ConstKeyIterator(const ConstKeyIterator &other): Super(other) {}
178  ConstKeyIterator(const NodeIterator &other): Super(typename StlMap::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 BidirectionalIterator<ValueIterator, Value, typename StlMap::iterator> {
189  typedef BidirectionalIterator<ValueIterator, Value, typename StlMap::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 BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> {
203  typedef BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> Super;
204  public:
205  ConstValueIterator() {}
206  ConstValueIterator(const ConstValueIterator &other): Super(other) {}
207  ConstValueIterator(const ValueIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
208  ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
209  ConstValueIterator(const NodeIterator &other): Super(typename StlMap::const_iterator(other.base())) {}
210  const Value& operator*() const { return this->base()->second; }
211  const Value* operator->() const { return &this->base()->second; }
212  };
213 
214 
216  // Constructors
218 public:
219 
223  Map() {}
224 
228  explicit Map(const Comparator &comparator, const Allocator &allocator = Allocator())
229  : map_(comparator, allocator) {}
230 
232  Map(const Map& other) {
233  map_ = other.map_;
234  }
235 
240  template<class Key2, class T2, class Cmp2, class Alloc2>
242  typedef typename Map<Key2, T2, Cmp2, Alloc2>::ConstNodeIterator OtherIterator;
243  boost::iterator_range<OtherIterator> otherNodes = other.nodes();
244  for (OtherIterator otherIter=otherNodes.begin(); otherIter!=otherNodes.end(); ++otherIter)
245  map_.insert(map_.end(), std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
246  }
247 
251  template<class Key2, class T2, class Cmp2, class Alloc2>
253  typedef typename Map<Key2, T2, Cmp2, Alloc2>::ConstNodeIterator OtherIterator;
254  clear();
255  boost::iterator_range<OtherIterator> otherNodes = other.nodes();
256  for (OtherIterator otherIter=otherNodes.begin(); otherIter!=otherNodes.end(); ++otherIter)
257  map_.insert(map_.end(), std::make_pair(Key(otherIter->key()), Value(otherIter->value())));
258  return *this;
259  }
260 
261 
263  // Iteration
265 public:
271  boost::iterator_range<NodeIterator> nodes() {
272  return boost::iterator_range<NodeIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
273  }
274  boost::iterator_range<ConstNodeIterator> nodes() const {
275  return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
276  }
284  boost::iterator_range<ConstKeyIterator> keys() {
285  return boost::iterator_range<ConstKeyIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
286  }
287  boost::iterator_range<ConstKeyIterator> keys() const {
288  return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
289  }
298  boost::iterator_range<ValueIterator> values() {
299  return boost::iterator_range<ValueIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
300  }
301  boost::iterator_range<ConstValueIterator> values() const {
302  return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
303  }
307  // Size and capacity
310 public:
311 
315  bool isEmpty() const {
316  return map_.empty();
317  }
318 
322  size_t size() const {
323  return map_.size();
324  }
325 
327  Key least() const {
328  ASSERT_forbid(isEmpty());
329  return map_.begin()->first;
330  }
331 
333  Key greatest() const {
334  ASSERT_forbid(isEmpty());
335  typename StlMap::const_iterator last = map_.end();
336  --last;
337  return last->first;
338  }
339 
347  Interval<Key> hull() const {
349  }
350 
351 
353  // Searching
355 public:
356 
364  NodeIterator find(const Key &key) {
365  return map_.find(key);
366  }
367  ConstNodeIterator find(const Key &key) const {
368  return map_.find(key);
369  }
377  bool exists(const Key &key) const {
378  return map_.find(key)!=map_.end();
379  }
380 
390  NodeIterator lowerBound(const Key &key) {
391  return map_.lower_bound(key);
392  }
393  ConstNodeIterator lowerBound(const Key &key) const {
394  return map_.lower_bound(key);
395  }
407  NodeIterator upperBound(const Key &key) {
408  return map_.upper_bound(key);
409  }
410  ConstNodeIterator upperBound(const Key &key) const {
411  return map_.upper_bound(key);
412  }
416  // Accessors
419 public:
420 
433  Value& operator[](const Key &key) {
434  return get(key);
435  }
436  const Value& operator[](const Key &key) const {
437  return get(key);
438  }
449  Value& get(const Key &key) {
450  typename StlMap::iterator found = map_.find(key);
451  if (found==map_.end())
452  throw std::domain_error("key lookup failure; key is not in map domain");
453  return found->second;
454  }
455  const Value& get(const Key &key) const {
456  typename StlMap::const_iterator found = map_.find(key);
457  if (found==map_.end())
458  throw std::domain_error("key lookup failure; key is not in map domain");
459  return found->second;
460  }
486  Optional<Value> getOptional(const Key &key) const {
487  typename StlMap::const_iterator found = map_.find(key);
488  return found == map_.end() ? Optional<Value>() : Optional<Value>(found->second);
489  }
490 
498  Value& getOrElse(const Key &key, Value &dflt) {
499  typename StlMap::iterator found = map_.find(key);
500  return found == map_.end() ? dflt : found->second;
501  }
502  const Value& getOrElse(const Key &key, const Value &dflt) const {
503  typename StlMap::const_iterator found = map_.find(key);
504  return found == map_.end() ? dflt : found->second;
505  }
513  const Value& getOrDefault(const Key &key) const {
514  static const Value dflt;
515  typename StlMap::const_iterator found = map_.find(key);
516  return found==map_.end() ? dflt : found->second;
517  }
518 
520  // Mutators
522 public:
523 
530  Map& insert(const Key &key, const Value &value) {
531  std::pair<typename StlMap::iterator, bool> inserted = map_.insert(std::make_pair(key, value));
532  if (!inserted.second)
533  inserted.first->second = value;
534  return *this;
535  }
536 
543  Map& insertDefault(const Key &key) {
544  map_[key] = T();
545  return *this;
546  }
547 
565  template<class OtherNodeIterator>
566  Map& insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end) {
567  for (OtherNodeIterator otherIter=begin; otherIter!=end; ++otherIter)
568  insert(Key(otherIter->key()), Value(otherIter->value()));
569  return *this;
570  }
571  template<class OtherNodeIterator>
572  Map& insertMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
573  return insertMultiple(range.begin(), range.end());
574  }
584  Value& insertMaybe(const Key &key, const Value &value) {
585  return map_.insert(std::make_pair(key, value)).first->second;
586  }
587 
595  Value& insertMaybeDefault(const Key &key) {
596  return map_.insert(std::make_pair(key, T())).first->second;
597  }
598 
605  template<class OtherNodeIterator>
606  Map& insertMaybeMultiple(const boost::iterator_range<OtherNodeIterator> &range) {
607  for (OtherNodeIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
608  insertMaybe(Key(otherIter->key()), Value(otherIter->value()));
609  return *this;
610  }
611 
616  Map& clear() {
617  map_.clear();
618  return *this;
619  }
620 
628  Map& erase(const Key &key) {
629  map_.erase(key);
630  return *this;
631  }
632 
641  template<class OtherKeyIterator>
642  Map& eraseMultiple(const boost::iterator_range<OtherKeyIterator> &range) {
643  for (OtherKeyIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
644  map_.erase(Key(*otherIter));
645  return *this;
646  }
647 
655  Map& eraseAt(const NodeIterator &iter) {
656  map_.erase(iter.base());
657  return *this;
658  }
659  Map& eraseAt(const ConstKeyIterator &iter) {
660  // std::map can't erase using a const_iterator
661  ASSERT_require(iter != keys().end());
662  typename StlMap::iterator stdIter = map_.find(*iter);
663  ASSERT_require(stdIter != map_.end());
664  map_.erase(stdIter);
665  return *this;
666  }
667  Map& eraseAt(const ValueIterator &iter) {
668  map_.erase(iter.base());
669  return *this;
670  }
680  template<class Iter>
681  Map& eraseAtMultiple(const Iter &begin, const Iter &end) {
682  map_.erase(begin.base(), end.base());
683  return *this;
684  }
685  template<class Iter>
686  Map& eraseAtMultiple(const boost::iterator_range<Iter> &range) {
687  map_.erase(range.begin().base(), range.end().base());
688  return *this;
689  }
692 };
693 
694 } // namespace
695 } // namespace
696 
697 #endif
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
Definition: Sawyer/Map.h:287
Map(const Map &other)
Copy constructor.
Definition: Sawyer/Map.h:232
bool exists(const Key &key) const
Determine if a key exists.
Definition: Sawyer/Map.h:377
Value & operator[](const Key &key)
Return a reference to an existing value.
Definition: Sawyer/Map.h:433
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
Definition: Sawyer/Map.h:486
const Value & operator[](const Key &key) const
Return a reference to an existing value.
Definition: Sawyer/Map.h:436
Map()
Default constructor.
Definition: Sawyer/Map.h:223
Value & value()
Value part of key/value node.
Definition: Sawyer/Map.h:103
ConstNodeIterator upperBound(const Key &key) const
Find a node close to a key.
Definition: Sawyer/Map.h:410
Map(const Comparator &comparator, const Allocator &allocator=Allocator())
Constructs an empty map.
Definition: Sawyer/Map.h:228
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
Definition: Sawyer/Map.h:274
const Value & getOrElse(const Key &key, const Value &dflt) const
Lookup and return a value or something else.
Definition: Sawyer/Map.h:502
ConstNodeIterator lowerBound(const Key &key) const
Find a node close to a key.
Definition: Sawyer/Map.h:393
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Definition: Sawyer/Map.h:595
Map & eraseAt(const ValueIterator &iter)
Remove a node by iterator.
Definition: Sawyer/Map.h:667
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:616
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Definition: Sawyer/Map.h:298
Cmp Comparator
Type of comparator, third template argument.
Definition: Sawyer/Map.h:68
Name space for the entire library.
Definition: Access.h:11
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:137
Alloc Allocator
Type of allocator, fourth template argument.
Definition: Sawyer/Map.h:69
Value & getOrElse(const Key &key, Value &dflt)
Lookup and return a value or something else.
Definition: Sawyer/Map.h:498
bool isEmpty() const
Determines whether this container is empty.
Definition: Sawyer/Map.h:315
Map & insertDefault(const Key &key)
Insert or update a key with a default value.
Definition: Sawyer/Map.h:543
ConstNodeIterator find(const Key &key) const
Find a node by key.
Definition: Sawyer/Map.h:367
Map & insertMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Insert multiple values.
Definition: Sawyer/Map.h:572
NodeIterator lowerBound(const Key &key)
Find a node close to a key.
Definition: Sawyer/Map.h:390
Bidirectional iterator over values.
Definition: Sawyer/Map.h:188
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
Definition: Sawyer/Map.h:301
const Key & key() const
Key part of key/value node.
Definition: Sawyer/Map.h:96
Map & insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end)
Insert multiple values.
Definition: Sawyer/Map.h:566
Bidirectional iterator over values.
Definition: Sawyer/Map.h:202
Map & operator=(const Map< Key2, T2, Cmp2, Alloc2 > &other)
Make this map be a copy of another map.
Definition: Sawyer/Map.h:252
Interval< Key > hull() const
Returns the range of keys in this map.
Definition: Sawyer/Map.h:347
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
Definition: Sawyer/Map.h:513
const Value & value() const
Value part of key/value node.
Definition: Sawyer/Map.h:104
Map & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
Definition: Sawyer/Map.h:655
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition: Sawyer/Map.h:284
Map & insertMaybeMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Conditionally insert multiple key/value pairs.
Definition: Sawyer/Map.h:606
Map & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
Definition: Sawyer/Map.h:681
T Value
Type for values associated with each key.
Definition: Sawyer/Map.h:67
Map & erase(const Key &key)
Remove a node with specified key.
Definition: Sawyer/Map.h:628
Range of values delimited by endpoints.
Definition: Interval.h:33
Map(const Map< Key2, T2, Cmp2, Alloc2 > &other)
Copy constructor.
Definition: Sawyer/Map.h:241
Map & eraseAt(const ConstKeyIterator &iter)
Remove a node by iterator.
Definition: Sawyer/Map.h:659
NodeIterator find(const Key &key)
Find a node by key.
Definition: Sawyer/Map.h:364
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: Sawyer/Map.h:530
Key least() const
Returns the minimum key.
Definition: Sawyer/Map.h:327
Bidirectional iterator over keys.
Definition: Sawyer/Map.h:173
NodeIterator upperBound(const Key &key)
Find a node close to a key.
Definition: Sawyer/Map.h:407
Map & eraseMultiple(const boost::iterator_range< OtherKeyIterator > &range)
Remove keys stored in another Map.
Definition: Sawyer/Map.h:642
Key greatest() const
Returns the maximum key.
Definition: Sawyer/Map.h:333
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Definition: Sawyer/Map.h:271
K Key
Type for keys.
Definition: Sawyer/Map.h:66
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:322
Container associating values with keys.
Definition: Sawyer/Map.h:64
Value & insertMaybe(const Key &key, const Value &value)
Conditionally insert a new key/value pair.
Definition: Sawyer/Map.h:584
Map & eraseAtMultiple(const boost::iterator_range< Iter > &range)
Remove multiple nodes by iterator range.
Definition: Sawyer/Map.h:686
Type for stored nodes.
Definition: Sawyer/Map.h:87
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:154