ROSE  0.9.9.109
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 #include <boost/foreach.hpp>
15 #include <boost/range/iterator_range.hpp>
16 #include <boost/serialization/serialization.hpp> // needed by <boost/serialization/set.hpp> in boost 1.58 - 1.60
17 #include <boost/serialization/access.hpp>
18 #include <boost/serialization/nvp.hpp>
19 #include <boost/serialization/set.hpp>
20 #include <vector>
21 
22 namespace Sawyer {
23 namespace Container {
24 
45 template<typename T, class C = std::less<T>, class A = std::allocator<T> >
46 class Set {
47  typedef std::set<T, C, A> InternalSet;
48  InternalSet set_;
49 public:
50  typedef T Value;
51  typedef C Comparator;
52  typedef A Allocator;
53  typedef typename InternalSet::const_iterator ConstIterator;
55  // Serialization
58 private:
59  friend class boost::serialization::access;
60 
61  template<class S>
62  void serialize(S &s, const unsigned /*version*/) {
63  s & BOOST_SERIALIZATION_NVP(set_);
64  }
65 
67  // Construction
69 public:
73  explicit Set(const Comparator &comparator = Comparator(), const Allocator &allocator = Allocator())
74  : set_(comparator, allocator) {}
75 
79  Set(const Value &value) /*implicit*/ {
80  set_.insert(value);
81  }
82 
93  template<class InputIterator>
94  Set(InputIterator begin, InputIterator end,
95  const Comparator &comparator = Comparator(), const Allocator &allocator = Allocator())
96  : set_(begin, end, comparator, allocator) {}
97 
98  template<class InputIterator>
99  explicit Set(const boost::iterator_range<InputIterator> &range,
100  const Comparator &/*comparator*/ = Comparator(), const Allocator &/*allocator*/ = Allocator())
101  : set_(range.begin(), range.end()) {}
105  Set(const Set &other)
106  : set_(other.set_) {}
107 
109  Set& operator=(const Set &other) {
110  set_ = other.set_;
111  return *this;
112  }
113 
115  // Iterators
117 public:
121  boost::iterator_range<ConstIterator> values() const {
122  return boost::iterator_range<ConstIterator>(set_.begin(), set_.end());
123  }
124 
126  // Predicates and queries
128 public:
132  bool isEmpty() const {
133  return set_.empty();
134  }
135 
139  bool exists(const Value &value) const {
140  return 1 == set_.count(value);
141  }
142 
146  bool existsAny(const Set &other) const {
147  BOOST_FOREACH (const Value &otherValue, other.values()) {
148  if (exists(otherValue))
149  return true;
150  }
151  return false;
152  }
153 
157  bool existsAll(const Set &other) const {
158  BOOST_FOREACH (const Value &otherValue, other.values()) {
159  if (!exists(otherValue))
160  return false;
161  }
162  return true;
163  }
164 
168  size_t size() const {
169  return set_.size();
170  }
171 
175  Value least() const {
176  ASSERT_forbid(isEmpty());
177  return *set_.begin();
178  }
179 
183  Value greatest() const {
184  ASSERT_forbid(isEmpty());
185  ConstIterator i = set_.end();
186  --i;
187  return *i;
188  }
189 
194  if (isEmpty())
195  return Interval<Value>();
196  return Interval<Value>::hull(least(), greatest());
197  }
198 
202  bool operator==(const Set &other) const {
203  return set_.size() == other.set_.size() && std::equal(set_.begin(), set_.end(), other.set_.begin());
204  }
205 
210  bool operator!=(const Set &other) const {
211  return (set_.size() != other.set_.size() ||
212  std::mismatch(set_.begin(), set_.end(), other.set_.begin()).first != set_.end());
213  }
214 
216  // Mutators
218 public:
222  bool insert(const Value &value) {
223  return set_.insert(value).second;
224  }
225 
230  bool insert(const Set &values) {
231  bool isInserted = false;
232  BOOST_FOREACH (const Value &value, values.values()) {
233  if (set_.insert(value).second)
234  isInserted = true;
235  }
236  return isInserted;
237  }
238 
242  bool erase(const Value &value) {
243  return 1 == set_.erase(value);
244  }
245 
250  bool erase(const Set &values) {
251  bool isErased = false;
252  BOOST_FOREACH (const Value &value, values.values()) {
253  if (1 == set_.erase(value))
254  isErased = true;
255  }
256  return isErased;
257  }
258 
262  void clear() {
263  set_.clear();
264  }
265 
269  Set& operator&=(const Set &other) {
270  std::vector<Value> toErase;
271  toErase.reserve(set_.size());
272  BOOST_FOREACH (const Value &value, set_) {
273  if (!other.exists(value))
274  toErase.push_back(value);
275  }
276  BOOST_FOREACH (const Value &value, toErase)
277  set_.erase(value);
278  return *this;
279  }
280 
284  Set& operator|=(const Set &other) {
285  BOOST_FOREACH (const Value &v, other.values())
286  set_.insert(v);
287  return *this;
288  }
289 
294  Set& operator-=(const Set &other) {
295  std::vector<Value> toErase;
296  toErase.reserve(set_.size());
297  BOOST_FOREACH (const Value &value, set_) {
298  if (other.exists(value))
299  toErase.push_back(value);
300  }
301  BOOST_FOREACH (const Value &value, toErase)
302  set_.erase(value);
303  return *this;
304  }
305 
306 
308  // Set-theoretic operations
310 public:
314  Set operator&(const Set &other) const {
315  Set retval = *this;
316  retval &= other;
317  return retval;
318  }
319 
323  Set operator|(const Set &other) const {
324  Set retval = *this;
325  retval |= other;
326  return retval;
327  }
328 
332  Set operator-(const Set &other) const {
333  Set retval = *this;
334  retval -= other;
335  return retval;
336  }
337 };
338 
339 } // namespace
340 } // namespace
341 
342 #endif
bool insert(const Set &values)
Insert multiple values.
Definition: Set.h:230
Set & operator-=(const Set &other)
Differences two sets.
Definition: Set.h:294
size_t size() const
Size of the set.
Definition: Set.h:168
Ordered set of values.
Definition: Set.h:46
bool existsAll(const Set &other) const
Whether all values exist.
Definition: Set.h:157
bool isEmpty() const
Whether the set is empty.
Definition: Set.h:132
void clear()
Erase all values.
Definition: Set.h:262
bool insert(const Value &value)
Insert a value.
Definition: Set.h:222
Set(const Comparator &comparator=Comparator(), const Allocator &allocator=Allocator())
Default constructor.
Definition: Set.h:73
bool exists(const Value &value) const
Whether a value exists.
Definition: Set.h:139
Set(const boost::iterator_range< InputIterator > &range, const Comparator &=Comparator(), const Allocator &=Allocator())
Iterative constructor.
Definition: Set.h:99
Set operator|(const Set &other) const
Compute the union of this set with another.
Definition: Set.h:323
Name space for the entire library.
Definition: Access.h:11
Value greatest() const
Largest member.
Definition: Set.h:183
bool erase(const Set &values)
Erase multiple values.
Definition: Set.h:250
C Comparator
How to compare values with each other.
Definition: Set.h:51
Set & operator&=(const Set &other)
Intersects this set with another.
Definition: Set.h:269
boost::iterator_range< ConstIterator > values() const
Value iterator range.
Definition: Set.h:121
Set operator&(const Set &other) const
Compute the intersection of this set with another.
Definition: Set.h:314
bool existsAny(const Set &other) const
Whether any value exists.
Definition: Set.h:146
bool operator!=(const Set &other) const
Whether two sets do not contain the same members.
Definition: Set.h:210
Interval< Value > hull() const
Range of members.
Definition: Set.h:193
InternalSet::const_iterator ConstIterator
Iterator for traversing values stored in the set.
Definition: Set.h:53
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
Definition: Interval.h:150
Set & operator=(const Set &other)
Assignment operator.
Definition: Set.h:109
Set & operator|=(const Set &other)
Unions this set with another.
Definition: Set.h:284
bool erase(const Value &value)
Erase a value.
Definition: Set.h:242
Set operator-(const Set &other) const
Compute the difference of this set with another.
Definition: Set.h:332
Set(InputIterator begin, InputIterator end, const Comparator &comparator=Comparator(), const Allocator &allocator=Allocator())
Iterative constructor.
Definition: Set.h:94
Value least() const
Smallest member.
Definition: Set.h:175
Range of values delimited by endpoints.
Definition: Interval.h:33
T Value
Type of values stored in this set.
Definition: Set.h:50
Set(const Set &other)
Copy constructor.
Definition: Set.h:105
Set(const Value &value)
Singleton constructor.
Definition: Set.h:79
A Allocator
How to allocate storge for new values.
Definition: Set.h:52
bool operator==(const Set &other) const
Whether two sets contain the same members.
Definition: Set.h:202