ROSE  0.11.96.11
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://github.com/matzke1/sawyer.
4 
5 
6 
7 
8 #ifndef Sawyer_GraphIteratorSet_H
9 #define Sawyer_GraphIteratorSet_H
10 
11 #include <Sawyer/Graph.h>
12 
13 namespace Sawyer {
14 namespace Container {
15 
26 template<class T>
28 public:
29  typedef T Value;
31 private:
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
41 public:
43  typedef typename StlVector::const_iterator ConstIterator;
44 
46  // Constructors
48 public:
51  : needsUpdate_(false) {}
52 
54  // Iteration
56 public:
60  boost::iterator_range<ConstIterator> values() const {
61  update();
62  return boost::iterator_range<ConstIterator>(items_.begin(), items_.end());
63  }
64 
66  // Mutators
68 public:
77  void updateIdNumbers() {
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
129 public:
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
151 private:
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
Sawyer::Container::GraphIteratorSet::clear
void clear()
Remove all edges or vertices from this set.
Definition: GraphIteratorSet.h:121
Sawyer::Container::GraphIteratorSet::updateIdNumbers
void updateIdNumbers()
Indicate that an update is necessary due to erasures.
Definition: GraphIteratorSet.h:77
Sawyer::Container::GraphIteratorSet::insert
void insert(const Value &item)
Insert the specified edge or vertex if its ID doesn't exist in this set.
Definition: GraphIteratorSet.h:82
Sawyer::Container::GraphIteratorSet::size
size_t size() const
Number of items stored in this set.
Definition: GraphIteratorSet.h:144
Sawyer::Container::GraphIteratorSet::ConstIterator
StlVector::const_iterator ConstIterator
Iterates over values in this set.
Definition: GraphIteratorSet.h:43
Sawyer::Container::GraphIteratorSet::values
boost::iterator_range< ConstIterator > values() const
Value iterator range.
Definition: GraphIteratorSet.h:60
Sawyer::Container::GraphIteratorSet::Value
T Value
Type of values stored in this set.
Definition: GraphIteratorSet.h:29
Sawyer::Container::GraphIteratorSet::GraphIteratorSet
GraphIteratorSet()
Default construct an empty set.
Definition: GraphIteratorSet.h:50
Sawyer::Container::GraphIteratorSet::erase
void erase(const Value &item) const
Remove the edge or vertex if it exists.
Definition: GraphIteratorSet.h:104
Sawyer::Container::GraphIteratorSet::isEmpty
bool isEmpty() const
True if container has no edges or vertices.
Definition: GraphIteratorSet.h:138
Sawyer::Container::GraphIteratorSet::exists
bool exists(const Value &item) const
Does the edge or vertex exist in this container?
Definition: GraphIteratorSet.h:131
Sawyer::Container::GraphIteratorSet::insert
void insert(const GraphIteratorSet &other)
Insert multiple edges or vertices.
Definition: GraphIteratorSet.h:88
Sawyer
Name space for the entire library.
Definition: Access.h:13
Sawyer::Container::GraphIteratorSet
Set of graph edge or vertex pointers (iterators).
Definition: GraphIteratorSet.h:27
Sawyer::Container::GraphIteratorSet::insert
void insert(const SrcIterator &begin, const SrcIterator &end)
Insert multiple edges or vertices.
Definition: GraphIteratorSet.h:97
Sawyer::Container::GraphIteratorSet::popFront
Value popFront()
Removes and returns the least iterator.
Definition: GraphIteratorSet.h:112