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>
28 template<
class K,
class V>
41 : key_(key), value_(value) {}
46 const Key&
key()
const {
return key_; }
51 Value&
value() {
return value_; }
52 const Value&
value()
const {
return value_; }
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:
public std::iterator<std::bidirectional_iterator_tag, Value> {
71 BidirectionalIterator() {}
72 BidirectionalIterator(
const BaseIterator &base): base_(base) {}
75 Derived& operator=(
const Derived &other) {
81 Derived& operator++() {
87 Derived operator++(
int) {
88 Derived old = *derived();
94 Derived& operator--() {
100 Derived operator--(
int) {
101 Derived old = *derived();
110 template<
class OtherIter>
111 bool operator==(
const OtherIter &other)
const {
112 return base_ == other.base();
116 template<
class OtherIter>
117 bool operator!=(
const OtherIter &other)
const {
118 return base_ != other.base();
121 const BaseIterator& base()
const {
126 return static_cast<Derived*
>(
this);
128 const Derived* derived()
const {
129 return static_cast<const Derived*
>(
this);
138 class NodeIterator:
public BidirectionalIterator<NodeIterator, Node, typename StlVector::iterator> {
139 typedef BidirectionalIterator<NodeIterator, Node, typename StlVector::iterator> Super;
148 return *this->base();
153 return &*this->base();
165 class ConstNodeIterator:
public BidirectionalIterator<ConstNodeIterator, const Node, typename StlVector::const_iterator> {
166 typedef BidirectionalIterator<ConstNodeIterator, const Node, typename StlVector::const_iterator> Super;
176 : Super(typename StlVector::const_iterator(other.base())) {}
180 return *this->base();
185 return &*this->base();
191 ConstNodeIterator(
const typename StlVector::iterator &base)
192 : Super(typename StlVector::const_iterator(base)) {}
199 class ConstKeyIterator:
public BidirectionalIterator<ConstKeyIterator, const Key, typename StlVector::const_iterator> {
200 typedef BidirectionalIterator<ConstKeyIterator, const Key, typename StlVector::const_iterator> Super;
210 : Super(typename StlVector::const_iterator(other.base())) {}
214 : Super(other.base()) {}
218 return this->base()->key();
223 return &this->base()->key();
231 class ValueIterator:
public BidirectionalIterator<ValueIterator, Value, typename StlVector::iterator> {
232 typedef BidirectionalIterator<ValueIterator, Value, typename StlVector::iterator> Super;
242 : Super(other.base()) {}
246 return this->base()->value();
251 return &this->base()->value();
258 class ConstValueIterator:
public BidirectionalIterator<ConstValueIterator, const Value, typename StlVector::const_iterator> {
259 typedef BidirectionalIterator<ConstValueIterator, const Value, typename StlVector::const_iterator> Super;
269 : Super(typename StlVector::const_iterator(other.base())) {}
273 : Super(other.base()) {}
277 : Super(typename StlVector::const_iterator(other.base())) {}
281 return this->base()->value();
286 return &this->base()->value();
293 typedef typename StlVector::value_type value_type;
294 typedef typename StlVector::allocator_type allocator_type;
295 typedef typename StlVector::reference reference;
296 typedef typename StlVector::pointer pointer;
297 typedef typename StlVector::const_pointer const_pointer;
298 typedef typename StlVector::iterator iterator;
299 typedef typename StlVector::const_iterator const_iterator;
300 typedef typename StlVector::reverse_iterator reverse_iterator;
301 typedef typename StlVector::const_reverse_iterator const_reverse_iterator;
302 typedef typename StlVector::difference_type difference_type;
303 typedef typename StlVector::size_type size_type;
311 : needsUpdate_(false) {}
334 void insert(
const Key &item,
const Value &value) {
336 Node node(item, value);
337 typename std::vector<Node>::iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
338 if (items_.end() == lb || lb->key()->id() != item->id()) {
339 items_.insert(lb, node);
351 Node node(item, value);
352 typename std::vector<Node>::iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
353 if (items_.end() == lb || lb->key()->id() != item->id())
354 lb = items_.insert(lb, node);
369 Node node(item,
Value());
370 typename std::vector<Node>::iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
371 if (lb != items_.end() && lb->key()->id() == item->id())
378 needsUpdate_ =
false;
388 Node node(item,
Value());
389 typename std::vector<Node>::const_iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
390 return lb != items_.end() && lb->key()->id() == item->id();
396 Node node(item,
Value());
397 typename std::vector<Node>::const_iterator lb = std::lower_bound(items_.begin(), items_.end(), node, sortById);
398 if (lb != items_.end() && lb->key()->id() == item->id()) {
420 boost::iterator_range<NodeIterator>
nodes() {
422 return boost::iterator_range<NodeIterator>(NodeIterator(items_.begin()), NodeIterator(items_.end()));
424 boost::iterator_range<ConstNodeIterator>
nodes()
const {
426 return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(items_.begin()), ConstNodeIterator(items_.end()));
435 boost::iterator_range<ConstKeyIterator>
keys() {
437 return boost::iterator_range<ConstKeyIterator>(NodeIterator(items_.begin()), NodeIterator(items_.end()));
439 boost::iterator_range<ConstKeyIterator>
keys()
const {
441 return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(items_.begin()), ConstNodeIterator(items_.end()));
451 boost::iterator_range<ValueIterator>
values() {
453 return boost::iterator_range<ValueIterator>(NodeIterator(items_.begin()), NodeIterator(items_.end()));
455 boost::iterator_range<ConstValueIterator>
values()
const {
457 return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(items_.begin()), ConstNodeIterator(items_.end()));
462 NodeIterator begin() {
return NodeIterator(items_.begin()); }
463 ConstNodeIterator begin()
const {
return NodeIterator(items_.begin()); }
464 NodeIterator end() {
return NodeIterator(items_.end()); }
465 ConstNodeIterator end()
const {
return NodeIterator(items_.end()); }
471 static bool sortById(
const Node &a,
const Node &b) {
472 return a.key()->id() < b.key()->id();
475 void update()
const {
477 std::sort(items_.begin(), items_.end(), sortById);
478 needsUpdate_ =
false;
485 for (
size_t i = 1; i < items_.size(); ++i)
486 ASSERT_require(sortById(items_[i-1], items_[i]));
Bidirectional iterator over keys.
void clear()
Remove all entries from this container.
void insert(const Key &item, const Value &value)
Insert the specified edge or vertex associated with a value.
Value * operator->() const
Dereference iterator to return address of user-defined value.
Value & operator*() const
Dereference iterator to return the user-defined value.
Bidirectional iterator over values.
ConstValueIterator(const ValueIterator &other)
Copy constructor.
const Value * operator->() const
Dereference iterator to return address of the user-defined data.
ValueIterator(const ValueIterator &other)
Copy constructor.
The data stored at each node of the map.
K Key
Graph edge or vertex iterator used as keys.
ConstNodeIterator(const ConstNodeIterator &other)
Copy constructor.
ConstValueIterator(const NodeIterator &other)
Copy constructor.
Bidirectional iterator over constant key/value nodes.
void updateIdNumbers()
Indicate that an update is necessary due to erasures.
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Node(const Key &key, const Value &value)
Constructor.
ConstKeyIterator(const ConstKeyIterator &other)
Copy constructor.
Name space for the entire library.
const Key & key() const
Access the key of this node.
V Value
Type of value associated with each key.
const Value & value() const
Access the value of this node.
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
ConstValueIterator(const ConstNodeIterator &other)
Copy constructor.
Node & operator*() const
Dereference iterator to return a storage node.
const Node * operator->() const
Returns a pointer to a storage node.
ConstNodeIterator(const NodeIterator &other)
Copy constructor.
Map of graph edge or vertex pointers to some other value.
Value & insertMaybeDefault(const Key &item)
Insert a default value if its key doesn't already exist.
Value & value()
Access the value of this node.
Bidirectional iterator over values.
void erase(const Key &item)
Erase the specified key if it exists.
Node * operator->() const
Pointer to storage node.
ConstValueIterator(const ConstValueIterator &other)
Copy constructor.
NodeIterator(const NodeIterator &other)
Copy constructor.
GraphIteratorMap()
Default construct an empty map.
ConstKeyIterator(const ConstNodeIterator &other)
Copy constructor.
ConstKeyIterator(const NodeIterator &other)
Copy constructor.
const Key * operator->() const
Returns a pointer to the key.
const Node & operator*() const
Dereference iterator to return a storage node.
ValueIterator(const NodeIterator &other)
Copy constructor.
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
bool exists(const Key &item) const
Does the key exist in the map?
Value & insertMaybe(const Key &item, const Value &value)
Insert a value only if its key doesn't already exist.
Bidirectional iterator over key/value nodes.
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
Value operator[](const Key &item) const
Return the value associated with an existing key.
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
const Value & operator*() const
Dereference iterator to return the value of the user-defined data.
const Key & operator*() const
Returns the key for the current iterator.
Sawyer::Optional< Value > find(const Key &item) const
Find the value associated with a particular key.