ROSE  0.11.50.0
Set.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_Container_Set_H
9 #define Sawyer_Container_Set_H
10 
11 #include <Sawyer/Interval.h>
12 #include <Sawyer/Sawyer.h>
13 
14 // Work around a bug in boost::serialization for 1.74.0
15 #include <boost/version.hpp>
16 #if BOOST_VERSION == 107400
17  #include <boost/serialization/library_version_type.hpp>
18 #endif
19 
20 #include <boost/foreach.hpp>
21 #include <boost/range/iterator_range.hpp>
22 #include <boost/serialization/serialization.hpp> // needed by <boost/serialization/set.hpp> in boost 1.58 - 1.60
23 #include <boost/serialization/access.hpp>
24 #include <boost/serialization/nvp.hpp>
25 #include <boost/serialization/set.hpp>
26 #include <vector>
27 
28 namespace Sawyer {
29 namespace Container {
30 
51 template<typename T, class C = std::less<T>, class A = std::allocator<T> >
52 class Set {
53  typedef std::set<T, C, A> InternalSet;
54  InternalSet set_;
55 public:
56  typedef T Value;
57  typedef C Comparator;
58  typedef A Allocator;
59  typedef typename InternalSet::const_iterator ConstIterator;
61  // Serialization
64 private:
65  friend class boost::serialization::access;
66 
67  template<class S>
68  void serialize(S &s, const unsigned /*version*/) {
69  s & BOOST_SERIALIZATION_NVP(set_);
70  }
71 
73  // Construction
75 public:
79  explicit Set(const Comparator &comparator = Comparator(), const Allocator &allocator = Allocator())
80  : set_(comparator, allocator) {}
81 
85  Set(const Value &value) /*implicit*/ {
86  set_.insert(value);
87  }
88 
99  template<class InputIterator>
100  Set(InputIterator begin, InputIterator end,
101  const Comparator &comparator = Comparator(), const Allocator &allocator = Allocator())
102  : set_(begin, end, comparator, allocator) {}
103 
104  template<class InputIterator>
105  explicit Set(const boost::iterator_range<InputIterator> &range,
106  const Comparator &/*comparator*/ = Comparator(), const Allocator &/*allocator*/ = Allocator())
107  : set_(range.begin(), range.end()) {}
111  Set(const Set &other)
112  : set_(other.set_) {}
113 
115  Set& operator=(const Set &other) {
116  set_ = other.set_;
117  return *this;
118  }
119 
121  // Iterators
123 public:
127  boost::iterator_range<ConstIterator> values() const {
128  return boost::iterator_range<ConstIterator>(set_.begin(), set_.end());
129  }
130 
132  // Predicates and queries
134 public:
138  bool isEmpty() const {
139  return set_.empty();
140  }
141 
145  bool exists(const Value &value) const {
146  return 1 == set_.count(value);
147  }
148 
152  bool existsAny(const Set &other) const {
153  BOOST_FOREACH (const Value &otherValue, other.values()) {
154  if (exists(otherValue))
155  return true;
156  }
157  return false;
158  }
159 
163  bool existsAll(const Set &other) const {
164  BOOST_FOREACH (const Value &otherValue, other.values()) {
165  if (!exists(otherValue))
166  return false;
167  }
168  return true;
169  }
170 
174  size_t size() const {
175  return set_.size();
176  }
177 
181  Value least() const {
182  ASSERT_forbid(isEmpty());
183  return *set_.begin();
184  }
185 
189  Value greatest() const {
190  ASSERT_forbid(isEmpty());
191  ConstIterator i = set_.end();
192  --i;
193  return *i;
194  }
195 
200  if (isEmpty())
201  return Interval<Value>();
202  return Interval<Value>::hull(least(), greatest());
203  }
204 
208  bool operator==(const Set &other) const {
209  return set_.size() == other.set_.size() && std::equal(set_.begin(), set_.end(), other.set_.begin());
210  }
211 
216  bool operator!=(const Set &other) const {
217  return (set_.size() != other.set_.size() ||
218  std::mismatch(set_.begin(), set_.end(), other.set_.begin()).first != set_.end());
219  }
220 
222  // Mutators
224 public:
228  bool insert(const Value &value) {
229  return set_.insert(value).second;
230  }
231 
236  bool insert(const Set &values) {
237  bool isInserted = false;
238  BOOST_FOREACH (const Value &value, values.values()) {
239  if (set_.insert(value).second)
240  isInserted = true;
241  }
242  return isInserted;
243  }
244 
248  bool erase(const Value &value) {
249  return 1 == set_.erase(value);
250  }
251 
256  bool erase(const Set &values) {
257  bool isErased = false;
258  BOOST_FOREACH (const Value &value, values.values()) {
259  if (1 == set_.erase(value))
260  isErased = true;
261  }
262  return isErased;
263  }
264 
268  void clear() {
269  set_.clear();
270  }
271 
275  Set& operator&=(const Set &other) {
276  std::vector<Value> toErase;
277  toErase.reserve(set_.size());
278  BOOST_FOREACH (const Value &value, set_) {
279  if (!other.exists(value))
280  toErase.push_back(value);
281  }
282  BOOST_FOREACH (const Value &value, toErase)
283  set_.erase(value);
284  return *this;
285  }
286 
290  Set& operator|=(const Set &other) {
291  BOOST_FOREACH (const Value &v, other.values())
292  set_.insert(v);
293  return *this;
294  }
295 
300  Set& operator-=(const Set &other) {
301  std::vector<Value> toErase;
302  toErase.reserve(set_.size());
303  BOOST_FOREACH (const Value &value, set_) {
304  if (other.exists(value))
305  toErase.push_back(value);
306  }
307  BOOST_FOREACH (const Value &value, toErase)
308  set_.erase(value);
309  return *this;
310  }
311 
312 
314  // Set-theoretic operations
316 public:
320  Set operator&(const Set &other) const {
321  Set retval = *this;
322  retval &= other;
323  return retval;
324  }
325 
329  Set operator|(const Set &other) const {
330  Set retval = *this;
331  retval |= other;
332  return retval;
333  }
334 
338  Set operator-(const Set &other) const {
339  Set retval = *this;
340  retval -= other;
341  return retval;
342  }
343 };
344 
345 } // namespace
346 } // namespace
347 
348 #endif
bool insert(const Set &values)
Insert multiple values.
Definition: Set.h:236
Set & operator-=(const Set &other)
Differences two sets.
Definition: Set.h:300
size_t size() const
Size of the set.
Definition: Set.h:174
Ordered set of values.
Definition: Set.h:52
bool existsAll(const Set &other) const
Whether all values exist.
Definition: Set.h:163
bool isEmpty() const
Whether the set is empty.
Definition: Set.h:138
void clear()
Erase all values.
Definition: Set.h:268
bool insert(const Value &value)
Insert a value.
Definition: Set.h:228
Set(const Comparator &comparator=Comparator(), const Allocator &allocator=Allocator())
Default constructor.
Definition: Set.h:79
bool exists(const Value &value) const
Whether a value exists.
Definition: Set.h:145
Set(const boost::iterator_range< InputIterator > &range, const Comparator &=Comparator(), const Allocator &=Allocator())
Iterative constructor.
Definition: Set.h:105
Set operator|(const Set &other) const
Compute the union of this set with another.
Definition: Set.h:329
Name space for the entire library.
Definition: FeasiblePath.h:787
Value greatest() const
Largest member.
Definition: Set.h:189
bool erase(const Set &values)
Erase multiple values.
Definition: Set.h:256
C Comparator
How to compare values with each other.
Definition: Set.h:57
Set & operator&=(const Set &other)
Intersects this set with another.
Definition: Set.h:275
boost::iterator_range< ConstIterator > values() const
Value iterator range.
Definition: Set.h:127
Set operator&(const Set &other) const
Compute the intersection of this set with another.
Definition: Set.h:320
bool existsAny(const Set &other) const
Whether any value exists.
Definition: Set.h:152
bool operator!=(const Set &other) const
Whether two sets do not contain the same members.
Definition: Set.h:216
Interval< Value > hull() const
Range of members.
Definition: Set.h:199
InternalSet::const_iterator ConstIterator
Iterator for traversing values stored in the set.
Definition: Set.h:59
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
Definition: Interval.h:151
Set & operator=(const Set &other)
Assignment operator.
Definition: Set.h:115
Set & operator|=(const Set &other)
Unions this set with another.
Definition: Set.h:290
bool erase(const Value &value)
Erase a value.
Definition: Set.h:248
Set operator-(const Set &other) const
Compute the difference of this set with another.
Definition: Set.h:338
Set(InputIterator begin, InputIterator end, const Comparator &comparator=Comparator(), const Allocator &allocator=Allocator())
Iterative constructor.
Definition: Set.h:100
Value least() const
Smallest member.
Definition: Set.h:181
Range of values delimited by endpoints.
Definition: Interval.h:33
T Value
Type of values stored in this set.
Definition: Set.h:56
Set(const Set &other)
Copy constructor.
Definition: Set.h:111
Set(const Value &value)
Singleton constructor.
Definition: Set.h:85
A Allocator
How to allocate storge for new values.
Definition: Set.h:58
bool operator==(const Set &other) const
Whether two sets contain the same members.
Definition: Set.h:208