ROSE  0.9.9.139
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_) {}
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:
156  class ConstIterator: public std::iterator<std::bidirectional_iterator_tag, const Value> {
157  friend class DenseIntegerSet;
158  const DenseIntegerSet *set_;
159  const Member *member_;
160  mutable Value value_; // so we can return a const ref
161 
162  ConstIterator(const DenseIntegerSet *s, const Member *m)
163  : set_(s), member_(m) {}
164 
165  public:
170  bool operator==(const ConstIterator &other) const {
171  return set_ == other.set_ && member_ == other.member_;
172  }
173 
177  bool operator!=(const ConstIterator &other) const {
178  return set_ != other.set_ || member_ != other.member_;
179  }
180 
191  bool operator<(const ConstIterator &other) const {
192  if (set_ != other.set_)
193  return set_ < other.set_;
194  return member_ < other.member_;
195  }
196 
204  member_ = member_->next;
205  return *this;
206  }
208  ConstIterator retval = *this;
209  ++*this;
210  return retval;
211  }
221  member_ = member_->prev;
222  return *this;
223  }
224 
226  ConstIterator retval = *this;
227  --*this;
228  return retval;
229  }
236  const Value& operator*() const {
237  value_ = set_->deref(*this);
238  return value_;
239  }
240  };
241 
245  boost::iterator_range<ConstIterator> values() const {
246  return boost::iterator_range<ConstIterator>(ConstIterator(this, head_.next), ConstIterator(this, &head_));
247  }
248 
250  // Predicates and queries
252 public:
256  bool isEmpty() const {
257  return head_.next == &head_;
258  }
259 
263  size_t size() const {
264  return nMembers_;
265  }
266 
271  return domain_;
272  }
273 
278  bool isStorable(Value v) const {
279  return domain().isContaining(v);
280  }
281 
286  bool exists(const Value &value) const {
287  if (isEmpty() || !isStorable(value))
288  return false;
289  const Member &m = members_[value - domain_.least()];
290  return head_.next == &m || m.prev != NULL;
291  }
292 
297  template<class SawyerContainer>
298  bool existsAny(const SawyerContainer &other) const {
299  BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values()) {
300  if (exists(otherValue))
301  return true;
302  }
303  return false;
304  }
305 
310  template<class SawyerContainer>
311  bool existsAll(const SawyerContainer &other) const {
312  BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values()) {
313  if (!exists(otherValue))
314  return false;
315  }
316  return true;
317  }
318 
322  template<class SawyerContainer>
323  bool operator==(const SawyerContainer &other) const {
324  return size() == other.size() && existsAll(other);
325  }
326 
330  template<class SawyerContainer>
331  bool operator!=(const SawyerContainer &other) const {
332  return size() != other.size() || !existsAll(other);
333  }
334 
336  // Modifiers
338 public:
342  void clear() {
343  Member *next = NULL;
344  for (Member *m = head_.next; m != &head_; m = next) {
345  next = m->next;
346  m->prev = m->next = NULL;
347  }
348  head_.next = head_.prev = &head_;
349  nMembers_ = 0;
350  }
351 
356  bool insert(Value value) {
357  if (!isStorable(value)) {
358  std::string mesg;
359  if (domain_.isEmpty()) {
360  mesg = "cannot insert a value into a destination set with an empty domain";
361  } else {
362  mesg = "cannot insert " + boost::lexical_cast<std::string>(value) + " into a destination set whose domain is [" +
363  boost::lexical_cast<std::string>(domain_.least()) + ", " +
364  boost::lexical_cast<std::string>(domain_.greatest()) + "]";
365  }
366  throw Exception::DomainError(mesg);
367  }
368  Member &m = members_[value - domain_.least()];
369  if (m.next)
370  return false; // already a member
371  m.prev = head_.prev;
372  m.next = &head_;
373  head_.prev->next = &m;
374  head_.prev = &m;
375  ++nMembers_;
376  return true;
377  }
378 
382  void insertAll() {
383  if (!members_.empty()) {
384  for (size_t i=0; i<members_.size(); ++i) {
385  if (0 == i) {
386  members_[0].prev = &head_;
387  head_.next = &members_[0];
388  } else {
389  members_[i].prev = &members_[i-1];
390  }
391  if (i+1 < members_.size()) {
392  members_[i].next = &members_[i+1];
393  } else {
394  members_[i].next = &head_;
395  head_.prev = &members_[i];
396  }
397  }
398  nMembers_ = members_.size();
399  }
400  }
401 
407  template<class SawyerContainer>
408  void insertMany(const SawyerContainer &other) {
409  BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values())
410  insert(otherValue);
411  }
412 
413  template<class SawyerContainer>
414  DenseIntegerSet& operator|=(const SawyerContainer &other) {
415  insertMany(other);
416  return *this;
417  }
429  bool erase(Value value) {
430  if (!exists(value))
431  return false;
432  Member &m = members_[value - domain_.least()];
433  m.prev->next = m.next;
434  m.next->prev = m.prev;
435  m.next = m.prev = NULL;
436  ASSERT_require(nMembers_ > 0);
437  --nMembers_;
438  return true;
439  }
440 
441  ConstIterator erase(const ConstIterator &iter) {
442  ASSERT_require2(iter.set_ != this, "iterator does not belong to this set");
443  ASSERT_require2(iter.member_ != &head_, "cannot erase the end iterator");
444  ASSERT_require2(iter.member_->next != NULL, "iterator no longer points to a member of this set");
445  ConstIterator retval = iter;
446  ++retval;
447  Member &m = iter->member_;
448  m.prev->next = m.next;
449  m.next->prev = m.prev;
450  m.next = m.prev = NULL;
451  ASSERT_require(nMembers_ > 0);
452  --nMembers_;
453  return retval;
454  }
462  template<class SawyerContainer>
463  void eraseMany(const SawyerContainer &other) {
464  BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values())
465  erase(otherValue);
466  }
467 
468  template<class SawyerContainer>
469  DenseIntegerSet& operator-=(const SawyerContainer &other) {
470  eraseMany(other);
471  return *this;
472  }
480  template<class SawyerContainer>
481  void intersect(const SawyerContainer &other) {
482  DenseIntegerSet tmp(*this);
483  clear();
484  BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values()) {
485  if (tmp.exists(otherValue))
486  insert(otherValue);
487  }
488  }
489 
490  template<class SawyerContainer>
491  DenseIntegerSet& operator&=(const SawyerContainer &other) {
492  intersect(other);
493  return *this;
494  }
497  // Set-theoretic operations
500 public:
504  template<class SawyerContainer>
505  DenseIntegerSet operator&(const SawyerContainer &other) const {
506  DenseIntegerSet retval = *this;
507  retval &= other;
508  return retval;
509  }
510 
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 
532  // Internal stuff
534 public:
535  // Dereference an iterator to get a value.
536  Value deref(const ConstIterator &iter) const {
537  const Member *m = iter.member_;
538  ASSERT_require2(m != &head_, "dereferencing an end iterator");
539  ASSERT_require2(m->next != NULL, "dereferencing erased member");
540  return domain_.least() + (m - &members_[0]);
541  }
542 };
543 
544 } // namespace
545 } // namespace
546 
547 #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:197
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: Access.h:11
DenseIntegerSet(Value n)
Construct an empty set that can hold values from the specified domain.
T least() const
Returns lower limit.
Definition: Interval.h:185
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:191
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.