ROSE 0.11.145.147
IndexedList.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#ifndef Sawyer_IndexedList_H
9#define Sawyer_IndexedList_H
10
11#include <Sawyer/Assert.h>
12#include <Sawyer/DefaultAllocator.h>
13#include <Sawyer/Optional.h>
14#include <Sawyer/Sawyer.h>
15
16#include <boost/range/iterator_range.hpp>
17#include <iterator>
18#include <vector>
19
20namespace Sawyer {
21namespace Container {
22
24template<class T>
26 typedef typename T::NodeIterator NodeIterator;
27 typedef typename T::ValueIterator ValueIterator;
28};
29
30template<class T>
31struct IndexedListTraits<const T> {
32 typedef typename T::ConstNodeIterator NodeIterator;
33 typedef typename T::ConstValueIterator ValueIterator;
34};
35
74template<class T, class Alloc = DefaultAllocator>
76public:
77 typedef T Value;
78 typedef Alloc Allocator;
79 class Node;
81private:
82
83 static const size_t NO_ID = (size_t)(-1);
84
85
86 // Forms a circular list. ProtoNode is the first part of a Node so that we can static_cast from ProtoNode to Node.
87 class ProtoNode {
88 public:
89 size_t id; // Unique, small, contiguous ID numbers
90 ProtoNode *next, *prev; // Linkage to neighoring nodes
91 explicit ProtoNode(size_t id=NO_ID): id(id), next(this), prev(this) {}
92 bool isHead() const { return id==NO_ID; } // implies no Node memory is attached; don't static_cast to Node!
93 void insert(ProtoNode &newNode) { // insert newNode before this node
94 ASSERT_forbid(newNode.isHead());
95 ASSERT_require(newNode.next==&newNode);
96 ASSERT_require(newNode.prev==&newNode);
97 prev->next = &newNode;
98 newNode.prev = prev;
99 prev = &newNode;
100 newNode.next = this;
101 }
102 void remove() { // remove this node from the list
103 ASSERT_forbid(isHead());
104 prev->next = next;
105 next->prev = prev;
106 next = prev = this;
107 }
108 Node& dereference() {
109 ASSERT_forbid(isHead());
110 Node *node = (Node*)this; // ProtoNode must be first data member of Node
111 ASSERT_require(&node->linkage_ == this); // it wasn't first
112 return *node;
113 }
114 const Node& dereference() const {
115 ASSERT_forbid(isHead());
116 const Node *node = (const Node*)this; // ProtoNode must be first data member of Node
117 ASSERT_require(&node->linkage_ == this); // it wasn't first
118 return *node;
119 }
120 };
121
122public:
127 class Node {
128 ProtoNode linkage_; // This member MUST BE FIRST so ProtoNode::dereference works
129 Value value_; // User-supplied data for each node
130 private:
131 friend class IndexedList;
132 Node(size_t id, const Value &value): linkage_(id), value_(value) { ASSERT_forbid(linkage_.isHead()); }
133 public:
140 const size_t& id() const { return linkage_.id; }
141
148 Value& value() { return value_; }
149 const Value& value() const { return value_; }
150 Value& operator*() { return value_; }
151 const Value& operator*() const { return value_; }
152 Value* operator->() { return &value_; }
153 const Value* operator->() const { return &value_; }
155 };
156
158 // Iterators
160private:
161 template<class Derived, class Value, class BaseIterator>
162 class IteratorBase {
163 public:
164 // Five standard iterator types
165 using iterator_category = std::bidirectional_iterator_tag;
166 using value_type = Value;
167 using difference_type = std::ptrdiff_t;
168 using pointer = Value*;
169 using reference = Value&;
170
171 protected:
172 BaseIterator base_;
173 IteratorBase() { base_ = NULL; }
174 IteratorBase(const IteratorBase &other): base_(other.base_) {}
175 IteratorBase(const BaseIterator &base): base_(base) {}
176 public:
177 IteratorBase& operator=(const IteratorBase &other) { base_ = other.base_; return *this; }
178 bool isAtEnd() const { return base_->isHead(); }
179 Derived& operator++() { base_ = base_->next; return *derived(); }
180 Derived operator++(int) { Derived old(this->base_); base_ = base_->next; return old; }
181 Derived& operator--() { base_ = base_->prev; return *derived(); }
182 Derived operator--(int) { Derived old(this->base_); base_ = base_->prev; return old; }
183 template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base(); }
184 template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base(); }
185 protected:
186 Derived* derived() { return static_cast<Derived*>(this); }
187 const Derived* derived() const { return static_cast<const Derived*>(this); }
188 public:
189 const BaseIterator& base() const { return base_; }
190 };
191
192public:
207 class NodeIterator: public IteratorBase<NodeIterator, Node, ProtoNode*> {
208 typedef IteratorBase<NodeIterator, Node, ProtoNode*> Super;
209 public:
210 NodeIterator() {}
211 NodeIterator(const NodeIterator &other): Super(other) {}
212 NodeIterator& operator=(const NodeIterator &other) { this->Super::operator=(other); return *this; }
213 Node& operator*() const { return this->base_->dereference(); }
214 Node* operator->() const { return &this->base_->dereference(); }
215 private:
216 friend class IndexedList;
217 NodeIterator(ProtoNode *base): Super(base) {}
218 NodeIterator(Node *node): Super(&node->linkage_) {}
219 };
220
235 class ConstNodeIterator: public IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> {
236 typedef IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> Super;
237 public:
239 ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
240 ConstNodeIterator(const NodeIterator &other): Super(other.base()) {}
241 ConstNodeIterator& operator=(const ConstNodeIterator &other) { this->Super::operator=(other); return *this; }
242 const Node& operator*() const { return this->base_->dereference(); }
243 const Node* operator->() const { return &this->base_->dereference(); }
244 private:
245 friend class IndexedList;
246 ConstNodeIterator(const ProtoNode *base): Super(base) {}
247 ConstNodeIterator(const Node *node): Super(&node->linkage_) {}
248 };
249
260 class ValueIterator: public IteratorBase<ValueIterator, Value, ProtoNode*> {
261 typedef IteratorBase<ValueIterator, Value, ProtoNode*> Super;
262 public:
263 ValueIterator() {}
264 ValueIterator(const ValueIterator &other): Super(other) {}
265 ValueIterator(const NodeIterator &other): Super(other.base()) {}
266 ValueIterator& operator=(const ValueIterator &other) { this->Super::operator=(other); return *this; }
267 Value& operator*() const { return this->base()->dereference().value(); }
268 Value* operator->() const { return &this->base()->dereference().value(); }
269 private:
270 friend class IndexedList;
271 ValueIterator(ProtoNode *base): Super(base) {}
272 ValueIterator(Node *node): Super(&node->linkage_) {}
273 };
274
285 class ConstValueIterator: public IteratorBase<ConstValueIterator, const Value, const ProtoNode*> {
286 typedef IteratorBase<ConstValueIterator, const Value, const ProtoNode*> Super;
287 public:
289 ConstValueIterator(const ConstValueIterator &other): Super(other) {}
290 ConstValueIterator(const NodeIterator &other): Super(other.base()) {}
291 ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
292 ConstValueIterator(const ValueIterator &other): Super(other.base()) {}
293 ConstValueIterator& operator=(const ConstValueIterator &other) { this->Super::operator=(other); return *this; }
294 const Value& operator*() const { return this->base()->dereference().value(); }
295 const Value* operator->() const { return &this->base()->dereference().value(); }
296 private:
297 friend class IndexedList;
298 ConstValueIterator(const ProtoNode *base): Super(base) {}
299 ConstValueIterator(const Node *node): Super(&node->linkage_) {}
300 };
301
302private:
303 Allocator allocator_; // provided allocator for list nodes
304 ProtoNode *head_; // always point to a list head, not a true node (normal allocator)
305 typedef std::vector<Node*> Index; // allocated with provided allocator
306 Index index_; // allocated with normal allocator
307
309 // Serialization
311#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
312private:
313 friend class boost::serialization::access;
314
315 template<class S>
316 void save(S &s, const unsigned /*version*/) const {
317 size_t n = size();
318 s <<BOOST_SERIALIZATION_NVP(n);
319 for (const ProtoNode *pnode = head_->next; pnode != head_; pnode = pnode->next) {
320 ASSERT_require(n-- > 0);
321 size_t id = pnode->dereference().id();
322 const Value &value = pnode->dereference().value();
323 s <<BOOST_SERIALIZATION_NVP(id);
324 s <<BOOST_SERIALIZATION_NVP(value);
325 }
326 }
327
328 template<class S>
329 void load(S &s, const unsigned /*version*/) {
330 clear();
331 size_t n = 0;
332 s >>BOOST_SERIALIZATION_NVP(n);
333 ASSERT_require(index_.empty());
334 index_.resize(n, NULL);
335 for (size_t i=0; i<n; ++i) {
336 size_t id = 0;
337 s >>BOOST_SERIALIZATION_NVP(id);
338 Node *node = new (allocator_.allocate(sizeof(Node))) Node(id, Value());
339 s >>boost::serialization::make_nvp("value", node->value());
340
341 ASSERT_require(id < index_.size());
342 ASSERT_require(index_[id] == NULL);
343 index_[id] = node;
344
345 head_->insert(node->linkage_); // append to end of node list
346 }
347 }
348
349 BOOST_SERIALIZATION_SPLIT_MEMBER();
350#endif
351
352#ifdef SAWYER_HAVE_CEREAL
353private:
354 friend class cereal::access;
355
356 template<class Archive>
357 void CEREAL_SAVE_FUNCTION_NAME(Archive &archive) const {
358 size_t n = size();
359 archive(CEREAL_NVP(n));
360 for (const ProtoNode *pnode = head_->next; pnode != head_; pnode = pnode->next) {
361 ASSERT_require(n-- > 0);
362 size_t id = pnode->dereference().id();
363 const Value &value = pnode->dereference().value();
364 archive(CEREAL_NVP(id));
365 archive(CEREAL_NVP(value));
366 }
367 }
368
369 template<class Archive>
370 void CEREAL_LOAD_FUNCTION_NAME(Archive &archive) {
371 clear();
372 size_t n = 0;
373 archive(CEREAL_NVP(n));
374 ASSERT_require(index_.empty());
375 index_.resize(n, NULL);
376 for (size_t i = 0; i < n; ++i) {
377 size_t id = 0;
378 archive(CEREAL_NVP(id));
379 Node *node = new (allocator_.allocate(sizeof(Node))) Node(id, Value());
380 archive(cereal::make_nvp("value", node->value()));
381
382 ASSERT_require(id < index_.size());
383 ASSERT_require(index_[id] == NULL);
384 index_[id] = node;
385
386 head_->insert(node->linkage_); // append to end of node list
387 }
388 }
389#endif
390
391
393 // Initialization
395public:
396
401 : allocator_(allocator), head_(new ProtoNode) {}
402
407 IndexedList(const IndexedList &other): allocator_(other.allocator_), head_(new ProtoNode) {
408 for (ConstValueIterator otherIter=other.values().begin(); otherIter!=other.values().end(); ++otherIter)
409 pushBack(*otherIter);
410 }
411
413 template<class T2, class Alloc2>
414 IndexedList(const IndexedList<T2, Alloc2> &other, const Allocator &/*allocator*/ = Allocator())
415 : allocator_(Allocator()), head_(new ProtoNode) {
416 typedef typename IndexedList<T2>::ConstValueIterator OtherIter;
417 for (OtherIter otherIter=other.values().begin(); otherIter!=other.values().end(); ++otherIter)
418 pushBack(Value(*otherIter));
419 }
420
424 explicit IndexedList(size_t nElmts, const Value &val = Value(), const Allocator &allocator = Allocator())
425 : allocator_(allocator), head_(new ProtoNode) {
426 index_.reserve(nElmts);
427 for (size_t i=0; i<nElmts; ++i)
428 pushBack(val);
429 }
430
436 clear();
437 insertMultiple(nodes().begin(), other.values());
438 return *this;
439 }
440
445 template<class T2>
447 clear();
448 insert(nodes().begin(), other.values());
449 return *this;
450 }
451
452 ~IndexedList() {
453 clear();
454 delete head_;
455 }
456
460 const Allocator& allocator() const {
461 return allocator_;
462 }
463
465 // Iteration
467public:
468
474 boost::iterator_range<NodeIterator> nodes() {
475 return boost::iterator_range<NodeIterator>(NodeIterator(head_->next), NodeIterator(head_));
476 }
477 boost::iterator_range<ConstNodeIterator> nodes() const {
478 return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(head_->next), ConstNodeIterator(head_));
479 }
480 boost::iterator_range<ValueIterator> values() {
481 return boost::iterator_range<ValueIterator>(ValueIterator(head_->next), ValueIterator(head_));
482 }
483 boost::iterator_range<ConstValueIterator> values() const {
484 return boost::iterator_range<ConstValueIterator>(ConstValueIterator(head_->next), ConstValueIterator(head_));
485 }
488private:
489 bool isLocalIterator(const ConstValueIterator &iter) const {
490 const ProtoNode *pn = iter.base();
491 ASSERT_not_null(pn);
492 if (pn == head_)
493 return true; // local end iterator
494 const Node *node = &pn->dereference();
495 size_t id = node->id();
496 return id<index_.size() && node==index_[id];
497 }
498
499
501 // Size and capacity
503public:
504
508 bool isEmpty() const {
509 return index_.empty();
510 }
511
515 size_t size() const {
516 return index_.size();
517 }
518
526 size_t capacity() const {
527 return index_.capacity();
528 }
529 void capacity(size_t n) {
530 index_.reserve(n);
531 }
536 // Searching
538public:
539
546 NodeIterator find(size_t id) {
547 ASSERT_require(id < index_.size());
548 ASSERT_not_null(index_[id]);
549 return NodeIterator(index_[id]);
550 }
551 ConstNodeIterator find(size_t id) const {
552 ASSERT_require(id < index_.size());
553 ASSERT_not_null(index_[id]);
554 return ConstNodeIterator(index_[id]);
555 }
560 // Accessors
562public:
563
570 ASSERT_forbid(isEmpty());
571 return head_->next->dereference();
572 }
573 const Node& frontNode() const {
574 ASSERT_forbid(isEmpty());
575 return head_->next->dereference();
576 }
578 return frontNode().value();
579 }
580 const Value& frontValue() const {
581 return frontNode().value();
582 }
591 ASSERT_forbid(isEmpty());
592 return head_->prev->dereference();
593 }
594 const Node& backNode() const {
595 ASSERT_forbid(isEmpty());
596 return head_->prev->dereference();
597 }
599 return backNode().value();
600 }
601 const Value& backValue() const {
602 return backNode().value();
603 }
612 Node& indexedNode(size_t id) {
613 ASSERT_require(id < size());
614 ASSERT_not_null(index_[id]);
615 return *index_[id];
616 }
617 const Node& indexedNode(size_t id) const {
618 ASSERT_require(id < size());
619 ASSERT_not_null(index_[id]);
620 return *index_[id];
621 }
622 Value& indexedValue(size_t id) {
623 return indexedNode(id).value();
624 }
625 const Value& indexedValue(size_t id) const {
626 return indexedNode(id).value();
627 }
628 Value& operator[](size_t id) {
629 return indexedValue(id);
630 }
631 const Value& operator[](size_t id) const {
632 return indexedValue(id);
633 }
634
635 Optional<Value> getOptional(size_t id) const {
636 return id < size() ? Optional<Value>(indexedValue(id)) : Optional<Value>();
637 }
638
639 Value& getOrElse(size_t id, Value &dflt) {
640 return id < size() ? indexedValue(id) : dflt;
641 }
642 const Value& getOrElse(size_t id, const Value &dflt) const {
643 return id < size() ? indexedValue(id) : dflt;
644 }
645
646 const Value& getOrDefault(size_t id) const {
647 static const Value dflt;
648 return id < size() ? indexedValue(id) : dflt;
649 }
653 // Mutators
655public:
656
661 IndexedList& pushFront(const Value &value) {
662 insert(nodes().begin(), value);
663 return *this;
664 }
665
670 IndexedList& pushBack(const Value &value) {
671 insert(nodes().end(), value);
672 return *this;
673 }
674
679 NodeIterator insert(const ValueIterator &position, const Value &value) {
680 ProtoNode *pos = position.base();
681 Node *node = new (allocator_.allocate(sizeof(Node))) Node(index_.size(), value);
682 index_.push_back(node);
683 pos->insert(node->linkage_);
684 return NodeIterator(node);
685 }
686
692 IndexedList& insert(const ValueIterator &position, size_t nElmts, const Value &value) {
693 for (size_t i=0; i<nElmts; ++i)
694 insert(position, value);
695 return *this;
696 }
697
704 template<class OtherValueIterator>
705 IndexedList& insertMultiple(const ValueIterator &position, const boost::iterator_range<OtherValueIterator> &range) {
706 for (OtherValueIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
707 insert(position, Value(*otherIter));
708 return *this;
709 }
710
711
715 void clear() {
716 for (size_t i=0; i<index_.size(); ++i) {
717 index_[i]->~Node();
718 allocator_.deallocate((void*)index_[i], sizeof(Node));
719 }
720 index_.clear();
721 head_->next = head_->prev = head_;
722 }
723
727 NodeIterator erase(size_t id) {
728 ASSERT_require(id < size());
729 return eraseAt(find(id));
730 }
731
737 ASSERT_require(isLocalIterator(position));
738 ProtoNode *pos = position.base();
739 ProtoNode *next = pos->next; // to build the return value
740 pos->remove(); // remove node from the doubly linked list w/out deleting
741 size_t id = pos->id;
742 if (id + 1 < index_.size()) {
743 std::swap(index_.back(), index_[id]);
744 index_[id]->linkage_.id = id;
745 }
746 index_.back()->~Node();
747 allocator_.deallocate(index_.back(), sizeof(Node));
748 index_.pop_back();
749 return NodeIterator(next);
750 }
751
752 // range must be a range within this container
753 NodeIterator eraseAtMultiple(const boost::iterator_range<NodeIterator> &range) {
754 boost::iterator_range<ValueIterator> valueRange(range.begin(), range.end());
755 return eraseAtMultiple(valueRange);
756 }
757 NodeIterator eraseAtMultiple(const boost::iterator_range<ValueIterator> &range) {
758 ValueIterator otherIter = range.begin();
759 while (otherIter!=range.end())
760 otherIter = eraseAt(otherIter);
761 return NodeIterator(range.end().base());
762 }
763
764 // debugging
765 void dump(std::ostream &o) const {
766 o <<"list contents:\n"
767 <<" index:\n";
768 for (size_t i=0; i<index_.size(); ++i)
769 o <<" [" <<i <<"]=" <<index_[i] <<"\n";
770 o <<" list:\n";
771 ProtoNode *pn = head_;
772 for (size_t i=0; i<index_.size()+1; ++i, pn=pn->next) {
773 o <<" " <<pn <<"\t" <<pn->next <<"\t" <<pn->prev <<"\t" <<pn->id <<"\n";
774 ASSERT_require(pn->isHead() || index_[pn->id]==&pn->dereference());
775 ASSERT_require(pn->next->prev == pn);
776 ASSERT_require(pn->prev->next == pn);
777 }
778 }
779};
780
781} // namespace
782} // namespace
783
784#endif
List const node bidirectional iterator.
List const value bidirectional iterator.
List node bidirectional iterator.
Combination user-defined value and ID number.
const Value & operator*() const
Accessor for user-defined value.
const size_t & id() const
Unique identification number.
const Value * operator->() const
Accessor for user-defined value.
Value * operator->()
Accessor for user-defined value.
Value & operator*()
Accessor for user-defined value.
const Value & value() const
Accessor for user-defined value.
Value & value()
Accessor for user-defined value.
List value bidirectional iterator.
Doubly-linked list with constant-time indexing.
Definition IndexedList.h:75
IndexedList & operator=(const IndexedList< T2 > &other)
Assignment from another list.
Alloc Allocator
Allocator for the storage nodes.
Definition IndexedList.h:78
bool isEmpty() const
Determines if this list is empty.
IndexedList(const Allocator &allocator=Allocator())
Default constructor.
Value & backValue()
Last element of list.
IndexedList(const IndexedList< T2, Alloc2 > &other, const Allocator &=Allocator())
Copy constructor.
NodeIterator eraseAt(const ValueIterator &position)
Remove one element.
IndexedList(const IndexedList &other)
Copy constructor.
IndexedList & pushFront(const Value &value)
Insert at the front of the list.
IndexedList & insertMultiple(const ValueIterator &position, const boost::iterator_range< OtherValueIterator > &range)
Insert elements at position.
const Value & backValue() const
Last element of list.
Node & backNode()
Last element of list.
NodeIterator erase(size_t id)
Erase one element.
Value & frontValue()
First element of list.
const Value & getOrElse(size_t id, const Value &dflt) const
Element reference by ID.
void capacity(size_t n)
Allocated capacity of the index.
const Value & indexedValue(size_t id) const
Element reference by ID.
NodeIterator find(size_t id)
Lookup by ID.
IndexedList & operator=(const IndexedList &other)
Assignment from another list.
const Allocator & allocator() const
Allocator.
NodeIterator insert(const ValueIterator &position, const Value &value)
Insert element at position.
Value & getOrElse(size_t id, Value &dflt)
Element reference by ID.
ConstNodeIterator find(size_t id) const
Lookup by ID.
const Node & frontNode() const
First element of list.
IndexedList & pushBack(const Value &value)
Insert at the back of the list.
const Node & backNode() const
Last element of list.
size_t size() const
Number of elements in list.
const Value & operator[](size_t id) const
Element reference by ID.
size_t capacity() const
Allocated capacity of the index.
Value & operator[](size_t id)
Element reference by ID.
const Value & frontValue() const
First element of list.
Value & indexedValue(size_t id)
Element reference by ID.
boost::iterator_range< ValueIterator > values()
All elements.
void clear()
Empties the list.
Optional< Value > getOptional(size_t id) const
Element reference by ID.
boost::iterator_range< ConstValueIterator > values() const
All elements.
boost::iterator_range< ConstNodeIterator > nodes() const
All elements.
const Value & getOrDefault(size_t id) const
Element reference by ID.
const Node & indexedNode(size_t id) const
Element reference by ID.
IndexedList(size_t nElmts, const Value &val=Value(), const Allocator &allocator=Allocator())
Filling constructor.
Node & frontNode()
First element of list.
T Value
Type of values stored in this container.
Definition IndexedList.h:77
IndexedList & insert(const ValueIterator &position, size_t nElmts, const Value &value)
Insert multiple copies at position.
boost::iterator_range< NodeIterator > nodes()
All elements.
Node & indexedNode(size_t id)
Element reference by ID.
Holds a value or nothing.
Definition Optional.h:56
Id id(const std::string &name)
Returns the ID for an attribute name.
Sawyer support library.
Traits for indexed lists.
Definition IndexedList.h:25