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 {
256 return boost::iterator_range<ConstIterator>(ConstIterator(
this, head_.next), ConstIterator(
this, &head_));
267 return head_.next == &head_;
289 return domain().isContaining(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()) +
"]";
378 Member &m = members_[value - domain_.
least()];
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>
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);
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;
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);
472 template<
class SawyerContainer>
474 BOOST_FOREACH (
const typename SawyerContainer::Value &otherValue, other.values())
478 template<
class SawyerContainer>
490 template<
class SawyerContainer>
494 BOOST_FOREACH (
const typename SawyerContainer::Value &otherValue, other.values()) {
495 if (tmp.
exists(otherValue))
500 template<
class SawyerContainer>
514 template<
class SawyerContainer>
524 template<
class SawyerContainer>
534 template<
class SawyerContainer>
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]);