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>
165 class IteratorBase:
public std::iterator<std::bidirectional_iterator_tag, Value> {
168 IteratorBase() { base_ = NULL; }
169 IteratorBase(
const IteratorBase &other): base_(other.base_) {}
170 IteratorBase(
const BaseIterator &base): base_(base) {}
172 bool isAtEnd()
const {
return base_->isHead(); }
173 Derived& operator++() { base_ = base_->next;
return *derived(); }
174 Derived operator++(
int) { Derived old(this->base_); base_ = base_->next;
return old; }
175 Derived& operator--() { base_ = base_->prev;
return *derived(); }
176 Derived operator--(
int) { Derived old(this->base_); base_ = base_->prev;
return old; }
177 template<
class OtherIter>
bool operator==(
const OtherIter &other)
const {
return base_ == other.base(); }
178 template<
class OtherIter>
bool operator!=(
const OtherIter &other)
const {
return base_ != other.base(); }
180 Derived* derived() {
return static_cast<Derived*
>(
this); }
181 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
183 const BaseIterator& base()
const {
return base_; }
201 class NodeIterator:
public IteratorBase<NodeIterator, Node, ProtoNode*> {
202 typedef IteratorBase<NodeIterator, Node, ProtoNode*> Super;
206 Node& operator*()
const {
return this->base_->dereference(); }
207 Node* operator->()
const {
return &this->base_->dereference(); }
229 typedef IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> Super;
234 const Node& operator*()
const {
return this->base_->dereference(); }
235 const Node* operator->()
const {
return &this->base_->dereference(); }
252 class ValueIterator:
public IteratorBase<ValueIterator, Value, ProtoNode*> {
253 typedef IteratorBase<ValueIterator, Value, ProtoNode*> Super;
258 Value& operator*()
const {
return this->base()->dereference().value(); }
259 Value* operator->()
const {
return &this->base()->dereference().value(); }
277 typedef IteratorBase<ConstValueIterator, const Value, const ProtoNode*> Super;
284 const Value& operator*()
const {
return this->base()->dereference().value(); }
285 const Value* operator->()
const {
return &this->base()->dereference().value(); }
294 Allocator allocator_;
296 typedef std::vector<Node*> Index;
303 friend class boost::serialization::access;
306 void save(S &s,
const unsigned )
const {
308 s <<BOOST_SERIALIZATION_NVP(n);
309 for (
const ProtoNode *pnode = head_->next; pnode != head_; pnode = pnode->next) {
310 ASSERT_require(n-- > 0);
311 size_t id = pnode->dereference().id();
312 const Value &value = pnode->dereference().value();
313 s <<BOOST_SERIALIZATION_NVP(
id);
314 s <<BOOST_SERIALIZATION_NVP(value);
319 void load(S &s,
const unsigned ) {
322 s >>BOOST_SERIALIZATION_NVP(n);
323 ASSERT_require(index_.empty());
324 index_.resize(n, NULL);
325 for (
size_t i=0; i<n; ++i) {
327 s >>BOOST_SERIALIZATION_NVP(
id);
328 Node *node =
new (allocator_.allocate(
sizeof(Node))) Node(
id,
Value());
329 s >>boost::serialization::make_nvp(
"value", node->value());
331 ASSERT_require(
id < index_.size());
332 ASSERT_require(index_[
id] == NULL);
335 head_->insert(node->linkage_);
339 BOOST_SERIALIZATION_SPLIT_MEMBER();
351 : allocator_(
allocator), head_(new ProtoNode) {}
358 for (ConstValueIterator otherIter=other.
values().begin(); otherIter!=other.
values().end(); ++otherIter)
363 template<
class T2,
class Alloc2>
365 : allocator_(Allocator()), head_(new ProtoNode) {
367 for (OtherIter otherIter=other.
values().begin(); otherIter!=other.
values().end(); ++otherIter)
375 : allocator_(
allocator), head_(new ProtoNode) {
376 index_.reserve(nElmts);
377 for (
size_t i=0; i<nElmts; ++i)
424 boost::iterator_range<NodeIterator>
nodes() {
425 return boost::iterator_range<NodeIterator>(NodeIterator(head_->next), NodeIterator(head_));
427 boost::iterator_range<ConstNodeIterator>
nodes()
const {
428 return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(head_->next), ConstNodeIterator(head_));
430 boost::iterator_range<ValueIterator>
values() {
431 return boost::iterator_range<ValueIterator>(ValueIterator(head_->next), ValueIterator(head_));
433 boost::iterator_range<ConstValueIterator>
values()
const {
434 return boost::iterator_range<ConstValueIterator>(ConstValueIterator(head_->next), ConstValueIterator(head_));
439 bool isLocalIterator(
const ConstValueIterator &iter)
const {
440 const ProtoNode *pn = iter.base();
444 const Node *node = &pn->dereference();
445 size_t id = node->id();
446 return id<index_.size() && node==index_[id];
459 return index_.empty();
466 return index_.size();
477 return index_.capacity();
497 ASSERT_require(
id < index_.size());
498 ASSERT_not_null(index_[
id]);
499 return NodeIterator(index_[
id]);
501 ConstNodeIterator
find(
size_t id)
const {
502 ASSERT_require(
id < index_.size());
503 ASSERT_not_null(index_[
id]);
504 return ConstNodeIterator(index_[
id]);
521 return head_->next->dereference();
525 return head_->next->dereference();
542 return head_->prev->dereference();
546 return head_->prev->dereference();
563 ASSERT_require(
id <
size());
564 ASSERT_not_null(index_[
id]);
568 ASSERT_require(
id <
size());
569 ASSERT_not_null(index_[
id]);
592 const Value&
getOrElse(
size_t id,
const Value &dflt)
const {
597 static const Value dflt;
629 NodeIterator
insert(
const ValueIterator &position,
const Value &value) {
630 ProtoNode *pos = position.base();
631 Node *node =
new (allocator_.allocate(
sizeof(Node))) Node(index_.size(), value);
632 index_.push_back(node);
633 pos->insert(node->linkage_);
634 return NodeIterator(node);
643 for (
size_t i=0; i<nElmts; ++i)
654 template<
class OtherValueIterator>
656 for (OtherValueIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
666 for (
size_t i=0; i<index_.size(); ++i) {
668 allocator_.deallocate((
void*)index_[i],
sizeof(Node));
671 head_->next = head_->prev = head_;
678 ASSERT_require(
id <
size());
686 NodeIterator
eraseAt(
const ValueIterator &position) {
687 ASSERT_require(isLocalIterator(position));
688 ProtoNode *pos = position.base();
689 ProtoNode *next = pos->next;
692 if (
id + 1 < index_.size()) {
693 std::swap(index_.back(), index_[id]);
694 index_[id]->linkage_.id = id;
696 index_.back()->~Node();
697 allocator_.deallocate(index_.back(),
sizeof(Node));
699 return NodeIterator(next);
703 NodeIterator eraseAtMultiple(
const boost::iterator_range<NodeIterator> &range) {
704 boost::iterator_range<ValueIterator> valueRange(range.begin(), range.end());
705 return eraseAtMultiple(valueRange);
707 NodeIterator eraseAtMultiple(
const boost::iterator_range<ValueIterator> &range) {
708 ValueIterator otherIter = range.begin();
709 while (otherIter!=range.end())
710 otherIter =
eraseAt(otherIter);
711 return NodeIterator(range.end().base());
715 void dump(std::ostream &o)
const {
716 o <<
"list contents:\n"
718 for (
size_t i=0; i<index_.size(); ++i)
719 o <<
" [" <<i <<
"]=" <<index_[i] <<
"\n";
721 ProtoNode *pn = head_;
722 for (
size_t i=0; i<index_.size()+1; ++i, pn=pn->next) {
723 o <<
" " <<pn <<
"\t" <<pn->next <<
"\t" <<pn->prev <<
"\t" <<pn->id <<
"\n";
724 ASSERT_require(pn->isHead() || index_[pn->id]==&pn->dereference());
725 ASSERT_require(pn->next->prev == pn);
726 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.