ROSE 0.11.145.147
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://gitlab.com/charger7534/sawyer.git.
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
21namespace Sawyer {
22namespace Container {
23
38template<typename T>
40public:
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
48private:
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
54public:
55 typedef T Value;
58 // Construction
60public:
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
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
142public:
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
262public:
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().contains(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
348public:
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 }
428
429 template<class SawyerContainer>
430 DenseIntegerSet& operator+=(const SawyerContainer &other) {
431 insertMany(other);
432 return *this;
433 }
445 bool erase(Value value) {
446 if (!exists(value))
447 return false;
448 Member &m = members_[value - domain_.least()];
449 m.prev->next = m.next;
450 m.next->prev = m.prev;
451 m.next = m.prev = NULL;
452 ASSERT_require(nMembers_ > 0);
453 --nMembers_;
454 return true;
455 }
456
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");
461 ConstIterator retval = iter;
462 ++retval;
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);
468 --nMembers_;
469 return retval;
470 }
478 template<class SawyerContainer>
479 void eraseMany(const SawyerContainer &other) {
480 BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values())
481 erase(otherValue);
482 }
483
484 template<class SawyerContainer>
485 DenseIntegerSet& operator-=(const SawyerContainer &other) {
486 eraseMany(other);
487 return *this;
488 }
496 template<class SawyerContainer>
497 void intersect(const SawyerContainer &other) {
498 DenseIntegerSet tmp(*this);
499 clear();
500 BOOST_FOREACH (const typename SawyerContainer::Value &otherValue, other.values()) {
501 if (tmp.exists(otherValue))
502 insert(otherValue);
503 }
504 }
505
506 template<class SawyerContainer>
507 DenseIntegerSet& operator&=(const SawyerContainer &other) {
508 intersect(other);
509 return *this;
510 }
514 // Set-theoretic operations
516public:
520 template<class SawyerContainer>
521 DenseIntegerSet operator&(const SawyerContainer &other) const {
522 DenseIntegerSet retval = *this;
523 retval &= other;
524 return retval;
525 }
526
532 template<class SawyerContainer>
533 DenseIntegerSet operator|(const SawyerContainer &other) const {
534 DenseIntegerSet retval = *this;
535 retval |= other;
536 return retval;
537 }
538 template<class SawyerContainer>
539 DenseIntegerSet operator+(const SawyerContainer &other) const {
540 return *this | other;
541 }
547 template<class SawyerContainer>
548 DenseIntegerSet operator-(const SawyerContainer &other) const {
549 DenseIntegerSet retval = *this;
550 retval -= other;
551 return retval;
552 }
553
555 // Internal stuff
557public:
558 // Dereference an iterator to get a value.
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]);
564 }
565};
566
567} // namespace
568} // namespace
569
570#endif
Bidirectional iterates over members of a set.
const Value & operator*() const
Dereference.
bool operator==(const ConstIterator &other) const
Iterators are comparable for equality.
bool operator!=(const ConstIterator &other) const
Iterators are comparable for inequality.
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.
Definition Interval.h:31
T greatest() const
Returns upper limit.
Definition Interval.h:224
bool isEmpty() const
True if interval is empty.
Definition Interval.h:230
T least() const
Returns lower limit.
Definition Interval.h:218
Base class for Sawyer domain errors.
Sawyer support library.