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 {
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&;
127 BidirectionalIterator() {}
128 BidirectionalIterator(
const BaseIterator &base): base_(base) {}
129 BidirectionalIterator(
const BidirectionalIterator &other): base_(other.base_) {}
132 Derived& operator=(
const Derived &other) { base_ = other.base_;
return *derived(); }
133 BidirectionalIterator& operator=(
const BidirectionalIterator &other) { base_ = other.base;
return *
this; }
136 Derived& operator++() { ++base_;
return *derived(); }
139 Derived operator++(
int) { Derived old=*derived(); ++*
this;
return old; }
142 Derived& operator--() { --base_;
return *derived(); }
145 Derived operator--(
int) { Derived old=*derived(); --*
this;
return old; }
151 template<
class OtherIter>
bool operator==(
const OtherIter &other)
const {
return base_ == other.base(); }
156 template<
class OtherIter>
bool operator!=(
const OtherIter &other)
const {
return base_ != other.base(); }
158 const BaseIterator& base()
const {
return base_; }
160 Derived* derived() {
return static_cast<Derived*
>(
this); }
161 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
169 class NodeIterator:
public BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> {
170 typedef BidirectionalIterator<NodeIterator, Node, typename StlMap::iterator> Super;
188 NodeIterator(
const typename StlMap::iterator &base): Super(base) {}
195 class ConstNodeIterator:
public BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> {
196 typedef BidirectionalIterator<ConstNodeIterator, const Node, typename StlMap::const_iterator> Super;
218 ConstNodeIterator(
const typename StlMap::iterator &base): Super(typename StlMap::const_iterator(base)) {}
225 class ConstKeyIterator:
public BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> {
226 typedef BidirectionalIterator<ConstKeyIterator, const Key, typename StlMap::const_iterator> Super;
243 const Key&
operator*()
const {
return this->base()->first; }
246 const Key*
operator->()
const {
return &this->base()->first; }
253 class ValueIterator:
public BidirectionalIterator<ValueIterator, Value, typename StlMap::iterator> {
254 typedef BidirectionalIterator<ValueIterator, Value, typename StlMap::iterator> Super;
268 Value&
operator*()
const {
return this->base()->second; }
278 class ConstValueIterator:
public BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> {
279 typedef BidirectionalIterator<ConstValueIterator, const Value, typename StlMap::const_iterator> Super;
299 const Value&
operator*()
const {
return this->base()->second; }
302 const Value*
operator->()
const {
return &this->base()->second; }
319 explicit Map(
const Comparator &comparator,
const Allocator &allocator =
Allocator())
320 : map_(comparator, allocator) {}
331 template<
class Key2,
class T2,
class Cmp2,
class Alloc2>
334 boost::iterator_range<OtherIterator> otherNodes = other.
nodes();
335 for (OtherIterator otherIter=otherNodes.begin(); otherIter!=otherNodes.end(); ++otherIter)
336 map_.insert(map_.end(), std::make_pair(
Key(otherIter->key()),
Value(otherIter->value())));
339 Map& operator=(
const Map &other) {
341 for (
const auto &node: other.
nodes())
342 map_.insert(map_.end(), std::make_pair(node.key(), node.value()));
349 template<
class Key2,
class T2,
class Cmp2,
class Alloc2>
353 boost::iterator_range<OtherIterator> otherNodes = other.
nodes();
354 for (OtherIterator otherIter=otherNodes.begin(); otherIter!=otherNodes.end(); ++otherIter)
355 map_.insert(map_.end(), std::make_pair(
Key(otherIter->key()),
Value(otherIter->value())));
369 boost::iterator_range<NodeIterator>
nodes() {
370 return boost::iterator_range<NodeIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
372 boost::iterator_range<ConstNodeIterator>
nodes()
const {
373 return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
382 boost::iterator_range<ConstKeyIterator>
keys() {
383 return boost::iterator_range<ConstKeyIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
385 boost::iterator_range<ConstKeyIterator>
keys()
const {
386 return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
396 boost::iterator_range<ValueIterator>
values() {
397 return boost::iterator_range<ValueIterator>(NodeIterator(map_.begin()), NodeIterator(map_.end()));
399 boost::iterator_range<ConstValueIterator>
values()
const {
400 return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(map_.begin()), ConstNodeIterator(map_.end()));
427 return map_.begin()->first;
433 typename StlMap::const_iterator last = map_.end();
462 NodeIterator
find(
const Key &key) {
463 return map_.find(key);
465 ConstNodeIterator
find(
const Key &key)
const {
466 return map_.find(key);
476 return map_.find(key)!=map_.end();
489 return map_.lower_bound(key);
492 return map_.lower_bound(key);
506 return map_.upper_bound(key);
509 return map_.upper_bound(key);
547 Value&
get(
const Key &key) {
548 typename StlMap::iterator found = map_.find(key);
549 if (found==map_.end())
550 throw std::domain_error(
"key lookup failure; key is not in map domain");
551 return found->second;
553 const Value&
get(
const Key &key)
const {
554 typename StlMap::const_iterator found = map_.find(key);
555 if (found==map_.end())
556 throw std::domain_error(
"key lookup failure; key is not in map domain");
557 return found->second;
585 typename StlMap::const_iterator found = map_.find(key);
597 typename StlMap::iterator found = map_.find(key);
598 return found == map_.end() ? dflt : found->second;
600 const Value&
getOrElse(
const Key &key,
const Value &dflt)
const {
601 typename StlMap::const_iterator found = map_.find(key);
602 return found == map_.end() ? dflt : found->second;
612 static const Value dflt;
613 typename StlMap::const_iterator found = map_.find(key);
614 return found==map_.end() ? dflt : found->second;
629 std::pair<typename StlMap::iterator, bool> inserted = map_.
insert(std::make_pair(key, value));
630 if (!inserted.second)
631 inserted.first->second = value;
663 template<
class OtherNodeIterator>
665 for (OtherNodeIterator otherIter=begin; otherIter!=end; ++otherIter)
669 template<
class OtherNodeIterator>
683 return map_.insert(std::make_pair(key, value)).first->second;
694 return map_.insert(std::make_pair(key, T())).first->second;
703 template<
class OtherNodeIterator>
705 for (OtherNodeIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
739 template<
class OtherKeyIterator>
741 for (OtherKeyIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
742 map_.
erase(Key(*otherIter));
754 map_.
erase(iter.base());
759 ASSERT_require(iter !=
keys().end());
760 typename StlMap::iterator stdIter = map_.find(*iter);
761 ASSERT_require(stdIter != map_.end());
766 map_.
erase(iter.base());
780 map_.
erase(begin.base(), end.base());
785 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.
ValueIterator & operator=(const ValueIterator &other)
Assignment.
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 & operator=(const ConstNodeIterator &other)
Assignment.
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.
NodeIterator & operator=(const NodeIterator &other)
Assignment.
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.
ConstValueIterator & operator=(const ConstValueIterator &other)
Assignment.
ConstKeyIterator & operator=(const ConstKeyIterator &other)
Assignment.
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.