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_) {}
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());
102 BOOST_FOREACH (Value v, other.
values())
112 BOOST_FOREACH (Value v, other.
values())
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_;
156 class ConstIterator:
public std::iterator<std::bidirectional_iterator_tag, const Value> {
160 mutable Value value_;
163 : set_(s), member_(m) {}
171 return set_ == other.set_ && member_ == other.member_;
178 return set_ != other.set_ || member_ != other.member_;
192 if (set_ != other.set_)
193 return set_ < other.set_;
194 return member_ < other.member_;
204 member_ = member_->next;
221 member_ = member_->prev;
237 value_ = set_->deref(*
this);
245 boost::iterator_range<ConstIterator>
values()
const {
246 return boost::iterator_range<ConstIterator>(ConstIterator(
this, head_.next), ConstIterator(
this, &head_));
257 return head_.next == &head_;
279 return domain().isContaining(v);
289 const Member &m = members_[value - domain_.
least()];
290 return head_.next == &m || m.prev != NULL;
297 template<
class SawyerContainer>
299 BOOST_FOREACH (
const typename SawyerContainer::Value &otherValue, other.values()) {
310 template<
class SawyerContainer>
312 BOOST_FOREACH (
const typename SawyerContainer::Value &otherValue, other.values()) {
322 template<
class SawyerContainer>
330 template<
class SawyerContainer>
344 for (Member *m = head_.next; m != &head_; m = next) {
346 m->prev = m->next = NULL;
348 head_.next = head_.prev = &head_;
360 mesg =
"cannot insert a value into a destination set with an empty domain";
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()) +
"]";
368 Member &m = members_[value - domain_.
least()];
373 head_.prev->next = &m;
383 if (!members_.empty()) {
384 for (
size_t i=0; i<members_.size(); ++i) {
386 members_[0].prev = &head_;
387 head_.next = &members_[0];
389 members_[i].prev = &members_[i-1];
391 if (i+1 < members_.size()) {
392 members_[i].next = &members_[i+1];
394 members_[i].next = &head_;
395 head_.prev = &members_[i];
398 nMembers_ = members_.size();
407 template<
class SawyerContainer>
409 BOOST_FOREACH (
const typename SawyerContainer::Value &otherValue, other.values())
413 template<
class SawyerContainer>
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);
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;
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);
462 template<
class SawyerContainer>
464 BOOST_FOREACH (
const typename SawyerContainer::Value &otherValue, other.values())
468 template<
class SawyerContainer>
480 template<
class SawyerContainer>
484 BOOST_FOREACH (
const typename SawyerContainer::Value &otherValue, other.values()) {
485 if (tmp.
exists(otherValue))
490 template<
class SawyerContainer>
504 template<
class SawyerContainer>
514 template<
class SawyerContainer>
524 template<
class SawyerContainer>
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]);
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.
Interval< Value > domain() const
Domain of storable values.
ConstIterator & operator--(int)
Decrement.
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.
ConstIterator & operator--()
Decrement.
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.
DenseIntegerSet(Value n)
Construct an empty set that can hold values from the specified domain.
T least() const
Returns lower limit.
bool insert(Value value)
Insert a value.
const Value & operator*() const
Dereference.
DenseIntegerSet & operator=(const DenseIntegerSet &other)
Assignment operator.
ConstIterator & operator++()
Increment.
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.
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.
ConstIterator operator++(int)
Increment.
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.
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.