8 #ifndef Sawyer_IndexedList_H
9 #define Sawyer_IndexedList_H
11 #include <Sawyer/Assert.h>
12 #include <Sawyer/DefaultAllocator.h>
13 #include <Sawyer/Optional.h>
14 #include <Sawyer/Sawyer.h>
16 #include <boost/range/iterator_range.hpp>
17 #include <boost/serialization/access.hpp>
18 #include <boost/serialization/nvp.hpp>
19 #include <boost/serialization/split_member.hpp>
29 typedef typename T::NodeIterator NodeIterator;
30 typedef typename T::ValueIterator ValueIterator;
35 typedef typename T::ConstNodeIterator NodeIterator;
36 typedef typename T::ConstValueIterator ValueIterator;
77 template<
class T,
class Alloc = DefaultAllocator>
86 static const size_t NO_ID = (size_t)(-1);
93 ProtoNode *next, *prev;
94 explicit ProtoNode(
size_t id=NO_ID): id(id), next(this), prev(this) {}
95 bool isHead()
const {
return id==NO_ID; }
96 void insert(ProtoNode &newNode) {
97 ASSERT_forbid(newNode.isHead());
98 ASSERT_require(newNode.next==&newNode);
99 ASSERT_require(newNode.prev==&newNode);
100 prev->next = &newNode;
106 ASSERT_forbid(isHead());
111 Node& dereference() {
112 ASSERT_forbid(isHead());
113 Node *node = (Node*)
this;
114 ASSERT_require(&node->linkage_ ==
this);
117 const Node& dereference()
const {
118 ASSERT_forbid(isHead());
119 const Node *node = (
const Node*)
this;
120 ASSERT_require(&node->linkage_ ==
this);
135 Node(
size_t id,
const Value &
value): linkage_(
id), value_(value) { ASSERT_forbid(linkage_.isHead()); }
143 const size_t&
id()
const {
return linkage_.id; }
152 const Value&
value()
const {
return value_; }
164 template<
class Derived,
class Value,
class BaseIterator>
168 using iterator_category = std::bidirectional_iterator_tag;
169 using value_type =
Value;
170 using difference_type = std::ptrdiff_t;
171 using pointer = Value*;
172 using reference = Value&;
176 IteratorBase() { base_ = NULL; }
177 IteratorBase(
const IteratorBase &other): base_(other.base_) {}
178 IteratorBase(
const BaseIterator &base): base_(base) {}
180 IteratorBase&
operator=(
const IteratorBase &other) { base_ = other.base_;
return *
this; }
181 bool isAtEnd()
const {
return base_->isHead(); }
182 Derived& operator++() { base_ = base_->next;
return *derived(); }
183 Derived operator++(
int) { Derived old(this->base_); base_ = base_->next;
return old; }
184 Derived& operator--() { base_ = base_->prev;
return *derived(); }
185 Derived operator--(
int) { Derived old(this->base_); base_ = base_->prev;
return old; }
186 template<
class OtherIter>
bool operator==(
const OtherIter &other)
const {
return base_ == other.base(); }
187 template<
class OtherIter>
bool operator!=(
const OtherIter &other)
const {
return base_ != other.base(); }
189 Derived* derived() {
return static_cast<Derived*
>(
this); }
190 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
192 const BaseIterator& base()
const {
return base_; }
210 class NodeIterator:
public IteratorBase<NodeIterator, Node, ProtoNode*> {
211 typedef IteratorBase<NodeIterator, Node, ProtoNode*> Super;
216 Node& operator*()
const {
return this->base_->dereference(); }
217 Node* operator->()
const {
return &this->base_->dereference(); }
239 typedef IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> Super;
245 const Node& operator*()
const {
return this->base_->dereference(); }
246 const Node* operator->()
const {
return &this->base_->dereference(); }
263 class ValueIterator:
public IteratorBase<ValueIterator, Value, ProtoNode*> {
264 typedef IteratorBase<ValueIterator, Value, ProtoNode*> Super;
270 Value& operator*()
const {
return this->base()->dereference().value(); }
271 Value* operator->()
const {
return &this->base()->dereference().value(); }
289 typedef IteratorBase<ConstValueIterator, const Value, const ProtoNode*> Super;
297 const Value& operator*()
const {
return this->base()->dereference().value(); }
298 const Value* operator->()
const {
return &this->base()->dereference().value(); }
307 Allocator allocator_;
309 typedef std::vector<Node*> Index;
316 friend class boost::serialization::access;
319 void save(S &s,
const unsigned )
const {
321 s <<BOOST_SERIALIZATION_NVP(n);
322 for (
const ProtoNode *pnode = head_->next; pnode != head_; pnode = pnode->next) {
323 ASSERT_require(n-- > 0);
324 size_t id = pnode->dereference().id();
325 const Value &value = pnode->dereference().value();
326 s <<BOOST_SERIALIZATION_NVP(
id);
327 s <<BOOST_SERIALIZATION_NVP(value);
332 void load(S &s,
const unsigned ) {
335 s >>BOOST_SERIALIZATION_NVP(n);
336 ASSERT_require(index_.empty());
337 index_.resize(n, NULL);
338 for (
size_t i=0; i<n; ++i) {
340 s >>BOOST_SERIALIZATION_NVP(
id);
341 Node *node =
new (allocator_.allocate(
sizeof(Node))) Node(
id,
Value());
342 s >>boost::serialization::make_nvp(
"value", node->value());
344 ASSERT_require(
id < index_.size());
345 ASSERT_require(index_[
id] == NULL);
348 head_->insert(node->linkage_);
352 BOOST_SERIALIZATION_SPLIT_MEMBER();
364 : allocator_(
allocator), head_(new ProtoNode) {}
371 for (ConstValueIterator otherIter=other.
values().begin(); otherIter!=other.
values().end(); ++otherIter)
376 template<
class T2,
class Alloc2>
378 : allocator_(Allocator()), head_(new ProtoNode) {
380 for (OtherIter otherIter=other.
values().begin(); otherIter!=other.
values().end(); ++otherIter)
388 : allocator_(
allocator), head_(new ProtoNode) {
389 index_.reserve(nElmts);
390 for (
size_t i=0; i<nElmts; ++i)
437 boost::iterator_range<NodeIterator>
nodes() {
438 return boost::iterator_range<NodeIterator>(NodeIterator(head_->next), NodeIterator(head_));
440 boost::iterator_range<ConstNodeIterator>
nodes()
const {
441 return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(head_->next), ConstNodeIterator(head_));
443 boost::iterator_range<ValueIterator>
values() {
444 return boost::iterator_range<ValueIterator>(ValueIterator(head_->next), ValueIterator(head_));
446 boost::iterator_range<ConstValueIterator>
values()
const {
447 return boost::iterator_range<ConstValueIterator>(ConstValueIterator(head_->next), ConstValueIterator(head_));
452 bool isLocalIterator(
const ConstValueIterator &iter)
const {
453 const ProtoNode *pn = iter.base();
457 const Node *node = &pn->dereference();
458 size_t id = node->id();
459 return id<index_.size() && node==index_[id];
472 return index_.empty();
479 return index_.size();
490 return index_.capacity();
510 ASSERT_require(
id < index_.size());
511 ASSERT_not_null(index_[
id]);
512 return NodeIterator(index_[
id]);
514 ConstNodeIterator
find(
size_t id)
const {
515 ASSERT_require(
id < index_.size());
516 ASSERT_not_null(index_[
id]);
517 return ConstNodeIterator(index_[
id]);
534 return head_->next->dereference();
538 return head_->next->dereference();
555 return head_->prev->dereference();
559 return head_->prev->dereference();
576 ASSERT_require(
id <
size());
577 ASSERT_not_null(index_[
id]);
581 ASSERT_require(
id <
size());
582 ASSERT_not_null(index_[
id]);
605 const Value&
getOrElse(
size_t id,
const Value &dflt)
const {
610 static const Value dflt;
642 NodeIterator
insert(
const ValueIterator &position,
const Value &value) {
643 ProtoNode *pos = position.base();
644 Node *node =
new (allocator_.allocate(
sizeof(Node))) Node(index_.size(), value);
645 index_.push_back(node);
646 pos->insert(node->linkage_);
647 return NodeIterator(node);
656 for (
size_t i=0; i<nElmts; ++i)
667 template<
class OtherValueIterator>
669 for (OtherValueIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
679 for (
size_t i=0; i<index_.size(); ++i) {
681 allocator_.deallocate((
void*)index_[i],
sizeof(Node));
684 head_->next = head_->prev = head_;
691 ASSERT_require(
id <
size());
699 NodeIterator
eraseAt(
const ValueIterator &position) {
700 ASSERT_require(isLocalIterator(position));
701 ProtoNode *pos = position.base();
702 ProtoNode *next = pos->next;
705 if (
id + 1 < index_.size()) {
706 std::swap(index_.back(), index_[id]);
707 index_[id]->linkage_.id = id;
709 index_.back()->~Node();
710 allocator_.deallocate(index_.back(),
sizeof(Node));
712 return NodeIterator(next);
716 NodeIterator eraseAtMultiple(
const boost::iterator_range<NodeIterator> &range) {
717 boost::iterator_range<ValueIterator> valueRange(range.begin(), range.end());
718 return eraseAtMultiple(valueRange);
720 NodeIterator eraseAtMultiple(
const boost::iterator_range<ValueIterator> &range) {
721 ValueIterator otherIter = range.begin();
722 while (otherIter!=range.end())
723 otherIter =
eraseAt(otherIter);
724 return NodeIterator(range.end().base());
728 void dump(std::ostream &o)
const {
729 o <<
"list contents:\n"
731 for (
size_t i=0; i<index_.size(); ++i)
732 o <<
" [" <<i <<
"]=" <<index_[i] <<
"\n";
734 ProtoNode *pn = head_;
735 for (
size_t i=0; i<index_.size()+1; ++i, pn=pn->next) {
736 o <<
" " <<pn <<
"\t" <<pn->next <<
"\t" <<pn->prev <<
"\t" <<pn->id <<
"\n";
737 ASSERT_require(pn->isHead() || index_[pn->id]==&pn->dereference());
738 ASSERT_require(pn->next->prev == pn);
739 ASSERT_require(pn->prev->next == pn);
size_t size() const
Number of elements in list.
T Value
Type of values stored in this container.
const Node & indexedNode(size_t id) const
Element reference by ID.
Node & backNode()
Last element of list.
IndexedList(const Allocator &allocator=Allocator())
Default constructor.
size_t capacity() const
Allocated capacity of the index.
bool isEmpty() const
Determines if this list is empty.
IndexedList & operator=(const IndexedList &other)
Assignment from another list.
Node & indexedNode(size_t id)
Element reference by ID.
Value & backValue()
Last element of list.
boost::iterator_range< ConstValueIterator > values() const
All elements.
const Value & indexedValue(size_t id) const
Element reference by ID.
IndexedList & insertMultiple(const ValueIterator &position, const boost::iterator_range< OtherValueIterator > &range)
Insert elements at position.
boost::iterator_range< ValueIterator > values()
All elements.
Value & getOrElse(size_t id, Value &dflt)
Element reference by ID.
Alloc Allocator
Allocator for the storage nodes.
NodeIterator erase(size_t id)
Erase one element.
List const value bidirectional iterator.
Value & value()
Accessor for user-defined value.
IndexedList & insert(const ValueIterator &position, size_t nElmts, const Value &value)
Insert multiple copies at position.
Value & indexedValue(size_t id)
Element reference by ID.
const Value & getOrDefault(size_t id) const
Element reference by ID.
Node & frontNode()
First element of list.
const Allocator & allocator() const
Allocator.
Name space for the entire library.
boost::iterator_range< NodeIterator > nodes()
All elements.
NodeIterator find(size_t id)
Lookup by ID.
const Value & getOrElse(size_t id, const Value &dflt) const
Element reference by ID.
void clear()
Empties the list.
void capacity(size_t n)
Allocated capacity of the index.
IndexedList & pushBack(const Value &value)
Insert at the back of the list.
IndexedList(const IndexedList< T2, Alloc2 > &other, const Allocator &=Allocator())
Copy constructor.
List const node bidirectional iterator.
IndexedList(const IndexedList &other)
Copy constructor.
Doubly-linked list with constant-time indexing.
const Value * operator->() const
Accessor for user-defined value.
Value & frontValue()
First element of list.
List value bidirectional iterator.
const Value & operator*() const
Accessor for user-defined value.
IndexedList(size_t nElmts, const Value &val=Value(), const Allocator &allocator=Allocator())
Filling constructor.
Value & operator*()
Accessor for user-defined value.
const Node & frontNode() const
First element of list.
Value * operator->()
Accessor for user-defined value.
NodeIterator insert(const ValueIterator &position, const Value &value)
Insert element at position.
const Value & frontValue() const
First element of list.
const size_t & id() const
Unique identification number.
Value & operator[](size_t id)
Element reference by ID.
NodeIterator eraseAt(const ValueIterator &position)
Remove one element.
Optional< Value > getOptional(size_t id) const
Element reference by ID.
ConstNodeIterator find(size_t id) const
Lookup by ID.
Traits for indexed lists.
const Value & backValue() const
Last element of list.
boost::iterator_range< ConstNodeIterator > nodes() const
All elements.
const Value & operator[](size_t id) const
Element reference by ID.
IndexedList & operator=(const IndexedList< T2 > &other)
Assignment from another list.
List node bidirectional iterator.
Combination user-defined value and ID number.
IndexedList & pushFront(const Value &value)
Insert at the front of the list.
const Node & backNode() const
Last element of list.
const Value & value() const
Accessor for user-defined value.