ROSE  0.11.96.11
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://github.com/matzke1/sawyer.
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 
15 namespace Sawyer {
16 namespace Container {
17 
28 template<class K, class V>
30 public:
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 
56 private:
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
66 private:
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 
141 public:
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:
176  ConstNodeIterator() {}
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:
210  ConstKeyIterator() {}
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:
269  ConstValueIterator() {}
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 
298 public:
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
316 public:
319  : needsUpdate_(false) {}
320 
322  // Mutators
324 public:
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 
370  Value& insertMaybeDefault(const Key &item) {
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
392 public:
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
478 private:
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
Sawyer::Container::GraphIteratorMap::insertMaybe
Value & insertMaybe(const Key &item, const Value &value)
Insert a value only if its key doesn't already exist.
Definition: GraphIteratorMap.h:357
Sawyer::Container::GraphIteratorMap::Node::value
const Value & value() const
Access the value of this node.
Definition: GraphIteratorMap.h:52
Sawyer::Container::GraphIteratorMap::ConstNodeIterator::operator*
const Node & operator*() const
Dereference iterator to return a storage node.
Definition: GraphIteratorMap.h:187
Sawyer::Container::GraphIteratorMap::NodeIterator::operator*
Node & operator*() const
Dereference iterator to return a storage node.
Definition: GraphIteratorMap.h:155
Sawyer::Container::GraphIteratorMap
Map of graph edge or vertex pointers to some other value.
Definition: GraphIteratorMap.h:29
Sawyer::Container::GraphIteratorMap::nodes
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for container nodes.
Definition: GraphIteratorMap.h:432
Sawyer::Optional< Value >
Sawyer::Container::GraphIteratorMap::ConstKeyIterator
Bidirectional iterator over keys.
Definition: GraphIteratorMap.h:207
Sawyer::Container::GraphIteratorMap::erase
void erase(const Key &item)
Erase the specified key if it exists.
Definition: GraphIteratorMap.h:375
Sawyer::Nothing
Represents no value.
Definition: Optional.h:32
Sawyer::Container::GraphIteratorMap::ConstValueIterator::ConstValueIterator
ConstValueIterator(const ConstNodeIterator &other)
Copy constructor.
Definition: GraphIteratorMap.h:280
Sawyer::Container::GraphIteratorMap::clear
void clear()
Remove all entries from this container.
Definition: GraphIteratorMap.h:384
Sawyer::Container::GraphIteratorMap::ValueIterator::ValueIterator
ValueIterator(const NodeIterator &other)
Copy constructor.
Definition: GraphIteratorMap.h:249
Sawyer::Container::GraphIteratorMap::values
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Definition: GraphIteratorMap.h:459
Sawyer::Container::GraphIteratorMap::ConstKeyIterator::operator->
const Key * operator->() const
Returns a pointer to the key.
Definition: GraphIteratorMap.h:230
Sawyer::Container::GraphIteratorMap::ConstValueIterator::ConstValueIterator
ConstValueIterator(const NodeIterator &other)
Copy constructor.
Definition: GraphIteratorMap.h:284
Sawyer::Container::GraphIteratorMap::Key
K Key
Graph edge or vertex iterator used as keys.
Definition: GraphIteratorMap.h:31
Sawyer::Container::GraphIteratorMap::updateIdNumbers
void updateIdNumbers()
Indicate that an update is necessary due to erasures.
Definition: GraphIteratorMap.h:333
Sawyer::Container::GraphIteratorMap::Node
The data stored at each node of the map.
Definition: GraphIteratorMap.h:35
Sawyer::Container::GraphIteratorMap::ValueIterator::operator*
Value & operator*() const
Dereference iterator to return the user-defined value.
Definition: GraphIteratorMap.h:253
Sawyer::Container::GraphIteratorMap::ValueIterator
Bidirectional iterator over values.
Definition: GraphIteratorMap.h:239
Sawyer::Container::GraphIteratorMap::Value
V Value
Type of value associated with each key.
Definition: GraphIteratorMap.h:32
Sawyer::Container::GraphIteratorMap::keys
boost::iterator_range< ConstKeyIterator > keys() const
Iterators for container keys.
Definition: GraphIteratorMap.h:447
Sawyer::Container::GraphIteratorMap::ValueIterator::ValueIterator
ValueIterator(const ValueIterator &other)
Copy constructor.
Definition: GraphIteratorMap.h:245
Sawyer::Container::GraphIteratorMap::insert
void insert(const Key &item, const Value &value)
Insert the specified edge or vertex associated with a value.
Definition: GraphIteratorMap.h:342
Sawyer::Container::GraphIteratorMap::Node::value
Value & value()
Access the value of this node.
Definition: GraphIteratorMap.h:51
Sawyer::Container::GraphIteratorMap::ConstKeyIterator::ConstKeyIterator
ConstKeyIterator(const NodeIterator &other)
Copy constructor.
Definition: GraphIteratorMap.h:217
Sawyer::Container::GraphIteratorMap::ConstValueIterator::ConstValueIterator
ConstValueIterator(const ConstValueIterator &other)
Copy constructor.
Definition: GraphIteratorMap.h:272
Sawyer::Container::GraphIteratorMap::ConstNodeIterator
Bidirectional iterator over constant key/value nodes.
Definition: GraphIteratorMap.h:173
Sawyer::Container::GraphIteratorMap::NodeIterator
Bidirectional iterator over key/value nodes.
Definition: GraphIteratorMap.h:146
Sawyer::Container::GraphIteratorMap::NodeIterator::operator->
Node * operator->() const
Pointer to storage node.
Definition: GraphIteratorMap.h:160
Sawyer::Container::GraphIteratorMap::ConstValueIterator::operator->
const Value * operator->() const
Dereference iterator to return address of the user-defined data.
Definition: GraphIteratorMap.h:293
Sawyer::Container::GraphIteratorMap::ConstNodeIterator::ConstNodeIterator
ConstNodeIterator(const ConstNodeIterator &other)
Copy constructor.
Definition: GraphIteratorMap.h:179
Sawyer::Container::GraphIteratorMap::ConstKeyIterator::ConstKeyIterator
ConstKeyIterator(const ConstNodeIterator &other)
Copy constructor.
Definition: GraphIteratorMap.h:221
Sawyer::Container::GraphIteratorMap::NodeIterator::NodeIterator
NodeIterator(const NodeIterator &other)
Copy constructor.
Definition: GraphIteratorMap.h:152
Sawyer::Container::GraphIteratorMap::ConstValueIterator::operator*
const Value & operator*() const
Dereference iterator to return the value of the user-defined data.
Definition: GraphIteratorMap.h:288
Sawyer::Container::GraphIteratorMap::find
Sawyer::Optional< Value > find(const Key &item) const
Find the value associated with a particular key.
Definition: GraphIteratorMap.h:402
Sawyer::Container::GraphIteratorMap::Node::Node
Node(const Key &key, const Value &value)
Constructor.
Definition: GraphIteratorMap.h:40
Sawyer
Name space for the entire library.
Definition: Access.h:13
Sawyer::Container::GraphIteratorMap::ConstValueIterator::ConstValueIterator
ConstValueIterator(const ValueIterator &other)
Copy constructor.
Definition: GraphIteratorMap.h:276
Sawyer::Container::GraphIteratorMap::ConstNodeIterator::ConstNodeIterator
ConstNodeIterator(const NodeIterator &other)
Copy constructor.
Definition: GraphIteratorMap.h:183
Sawyer::Container::GraphIteratorMap::nodes
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Definition: GraphIteratorMap.h:428
Sawyer::Container::GraphIteratorMap::operator[]
Value operator[](const Key &item) const
Return the value associated with an existing key.
Definition: GraphIteratorMap.h:414
Sawyer::Container::GraphIteratorMap::Node::key
const Key & key() const
Access the key of this node.
Definition: GraphIteratorMap.h:46
Sawyer::Container::GraphIteratorMap::ConstNodeIterator::operator->
const Node * operator->() const
Returns a pointer to a storage node.
Definition: GraphIteratorMap.h:192
Sawyer::Container::GraphIteratorMap::keys
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition: GraphIteratorMap.h:443
Sawyer::Container::GraphIteratorMap::insertMaybeDefault
Value & insertMaybeDefault(const Key &item)
Insert a default value if its key doesn't already exist.
Definition: GraphIteratorMap.h:370
Sawyer::Container::GraphIteratorMap::GraphIteratorMap
GraphIteratorMap()
Default construct an empty map.
Definition: GraphIteratorMap.h:318
Sawyer::Container::GraphIteratorMap::ConstKeyIterator::operator*
const Key & operator*() const
Returns the key for the current iterator.
Definition: GraphIteratorMap.h:225
Sawyer::Container::GraphIteratorMap::exists
bool exists(const Key &item) const
Does the key exist in the map?
Definition: GraphIteratorMap.h:394
Sawyer::Container::GraphIteratorMap::ConstKeyIterator::ConstKeyIterator
ConstKeyIterator(const ConstKeyIterator &other)
Copy constructor.
Definition: GraphIteratorMap.h:213
Sawyer::Container::GraphIteratorMap::values
boost::iterator_range< ConstValueIterator > values() const
Iterators for container values.
Definition: GraphIteratorMap.h:463
Sawyer::Container::GraphIteratorMap::ConstValueIterator
Bidirectional iterator over values.
Definition: GraphIteratorMap.h:266
Sawyer::Container::GraphIteratorMap::ValueIterator::operator->
Value * operator->() const
Dereference iterator to return address of user-defined value.
Definition: GraphIteratorMap.h:258