ROSE  0.11.145.0
DenseIntegerSet.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 // Set optimized to store densely-packed integers
9 #ifndef Sawyer_DenseIntegerSet_H
10 #define Sawyer_DenseIntegerSet_H
11
12 #include <Sawyer/Sawyer.h>
13 #include <Sawyer/Exception.h>
14 #include <Sawyer/Interval.h>
15 #include <boost/foreach.hpp>
16 #include <boost/lexical_cast.hpp>
17 #include <boost/range/iterator_range.hpp>
18 #include <string>
19 #include <vector>
20
21 namespace Sawyer {
22 namespace Container {
23
38 template<typename T>
40 public:
41  // Needed by iterators
42  struct Member {
43  Member *next, *prev; // circular list inc. head_; nulls imply member is not present in set
44  Member(): next(NULL), prev(NULL) {}
45  Member(Member *next, Member *prev): next(next), prev(prev) {}
46  };
47
48 private:
49  Interval<T> domain_; // domain of values that can be members of this set
50  std::vector<Member> members_; // members forming a doubly-linked circular list inc. head_
52  size_t nMembers_; // number of members contained in the set
53
54 public:
55  typedef T Value;
57  // Construction
60 public:
67
77  size_t n = (size_t)domain.greatest() - (size_t)domain.least() + 1;
78  ASSERT_require(n != 0 || !domain.isEmpty());
79  members_.resize(n);
80  }
81
82  DenseIntegerSet(Value least, Value greatest)
84  size_t n = (size_t)greatest - (size_t)least + 1;
85  ASSERT_require(n != 0 || !domain_.isEmpty());
86  members_.resize(n);
87  }
88
89  explicit DenseIntegerSet(Value n)
91  if (0 == n)
92  domain_ = Interval<Value>();
93  }
99  size_t n = (size_t)domain_.greatest() - (size_t)domain_.least() + 1;
100  ASSERT_require(n != 0 || !domain_.isEmpty());
101  members_.resize(n);
102  BOOST_FOREACH (Value v, other.values())
103  insert(v);
104  }
105
111  DenseIntegerSet tmp(domain());
112  BOOST_FOREACH (Value v, other.values())
113  tmp.insert(v);
114  std::swap(domain_, tmp.domain_);
115  std::swap(members_, tmp.members_);
116  std::swap(nMembers_, tmp.nMembers_);
117
118  // heads require some fixups because the prev/next pointers of the list and the heads point to the address of the head
119  // in their original object, not the new object.
123  } else {
126  }
127
128  // Fix up tmp's list too for completeness, although the only thing we do is delete it.
131  } else {
134  }
135
136  return *this;
137  }
138
140  // Iterators
142 public:
157  public:
158  // Five standard iterator types
159  using iterator_category = std::output_iterator_tag;
160  using value_type = const Value;
161  using difference_type = std::ptrdiff_t;
162  using pointer = const Value*;
163  using reference = const Value&;
164
165  private:
166  friend class DenseIntegerSet;
167  const DenseIntegerSet *set_;
168  const Member *member_;
169  mutable Value value_; // so we can return a const ref
170
171  private:
172  ConstIterator(const DenseIntegerSet *s, const Member *m)
173  : set_(s), member_(m) {}
174
175  public:
180  bool operator==(const ConstIterator &other) const {
181  return set_ == other.set_ && member_ == other.member_;
182  }
183
187  bool operator!=(const ConstIterator &other) const {
188  return set_ != other.set_ || member_ != other.member_;
189  }
190
201  bool operator<(const ConstIterator &other) const {
202  if (set_ != other.set_)
203  return set_ < other.set_;
204  return member_ < other.member_;
205  }
206
214  member_ = member_->next;
215  return *this;
216  }
218  ConstIterator retval = *this;
219  ++*this;
220  return retval;
221  }
231  member_ = member_->prev;
232  return *this;
233  }
234
236  ConstIterator retval = *this;
237  --*this;
238  return retval;
239  }
246  const Value& operator*() const {
247  value_ = set_->deref(*this);
248  return value_;
249  }
250  };
251
255  boost::iterator_range<ConstIterator> values() const {
257  }
258
260  // Predicates and queries
262 public:
266  bool isEmpty() const {
268  }
269
273  size_t size() const {
274  return nMembers_;
275  }
276
281  return domain_;
282  }
283
288  bool isStorable(Value v) const {
289  return domain().contains(v);
290  }
291
296  bool exists(const Value &value) const {
297  if (isEmpty() || !isStorable(value))
298  return false;
299  const Member &m = members_[value - domain_.least()];
300  return head_.next == &m || m.prev != NULL;
301  }
302
307  template<class SawyerContainer>
308  bool existsAny(const SawyerContainer &other) const {
309  BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values()) {
310  if (exists(otherValue))
311  return true;
312  }
313  return false;
314  }
315
320  template<class SawyerContainer>
321  bool existsAll(const SawyerContainer &other) const {
322  BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values()) {
323  if (!exists(otherValue))
324  return false;
325  }
326  return true;
327  }
328
332  template<class SawyerContainer>
333  bool operator==(const SawyerContainer &other) const {
334  return size() == other.size() && existsAll(other);
335  }
336
340  template<class SawyerContainer>
341  bool operator!=(const SawyerContainer &other) const {
342  return size() != other.size() || !existsAll(other);
343  }
344
346  // Modifiers
348 public:
352  void clear() {
353  Member *next = NULL;
354  for (Member *m = head_.next; m != &head_; m = next) {
355  next = m->next;
356  m->prev = m->next = NULL;
357  }
359  nMembers_ = 0;
360  }
361
366  bool insert(Value value) {
367  if (!isStorable(value)) {
368  std::string mesg;
369  if (domain_.isEmpty()) {
370  mesg = "cannot insert a value into a destination set with an empty domain";
371  } else {
372  mesg = "cannot insert " + boost::lexical_cast<std::string>(value) + " into a destination set whose domain is [" +
373  boost::lexical_cast<std::string>(domain_.least()) + ", " +
374  boost::lexical_cast<std::string>(domain_.greatest()) + "]";
375  }
376  throw Exception::DomainError(mesg);
377  }
378  Member &m = members_[value - domain_.least()];
379  if (m.next)
380  return false; // already a member
385  ++nMembers_;
386  return true;
387  }
388
392  void insertAll() {
393  if (!members_.empty()) {
394  for (size_t i=0; i<members_.size(); ++i) {
395  if (0 == i) {
398  } else {
399  members_[i].prev = &members_[i-1];
400  }
401  if (i+1 < members_.size()) {
402  members_[i].next = &members_[i+1];
403  } else {
406  }
407  }
408  nMembers_ = members_.size();
409  }
410  }
411
417  template<class SawyerContainer>
418  void insertMany(const SawyerContainer &other) {
419  BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values())
420  insert(otherValue);
421  }
422
423  template<class SawyerContainer>
424  DenseIntegerSet& operator|=(const SawyerContainer &other) {
425  insertMany(other);
426  return *this;
427  }
439  bool erase(Value value) {
440  if (!exists(value))
441  return false;
442  Member &m = members_[value - domain_.least()];
443  m.prev->next = m.next;
444  m.next->prev = m.prev;
445  m.next = m.prev = NULL;
446  ASSERT_require(nMembers_ > 0);
447  --nMembers_;
448  return true;
449  }
450
451  ConstIterator erase(const ConstIterator &iter) {
452  ASSERT_require2(iter.set_ != this, "iterator does not belong to this set");
453  ASSERT_require2(iter.member_ != &head_, "cannot erase the end iterator");
454  ASSERT_require2(iter.member_->next != NULL, "iterator no longer points to a member of this set");
455  ConstIterator retval = iter;
456  ++retval;
457  Member &m = iter->member_;
458  m.prev->next = m.next;
459  m.next->prev = m.prev;
460  m.next = m.prev = NULL;
461  ASSERT_require(nMembers_ > 0);
462  --nMembers_;
463  return retval;
464  }
472  template<class SawyerContainer>
473  void eraseMany(const SawyerContainer &other) {
474  BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values())
475  erase(otherValue);
476  }
477
478  template<class SawyerContainer>
479  DenseIntegerSet& operator-=(const SawyerContainer &other) {
480  eraseMany(other);
481  return *this;
482  }
490  template<class SawyerContainer>
491  void intersect(const SawyerContainer &other) {
492  DenseIntegerSet tmp(*this);
493  clear();
494  BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values()) {
495  if (tmp.exists(otherValue))
496  insert(otherValue);
497  }
498  }
499
500  template<class SawyerContainer>
501  DenseIntegerSet& operator&=(const SawyerContainer &other) {
502  intersect(other);
503  return *this;
504  }
507  // Set-theoretic operations
510 public:
514  template<class SawyerContainer>
515  DenseIntegerSet operator&(const SawyerContainer &other) const {
516  DenseIntegerSet retval = *this;
517  retval &= other;
518  return retval;
519  }
520
524  template<class SawyerContainer>
525  DenseIntegerSet operator|(const SawyerContainer &other) const {
526  DenseIntegerSet retval = *this;
527  retval |= other;
528  return retval;
529  }
530
534  template<class SawyerContainer>
535  DenseIntegerSet operator-(const SawyerContainer &other) const {
536  DenseIntegerSet retval = *this;
537  retval -= other;
538  return retval;
539  }
540
542  // Internal stuff
544 public:
545  // Dereference an iterator to get a value.
546  Value deref(const ConstIterator &iter) const {
547  const Member *m = iter.member_;
548  ASSERT_require2(m != &head_, "dereferencing an end iterator");
549  ASSERT_require2(m->next != NULL, "dereferencing erased member");
550  return domain_.least() + (m - &members_[0]);
551  }
552 };
553
554 } // namespace
555 } // namespace
556
557 #endif
bool operator==(const ConstIterator &other) const
Iterators are comparable for equality.
void clear()
Remove all members from this set.
bool operator!=(const SawyerContainer &other) const
Whether two sets do not contain the same members.
T Value
Type of values stored in this container.
bool isEmpty() const
True if interval is empty.
Definition: Interval.h:219
Interval< Value > domain() const
Domain of storable values.
bool isStorable(Value v) const
Determines if a value is storable.
void eraseMany(const SawyerContainer &other)
Erase many values.
ConstIterator erase(const ConstIterator &iter)
Erase a value.
size_t size() const
Number of members present.
bool isEmpty() const
Whether the set is empty.
boost::iterator_range< ConstIterator > values() const
Iterator range for set members.
bool exists(const Value &value) const
Determines whether a value is stored.
DenseIntegerSet operator|(const SawyerContainer &other) const
Compute the union of this set with another.
DenseIntegerSet & operator-=(const SawyerContainer &other)
Erase many values.
Name space for the entire library.
Definition: FeasiblePath.h:767
T & deref(T *ptr, const char *file=0, size_t ln=0)
dereferences an object (= checked dereference in debug mode)
Definition: sageGeneric.h:98
DenseIntegerSet(Value n)
Construct an empty set that can hold values from the specified domain.
T least() const
Returns lower limit.
Definition: Interval.h:207
bool insert(Value value)
Insert a value.
const Value & operator*() const
Dereference.
DenseIntegerSet & operator=(const DenseIntegerSet &other)
Assignment operator.
bool existsAny(const SawyerContainer &other) const
Whether any value exists.
bool operator==(const SawyerContainer &other) const
Whether two sets contain the same members.
bool erase(Value value)
Erase a value.
DenseIntegerSet()
Construct an empty set that cannot store any members.
DenseIntegerSet(Value least, Value greatest)
Construct an empty set that can hold values from the specified domain.
DenseIntegerSet & operator|=(const SawyerContainer &other)
Insert many values from another set.
void intersect(const SawyerContainer &other)
Intersect this set with another.
bool existsAll(const SawyerContainer &other) const
Whether all values exist.
Range of values delimited by endpoints.
Definition: Interval.h:33
Unordered set of densely-packed integers.
DenseIntegerSet & operator&=(const SawyerContainer &other)
Intersect this set with another.
bool operator<(const ConstIterator &other) const
Iterators are less-than comparable.
void insertMany(const SawyerContainer &other)
Insert many values from another set.
DenseIntegerSet(const DenseIntegerSet &other)
Copy constructor.
void insertAll()
Insert all possible members.
T greatest() const
Returns upper limit.
Definition: Interval.h:213
bool operator!=(const ConstIterator &other) const
Iterators are comparable for inequality.
DenseIntegerSet operator-(const SawyerContainer &other) const
Compute the difference of this set with another.
DenseIntegerSet operator&(const SawyerContainer &other) const
Compute the intersection of this set with another.
Base class for Sawyer domain errors.
DenseIntegerSet(const Interval< Value > &domain)
Construct an empty set that can hold values from the specified domain.
Bidirectional iterates over members of a set.