ROSE  0.9.9.139
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://github.com/matzke1/sawyer.
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 <boost/serialization/access.hpp>
18 #include <boost/serialization/nvp.hpp>
19 #include <boost/serialization/split_member.hpp>
20 #include <iterator>
21 #include <vector>
22 
23 namespace Sawyer {
24 namespace Container {
25 
27 template<class T>
29  typedef typename T::NodeIterator NodeIterator;
30  typedef typename T::ValueIterator ValueIterator;
31 };
32 
33 template<class T>
34 struct IndexedListTraits<const T> {
35  typedef typename T::ConstNodeIterator NodeIterator;
36  typedef typename T::ConstValueIterator ValueIterator;
37 };
38 
77 template<class T, class Alloc = DefaultAllocator>
78 class IndexedList {
79 public:
80  typedef T Value;
81  typedef Alloc Allocator;
82  class Node;
84 private:
85 
86  static const size_t NO_ID = (size_t)(-1);
87 
88 
89  // Forms a circular list. ProtoNode is the first part of a Node so that we can static_cast from ProtoNode to Node.
90  class ProtoNode {
91  public:
92  size_t id; // Unique, small, contiguous ID numbers
93  ProtoNode *next, *prev; // Linkage to neighoring nodes
94  explicit ProtoNode(size_t id=NO_ID): id(id), next(this), prev(this) {}
95  bool isHead() const { return id==NO_ID; } // implies no Node memory is attached; don't static_cast to Node!
96  void insert(ProtoNode &newNode) { // insert newNode before this node
97  ASSERT_forbid(newNode.isHead());
98  ASSERT_require(newNode.next==&newNode);
99  ASSERT_require(newNode.prev==&newNode);
100  prev->next = &newNode;
101  newNode.prev = prev;
102  prev = &newNode;
103  newNode.next = this;
104  }
105  void remove() { // remove this node from the list
106  ASSERT_forbid(isHead());
107  prev->next = next;
108  next->prev = prev;
109  next = prev = this;
110  }
111  Node& dereference() {
112  ASSERT_forbid(isHead());
113  Node *node = (Node*)this; // ProtoNode must be first data member of Node
114  ASSERT_require(&node->linkage_ == this); // it wasn't first
115  return *node;
116  }
117  const Node& dereference() const {
118  ASSERT_forbid(isHead());
119  const Node *node = (const Node*)this; // ProtoNode must be first data member of Node
120  ASSERT_require(&node->linkage_ == this); // it wasn't first
121  return *node;
122  }
123  };
124 
125 public:
130  class Node {
131  ProtoNode linkage_; // This member MUST BE FIRST so ProtoNode::dereference works
132  Value value_; // User-supplied data for each node
133  private:
134  friend class IndexedList;
135  Node(size_t id, const Value &value): linkage_(id), value_(value) { ASSERT_forbid(linkage_.isHead()); }
136  public:
143  const size_t& id() const { return linkage_.id; }
144 
151  Value& value() { return value_; }
152  const Value& value() const { return value_; }
153  Value& operator*() { return value_; }
154  const Value& operator*() const { return value_; }
155  Value* operator->() { return &value_; }
156  const Value* operator->() const { return &value_; }
158  };
159 
161  // Iterators
163 private:
164  template<class Derived, class Value, class BaseIterator>
165  class IteratorBase: public std::iterator<std::bidirectional_iterator_tag, Value> {
166  protected:
167  BaseIterator base_;
168  IteratorBase() { base_ = NULL; }
169  IteratorBase(const IteratorBase &other): base_(other.base_) {}
170  IteratorBase(const BaseIterator &base): base_(base) {}
171  public:
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(); }
179  bool operator<(const IteratorBase &other) const { return base_ < other.base_; }
180  protected:
181  Derived* derived() { return static_cast<Derived*>(this); }
182  const Derived* derived() const { return static_cast<const Derived*>(this); }
183  public:
184  const BaseIterator& base() const { return base_; }
185  };
186 
187 public:
202  class NodeIterator: public IteratorBase<NodeIterator, Node, ProtoNode*> {
203  typedef IteratorBase<NodeIterator, Node, ProtoNode*> Super;
204  public:
205  NodeIterator() {}
206  NodeIterator(const NodeIterator &other): Super(other) {}
207  Node& operator*() const { return this->base_->dereference(); }
208  Node* operator->() const { return &this->base_->dereference(); }
209  private:
210  friend class IndexedList;
211  NodeIterator(ProtoNode *base): Super(base) {}
212  NodeIterator(Node *node): Super(&node->linkage_) {}
213  };
214 
229  class ConstNodeIterator: public IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> {
230  typedef IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> Super;
231  public:
232  ConstNodeIterator() {}
233  ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
234  ConstNodeIterator(const NodeIterator &other): Super(other.base()) {}
235  const Node& operator*() const { return this->base_->dereference(); }
236  const Node* operator->() const { return &this->base_->dereference(); }
237  private:
238  friend class IndexedList;
239  ConstNodeIterator(const ProtoNode *base): Super(base) {}
240  ConstNodeIterator(const Node *node): Super(&node->linkage_) {}
241  };
242 
253  class ValueIterator: public IteratorBase<ValueIterator, Value, ProtoNode*> {
254  typedef IteratorBase<ValueIterator, Value, ProtoNode*> Super;
255  public:
256  ValueIterator() {}
257  ValueIterator(const ValueIterator &other): Super(other) {}
258  ValueIterator(const NodeIterator &other): Super(other.base()) {}
259  Value& operator*() const { return this->base()->dereference().value(); }
260  Value* operator->() const { return &this->base()->dereference().value(); }
261  private:
262  friend class IndexedList;
263  ValueIterator(ProtoNode *base): Super(base) {}
264  ValueIterator(Node *node): Super(&node->linkage_) {}
265  };
266 
277  class ConstValueIterator: public IteratorBase<ConstValueIterator, const Value, const ProtoNode*> {
278  typedef IteratorBase<ConstValueIterator, const Value, const ProtoNode*> Super;
279  public:
280  ConstValueIterator() {}
281  ConstValueIterator(const ConstValueIterator &other): Super(other) {}
282  ConstValueIterator(const NodeIterator &other): Super(other.base()) {}
283  ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
284  ConstValueIterator(const ValueIterator &other): Super(other.base()) {}
285  const Value& operator*() const { return this->base()->dereference().value(); }
286  const Value* operator->() const { return &this->base()->dereference().value(); }
287  private:
288  friend class IndexedList;
289  ConstValueIterator(const ProtoNode *base): Super(base) {}
290  ConstValueIterator(const Node *node): Super(&node->linkage_) {}
291  };
294 private:
295  Allocator allocator_; // provided allocator for list nodes
296  ProtoNode *head_; // always point to a list head, not a true node (normal allocator)
297  typedef std::vector<Node*> Index; // allocated with provided allocator
298  Index index_; // allocated with normal allocator
299 
301  // Serialization
303 private:
304  friend class boost::serialization::access;
305 
306  template<class S>
307  void save(S &s, const unsigned /*version*/) const {
308  size_t n = size();
309  s <<BOOST_SERIALIZATION_NVP(n);
310  for (const ProtoNode *pnode = head_->next; pnode != head_; pnode = pnode->next) {
311  ASSERT_require(n-- > 0);
312  size_t id = pnode->dereference().id();
313  const Value &value = pnode->dereference().value();
314  s <<BOOST_SERIALIZATION_NVP(id);
315  s <<BOOST_SERIALIZATION_NVP(value);
316  }
317  }
318 
319  template<class S>
320  void load(S &s, const unsigned /*version*/) {
321  clear();
322  size_t n = 0;
323  s >>BOOST_SERIALIZATION_NVP(n);
324  ASSERT_require(index_.empty());
325  index_.resize(n, NULL);
326  for (size_t i=0; i<n; ++i) {
327  size_t id = 0;
328  s >>BOOST_SERIALIZATION_NVP(id);
329  Node *node = new (allocator_.allocate(sizeof(Node))) Node(id, Value());
330  s >>boost::serialization::make_nvp("value", node->value());
331 
332  ASSERT_require(id < index_.size());
333  ASSERT_require(index_[id] == NULL);
334  index_[id] = node;
335 
336  head_->insert(node->linkage_); // append to end of node list
337  }
338  }
339 
340  BOOST_SERIALIZATION_SPLIT_MEMBER();
341 
342 
344  // Initialization
346 public:
347 
351  explicit IndexedList(const Allocator &allocator = Allocator())
352  : allocator_(allocator), head_(new ProtoNode) {}
353 
358  IndexedList(const IndexedList &other): allocator_(other.allocator_), head_(new ProtoNode) {
359  for (ConstValueIterator otherIter=other.values().begin(); otherIter!=other.values().end(); ++otherIter)
360  pushBack(*otherIter);
361  }
362 
364  template<class T2, class Alloc2>
365  IndexedList(const IndexedList<T2, Alloc2> &other, const Allocator &/*allocator*/ = Allocator())
366  : allocator_(Allocator()), head_(new ProtoNode) {
367  typedef typename IndexedList<T2>::ConstValueIterator OtherIter;
368  for (OtherIter otherIter=other.values().begin(); otherIter!=other.values().end(); ++otherIter)
369  pushBack(Value(*otherIter));
370  }
371 
375  explicit IndexedList(size_t nElmts, const Value &val = Value(), const Allocator &allocator = Allocator())
376  : allocator_(allocator), head_(new ProtoNode) {
377  index_.reserve(nElmts);
378  for (size_t i=0; i<nElmts; ++i)
379  pushBack(val);
380  }
381 
387  clear();
388  insertMultiple(nodes().begin(), other.values());
389  return *this;
390  }
391 
396  template<class T2>
398  clear();
399  insert(nodes().begin(), other.values());
400  return *this;
401  }
402 
403  ~IndexedList() {
404  clear();
405  delete head_;
406  }
407 
411  const Allocator& allocator() const {
412  return allocator_;
413  }
414 
416  // Iteration
418 public:
419 
425  boost::iterator_range<NodeIterator> nodes() {
426  return boost::iterator_range<NodeIterator>(NodeIterator(head_->next), NodeIterator(head_));
427  }
428  boost::iterator_range<ConstNodeIterator> nodes() const {
429  return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(head_->next), ConstNodeIterator(head_));
430  }
431  boost::iterator_range<ValueIterator> values() {
432  return boost::iterator_range<ValueIterator>(ValueIterator(head_->next), ValueIterator(head_));
433  }
434  boost::iterator_range<ConstValueIterator> values() const {
435  return boost::iterator_range<ConstValueIterator>(ConstValueIterator(head_->next), ConstValueIterator(head_));
436  }
439 private:
440  bool isLocalIterator(const ConstValueIterator &iter) const {
441  const ProtoNode *pn = iter.base();
442  ASSERT_not_null(pn);
443  if (pn == head_)
444  return true; // local end iterator
445  const Node *node = &pn->dereference();
446  size_t id = node->id();
447  return id<index_.size() && node==index_[id];
448  }
449 
450 
452  // Size and capacity
454 public:
455 
459  bool isEmpty() const {
460  return index_.empty();
461  }
462 
466  size_t size() const {
467  return index_.size();
468  }
469 
477  size_t capacity() const {
478  return index_.capacity();
479  }
480  void capacity(size_t n) {
481  index_.reserve(n);
482  }
486  // Searching
489 public:
490 
497  NodeIterator find(size_t id) {
498  ASSERT_require(id < index_.size());
499  ASSERT_not_null(index_[id]);
500  return NodeIterator(index_[id]);
501  }
502  ConstNodeIterator find(size_t id) const {
503  ASSERT_require(id < index_.size());
504  ASSERT_not_null(index_[id]);
505  return ConstNodeIterator(index_[id]);
506  }
510  // Accessors
513 public:
514 
520  Node& frontNode() {
521  ASSERT_forbid(isEmpty());
522  return head_->next->dereference();
523  }
524  const Node& frontNode() const {
525  ASSERT_forbid(isEmpty());
526  return head_->next->dereference();
527  }
528  Value& frontValue() {
529  return frontNode().value();
530  }
531  const Value& frontValue() const {
532  return frontNode().value();
533  }
541  Node& backNode() {
542  ASSERT_forbid(isEmpty());
543  return head_->prev->dereference();
544  }
545  const Node& backNode() const {
546  ASSERT_forbid(isEmpty());
547  return head_->prev->dereference();
548  }
549  Value& backValue() {
550  return backNode().value();
551  }
552  const Value& backValue() const {
553  return backNode().value();
554  }
563  Node& indexedNode(size_t id) {
564  ASSERT_require(id < size());
565  ASSERT_not_null(index_[id]);
566  return *index_[id];
567  }
568  const Node& indexedNode(size_t id) const {
569  ASSERT_require(id < size());
570  ASSERT_not_null(index_[id]);
571  return *index_[id];
572  }
573  Value& indexedValue(size_t id) {
574  return indexedNode(id).value();
575  }
576  const Value& indexedValue(size_t id) const {
577  return indexedNode(id).value();
578  }
579  Value& operator[](size_t id) {
580  return indexedValue(id);
581  }
582  const Value& operator[](size_t id) const {
583  return indexedValue(id);
584  }
585 
586  Optional<Value> getOptional(size_t id) const {
587  return id < size() ? Optional<Value>(indexedValue(id)) : Optional<Value>();
588  }
589 
590  Value& getOrElse(size_t id, Value &dflt) {
591  return id < size() ? indexedValue(id) : dflt;
592  }
593  const Value& getOrElse(size_t id, const Value &dflt) const {
594  return id < size() ? indexedValue(id) : dflt;
595  }
596 
597  const Value& getOrDefault(size_t id) const {
598  static const Value dflt;
599  return id < size() ? indexedValue(id) : dflt;
600  }
603  // Mutators
606 public:
607 
612  IndexedList& pushFront(const Value &value) {
613  insert(nodes().begin(), value);
614  return *this;
615  }
616 
621  IndexedList& pushBack(const Value &value) {
622  insert(nodes().end(), value);
623  return *this;
624  }
625 
630  NodeIterator insert(const ValueIterator &position, const Value &value) {
631  ProtoNode *pos = position.base();
632  Node *node = new (allocator_.allocate(sizeof(Node))) Node(index_.size(), value);
633  index_.push_back(node);
634  pos->insert(node->linkage_);
635  return NodeIterator(node);
636  }
637 
643  IndexedList& insert(const ValueIterator &position, size_t nElmts, const Value &value) {
644  for (size_t i=0; i<nElmts; ++i)
645  insert(position, value);
646  return *this;
647  }
648 
655  template<class OtherValueIterator>
656  IndexedList& insertMultiple(const ValueIterator &position, const boost::iterator_range<OtherValueIterator> &range) {
657  for (OtherValueIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
658  insert(position, Value(*otherIter));
659  return *this;
660  }
661 
662 
666  void clear() {
667  for (size_t i=0; i<index_.size(); ++i) {
668  index_[i]->~Node();
669  allocator_.deallocate((void*)index_[i], sizeof(Node));
670  }
671  index_.clear();
672  head_->next = head_->prev = head_;
673  }
674 
678  NodeIterator erase(size_t id) {
679  ASSERT_require(id < size());
680  return eraseAt(find(id));
681  }
682 
687  NodeIterator eraseAt(const ValueIterator &position) {
688  ASSERT_require(isLocalIterator(position));
689  ProtoNode *pos = position.base();
690  ProtoNode *next = pos->next; // to build the return value
691  pos->remove(); // remove node from the doubly linked list w/out deleting
692  size_t id = pos->id;
693  if (id + 1 < index_.size()) {
694  std::swap(index_.back(), index_[id]);
695  index_[id]->linkage_.id = id;
696  }
697  index_.back()->~Node();
698  allocator_.deallocate(index_.back(), sizeof(Node));
699  index_.pop_back();
700  return NodeIterator(next);
701  }
702 
703  // range must be a range within this container
704  NodeIterator eraseAtMultiple(const boost::iterator_range<NodeIterator> &range) {
705  boost::iterator_range<ValueIterator> valueRange(range.begin(), range.end());
706  return eraseAtMultiple(valueRange);
707  }
708  NodeIterator eraseAtMultiple(const boost::iterator_range<ValueIterator> &range) {
709  ValueIterator otherIter = range.begin();
710  while (otherIter!=range.end())
711  otherIter = eraseAt(otherIter);
712  return NodeIterator(range.end().base());
713  }
714 
715  // debugging
716  void dump(std::ostream &o) const {
717  o <<"list contents:\n"
718  <<" index:\n";
719  for (size_t i=0; i<index_.size(); ++i)
720  o <<" [" <<i <<"]=" <<index_[i] <<"\n";
721  o <<" list:\n";
722  ProtoNode *pn = head_;
723  for (size_t i=0; i<index_.size()+1; ++i, pn=pn->next) {
724  o <<" " <<pn <<"\t" <<pn->next <<"\t" <<pn->prev <<"\t" <<pn->id <<"\n";
725  ASSERT_require(pn->isHead() || index_[pn->id]==&pn->dereference());
726  ASSERT_require(pn->next->prev == pn);
727  ASSERT_require(pn->prev->next == pn);
728  }
729  }
730 };
731 
732 } // namespace
733 } // namespace
734 
735 #endif
size_t size() const
Number of elements in list.
Definition: IndexedList.h:466
T Value
Type of values stored in this container.
Definition: IndexedList.h:80
const Node & indexedNode(size_t id) const
Element reference by ID.
Definition: IndexedList.h:568
Node & backNode()
Last element of list.
Definition: IndexedList.h:541
IndexedList(const Allocator &allocator=Allocator())
Default constructor.
Definition: IndexedList.h:351
size_t capacity() const
Allocated capacity of the index.
Definition: IndexedList.h:477
bool isEmpty() const
Determines if this list is empty.
Definition: IndexedList.h:459
IndexedList & operator=(const IndexedList &other)
Assignment from another list.
Definition: IndexedList.h:386
Node & indexedNode(size_t id)
Element reference by ID.
Definition: IndexedList.h:563
Value & backValue()
Last element of list.
Definition: IndexedList.h:549
boost::iterator_range< ConstValueIterator > values() const
All elements.
Definition: IndexedList.h:434
const Value & indexedValue(size_t id) const
Element reference by ID.
Definition: IndexedList.h:576
IndexedList & insertMultiple(const ValueIterator &position, const boost::iterator_range< OtherValueIterator > &range)
Insert elements at position.
Definition: IndexedList.h:656
boost::iterator_range< ValueIterator > values()
All elements.
Definition: IndexedList.h:431
Value & getOrElse(size_t id, Value &dflt)
Element reference by ID.
Definition: IndexedList.h:590
Alloc Allocator
Allocator for the storage nodes.
Definition: IndexedList.h:81
NodeIterator erase(size_t id)
Erase one element.
Definition: IndexedList.h:678
List const value bidirectional iterator.
Definition: IndexedList.h:277
Value & value()
Accessor for user-defined value.
Definition: IndexedList.h:151
IndexedList & insert(const ValueIterator &position, size_t nElmts, const Value &value)
Insert multiple copies at position.
Definition: IndexedList.h:643
Value & indexedValue(size_t id)
Element reference by ID.
Definition: IndexedList.h:573
const Value & getOrDefault(size_t id) const
Element reference by ID.
Definition: IndexedList.h:597
Node & frontNode()
First element of list.
Definition: IndexedList.h:520
const Allocator & allocator() const
Allocator.
Definition: IndexedList.h:411
Name space for the entire library.
Definition: Access.h:11
boost::iterator_range< NodeIterator > nodes()
All elements.
Definition: IndexedList.h:425
NodeIterator find(size_t id)
Lookup by ID.
Definition: IndexedList.h:497
const Value & getOrElse(size_t id, const Value &dflt) const
Element reference by ID.
Definition: IndexedList.h:593
void clear()
Empties the list.
Definition: IndexedList.h:666
void capacity(size_t n)
Allocated capacity of the index.
Definition: IndexedList.h:480
IndexedList & pushBack(const Value &value)
Insert at the back of the list.
Definition: IndexedList.h:621
IndexedList(const IndexedList< T2, Alloc2 > &other, const Allocator &=Allocator())
Copy constructor.
Definition: IndexedList.h:365
List const node bidirectional iterator.
Definition: IndexedList.h:229
IndexedList(const IndexedList &other)
Copy constructor.
Definition: IndexedList.h:358
Doubly-linked list with constant-time indexing.
Definition: IndexedList.h:78
const Value * operator->() const
Accessor for user-defined value.
Definition: IndexedList.h:156
Value & frontValue()
First element of list.
Definition: IndexedList.h:528
List value bidirectional iterator.
Definition: IndexedList.h:253
const Value & operator*() const
Accessor for user-defined value.
Definition: IndexedList.h:154
IndexedList(size_t nElmts, const Value &val=Value(), const Allocator &allocator=Allocator())
Filling constructor.
Definition: IndexedList.h:375
Value & operator*()
Accessor for user-defined value.
Definition: IndexedList.h:153
const Node & frontNode() const
First element of list.
Definition: IndexedList.h:524
Value * operator->()
Accessor for user-defined value.
Definition: IndexedList.h:155
NodeIterator insert(const ValueIterator &position, const Value &value)
Insert element at position.
Definition: IndexedList.h:630
const Value & frontValue() const
First element of list.
Definition: IndexedList.h:531
const size_t & id() const
Unique identification number.
Definition: IndexedList.h:143
Value & operator[](size_t id)
Element reference by ID.
Definition: IndexedList.h:579
NodeIterator eraseAt(const ValueIterator &position)
Remove one element.
Definition: IndexedList.h:687
Optional< Value > getOptional(size_t id) const
Element reference by ID.
Definition: IndexedList.h:586
ConstNodeIterator find(size_t id) const
Lookup by ID.
Definition: IndexedList.h:502
Traits for indexed lists.
Definition: IndexedList.h:28
const Value & backValue() const
Last element of list.
Definition: IndexedList.h:552
boost::iterator_range< ConstNodeIterator > nodes() const
All elements.
Definition: IndexedList.h:428
const Value & operator[](size_t id) const
Element reference by ID.
Definition: IndexedList.h:582
IndexedList & operator=(const IndexedList< T2 > &other)
Assignment from another list.
Definition: IndexedList.h:397
List node bidirectional iterator.
Definition: IndexedList.h:202
Combination user-defined value and ID number.
Definition: IndexedList.h:130
IndexedList & pushFront(const Value &value)
Insert at the front of the list.
Definition: IndexedList.h:612
const Node & backNode() const
Last element of list.
Definition: IndexedList.h:545
const Value & value() const
Accessor for user-defined value.
Definition: IndexedList.h:152