ROSE  0.11.96.11
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_
51  Member head_; // head node of doubly-linked circular member list.
52  size_t nMembers_; // number of members contained in the set
53 
54 public:
55  typedef T Value;
57  // Construction
60 public:
66  : head_(&head_, &head_), nMembers_(0) {}
67 
76  : domain_(domain), head_(&head_, &head_), nMembers_(0) {
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)
83  : domain_(Interval<Value>::hull(least, greatest)), head_(&head_, &head_), nMembers_(0) {
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)
90  : domain_(Interval<Value>::baseSize(0, n)), members_(n), head_(&head_, &head_), nMembers_(n) {
91  if (0 == n)
92  domain_ = Interval<Value>();
93  }
98  : domain_(other.domain_), head_(&head_, &head_), nMembers_(0) {
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.
120  std::swap(head_, tmp.head_);
121  if (head_.next == &tmp.head_) {
122  head_.next = head_.prev = &head_;
123  } else {
124  head_.prev->next = &head_;
125  head_.next->prev = &head_;
126  }
127 
128  // Fix up tmp's list too for completeness, although the only thing we do is delete it.
129  if (tmp.head_.next == &head_) {
130  tmp.head_.next = tmp.head_.prev = &tmp.head_;
131  } else {
132  tmp.head_.prev->next = &tmp.head_;
133  tmp.head_.next->prev = &tmp.head_;
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 {
256  return boost::iterator_range<ConstIterator>(ConstIterator(this, head_.next), ConstIterator(this, &head_));
257  }
258 
260  // Predicates and queries
262 public:
266  bool isEmpty() const {
267  return head_.next == &head_;
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().isContaining(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  }
358  head_.next = head_.prev = &head_;
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
381  m.prev = head_.prev;
382  m.next = &head_;
383  head_.prev->next = &m;
384  head_.prev = &m;
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) {
396  members_[0].prev = &head_;
397  head_.next = &members_[0];
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 {
404  members_[i].next = &head_;
405  head_.prev = &members_[i];
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
Sawyer::Container::DenseIntegerSet::Member
Definition: DenseIntegerSet.h:42
Sawyer::Container::DenseIntegerSet::ConstIterator::operator--
ConstIterator & operator--(int)
Decrement.
Definition: DenseIntegerSet.h:235
Sawyer::Container::DenseIntegerSet
Unordered set of densely-packed integers.
Definition: DenseIntegerSet.h:39
Sawyer::Container::DenseIntegerSet::ConstIterator::operator++
ConstIterator operator++(int)
Increment.
Definition: DenseIntegerSet.h:217
Sawyer::Container::DenseIntegerSet::ConstIterator::operator--
ConstIterator & operator--()
Decrement.
Definition: DenseIntegerSet.h:230
Sawyer::Container::DenseIntegerSet::erase
bool erase(Value value)
Erase a value.
Definition: DenseIntegerSet.h:439
sg::deref
T & deref(T *ptr, const char *file=0, size_t ln=0)
dereferences an object (= checked dereference in debug mode)
Definition: sageGeneric.h:98
Sawyer::Container::DenseIntegerSet::insert
bool insert(Value value)
Insert a value.
Definition: DenseIntegerSet.h:366
Sawyer::Container::DenseIntegerSet::insertAll
void insertAll()
Insert all possible members.
Definition: DenseIntegerSet.h:392
Sawyer::Container::DenseIntegerSet::operator!=
bool operator!=(const SawyerContainer &other) const
Whether two sets do not contain the same members.
Definition: DenseIntegerSet.h:341
Sawyer::Container::DenseIntegerSet::operator|=
DenseIntegerSet & operator|=(const SawyerContainer &other)
Insert many values from another set.
Definition: DenseIntegerSet.h:424
Sawyer::Container::DenseIntegerSet::erase
ConstIterator erase(const ConstIterator &iter)
Erase a value.
Definition: DenseIntegerSet.h:451
Sawyer::Container::DenseIntegerSet::operator=
DenseIntegerSet & operator=(const DenseIntegerSet &other)
Assignment operator.
Definition: DenseIntegerSet.h:110
Sawyer::Container::Interval::greatest
T greatest() const
Returns upper limit.
Definition: Interval.h:213
Sawyer::Container::DenseIntegerSet::ConstIterator
Bidirectional iterates over members of a set.
Definition: DenseIntegerSet.h:156
Sawyer::Container::DenseIntegerSet::ConstIterator::operator==
bool operator==(const ConstIterator &other) const
Iterators are comparable for equality.
Definition: DenseIntegerSet.h:180
Sawyer::Container::Interval::least
T least() const
Returns lower limit.
Definition: Interval.h:207
Sawyer::Container::DenseIntegerSet::operator-
DenseIntegerSet operator-(const SawyerContainer &other) const
Compute the difference of this set with another.
Definition: DenseIntegerSet.h:535
Sawyer::Container::DenseIntegerSet::operator&=
DenseIntegerSet & operator&=(const SawyerContainer &other)
Intersect this set with another.
Definition: DenseIntegerSet.h:501
Sawyer::Exception::DomainError
Base class for Sawyer domain errors.
Definition: util/Sawyer/Exception.h:27
Sawyer::Container::DenseIntegerSet::DenseIntegerSet
DenseIntegerSet()
Construct an empty set that cannot store any members.
Definition: DenseIntegerSet.h:65
Sawyer::Container::DenseIntegerSet::Value
T Value
Type of values stored in this container.
Definition: DenseIntegerSet.h:55
Sawyer::Container::DenseIntegerSet::ConstIterator::operator!=
bool operator!=(const ConstIterator &other) const
Iterators are comparable for inequality.
Definition: DenseIntegerSet.h:187
Sawyer::Container::DenseIntegerSet::DenseIntegerSet
DenseIntegerSet(const DenseIntegerSet &other)
Copy constructor.
Definition: DenseIntegerSet.h:97
Sawyer::Container::DenseIntegerSet::isEmpty
bool isEmpty() const
Whether the set is empty.
Definition: DenseIntegerSet.h:266
Sawyer::Container::DenseIntegerSet::intersect
void intersect(const SawyerContainer &other)
Intersect this set with another.
Definition: DenseIntegerSet.h:491
Sawyer::Container::DenseIntegerSet::exists
bool exists(const Value &value) const
Determines whether a value is stored.
Definition: DenseIntegerSet.h:296
Sawyer::Container::DenseIntegerSet::clear
void clear()
Remove all members from this set.
Definition: DenseIntegerSet.h:352
Sawyer::Container::DenseIntegerSet::DenseIntegerSet
DenseIntegerSet(Value n)
Construct an empty set that can hold values from the specified domain.
Definition: DenseIntegerSet.h:89
Sawyer::Container::DenseIntegerSet::ConstIterator::operator++
ConstIterator & operator++()
Increment.
Definition: DenseIntegerSet.h:213
Sawyer::Container::DenseIntegerSet::DenseIntegerSet
DenseIntegerSet(Value least, Value greatest)
Construct an empty set that can hold values from the specified domain.
Definition: DenseIntegerSet.h:82
Sawyer::Container::DenseIntegerSet::ConstIterator::operator*
const Value & operator*() const
Dereference.
Definition: DenseIntegerSet.h:246
Sawyer::Container::DenseIntegerSet::operator-=
DenseIntegerSet & operator-=(const SawyerContainer &other)
Erase many values.
Definition: DenseIntegerSet.h:479
Sawyer::Container::DenseIntegerSet::DenseIntegerSet
DenseIntegerSet(const Interval< Value > &domain)
Construct an empty set that can hold values from the specified domain.
Definition: DenseIntegerSet.h:75
Sawyer
Name space for the entire library.
Definition: Access.h:13
Sawyer::Container::DenseIntegerSet::ConstIterator::operator<
bool operator<(const ConstIterator &other) const
Iterators are less-than comparable.
Definition: DenseIntegerSet.h:201
Sawyer::Container::DenseIntegerSet::values
boost::iterator_range< ConstIterator > values() const
Iterator range for set members.
Definition: DenseIntegerSet.h:255
Sawyer::Container::Interval
Range of values delimited by endpoints.
Definition: Interval.h:33
Sawyer::Container::DenseIntegerSet::isStorable
bool isStorable(Value v) const
Determines if a value is storable.
Definition: DenseIntegerSet.h:288
Sawyer::Container::DenseIntegerSet::eraseMany
void eraseMany(const SawyerContainer &other)
Erase many values.
Definition: DenseIntegerSet.h:473
Sawyer::Container::DenseIntegerSet::size
size_t size() const
Number of members present.
Definition: DenseIntegerSet.h:273
Sawyer::Container::DenseIntegerSet::operator|
DenseIntegerSet operator|(const SawyerContainer &other) const
Compute the union of this set with another.
Definition: DenseIntegerSet.h:525
Sawyer::Container::DenseIntegerSet::insertMany
void insertMany(const SawyerContainer &other)
Insert many values from another set.
Definition: DenseIntegerSet.h:418
Sawyer::Container::Interval::isEmpty
bool isEmpty() const
True if interval is empty.
Definition: Interval.h:219
Sawyer::Container::DenseIntegerSet::operator==
bool operator==(const SawyerContainer &other) const
Whether two sets contain the same members.
Definition: DenseIntegerSet.h:333
Sawyer::Container::DenseIntegerSet::operator&
DenseIntegerSet operator&(const SawyerContainer &other) const
Compute the intersection of this set with another.
Definition: DenseIntegerSet.h:515
Sawyer::Container::DenseIntegerSet::domain
Interval< Value > domain() const
Domain of storable values.
Definition: DenseIntegerSet.h:280
Sawyer::Container::DenseIntegerSet::existsAll
bool existsAll(const SawyerContainer &other) const
Whether all values exist.
Definition: DenseIntegerSet.h:321
Sawyer::Container::DenseIntegerSet::existsAny
bool existsAny(const SawyerContainer &other) const
Whether any value exists.
Definition: DenseIntegerSet.h:308