8#ifndef Sawyer_GraphIteratorMap_H
9#define Sawyer_GraphIteratorMap_H
11#include <Sawyer/Graph.h>
12#include <Sawyer/Optional.h>
13#include <boost/range/iterator_range.hpp>
28template<
class K,
class V>
46 const Key&
key()
const {
return key_; }
59 typedef std::vector<Node> StlVector;
60 mutable StlVector items_;
61 mutable bool needsUpdate_;
67 template<
class Derived,
class Value,
class BaseIterator>
68 class BidirectionalIterator {
71 using iterator_category = std::bidirectional_iterator_tag;
72 using value_type =
Value;
73 using difference_type = std::ptrdiff_t;
74 using pointer =
Value*;
75 using reference =
Value&;
79 BidirectionalIterator() {}
80 BidirectionalIterator(
const BaseIterator &base): base_(base) {}
83 Derived& operator=(
const Derived &other) {
89 Derived& operator++() {
95 Derived operator++(
int) {
96 Derived old = *derived();
102 Derived& operator--() {
108 Derived operator--(
int) {
109 Derived old = *derived();
118 template<
class OtherIter>
119 bool operator==(
const OtherIter &other)
const {
120 return base_ == other.base();
124 template<
class OtherIter>
125 bool operator!=(
const OtherIter &other)
const {
126 return base_ != other.base();
129 const BaseIterator& base()
const {
134 return static_cast<Derived*
>(
this);
136 const Derived* derived()
const {
137 return static_cast<const Derived*
>(
this);
146 class NodeIterator:
public BidirectionalIterator<NodeIterator, Node, typename StlVector::iterator> {
147 typedef BidirectionalIterator<NodeIterator, Node, typename StlVector::iterator> Super;
156 return *this->base();
161 return &*this->base();
173 class ConstNodeIterator:
public BidirectionalIterator<ConstNodeIterator, const Node, typename StlVector::const_iterator> {
174 typedef BidirectionalIterator<ConstNodeIterator, const Node, typename StlVector::const_iterator> Super;
184 : Super(typename StlVector::const_iterator(other.base())) {}
188 return *this->base();
193 return &*this->base();
199 ConstNodeIterator(
const typename StlVector::iterator &base)
200 : Super(typename StlVector::const_iterator(base)) {}
207 class ConstKeyIterator:
public BidirectionalIterator<ConstKeyIterator, const Key, typename StlVector::const_iterator> {
208 typedef BidirectionalIterator<ConstKeyIterator, const Key, typename StlVector::const_iterator> Super;
218 : Super(typename StlVector::const_iterator(other.base())) {}
222 : Super(other.base()) {}
226 return this->base()->key();
231 return &this->base()->key();
239 class ValueIterator:
public BidirectionalIterator<ValueIterator, Value, typename StlVector::iterator> {
240 typedef BidirectionalIterator<ValueIterator, Value, typename StlVector::iterator> Super;
250 : Super(other.base()) {}
254 return this->base()->value();
259 return &this->base()->value();
266 class ConstValueIterator:
public BidirectionalIterator<ConstValueIterator, const Value, typename StlVector::const_iterator> {
267 typedef BidirectionalIterator<ConstValueIterator, const Value, typename StlVector::const_iterator> Super;
277 : Super(typename StlVector::const_iterator(other.base())) {}
281 : Super(other.base()) {}
285 : Super(typename StlVector::const_iterator(other.base())) {}
289 return this->base()->value();
294 return &this->base()->value();
301 typedef typename StlVector::value_type value_type;
302 typedef typename StlVector::allocator_type allocator_type;
303 typedef typename StlVector::reference reference;
304 typedef typename StlVector::pointer pointer;
305 typedef typename StlVector::const_pointer const_pointer;
306 typedef typename StlVector::iterator iterator;
307 typedef typename StlVector::const_iterator const_iterator;
308 typedef typename StlVector::reverse_iterator reverse_iterator;
309 typedef typename StlVector::const_reverse_iterator const_reverse_iterator;
310 typedef typename StlVector::difference_type difference_type;
311 typedef typename StlVector::size_type size_type;
319 : needsUpdate_(false) {}
344 Node node(item, value);
345 typename std::vector<Node>::iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
346 if (items_.end() == lb || lb->key()->id() != item->id()) {
347 items_.insert(lb, node);
359 Node node(item, value);
360 typename std::vector<Node>::iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
361 if (items_.end() == lb || lb->key()->id() != item->id())
362 lb = items_.insert(lb, node);
378 typename std::vector<Node>::iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
379 if (lb != items_.end() && lb->key()->id() == item->id())
386 needsUpdate_ =
false;
397 typename std::vector<Node>::const_iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
398 return lb != items_.end() && lb->key()->id() == item->id();
405 typename std::vector<Node>::const_iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
406 if (lb != items_.end() && lb->key()->id() == item->id()) {
428 boost::iterator_range<NodeIterator>
nodes() {
432 boost::iterator_range<ConstNodeIterator>
nodes()
const {
443 boost::iterator_range<ConstKeyIterator>
keys() {
447 boost::iterator_range<ConstKeyIterator>
keys()
const {
459 boost::iterator_range<ValueIterator>
values() {
463 boost::iterator_range<ConstValueIterator>
values()
const {
470 NodeIterator begin() {
return NodeIterator(items_.begin()); }
471 ConstNodeIterator begin()
const {
return NodeIterator(items_.begin()); }
472 NodeIterator end() {
return NodeIterator(items_.end()); }
473 ConstNodeIterator end()
const {
return NodeIterator(items_.end()); }
479 static bool sortById(
const Node &a,
const Node &b) {
480 return a.key()->id() < b.key()->id();
483 void update()
const {
485 std::sort(items_.begin(), items_.end(), sortById);
486 needsUpdate_ =
false;
493 for (
size_t i = 1; i < items_.size(); ++i)
494 ASSERT_require(sortById(items_[i-1], items_[i]));
Bidirectional iterator over keys.
const Key * operator->() const
Returns a pointer to the key.
ConstKeyIterator(const ConstKeyIterator &other)
Copy constructor.
ConstKeyIterator(const NodeIterator &other)
Copy constructor.
ConstKeyIterator(const ConstNodeIterator &other)
Copy constructor.
const Key & operator*() const
Returns the key for the current iterator.
Bidirectional iterator over constant key/value nodes.
const Node * operator->() const
Returns a pointer to a storage node.
ConstNodeIterator(const NodeIterator &other)
Copy constructor.
const Node & operator*() const
Dereference iterator to return a storage node.
ConstNodeIterator(const ConstNodeIterator &other)
Copy constructor.
Bidirectional iterator over values.
ConstValueIterator(const ConstNodeIterator &other)
Copy constructor.
ConstValueIterator(const ConstValueIterator &other)
Copy constructor.
const Value & operator*() const
Dereference iterator to return the value of the user-defined data.
const Value * operator->() const
Dereference iterator to return address of the user-defined data.
ConstValueIterator(const ValueIterator &other)
Copy constructor.
ConstValueIterator(const NodeIterator &other)
Copy constructor.
Bidirectional iterator over key/value nodes.
Node * operator->() const
Pointer to storage node.
Node & operator*() const
Dereference iterator to return a storage node.
NodeIterator(const NodeIterator &other)
Copy constructor.
The data stored at each node of the map.
Node(const Key &key, const Value &value)
Constructor.
const Value & value() const
Access the value of this node.
const Key & key() const
Access the key of this node.
Value & value()
Access the value of this node.
Bidirectional iterator over values.
ValueIterator(const NodeIterator &other)
Copy constructor.
ValueIterator(const ValueIterator &other)
Copy constructor.
Value & operator*() const
Dereference iterator to return the user-defined value.
Value * operator->() const
Dereference iterator to return address of user-defined value.
Map of graph edge or vertex pointers to some other value.
void erase(const Key &item)
Erase the specified key if it exists.
Value & insertMaybeDefault(const Key &item)
Insert a default value if its key doesn't already exist.
void updateIdNumbers()
Indicate that an update is necessary due to erasures.
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
boost::iterator_range< ValueIterator > values()
Iterators for container values.
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
Value operator[](const Key &item) const
Return the value associated with an existing key.
V Value
Type of value associated with each key.
K Key
Graph edge or vertex iterator used as keys.
bool exists(const Key &item) const
Does the key exist in the map?
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
void insert(const Key &item, const Value &value)
Insert the specified edge or vertex associated with a value.
Value & insertMaybe(const Key &item, const Value &value)
Insert a value only if its key doesn't already exist.
Sawyer::Optional< Value > find(const Key &item) const
Find the value associated with a particular key.
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
void clear()
Remove all entries from this container.
GraphIteratorMap()
Default construct an empty map.
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
Holds a value or nothing.