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>
64 class Cmp = std::less<K>,
65 class Alloc = std::allocator<std::pair<const K, T> > >
74 typedef std::map<Key, Value, Comparator, Alloc> StlMap;
78 friend class boost::serialization::access;
81 void serialize(S &s,
const unsigned ) {
82 s & BOOST_SERIALIZATION_NVP(map_);
89 class Node:
private std::pair<const Key, Value> {
92 explicit Node(
const std::pair<const Key, Value> &pair): std::pair<const Key, Value>(pair) {}
98 const Key&
key()
const {
return this->first; }
105 Value&
value() {
return this->second; }
106 const Value&
value()
const {
return this->second; }
114 template<
class Derived,
class Value,
class BaseIterator>
115 class BidirectionalIterator:
public std::iterator<std::bidirectional_iterator_tag, Value> {
118 BidirectionalIterator() {}
119 BidirectionalIterator(
const BaseIterator &base): base_(base) {}
121 Derived&
operator=(
const Derived &other) { base_ = other.base_;
return *derived(); }
124 Derived& operator++() { ++base_;
return *derived(); }
127 Derived operator++(
int) { Derived old=*derived(); ++*
this;
return old; }
130 Derived& operator--() { --base_;
return *derived(); }
133 Derived operator--(
int) { Derived old=*derived(); --*
this;
return old; }
139 template<
class OtherIter>
bool operator==(
const OtherIter &other)
const {
return base_ == other.base(); }
144 template<
class OtherIter>
bool operator!=(
const OtherIter &other)
const {
return base_ != other.base(); }
146 const BaseIterator& base()
const {
return base_; }
148 Derived* derived() {
return static_cast<Derived*
>(
this); }
149 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
157 class NodeIterator:
public BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> {
158 typedef BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> Super;
173 NodeIterator(
const typename StlMap::iterator &base): Super(base) {}
180 class ConstNodeIterator:
public BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> {
181 typedef BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> Super;
200 ConstNodeIterator(
const typename StlMap::iterator &base): Super(typename StlMap::const_iterator(base)) {}
207 class ConstKeyIterator:
public BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> {
208 typedef BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> Super;
222 const Key&
operator*()
const {
return this->base()->first; }
225 const Key*
operator->()
const {
return &this->base()->first; }
232 class ValueIterator:
public BidirectionalIterator<ValueIterator, Value, typename StlMap::iterator> {
233 typedef BidirectionalIterator<ValueIterator, Value, typename StlMap::iterator> Super;
244 Value&
operator*()
const {
return this->base()->second; }
254 class ConstValueIterator:
public BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> {
255 typedef BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> Super;
272 const Value&
operator*()
const {
return this->base()->second; }
275 const Value*
operator->()
const {
return &this->base()->second; }
292 explicit Map(
const Comparator &comparator,
const Allocator &allocator =
Allocator())
293 : map_(comparator, allocator) {}
304 template<
class Key2,
class T2,
class Cmp2,
class Alloc2>
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())));
315 template<
class Key2,
class T2,
class Cmp2,
class Alloc2>
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())));
335 boost::iterator_range<NodeIterator>
nodes() {
336 return boost::iterator_range<NodeIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
338 boost::iterator_range<ConstNodeIterator>
nodes()
const {
339 return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
348 boost::iterator_range<ConstKeyIterator>
keys() {
349 return boost::iterator_range<ConstKeyIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
351 boost::iterator_range<ConstKeyIterator>
keys()
const {
352 return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
362 boost::iterator_range<ValueIterator>
values() {
363 return boost::iterator_range<ValueIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
365 boost::iterator_range<ConstValueIterator>
values()
const {
366 return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
393 return map_.begin()->first;
399 typename StlMap::const_iterator last = map_.end();
428 NodeIterator
find(
const Key &key) {
429 return map_.find(key);
431 ConstNodeIterator
find(
const Key &key)
const {
432 return map_.find(key);
442 return map_.find(key)!=map_.end();
455 return map_.lower_bound(key);
458 return map_.lower_bound(key);
472 return map_.upper_bound(key);
475 return map_.upper_bound(key);
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;
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;
551 typename StlMap::const_iterator found = map_.find(key);
563 typename StlMap::iterator found = map_.find(key);
564 return found == map_.end() ? dflt : found->second;
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;
578 static const Value dflt;
579 typename StlMap::const_iterator found = map_.find(key);
580 return found==map_.end() ? dflt : found->second;
595 std::pair<typename StlMap::iterator, bool> inserted = map_.
insert(std::make_pair(key, value));
596 if (!inserted.second)
597 inserted.first->second = value;
629 template<
class OtherNodeIterator>
631 for (OtherNodeIterator otherIter=begin; otherIter!=end; ++otherIter)
635 template<
class OtherNodeIterator>
649 return map_.insert(std::make_pair(key, value)).first->second;
660 return map_.insert(std::make_pair(key, T())).first->second;
669 template<
class OtherNodeIterator>
671 for (OtherNodeIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
705 template<
class OtherKeyIterator>
707 for (OtherKeyIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
708 map_.
erase(Key(*otherIter));
720 map_.
erase(iter.base());
725 ASSERT_require(iter !=
keys().end());
726 typename StlMap::iterator stdIter = map_.find(*iter);
727 ASSERT_require(stdIter != map_.end());
732 map_.
erase(iter.base());
746 map_.
erase(begin.base(), end.base());
751 map_.
erase(range.begin().base(), range.end().base());
const Value * operator->() const
Returns a pointer to the value of the storage node.
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
Map(const Map &other)
Copy constructor.
bool exists(const Key &key) const
Determine if a key exists.
Value & operator[](const Key &key)
Return a reference to an existing value.
NodeIterator(const NodeIterator &other)
Copy constructor.
Optional< Value > getOptional(const Key &key) const
Lookup and return a value or nothing.
const Value & operator[](const Key &key) const
Return a reference to an existing value.
Map()
Default constructor.
ValueIterator(const ValueIterator &other)
Copy constructor.
ConstNodeIterator(const ConstNodeIterator &other)
Copy constructor.
Value & value()
Value part of key/value node.
ConstNodeIterator upperBound(const Key &key) const
Find a node close to a key.
Map(const Comparator &comparator, const Allocator &allocator=Allocator())
Constructs an empty map.
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
Value & operator*() const
Dereference iterator to return the value of the storage node.
const Value & getOrElse(const Key &key, const Value &dflt) const
Lookup and return a value or something else.
ConstNodeIterator lowerBound(const Key &key) const
Find a node close to a key.
Value & insertMaybeDefault(const Key &key)
Conditionally insert a new key with default value.
Map & eraseAt(const ValueIterator &iter)
Remove a node by iterator.
const Key & operator*() const
Dereference iterator to return the interval of the storage node.
Node * operator->() const
Returns a pointer to a storage node.
Map & clear()
Remove all nodes.
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Cmp Comparator
Type of comparator, third template argument.
Name space for the entire library.
Bidirectional iterator over key/value nodes.
Alloc Allocator
Type of allocator, fourth template argument.
Value & getOrElse(const Key &key, Value &dflt)
Lookup and return a value or something else.
bool isEmpty() const
Determines whether this container is empty.
Map & insertDefault(const Key &key)
Insert or update a key with a default value.
ConstNodeIterator find(const Key &key) const
Find a node by key.
Map & insertMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Insert multiple values.
NodeIterator lowerBound(const Key &key)
Find a node close to a key.
Bidirectional iterator over values.
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
const Key * operator->() const
Returns a pointer to the interval of the storage node.
ConstKeyIterator(const NodeIterator &other)
Copy constructor.
ConstKeyIterator(const ConstKeyIterator &other)
Copy constructor.
ConstValueIterator(const ConstNodeIterator &other)
Copy constructor.
Node & operator*() const
Dereference iterator to return a storage node.
const Key & key() const
Key part of key/value node.
Map & insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end)
Insert multiple values.
Bidirectional iterator over values.
Map & operator=(const Map< Key2, T2, Cmp2, Alloc2 > &other)
Make this map be a copy of another map.
ConstNodeIterator(const NodeIterator &other)
Copy constructor.
Interval< Key > hull() const
Returns the range of keys in this map.
const Value & getOrDefault(const Key &key) const
Lookup and return a value or a default.
const Value & value() const
Value part of key/value node.
Map & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Map & insertMaybeMultiple(const boost::iterator_range< OtherNodeIterator > &range)
Conditionally insert multiple key/value pairs.
Map & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
T Value
Type for values associated with each key.
Map & erase(const Key &key)
Remove a node with specified key.
Range of values delimited by endpoints.
Map(const Map< Key2, T2, Cmp2, Alloc2 > &other)
Copy constructor.
Map & eraseAt(const ConstKeyIterator &iter)
Remove a node by iterator.
NodeIterator find(const Key &key)
Find a node by key.
ConstValueIterator(const ConstValueIterator &other)
Copy constructor.
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Key least() const
Returns the minimum key.
ConstKeyIterator(const ConstNodeIterator &other)
Copy constructor.
ConstValueIterator(const ValueIterator &other)
Copy constructor.
const Node * operator->() const
Returns a pointer to a storage node.
Bidirectional iterator over keys.
NodeIterator upperBound(const Key &key)
Find a node close to a key.
Map & eraseMultiple(const boost::iterator_range< OtherKeyIterator > &range)
Remove keys stored in another Map.
ConstValueIterator(const NodeIterator &other)
Copy constructor.
Key greatest() const
Returns the maximum key.
const Node & operator*() const
Dereference iterator to return a storage node.
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
size_t size() const
Number of nodes, keys, or values in this container.
Container associating values with keys.
const Value & operator*() const
Dereference iterator to return the value of the storage node.
Value & insertMaybe(const Key &key, const Value &value)
Conditionally insert a new key/value pair.
Map & eraseAtMultiple(const boost::iterator_range< Iter > &range)
Remove multiple nodes by iterator range.
Bidirectional iterator over key/value nodes.
Value * operator->() const
Returns a pointer to the value of the storage node.
ValueIterator(const NodeIterator &other)
Copy constructor.