ROSE  0.11.2.0
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: public std::iterator<std::bidirectional_iterator_tag, Value> {
69  protected:
70  BaseIterator base_;
71  BidirectionalIterator() {}
72  BidirectionalIterator(const BaseIterator &base): base_(base) {}
73  public:
75  Derived& operator=(const Derived &other) {
76  base_ = other.base_;
77  return *derived();
78  }
79 
81  Derived& operator++() {
82  ++base_;
83  return *derived();
84  }
85 
87  Derived operator++(int) {
88  Derived old = *derived();
89  ++*this;
90  return old;
91  }
92 
94  Derived& operator--() {
95  --base_;
96  return *derived();
97  }
98 
100  Derived operator--(int) {
101  Derived old = *derived();
102  ++*this;
103  return old;
104  }
105 
110  template<class OtherIter>
111  bool operator==(const OtherIter &other) const {
112  return base_ == other.base();
113  }
114 
116  template<class OtherIter>
117  bool operator!=(const OtherIter &other) const {
118  return base_ != other.base();
119  }
120 
121  const BaseIterator& base() const {
122  return base_;
123  }
124  protected:
125  Derived* derived() {
126  return static_cast<Derived*>(this);
127  }
128  const Derived* derived() const {
129  return static_cast<const Derived*>(this);
130  }
131  };
132 
133 public:
138  class NodeIterator: public BidirectionalIterator<NodeIterator, Node, typename StlVector::iterator> {
139  typedef BidirectionalIterator<NodeIterator, Node, typename StlVector::iterator> Super;
140  public:
141  NodeIterator() {}
142 
144  NodeIterator(const NodeIterator &other): Super(other) {} // implicit
145 
147  Node& operator*() const {
148  return *this->base();
149  }
150 
152  Node* operator->() const {
153  return &*this->base();
154  }
155  private:
156  friend class GraphIteratorMap;
157  NodeIterator(const typename StlVector::iterator &base)
158  : Super(base) {}
159  };
160 
165  class ConstNodeIterator: public BidirectionalIterator<ConstNodeIterator, const Node, typename StlVector::const_iterator> {
166  typedef BidirectionalIterator<ConstNodeIterator, const Node, typename StlVector::const_iterator> Super;
167  public:
168  ConstNodeIterator() {}
169 
171  ConstNodeIterator(const ConstNodeIterator &other) // implicit
172  : Super(other) {}
173 
175  ConstNodeIterator(const NodeIterator &other) // implicit
176  : Super(typename StlVector::const_iterator(other.base())) {}
177 
179  const Node& operator*() const {
180  return *this->base();
181  }
182 
184  const Node* operator->() const {
185  return &*this->base();
186  }
187  private:
188  friend class GraphIteratorMap;
189  ConstNodeIterator(const typename StlVector::const_iterator &base)
190  : Super(base) {}
191  ConstNodeIterator(const typename StlVector::iterator &base)
192  : Super(typename StlVector::const_iterator(base)) {}
193  };
194 
199  class ConstKeyIterator: public BidirectionalIterator<ConstKeyIterator, const Key, typename StlVector::const_iterator> {
200  typedef BidirectionalIterator<ConstKeyIterator, const Key, typename StlVector::const_iterator> Super;
201  public:
202  ConstKeyIterator() {}
203 
205  ConstKeyIterator(const ConstKeyIterator &other) // implicit
206  : Super(other) {}
207 
209  ConstKeyIterator(const NodeIterator &other) // implicit
210  : Super(typename StlVector::const_iterator(other.base())) {}
211 
213  ConstKeyIterator(const ConstNodeIterator &other) // implicit
214  : Super(other.base()) {}
215 
217  const Key& operator*() const {
218  return this->base()->key();
219  }
220 
222  const Key* operator->() const {
223  return &this->base()->key();
224  }
225  };
226 
231  class ValueIterator: public BidirectionalIterator<ValueIterator, Value, typename StlVector::iterator> {
232  typedef BidirectionalIterator<ValueIterator, Value, typename StlVector::iterator> Super;
233  public:
234  ValueIterator() {}
235 
238  : Super(other) {}
239 
241  ValueIterator(const NodeIterator &other) // implicit
242  : Super(other.base()) {}
243 
245  Value& operator*() const {
246  return this->base()->value();
247  }
248 
250  Value* operator->() const {
251  return &this->base()->value();
252  }
253  };
254 
258  class ConstValueIterator: public BidirectionalIterator<ConstValueIterator, const Value, typename StlVector::const_iterator> {
259  typedef BidirectionalIterator<ConstValueIterator, const Value, typename StlVector::const_iterator> Super;
260  public:
261  ConstValueIterator() {}
262 
265  : Super(other) {}
266 
268  ConstValueIterator(const ValueIterator &other) // implicit
269  : Super(typename StlVector::const_iterator(other.base())) {}
270 
272  ConstValueIterator(const ConstNodeIterator &other) // implicit
273  : Super(other.base()) {}
274 
276  ConstValueIterator(const NodeIterator &other) // implicit
277  : Super(typename StlVector::const_iterator(other.base())) {}
278 
280  const Value& operator*() const {
281  return this->base()->value();
282  }
283 
285  const Value* operator->() const {
286  return &this->base()->value();
287  }
288  };
289 
290 public:
291  // Standard types needed by C++ containers with random access iterators for the C++-style iterating functions like begin()
292  // and end().
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;
304 
306  // Constructors
308 public:
311  : needsUpdate_(false) {}
312 
314  // Mutators
316 public:
326  needsUpdate_ = true;
327  }
328 
334  void insert(const Key &item, const Value &value) {
335  update();
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);
340  } else {
341  lb->value() = value;
342  }
343  }
344 
349  Value& insertMaybe(const Key &item, const Value &value) {
350  update();
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);
355  return lb->value();
356  }
357 
362  Value& insertMaybeDefault(const Key &item) {
363  return insertMaybe(item, Value());
364  }
365 
367  void erase(const Key &item) {
368  update();
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())
372  items_.erase(lb);
373  }
374 
376  void clear() {
377  items_.clear();
378  needsUpdate_ = false;
379  }
380 
382  // Queries
384 public:
386  bool exists(const Key &item) const {
387  update();
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();
391  }
392 
394  Sawyer::Optional<Value> find(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  if (lb != items_.end() && lb->key()->id() == item->id()) {
399  return lb->value();
400  } else {
401  return Sawyer::Nothing();
402  }
403  }
404 
406  Value operator[](const Key &item) const {
407  update();
408  return *find(item);
409  }
410 
412  // Iteration
414 
420  boost::iterator_range<NodeIterator> nodes() {
421  update();
422  return boost::iterator_range<NodeIterator>(NodeIterator(items_.begin()), NodeIterator(items_.end()));
423  }
424  boost::iterator_range<ConstNodeIterator> nodes() const {
425  update();
426  return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(items_.begin()), ConstNodeIterator(items_.end()));
427  }
435  boost::iterator_range<ConstKeyIterator> keys() {
436  update();
437  return boost::iterator_range<ConstKeyIterator>(NodeIterator(items_.begin()), NodeIterator(items_.end()));
438  }
439  boost::iterator_range<ConstKeyIterator> keys() const {
440  update();
441  return boost::iterator_range<ConstKeyIterator>(ConstNodeIterator(items_.begin()), ConstNodeIterator(items_.end()));
442  }
451  boost::iterator_range<ValueIterator> values() {
452  update();
453  return boost::iterator_range<ValueIterator>(NodeIterator(items_.begin()), NodeIterator(items_.end()));
454  }
455  boost::iterator_range<ConstValueIterator> values() const {
456  update();
457  return boost::iterator_range<ConstValueIterator>(ConstNodeIterator(items_.begin()), ConstNodeIterator(items_.end()));
458  }
461  // Undocumented C++-style iterators iterator over the key+value nodes.
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()); }
466 
468  // Internal functions
470 private:
471  static bool sortById(const Node &a, const Node &b) {
472  return a.key()->id() < b.key()->id();
473  }
474 
475  void update() const {
476  if (needsUpdate_) {
477  std::sort(items_.begin(), items_.end(), sortById);
478  needsUpdate_ = false;
479  } else {
480  check();
481  }
482  }
483 
484  void check() const {
485  for (size_t i = 1; i < items_.size(); ++i)
486  ASSERT_require(sortById(items_[i-1], items_[i]));
487  }
488 };
489 
490 } // namespace
491 } // namespace
492 
493 #endif
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.
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.
Represents no value.
Definition: Optional.h:32
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.