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; }
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 bool isAtEnd()
const {
return base_->isHead(); }
181 Derived& operator++() { base_ = base_->next;
return *derived(); }
182 Derived operator++(
int) { Derived old(this->base_); base_ = base_->next;
return old; }
183 Derived& operator--() { base_ = base_->prev;
return *derived(); }
184 Derived operator--(
int) { Derived old(this->base_); base_ = base_->prev;
return old; }
185 template<
class OtherIter>
bool operator==(
const OtherIter &other)
const {
return base_ == other.base(); }
186 template<
class OtherIter>
bool operator!=(
const OtherIter &other)
const {
return base_ != other.base(); }
188 Derived* derived() {
return static_cast<Derived*
>(
this); }
189 const Derived* derived()
const {
return static_cast<const Derived*
>(
this); }
191 const BaseIterator& base()
const {
return base_; }
209 class NodeIterator:
public IteratorBase<NodeIterator, Node, ProtoNode*> {
210 typedef IteratorBase<NodeIterator, Node, ProtoNode*> Super;
214 Node& operator*()
const {
return this->base_->dereference(); }
215 Node* operator->()
const {
return &this->base_->dereference(); }
237 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;
266 Value& operator*()
const {
return this->base()->dereference().value(); }
267 Value* operator->()
const {
return &this->base()->dereference().value(); }
285 typedef IteratorBase<ConstValueIterator, const Value, const ProtoNode*> Super;
292 const Value& operator*()
const {
return this->base()->dereference().value(); }
293 const Value* operator->()
const {
return &this->base()->dereference().value(); }
304 typedef std::vector<Node*> Index;
311 friend class boost::serialization::access;
314 void save(S &s,
const unsigned )
const {
316 s <<BOOST_SERIALIZATION_NVP(n);
317 for (
const ProtoNode *pnode = head_->next; pnode != head_; pnode = pnode->next) {
318 ASSERT_require(n-- > 0);
319 size_t id = pnode->dereference().id();
320 const Value &value = pnode->dereference().value();
321 s <<BOOST_SERIALIZATION_NVP(
id);
322 s <<BOOST_SERIALIZATION_NVP(value);
327 void load(S &s,
const unsigned ) {
330 s >>BOOST_SERIALIZATION_NVP(n);
331 ASSERT_require(index_.empty());
332 index_.resize(n, NULL);
333 for (
size_t i=0; i<n; ++i) {
335 s >>BOOST_SERIALIZATION_NVP(
id);
336 Node *node =
new (allocator_.allocate(
sizeof(Node))) Node(
id,
Value());
337 s >>boost::serialization::make_nvp(
"value", node->value());
339 ASSERT_require(
id < index_.size());
340 ASSERT_require(index_[
id] == NULL);
343 head_->insert(node->linkage_);
347 BOOST_SERIALIZATION_SPLIT_MEMBER();
359 : allocator_(
allocator), head_(new ProtoNode) {}
366 for (ConstValueIterator otherIter=other.
values().begin(); otherIter!=other.
values().end(); ++otherIter)
371 template<
class T2,
class Alloc2>
373 : allocator_(
Allocator()), head_(new ProtoNode) {
375 for (OtherIter otherIter=other.
values().begin(); otherIter!=other.
values().end(); ++otherIter)
383 : allocator_(
allocator), head_(new ProtoNode) {
384 index_.reserve(nElmts);
385 for (
size_t i=0; i<nElmts; ++i)
432 boost::iterator_range<NodeIterator>
nodes() {
433 return boost::iterator_range<NodeIterator>(NodeIterator(head_->next), NodeIterator(head_));
435 boost::iterator_range<ConstNodeIterator>
nodes()
const {
436 return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(head_->next), ConstNodeIterator(head_));
438 boost::iterator_range<ValueIterator>
values() {
439 return boost::iterator_range<ValueIterator>(ValueIterator(head_->next), ValueIterator(head_));
441 boost::iterator_range<ConstValueIterator>
values()
const {
442 return boost::iterator_range<ConstValueIterator>(ConstValueIterator(head_->next), ConstValueIterator(head_));
447 bool isLocalIterator(
const ConstValueIterator &iter)
const {
448 const ProtoNode *pn = iter.base();
452 const Node *node = &pn->dereference();
453 size_t id = node->id();
454 return id<index_.size() && node==index_[id];
467 return index_.empty();
474 return index_.size();
485 return index_.capacity();
505 ASSERT_require(
id < index_.size());
506 ASSERT_not_null(index_[
id]);
507 return NodeIterator(index_[
id]);
509 ConstNodeIterator
find(
size_t id)
const {
510 ASSERT_require(
id < index_.size());
511 ASSERT_not_null(index_[
id]);
512 return ConstNodeIterator(index_[
id]);
529 return head_->next->dereference();
533 return head_->next->dereference();
550 return head_->prev->dereference();
554 return head_->prev->dereference();
571 ASSERT_require(
id <
size());
572 ASSERT_not_null(index_[
id]);
576 ASSERT_require(
id <
size());
577 ASSERT_not_null(index_[
id]);
605 static const Value dflt;
637 NodeIterator
insert(
const ValueIterator &position,
const Value &value) {
638 ProtoNode *pos = position.base();
639 Node *node =
new (allocator_.allocate(
sizeof(Node))) Node(index_.size(), value);
640 index_.push_back(node);
641 pos->insert(node->linkage_);
642 return NodeIterator(node);
651 for (
size_t i=0; i<nElmts; ++i)
662 template<
class OtherValueIterator>
664 for (OtherValueIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
674 for (
size_t i=0; i<index_.size(); ++i) {
676 allocator_.deallocate((
void*)index_[i],
sizeof(Node));
679 head_->next = head_->prev = head_;
686 ASSERT_require(
id <
size());
694 NodeIterator
eraseAt(
const ValueIterator &position) {
695 ASSERT_require(isLocalIterator(position));
696 ProtoNode *pos = position.base();
697 ProtoNode *next = pos->next;
700 if (
id + 1 < index_.size()) {
701 std::swap(index_.back(), index_[
id]);
702 index_[id]->linkage_.id = id;
704 index_.back()->~Node();
705 allocator_.deallocate(index_.back(),
sizeof(Node));
707 return NodeIterator(next);
711 NodeIterator eraseAtMultiple(
const boost::iterator_range<NodeIterator> &range) {
712 boost::iterator_range<ValueIterator> valueRange(range.begin(), range.end());
713 return eraseAtMultiple(valueRange);
715 NodeIterator eraseAtMultiple(
const boost::iterator_range<ValueIterator> &range) {
716 ValueIterator otherIter = range.begin();
717 while (otherIter!=range.end())
718 otherIter =
eraseAt(otherIter);
719 return NodeIterator(range.end().base());
723 void dump(std::ostream &o)
const {
724 o <<
"list contents:\n"
726 for (
size_t i=0; i<index_.size(); ++i)
727 o <<
" [" <<i <<
"]=" <<index_[i] <<
"\n";
729 ProtoNode *pn = head_;
730 for (
size_t i=0; i<index_.size()+1; ++i, pn=pn->next) {
731 o <<
" " <<pn <<
"\t" <<pn->next <<
"\t" <<pn->prev <<
"\t" <<pn->id <<
"\n";
732 ASSERT_require(pn->isHead() || index_[pn->id]==&pn->dereference());
733 ASSERT_require(pn->next->prev == pn);
734 ASSERT_require(pn->prev->next == pn);