9#ifndef Sawyer_DenseIntegerSet_H
10#define Sawyer_DenseIntegerSet_H
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>
44 Member(): next(NULL), prev(NULL) {}
50 std::vector<Member> members_;
66 : head_(&head_, &head_), nMembers_(0) {}
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());
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());
90 : domain_(
Interval<
Value>::baseSize(0, n)), members_(n), head_(&head_, &head_), nMembers_(n) {
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());
114 std::swap(domain_, tmp.domain_);
115 std::swap(members_, tmp.members_);
116 std::swap(nMembers_, tmp.nMembers_);
120 std::swap(head_, tmp.head_);
121 if (head_.next == &tmp.head_) {
122 head_.next = head_.prev = &head_;
124 head_.prev->next = &head_;
125 head_.next->prev = &head_;
129 if (tmp.head_.next == &head_) {
130 tmp.head_.next = tmp.head_.prev = &tmp.head_;
132 tmp.head_.prev->next = &tmp.head_;
133 tmp.head_.next->prev = &tmp.head_;
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&;
169 mutable Value value_;
173 : set_(s), member_(m) {}
181 return set_ == other.set_ && member_ == other.member_;
188 return set_ != other.set_ || member_ != other.member_;
202 if (set_ != other.set_)
203 return set_ < other.set_;
204 return member_ < other.member_;
214 member_ = member_->next;
231 member_ = member_->prev;
247 value_ = set_->deref(*
this);
255 boost::iterator_range<ConstIterator>
values()
const {
267 return head_.next == &head_;
289 return domain().contains(v);
299 const Member &m = members_[value - domain_.
least()];
300 return head_.next == &m || m.prev != NULL;
307 template<
class SawyerContainer>
309 BOOST_FOREACH (
const typename SawyerContainer::Value &otherValue, other.values()) {
320 template<
class SawyerContainer>
322 BOOST_FOREACH (
const typename SawyerContainer::Value &otherValue, other.values()) {
332 template<
class SawyerContainer>
340 template<
class SawyerContainer>
354 for (
Member *m = head_.next; m != &head_; m = next) {
356 m->prev = m->next = NULL;
358 head_.next = head_.prev = &head_;
370 mesg =
"cannot insert a value into a destination set with an empty domain";
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()) +
"]";
383 head_.prev->next = &m;
393 if (!members_.empty()) {
394 for (
size_t i=0; i<members_.size(); ++i) {
396 members_[0].prev = &head_;
397 head_.next = &members_[0];
399 members_[i].prev = &members_[i-1];
401 if (i+1 < members_.size()) {
402 members_[i].next = &members_[i+1];
404 members_[i].next = &head_;
405 head_.prev = &members_[i];
408 nMembers_ = members_.size();
417 template<
class SawyerContainer>
419 BOOST_FOREACH (
const typename SawyerContainer::Value &otherValue, other.values())
423 template<
class SawyerContainer>
429 template<
class SawyerContainer>
449 m.prev->next = m.next;
450 m.next->prev = m.prev;
451 m.next = m.prev = NULL;
452 ASSERT_require(nMembers_ > 0);
458 ASSERT_require2(iter.set_ !=
this,
"iterator does not belong to this set");
459 ASSERT_require2(iter.member_ != &head_,
"cannot erase the end iterator");
460 ASSERT_require2(iter.member_->next != NULL,
"iterator no longer points to a member of this set");
463 Member &m = iter->member_;
464 m.prev->next = m.next;
465 m.next->prev = m.prev;
466 m.next = m.prev = NULL;
467 ASSERT_require(nMembers_ > 0);
478 template<
class SawyerContainer>
480 BOOST_FOREACH (
const typename SawyerContainer::Value &otherValue, other.values())
484 template<
class SawyerContainer>
496 template<
class SawyerContainer>
500 BOOST_FOREACH (
const typename SawyerContainer::Value &otherValue, other.values()) {
501 if (tmp.
exists(otherValue))
506 template<
class SawyerContainer>
520 template<
class SawyerContainer>
532 template<
class SawyerContainer>
538 template<
class SawyerContainer>
540 return *
this | other;
547 template<
class SawyerContainer>
559 Value deref(
const ConstIterator &iter)
const {
560 const Member *m = iter.member_;
561 ASSERT_require2(m != &head_,
"dereferencing an end iterator");
562 ASSERT_require2(m->next != NULL,
"dereferencing erased member");
563 return domain_.
least() + (m - &members_[0]);
Bidirectional iterates over members of a set.
const Value & operator*() const
Dereference.
ConstIterator & operator++()
Increment.
ConstIterator & operator--()
Decrement.
bool operator==(const ConstIterator &other) const
Iterators are comparable for equality.
bool operator!=(const ConstIterator &other) const
Iterators are comparable for inequality.
ConstIterator & operator--(int)
Decrement.
ConstIterator operator++(int)
Increment.
bool operator<(const ConstIterator &other) const
Iterators are less-than comparable.
Unordered set of densely-packed integers.
bool insert(Value value)
Insert a value.
size_t size() const
Number of members present.
DenseIntegerSet(Value n)
Construct an empty set that can hold values from the specified domain.
bool existsAll(const SawyerContainer &other) const
Whether all values exist.
DenseIntegerSet operator&(const SawyerContainer &other) const
Compute the intersection of this set with another.
bool erase(Value value)
Erase a value.
DenseIntegerSet(const Interval< Value > &domain)
Construct an empty set that can hold values from the specified domain.
Interval< Value > domain() const
Domain of storable values.
DenseIntegerSet & operator|=(const SawyerContainer &other)
Insert many values from another set.
bool operator!=(const SawyerContainer &other) const
Whether two sets do not contain the same members.
DenseIntegerSet operator-(const SawyerContainer &other) const
Compute the difference of this set with another.
DenseIntegerSet & operator+=(const SawyerContainer &other)
Insert many values from another set.
bool existsAny(const SawyerContainer &other) const
Whether any value exists.
bool operator==(const SawyerContainer &other) const
Whether two sets contain the same members.
DenseIntegerSet(Value least, Value greatest)
Construct an empty set that can hold values from the specified domain.
void insertMany(const SawyerContainer &other)
Insert many values from another set.
bool isEmpty() const
Whether the set is empty.
bool isStorable(Value v) const
Determines if a value is storable.
ConstIterator erase(const ConstIterator &iter)
Erase a value.
DenseIntegerSet(const DenseIntegerSet &other)
Copy constructor.
DenseIntegerSet operator+(const SawyerContainer &other) const
Compute the union of this set with another.
void insertAll()
Insert all possible members.
DenseIntegerSet operator|(const SawyerContainer &other) const
Compute the union of this set with another.
DenseIntegerSet & operator&=(const SawyerContainer &other)
Intersect this set with another.
DenseIntegerSet & operator-=(const SawyerContainer &other)
Erase many values.
void clear()
Remove all members from this set.
bool exists(const Value &value) const
Determines whether a value is stored.
void eraseMany(const SawyerContainer &other)
Erase many values.
boost::iterator_range< ConstIterator > values() const
Iterator range for set members.
DenseIntegerSet & operator=(const DenseIntegerSet &other)
Assignment operator.
T Value
Type of values stored in this container.
void intersect(const SawyerContainer &other)
Intersect this set with another.
DenseIntegerSet()
Construct an empty set that cannot store any members.
Range of values delimited by endpoints.
T greatest() const
Returns upper limit.
bool isEmpty() const
True if interval is empty.
T least() const
Returns lower limit.
Base class for Sawyer domain errors.