ROSE  0.11.145.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 
224  explicit operator bool() const {
225  return !isEmpty();
226  }
227 
231  bool operator!() const {
232  return isEmpty();
233  }
234 
236  // Mutators
238 public:
242  bool insert(const Value &value) {
243  return set_.insert(value).second;
244  }
245 
250  bool insert(const Set &values) {
251  bool isInserted = false;
252  BOOST_FOREACH (const Value &value, values.values()) {
253  if (set_.insert(value).second)
254  isInserted = true;
255  }
256  return isInserted;
257  }
258 
262  bool erase(const Value &value) {
263  return 1 == set_.erase(value);
264  }
265 
270  bool erase(const Set &values) {
271  bool isErased = false;
272  BOOST_FOREACH (const Value &value, values.values()) {
273  if (1 == set_.erase(value))
274  isErased = true;
275  }
276  return isErased;
277  }
278 
282  void clear() {
283  set_.clear();
284  }
285 
289  Set& operator&=(const Set &other) {
290  std::vector<Value> toErase;
291  toErase.reserve(set_.size());
292  BOOST_FOREACH (const Value &value, set_) {
293  if (!other.exists(value))
294  toErase.push_back(value);
295  }
296  BOOST_FOREACH (const Value &value, toErase)
297  set_.erase(value);
298  return *this;
299  }
300 
304  Set& operator|=(const Set &other) {
305  BOOST_FOREACH (const Value &v, other.values())
306  set_.insert(v);
307  return *this;
308  }
309 
314  Set& operator-=(const Set &other) {
315  std::vector<Value> toErase;
316  toErase.reserve(set_.size());
317  BOOST_FOREACH (const Value &value, set_) {
318  if (other.exists(value))
319  toErase.push_back(value);
320  }
321  BOOST_FOREACH (const Value &value, toErase)
322  set_.erase(value);
323  return *this;
324  }
325 
326 
328  // Set-theoretic operations
330 public:
334  Set operator&(const Set &other) const {
335  Set retval = *this;
336  retval &= other;
337  return retval;
338  }
339 
343  Set operator|(const Set &other) const {
344  Set retval = *this;
345  retval |= other;
346  return retval;
347  }
348 
352  Set operator-(const Set &other) const {
353  Set retval = *this;
354  retval -= other;
355  return retval;
356  }
357 };
358 
359 } // namespace
360 } // namespace
361 
362 #endif
bool insert(const Set &values)
Insert multiple values.
Definition: Set.h:250
Set & operator-=(const Set &other)
Differences two sets.
Definition: Set.h:314
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:282
bool insert(const Value &value)
Insert a value.
Definition: Set.h:242
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:343
Name space for the entire library.
Definition: FeasiblePath.h:767
Value greatest() const
Largest member.
Definition: Set.h:189
bool erase(const Set &values)
Erase multiple values.
Definition: Set.h:270
bool operator!() const
Whether the set is empty.
Definition: Set.h:231
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:289
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:334
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:304
bool erase(const Value &value)
Erase a value.
Definition: Set.h:262
Set operator-(const Set &other) const
Compute the difference of this set with another.
Definition: Set.h:352
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