ROSE 0.11.145.192
GraphIteratorSet.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_GraphIteratorSet_H
9#define Sawyer_GraphIteratorSet_H
10
11#include <Sawyer/Graph.h>
12
13namespace Sawyer {
14namespace Container {
15
26template<class T>
28public:
29 typedef T Value;
31private:
32 // These members are mutable so that we can delay the sorting until the last possible minute while still appearing to
33 // have a const-correct interface.
34 typedef std::vector<Value> StlVector;
35 mutable StlVector items_; // the pointers to graph edges or vertices stored in this container
36 mutable bool needsUpdate_; // true if the items_ are possibly not sorted
37
39 // Iterators
41public:
43 typedef typename StlVector::const_iterator ConstIterator;
44
46 // Constructors
48public:
51 : needsUpdate_(false) {}
52
54 // Iteration
56public:
60 boost::iterator_range<ConstIterator> values() const {
61 update();
62 return boost::iterator_range<ConstIterator>(items_.begin(), items_.end());
63 }
64
66 // Mutators
68public:
78 needsUpdate_ = true;
79 }
80
82 void insert(const Value &item) {
83 update();
84 insertUnique(item);
85 }
86
88 void insert(const GraphIteratorSet &other) {
89 update();
90 BOOST_FOREACH (const Value &item, other.values()) {
91 insert(item);
92 }
93 }
94
96 template<class SrcIterator>
97 void insert(const SrcIterator &begin, const SrcIterator &end) {
98 update();
99 for (SrcIterator i = begin; i != end; ++i)
100 insertUnique(*i);
101 }
102
104 void erase(const Value &item) const {
105 update();
106 typename std::vector<Value>::iterator lb = std::lower_bound(items_.begin(), items_.end(), item, sortById);
107 if (lb != items_.end() && (*lb)->id() == item->id())
108 items_.erase(lb);
109 }
110
113 update();
114 ASSERT_forbid(isEmpty());
115 Value retval = items_[0];
116 items_.erase(items_.begin());
117 return retval;
118 }
119
121 void clear() {
122 items_.clear();
123 needsUpdate_ = false;
124 }
125
127 // Queries
129public:
131 bool exists(const Value &item) const {
132 update();
133 typename std::vector<Value>::iterator lb = std::lower_bound(items_.begin(), items_.end(), item, sortById);
134 return lb != items_.end() && (*lb)->id() == item->id();
135 }
136
138 bool isEmpty() const {
139 return items_.empty();
140 }
141 bool empty() const { return isEmpty(); } // undocumented compatibility
142
144 size_t size() const {
145 return items_.size();
146 }
147
149 // Internal stuff
151private:
152 static bool sortById(const Value &a, const Value &b) {
153 return a->id() < b->id();
154 }
155
156 void update() const {
157 if (needsUpdate_) {
158 std::sort(items_.begin(), items_.end(), sortById);
159 needsUpdate_ = false;
160 } else {
161 check();
162 }
163 }
164
165 void check() const {
166 for (size_t i = 1; i < items_.size(); ++i)
167 ASSERT_require(sortById(items_[i-1], items_[i]));
168 }
169
170 void insertUnique(const Value &item) {
171 typename std::vector<Value>::iterator lb = std::lower_bound(items_.begin(), items_.end(), item, sortById);
172 if (lb == items_.end() || (*lb)->id() != item->id())
173 items_.insert(lb, item);
174 }
175};
176
177} // namespace
178} // namespace
179
180#endif
Set of graph edge or vertex pointers (iterators).
void insert(const SrcIterator &begin, const SrcIterator &end)
Insert multiple edges or vertices.
void insert(const Value &item)
Insert the specified edge or vertex if its ID doesn't exist in this set.
void clear()
Remove all edges or vertices from this set.
bool exists(const Value &item) const
Does the edge or vertex exist in this container?
Value popFront()
Removes and returns the least iterator.
bool isEmpty() const
True if container has no edges or vertices.
T Value
Type of values stored in this set.
GraphIteratorSet()
Default construct an empty set.
size_t size() const
Number of items stored in this set.
void insert(const GraphIteratorSet &other)
Insert multiple edges or vertices.
void erase(const Value &item) const
Remove the edge or vertex if it exists.
void updateIdNumbers()
Indicate that an update is necessary due to erasures.
boost::iterator_range< ConstIterator > values() const
Value iterator range.
StlVector::const_iterator ConstIterator
Iterates over values in this set.
Sawyer support library.