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>
26 typedef typename T::NodeIterator NodeIterator;
27 typedef typename T::ValueIterator ValueIterator;
32 typedef typename T::ConstNodeIterator NodeIterator;
33 typedef typename T::ConstValueIterator ValueIterator;
74template<
class T,
class Alloc = DefaultAllocator>
83 static const size_t NO_ID = (size_t)(-1);
90 ProtoNode *next, *prev;
91 explicit ProtoNode(
size_t id=NO_ID): id(id), next(this), prev(this) {}
92 bool isHead()
const {
return id==NO_ID; }
93 void insert(ProtoNode &newNode) {
94 ASSERT_forbid(newNode.isHead());
95 ASSERT_require(newNode.next==&newNode);
96 ASSERT_require(newNode.prev==&newNode);
97 prev->next = &newNode;
103 ASSERT_forbid(isHead());
108 Node& dereference() {
109 ASSERT_forbid(isHead());
110 Node *node = (Node*)
this;
111 ASSERT_require(&node->linkage_ ==
this);
114 const Node& dereference()
const {
115 ASSERT_forbid(isHead());
116 const Node *node = (
const Node*)
this;
117 ASSERT_require(&node->linkage_ ==
this);
132 Node(
size_t id,
const Value &
value): linkage_(
id), value_(
value) { ASSERT_forbid(linkage_.isHead()); }
140 const size_t&
id()
const {
return linkage_.id; }
161 template<
class Derived,
class Value,
class BaseIterator>
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&;
173 IteratorBase() { base_ = NULL; }
174 IteratorBase(
const IteratorBase &other): base_(other.base_) {}
175 IteratorBase(
const BaseIterator &base): base_(base) {}
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(); }
186 Derived* derived() {
return static_cast<Derived*
>(
this); }
187 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
189 const BaseIterator& base()
const {
return base_; }
207 class NodeIterator:
public IteratorBase<NodeIterator, Node, ProtoNode*> {
208 typedef IteratorBase<NodeIterator, Node, ProtoNode*> Super;
213 Node& operator*()
const {
return this->base_->dereference(); }
214 Node* operator->()
const {
return &this->base_->dereference(); }
236 typedef IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> Super;
242 const Node& operator*()
const {
return this->base_->dereference(); }
243 const Node* operator->()
const {
return &this->base_->dereference(); }
260 class ValueIterator:
public IteratorBase<ValueIterator, Value, ProtoNode*> {
261 typedef IteratorBase<ValueIterator, Value, ProtoNode*> Super;
267 Value& operator*()
const {
return this->base()->dereference().value(); }
268 Value* operator->()
const {
return &this->base()->dereference().value(); }
286 typedef IteratorBase<ConstValueIterator, const Value, const ProtoNode*> Super;
294 const Value& operator*()
const {
return this->base()->dereference().value(); }
295 const Value* operator->()
const {
return &this->base()->dereference().value(); }
305 typedef std::vector<Node*> Index;
311#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
313 friend class boost::serialization::access;
316 void save(S &s,
const unsigned )
const {
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);
329 void load(S &s,
const unsigned ) {
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) {
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());
341 ASSERT_require(
id < index_.size());
342 ASSERT_require(index_[
id] == NULL);
345 head_->insert(node->linkage_);
349 BOOST_SERIALIZATION_SPLIT_MEMBER();
352#ifdef SAWYER_HAVE_CEREAL
354 friend class cereal::access;
356 template<
class Archive>
357 void CEREAL_SAVE_FUNCTION_NAME(Archive &archive)
const {
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));
369 template<
class Archive>
370 void CEREAL_LOAD_FUNCTION_NAME(Archive &archive) {
373 archive(CEREAL_NVP(n));
374 ASSERT_require(index_.empty());
375 index_.resize(n, NULL);
376 for (
size_t i = 0; i < n; ++i) {
378 archive(CEREAL_NVP(
id));
379 Node *node =
new (allocator_.allocate(
sizeof(Node))) Node(
id,
Value());
380 archive(cereal::make_nvp(
"value", node->value()));
382 ASSERT_require(
id < index_.size());
383 ASSERT_require(index_[
id] == NULL);
386 head_->insert(node->linkage_);
401 : allocator_(
allocator), head_(new ProtoNode) {}
413 template<
class T2,
class Alloc2>
415 : allocator_(
Allocator()), head_(new ProtoNode) {
417 for (OtherIter otherIter=other.
values().begin(); otherIter!=other.
values().end(); ++otherIter)
425 : allocator_(
allocator), head_(new ProtoNode) {
426 index_.reserve(nElmts);
427 for (
size_t i=0; i<nElmts; ++i)
474 boost::iterator_range<NodeIterator>
nodes() {
477 boost::iterator_range<ConstNodeIterator>
nodes()
const {
480 boost::iterator_range<ValueIterator>
values() {
483 boost::iterator_range<ConstValueIterator>
values()
const {
489 bool isLocalIterator(
const ConstValueIterator &iter)
const {
490 const ProtoNode *pn = iter.base();
494 const Node *node = &pn->dereference();
495 size_t id = node->id();
496 return id<index_.size() && node==index_[id];
509 return index_.empty();
516 return index_.size();
527 return index_.capacity();
547 ASSERT_require(
id < index_.size());
548 ASSERT_not_null(index_[
id]);
552 ASSERT_require(
id < index_.size());
553 ASSERT_not_null(index_[
id]);
571 return head_->next->dereference();
575 return head_->next->dereference();
592 return head_->prev->dereference();
596 return head_->prev->dereference();
613 ASSERT_require(
id <
size());
614 ASSERT_not_null(index_[
id]);
618 ASSERT_require(
id <
size());
619 ASSERT_not_null(index_[
id]);
647 static const Value dflt;
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_);
693 for (
size_t i=0; i<nElmts; ++i)
704 template<
class OtherValueIterator>
706 for (OtherValueIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
716 for (
size_t i=0; i<index_.size(); ++i) {
718 allocator_.deallocate((
void*)index_[i],
sizeof(
Node));
721 head_->next = head_->prev = head_;
728 ASSERT_require(
id <
size());
737 ASSERT_require(isLocalIterator(position));
738 ProtoNode *pos = position.base();
739 ProtoNode *next = pos->next;
742 if (
id + 1 < index_.size()) {
743 std::swap(index_.back(), index_[
id]);
744 index_[id]->linkage_.id = id;
746 index_.back()->~Node();
747 allocator_.deallocate(index_.back(),
sizeof(
Node));
753 NodeIterator eraseAtMultiple(
const boost::iterator_range<NodeIterator> &range) {
754 boost::iterator_range<ValueIterator> valueRange(range.begin(), range.end());
755 return eraseAtMultiple(valueRange);
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());
765 void dump(std::ostream &o)
const {
766 o <<
"list contents:\n"
768 for (
size_t i=0; i<index_.size(); ++i)
769 o <<
" [" <<i <<
"]=" <<index_[i] <<
"\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);
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.
IndexedList & operator=(const IndexedList< T2 > &other)
Assignment from another list.
Alloc Allocator
Allocator for the storage nodes.
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.
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.
Id id(const std::string &name)
Returns the ID for an attribute name.
Traits for indexed lists.