ROSE 0.11.145.147
GraphIteratorMap.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://gitlab.com/charger7534/sawyer.git.
4
5
6
7
8#ifndef Sawyer_GraphIteratorMap_H
9#define Sawyer_GraphIteratorMap_H
10
11#include <Sawyer/Graph.h>
12#include <Sawyer/Optional.h>
13#include <boost/range/iterator_range.hpp>
14
15namespace Sawyer {
16namespace Container {
17
28template<class K, class V>
30public:
31 typedef K Key;
32 typedef V Value;
35 class Node {
36 Key key_;
37 Value value_;
38 public:
40 Node(const Key &key, const Value &value)
41 : key_(key), value_(value) {}
42
46 const Key& key() const { return key_; }
47
51 Value& value() { return value_; }
52 const Value& value() const { return value_; }
54 };
55
56private:
57 // These members are mutable so that we can delay the sorting until the last possible minute while still appearing to
58 // have a const-correct interface.
59 typedef std::vector<Node> StlVector;
60 mutable StlVector items_; // the pointers to graph edges or vertices stored in this container
61 mutable bool needsUpdate_; // true if the items_ are possibly not sorted
62
64 // Iterators
66private:
67 template<class Derived, class Value, class BaseIterator>
68 class BidirectionalIterator {
69 public:
70 // Five standard iterator types
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&;
76
77 protected:
78 BaseIterator base_;
79 BidirectionalIterator() {}
80 BidirectionalIterator(const BaseIterator &base): base_(base) {}
81 public:
83 Derived& operator=(const Derived &other) {
84 base_ = other.base_;
85 return *derived();
86 }
87
89 Derived& operator++() {
90 ++base_;
91 return *derived();
92 }
93
95 Derived operator++(int) {
96 Derived old = *derived();
97 ++*this;
98 return old;
99 }
100
102 Derived& operator--() {
103 --base_;
104 return *derived();
105 }
106
108 Derived operator--(int) {
109 Derived old = *derived();
110 ++*this;
111 return old;
112 }
113
118 template<class OtherIter>
119 bool operator==(const OtherIter &other) const {
120 return base_ == other.base();
121 }
122
124 template<class OtherIter>
125 bool operator!=(const OtherIter &other) const {
126 return base_ != other.base();
127 }
128
129 const BaseIterator& base() const {
130 return base_;
131 }
132 protected:
133 Derived* derived() {
134 return static_cast<Derived*>(this);
135 }
136 const Derived* derived() const {
137 return static_cast<const Derived*>(this);
138 }
139 };
140
141public:
146 class NodeIterator: public BidirectionalIterator<NodeIterator, Node, typename StlVector::iterator> {
147 typedef BidirectionalIterator<NodeIterator, Node, typename StlVector::iterator> Super;
148 public:
149 NodeIterator() {}
150
152 NodeIterator(const NodeIterator &other): Super(other) {} // implicit
153
155 Node& operator*() const {
156 return *this->base();
157 }
158
160 Node* operator->() const {
161 return &*this->base();
162 }
163 private:
164 friend class GraphIteratorMap;
165 NodeIterator(const typename StlVector::iterator &base)
166 : Super(base) {}
167 };
168
173 class ConstNodeIterator: public BidirectionalIterator<ConstNodeIterator, const Node, typename StlVector::const_iterator> {
174 typedef BidirectionalIterator<ConstNodeIterator, const Node, typename StlVector::const_iterator> Super;
175 public:
177
179 ConstNodeIterator(const ConstNodeIterator &other) // implicit
180 : Super(other) {}
181
183 ConstNodeIterator(const NodeIterator &other) // implicit
184 : Super(typename StlVector::const_iterator(other.base())) {}
185
187 const Node& operator*() const {
188 return *this->base();
189 }
190
192 const Node* operator->() const {
193 return &*this->base();
194 }
195 private:
196 friend class GraphIteratorMap;
197 ConstNodeIterator(const typename StlVector::const_iterator &base)
198 : Super(base) {}
199 ConstNodeIterator(const typename StlVector::iterator &base)
200 : Super(typename StlVector::const_iterator(base)) {}
201 };
202
207 class ConstKeyIterator: public BidirectionalIterator<ConstKeyIterator, const Key, typename StlVector::const_iterator> {
208 typedef BidirectionalIterator<ConstKeyIterator, const Key, typename StlVector::const_iterator> Super;
209 public:
211
213 ConstKeyIterator(const ConstKeyIterator &other) // implicit
214 : Super(other) {}
215
217 ConstKeyIterator(const NodeIterator &other) // implicit
218 : Super(typename StlVector::const_iterator(other.base())) {}
219
221 ConstKeyIterator(const ConstNodeIterator &other) // implicit
222 : Super(other.base()) {}
223
225 const Key& operator*() const {
226 return this->base()->key();
227 }
228
230 const Key* operator->() const {
231 return &this->base()->key();
232 }
233 };
234
239 class ValueIterator: public BidirectionalIterator<ValueIterator, Value, typename StlVector::iterator> {
240 typedef BidirectionalIterator<ValueIterator, Value, typename StlVector::iterator> Super;
241 public:
242 ValueIterator() {}
243
246 : Super(other) {}
247
249 ValueIterator(const NodeIterator &other) // implicit
250 : Super(other.base()) {}
251
253 Value& operator*() const {
254 return this->base()->value();
255 }
256
258 Value* operator->() const {
259 return &this->base()->value();
260 }
261 };
262
266 class ConstValueIterator: public BidirectionalIterator<ConstValueIterator, const Value, typename StlVector::const_iterator> {
267 typedef BidirectionalIterator<ConstValueIterator, const Value, typename StlVector::const_iterator> Super;
268 public:
270
273 : Super(other) {}
274
276 ConstValueIterator(const ValueIterator &other) // implicit
277 : Super(typename StlVector::const_iterator(other.base())) {}
278
280 ConstValueIterator(const ConstNodeIterator &other) // implicit
281 : Super(other.base()) {}
282
284 ConstValueIterator(const NodeIterator &other) // implicit
285 : Super(typename StlVector::const_iterator(other.base())) {}
286
288 const Value& operator*() const {
289 return this->base()->value();
290 }
291
293 const Value* operator->() const {
294 return &this->base()->value();
295 }
296 };
297
298public:
299 // Standard types needed by C++ containers with random access iterators for the C++-style iterating functions like begin()
300 // and end().
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;
312
314 // Constructors
316public:
319 : needsUpdate_(false) {}
320
322 // Mutators
324public:
334 needsUpdate_ = true;
335 }
336
342 void insert(const Key &item, const Value &value) {
343 update();
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);
348 } else {
349 lb->value() = value;
350 }
351 }
352
357 Value& insertMaybe(const Key &item, const Value &value) {
358 update();
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);
363 return lb->value();
364 }
365
371 return insertMaybe(item, Value());
372 }
373
375 void erase(const Key &item) {
376 update();
377 Node node(item, Value());
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())
380 items_.erase(lb);
381 }
382
384 void clear() {
385 items_.clear();
386 needsUpdate_ = false;
387 }
388
390 // Queries
392public:
394 bool exists(const Key &item) const {
395 update();
396 Node node(item, Value());
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();
399 }
400
402 Sawyer::Optional<Value> find(const Key &item) const {
403 update();
404 Node node(item, Value());
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()) {
407 return lb->value();
408 } else {
409 return Sawyer::Nothing();
410 }
411 }
412
414 Value operator[](const Key &item) const {
415 update();
416 return *find(item);
417 }
418
420 // Iteration
422
428 boost::iterator_range<NodeIterator> nodes() {
429 update();
430 return boost::iterator_range<NodeIterator>(NodeIterator(items_.begin()), NodeIterator(items_.end()));
431 }
432 boost::iterator_range<ConstNodeIterator> nodes() const {
433 update();
434 return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(items_.begin()), ConstNodeIterator(items_.end()));
435 }
443 boost::iterator_range<ConstKeyIterator> keys() {
444 update();
445 return boost::iterator_range<ConstKeyIterator>(NodeIterator(items_.begin()), NodeIterator(items_.end()));
446 }
447 boost::iterator_range<ConstKeyIterator> keys() const {
448 update();
449 return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(items_.begin()), ConstNodeIterator(items_.end()));
450 }
459 boost::iterator_range<ValueIterator> values() {
460 update();
461 return boost::iterator_range<ValueIterator>(NodeIterator(items_.begin()), NodeIterator(items_.end()));
462 }
463 boost::iterator_range<ConstValueIterator> values() const {
464 update();
465 return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(items_.begin()), ConstNodeIterator(items_.end()));
466 }
469 // Undocumented C++-style iterators iterator over the key+value nodes.
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()); }
474
476 // Internal functions
478private:
479 static bool sortById(const Node &a, const Node &b) {
480 return a.key()->id() < b.key()->id();
481 }
482
483 void update() const {
484 if (needsUpdate_) {
485 std::sort(items_.begin(), items_.end(), sortById);
486 needsUpdate_ = false;
487 } else {
488 check();
489 }
490 }
491
492 void check() const {
493 for (size_t i = 1; i < items_.size(); ++i)
494 ASSERT_require(sortById(items_[i-1], items_[i]));
495 }
496};
497
498} // namespace
499} // namespace
500
501#endif
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.
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.
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.
Represents no value.
Definition Optional.h:36
Holds a value or nothing.
Definition Optional.h:56
Sawyer support library.