ROSE  0.11.2.0
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  protected:
180  Derived* derived() { return static_cast<Derived*>(this); }
181  const Derived* derived() const { return static_cast<const Derived*>(this); }
182  public:
183  const BaseIterator& base() const { return base_; }
184  };
185 
186 public:
201  class NodeIterator: public IteratorBase<NodeIterator, Node, ProtoNode*> {
202  typedef IteratorBase<NodeIterator, Node, ProtoNode*> Super;
203  public:
204  NodeIterator() {}
205  NodeIterator(const NodeIterator &other): Super(other) {}
206  Node& operator*() const { return this->base_->dereference(); }
207  Node* operator->() const { return &this->base_->dereference(); }
208  private:
209  friend class IndexedList;
210  NodeIterator(ProtoNode *base): Super(base) {}
211  NodeIterator(Node *node): Super(&node->linkage_) {}
212  };
213 
228  class ConstNodeIterator: public IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> {
229  typedef IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> Super;
230  public:
231  ConstNodeIterator() {}
232  ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
233  ConstNodeIterator(const NodeIterator &other): Super(other.base()) {}
234  const Node& operator*() const { return this->base_->dereference(); }
235  const Node* operator->() const { return &this->base_->dereference(); }
236  private:
237  friend class IndexedList;
238  ConstNodeIterator(const ProtoNode *base): Super(base) {}
239  ConstNodeIterator(const Node *node): Super(&node->linkage_) {}
240  };
241 
252  class ValueIterator: public IteratorBase<ValueIterator, Value, ProtoNode*> {
253  typedef IteratorBase<ValueIterator, Value, ProtoNode*> Super;
254  public:
255  ValueIterator() {}
256  ValueIterator(const ValueIterator &other): Super(other) {}
257  ValueIterator(const NodeIterator &other): Super(other.base()) {}
258  Value& operator*() const { return this->base()->dereference().value(); }
259  Value* operator->() const { return &this->base()->dereference().value(); }
260  private:
261  friend class IndexedList;
262  ValueIterator(ProtoNode *base): Super(base) {}
263  ValueIterator(Node *node): Super(&node->linkage_) {}
264  };
265 
276  class ConstValueIterator: public IteratorBase<ConstValueIterator, const Value, const ProtoNode*> {
277  typedef IteratorBase<ConstValueIterator, const Value, const ProtoNode*> Super;
278  public:
279  ConstValueIterator() {}
280  ConstValueIterator(const ConstValueIterator &other): Super(other) {}
281  ConstValueIterator(const NodeIterator &other): Super(other.base()) {}
282  ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
283  ConstValueIterator(const ValueIterator &other): Super(other.base()) {}
284  const Value& operator*() const { return this->base()->dereference().value(); }
285  const Value* operator->() const { return &this->base()->dereference().value(); }
286  private:
287  friend class IndexedList;
288  ConstValueIterator(const ProtoNode *base): Super(base) {}
289  ConstValueIterator(const Node *node): Super(&node->linkage_) {}
290  };
293 private:
294  Allocator allocator_; // provided allocator for list nodes
295  ProtoNode *head_; // always point to a list head, not a true node (normal allocator)
296  typedef std::vector<Node*> Index; // allocated with provided allocator
297  Index index_; // allocated with normal allocator
298 
300  // Serialization
302 private:
303  friend class boost::serialization::access;
304 
305  template<class S>
306  void save(S &s, const unsigned /*version*/) const {
307  size_t n = size();
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);
315  }
316  }
317 
318  template<class S>
319  void load(S &s, const unsigned /*version*/) {
320  clear();
321  size_t n = 0;
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) {
326  size_t id = 0;
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());
330 
331  ASSERT_require(id < index_.size());
332  ASSERT_require(index_[id] == NULL);
333  index_[id] = node;
334 
335  head_->insert(node->linkage_); // append to end of node list
336  }
337  }
338 
339  BOOST_SERIALIZATION_SPLIT_MEMBER();
340 
341 
343  // Initialization
345 public:
346 
350  explicit IndexedList(const Allocator &allocator = Allocator())
351  : allocator_(allocator), head_(new ProtoNode) {}
352 
357  IndexedList(const IndexedList &other): allocator_(other.allocator_), head_(new ProtoNode) {
358  for (ConstValueIterator otherIter=other.values().begin(); otherIter!=other.values().end(); ++otherIter)
359  pushBack(*otherIter);
360  }
361 
363  template<class T2, class Alloc2>
364  IndexedList(const IndexedList<T2, Alloc2> &other, const Allocator &/*allocator*/ = Allocator())
365  : allocator_(Allocator()), head_(new ProtoNode) {
366  typedef typename IndexedList<T2>::ConstValueIterator OtherIter;
367  for (OtherIter otherIter=other.values().begin(); otherIter!=other.values().end(); ++otherIter)
368  pushBack(Value(*otherIter));
369  }
370 
374  explicit IndexedList(size_t nElmts, const Value &val = Value(), const Allocator &allocator = Allocator())
375  : allocator_(allocator), head_(new ProtoNode) {
376  index_.reserve(nElmts);
377  for (size_t i=0; i<nElmts; ++i)
378  pushBack(val);
379  }
380 
386  clear();
387  insertMultiple(nodes().begin(), other.values());
388  return *this;
389  }
390 
395  template<class T2>
397  clear();
398  insert(nodes().begin(), other.values());
399  return *this;
400  }
401 
402  ~IndexedList() {
403  clear();
404  delete head_;
405  }
406 
410  const Allocator& allocator() const {
411  return allocator_;
412  }
413 
415  // Iteration
417 public:
418 
424  boost::iterator_range<NodeIterator> nodes() {
425  return boost::iterator_range<NodeIterator>(NodeIterator(head_->next), NodeIterator(head_));
426  }
427  boost::iterator_range<ConstNodeIterator> nodes() const {
428  return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(head_->next), ConstNodeIterator(head_));
429  }
430  boost::iterator_range<ValueIterator> values() {
431  return boost::iterator_range<ValueIterator>(ValueIterator(head_->next), ValueIterator(head_));
432  }
433  boost::iterator_range<ConstValueIterator> values() const {
434  return boost::iterator_range<ConstValueIterator>(ConstValueIterator(head_->next), ConstValueIterator(head_));
435  }
438 private:
439  bool isLocalIterator(const ConstValueIterator &iter) const {
440  const ProtoNode *pn = iter.base();
441  ASSERT_not_null(pn);
442  if (pn == head_)
443  return true; // local end iterator
444  const Node *node = &pn->dereference();
445  size_t id = node->id();
446  return id<index_.size() && node==index_[id];
447  }
448 
449 
451  // Size and capacity
453 public:
454 
458  bool isEmpty() const {
459  return index_.empty();
460  }
461 
465  size_t size() const {
466  return index_.size();
467  }
468 
476  size_t capacity() const {
477  return index_.capacity();
478  }
479  void capacity(size_t n) {
480  index_.reserve(n);
481  }
485  // Searching
488 public:
489 
496  NodeIterator find(size_t id) {
497  ASSERT_require(id < index_.size());
498  ASSERT_not_null(index_[id]);
499  return NodeIterator(index_[id]);
500  }
501  ConstNodeIterator find(size_t id) const {
502  ASSERT_require(id < index_.size());
503  ASSERT_not_null(index_[id]);
504  return ConstNodeIterator(index_[id]);
505  }
509  // Accessors
512 public:
513 
519  Node& frontNode() {
520  ASSERT_forbid(isEmpty());
521  return head_->next->dereference();
522  }
523  const Node& frontNode() const {
524  ASSERT_forbid(isEmpty());
525  return head_->next->dereference();
526  }
527  Value& frontValue() {
528  return frontNode().value();
529  }
530  const Value& frontValue() const {
531  return frontNode().value();
532  }
540  Node& backNode() {
541  ASSERT_forbid(isEmpty());
542  return head_->prev->dereference();
543  }
544  const Node& backNode() const {
545  ASSERT_forbid(isEmpty());
546  return head_->prev->dereference();
547  }
548  Value& backValue() {
549  return backNode().value();
550  }
551  const Value& backValue() const {
552  return backNode().value();
553  }
562  Node& indexedNode(size_t id) {
563  ASSERT_require(id < size());
564  ASSERT_not_null(index_[id]);
565  return *index_[id];
566  }
567  const Node& indexedNode(size_t id) const {
568  ASSERT_require(id < size());
569  ASSERT_not_null(index_[id]);
570  return *index_[id];
571  }
572  Value& indexedValue(size_t id) {
573  return indexedNode(id).value();
574  }
575  const Value& indexedValue(size_t id) const {
576  return indexedNode(id).value();
577  }
578  Value& operator[](size_t id) {
579  return indexedValue(id);
580  }
581  const Value& operator[](size_t id) const {
582  return indexedValue(id);
583  }
584 
585  Optional<Value> getOptional(size_t id) const {
586  return id < size() ? Optional<Value>(indexedValue(id)) : Optional<Value>();
587  }
588 
589  Value& getOrElse(size_t id, Value &dflt) {
590  return id < size() ? indexedValue(id) : dflt;
591  }
592  const Value& getOrElse(size_t id, const Value &dflt) const {
593  return id < size() ? indexedValue(id) : dflt;
594  }
595 
596  const Value& getOrDefault(size_t id) const {
597  static const Value dflt;
598  return id < size() ? indexedValue(id) : dflt;
599  }
602  // Mutators
605 public:
606 
611  IndexedList& pushFront(const Value &value) {
612  insert(nodes().begin(), value);
613  return *this;
614  }
615 
620  IndexedList& pushBack(const Value &value) {
621  insert(nodes().end(), value);
622  return *this;
623  }
624 
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);
635  }
636 
642  IndexedList& insert(const ValueIterator &position, size_t nElmts, const Value &value) {
643  for (size_t i=0; i<nElmts; ++i)
644  insert(position, value);
645  return *this;
646  }
647 
654  template<class OtherValueIterator>
655  IndexedList& insertMultiple(const ValueIterator &position, const boost::iterator_range<OtherValueIterator> &range) {
656  for (OtherValueIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
657  insert(position, Value(*otherIter));
658  return *this;
659  }
660 
661 
665  void clear() {
666  for (size_t i=0; i<index_.size(); ++i) {
667  index_[i]->~Node();
668  allocator_.deallocate((void*)index_[i], sizeof(Node));
669  }
670  index_.clear();
671  head_->next = head_->prev = head_;
672  }
673 
677  NodeIterator erase(size_t id) {
678  ASSERT_require(id < size());
679  return eraseAt(find(id));
680  }
681 
686  NodeIterator eraseAt(const ValueIterator &position) {
687  ASSERT_require(isLocalIterator(position));
688  ProtoNode *pos = position.base();
689  ProtoNode *next = pos->next; // to build the return value
690  pos->remove(); // remove node from the doubly linked list w/out deleting
691  size_t id = pos->id;
692  if (id + 1 < index_.size()) {
693  std::swap(index_.back(), index_[id]);
694  index_[id]->linkage_.id = id;
695  }
696  index_.back()->~Node();
697  allocator_.deallocate(index_.back(), sizeof(Node));
698  index_.pop_back();
699  return NodeIterator(next);
700  }
701 
702  // range must be a range within this container
703  NodeIterator eraseAtMultiple(const boost::iterator_range<NodeIterator> &range) {
704  boost::iterator_range<ValueIterator> valueRange(range.begin(), range.end());
705  return eraseAtMultiple(valueRange);
706  }
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());
712  }
713 
714  // debugging
715  void dump(std::ostream &o) const {
716  o <<"list contents:\n"
717  <<" index:\n";
718  for (size_t i=0; i<index_.size(); ++i)
719  o <<" [" <<i <<"]=" <<index_[i] <<"\n";
720  o <<" list:\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);
727  }
728  }
729 };
730 
731 } // namespace
732 } // namespace
733 
734 #endif
size_t size() const
Number of elements in list.
Definition: IndexedList.h:465
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:567
Node & backNode()
Last element of list.
Definition: IndexedList.h:540
IndexedList(const Allocator &allocator=Allocator())
Default constructor.
Definition: IndexedList.h:350
size_t capacity() const
Allocated capacity of the index.
Definition: IndexedList.h:476
bool isEmpty() const
Determines if this list is empty.
Definition: IndexedList.h:458
IndexedList & operator=(const IndexedList &other)
Assignment from another list.
Definition: IndexedList.h:385
Node & indexedNode(size_t id)
Element reference by ID.
Definition: IndexedList.h:562
Value & backValue()
Last element of list.
Definition: IndexedList.h:548
boost::iterator_range< ConstValueIterator > values() const
All elements.
Definition: IndexedList.h:433
const Value & indexedValue(size_t id) const
Element reference by ID.
Definition: IndexedList.h:575
IndexedList & insertMultiple(const ValueIterator &position, const boost::iterator_range< OtherValueIterator > &range)
Insert elements at position.
Definition: IndexedList.h:655
boost::iterator_range< ValueIterator > values()
All elements.
Definition: IndexedList.h:430
Value & getOrElse(size_t id, Value &dflt)
Element reference by ID.
Definition: IndexedList.h:589
Alloc Allocator
Allocator for the storage nodes.
Definition: IndexedList.h:81
NodeIterator erase(size_t id)
Erase one element.
Definition: IndexedList.h:677
List const value bidirectional iterator.
Definition: IndexedList.h:276
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:642
Value & indexedValue(size_t id)
Element reference by ID.
Definition: IndexedList.h:572
const Value & getOrDefault(size_t id) const
Element reference by ID.
Definition: IndexedList.h:596
Node & frontNode()
First element of list.
Definition: IndexedList.h:519
const Allocator & allocator() const
Allocator.
Definition: IndexedList.h:410
Name space for the entire library.
boost::iterator_range< NodeIterator > nodes()
All elements.
Definition: IndexedList.h:424
NodeIterator find(size_t id)
Lookup by ID.
Definition: IndexedList.h:496
const Value & getOrElse(size_t id, const Value &dflt) const
Element reference by ID.
Definition: IndexedList.h:592
void clear()
Empties the list.
Definition: IndexedList.h:665
void capacity(size_t n)
Allocated capacity of the index.
Definition: IndexedList.h:479
IndexedList & pushBack(const Value &value)
Insert at the back of the list.
Definition: IndexedList.h:620
IndexedList(const IndexedList< T2, Alloc2 > &other, const Allocator &=Allocator())
Copy constructor.
Definition: IndexedList.h:364
List const node bidirectional iterator.
Definition: IndexedList.h:228
IndexedList(const IndexedList &other)
Copy constructor.
Definition: IndexedList.h:357
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:527
List value bidirectional iterator.
Definition: IndexedList.h:252
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:374
Value & operator*()
Accessor for user-defined value.
Definition: IndexedList.h:153
const Node & frontNode() const
First element of list.
Definition: IndexedList.h:523
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:629
const Value & frontValue() const
First element of list.
Definition: IndexedList.h:530
const size_t & id() const
Unique identification number.
Definition: IndexedList.h:143
Value & operator[](size_t id)
Element reference by ID.
Definition: IndexedList.h:578
NodeIterator eraseAt(const ValueIterator &position)
Remove one element.
Definition: IndexedList.h:686
Optional< Value > getOptional(size_t id) const
Element reference by ID.
Definition: IndexedList.h:585
ConstNodeIterator find(size_t id) const
Lookup by ID.
Definition: IndexedList.h:501
Traits for indexed lists.
Definition: IndexedList.h:28
const Value & backValue() const
Last element of list.
Definition: IndexedList.h:551
boost::iterator_range< ConstNodeIterator > nodes() const
All elements.
Definition: IndexedList.h:427
const Value & operator[](size_t id) const
Element reference by ID.
Definition: IndexedList.h:581
IndexedList & operator=(const IndexedList< T2 > &other)
Assignment from another list.
Definition: IndexedList.h:396
List node bidirectional iterator.
Definition: IndexedList.h:201
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:611
const Node & backNode() const
Last element of list.
Definition: IndexedList.h:544
const Value & value() const
Accessor for user-defined value.
Definition: IndexedList.h:152