ROSE  0.11.98.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 {
166  public:
167  // Five standard iterator types
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&;
173 
174  protected:
175  BaseIterator base_;
176  IteratorBase() { base_ = NULL; }
177  IteratorBase(const IteratorBase &other): base_(other.base_) {}
178  IteratorBase(const BaseIterator &base): base_(base) {}
179  public:
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(); }
187  protected:
188  Derived* derived() { return static_cast<Derived*>(this); }
189  const Derived* derived() const { return static_cast<const Derived*>(this); }
190  public:
191  const BaseIterator& base() const { return base_; }
192  };
193 
194 public:
209  class NodeIterator: public IteratorBase<NodeIterator, Node, ProtoNode*> {
210  typedef IteratorBase<NodeIterator, Node, ProtoNode*> Super;
211  public:
212  NodeIterator() {}
213  NodeIterator(const NodeIterator &other): Super(other) {}
214  Node& operator*() const { return this->base_->dereference(); }
215  Node* operator->() const { return &this->base_->dereference(); }
216  private:
217  friend class IndexedList;
218  NodeIterator(ProtoNode *base): Super(base) {}
219  NodeIterator(Node *node): Super(&node->linkage_) {}
220  };
221 
236  class ConstNodeIterator: public IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> {
237  typedef IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> Super;
238  public:
239  ConstNodeIterator() {}
240  ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
241  ConstNodeIterator(const NodeIterator &other): Super(other.base()) {}
242  const Node& operator*() const { return this->base_->dereference(); }
243  const Node* operator->() const { return &this->base_->dereference(); }
244  private:
245  friend class IndexedList;
246  ConstNodeIterator(const ProtoNode *base): Super(base) {}
247  ConstNodeIterator(const Node *node): Super(&node->linkage_) {}
248  };
249 
260  class ValueIterator: public IteratorBase<ValueIterator, Value, ProtoNode*> {
261  typedef IteratorBase<ValueIterator, Value, ProtoNode*> Super;
262  public:
263  ValueIterator() {}
264  ValueIterator(const ValueIterator &other): Super(other) {}
265  ValueIterator(const NodeIterator &other): Super(other.base()) {}
266  Value& operator*() const { return this->base()->dereference().value(); }
267  Value* operator->() const { return &this->base()->dereference().value(); }
268  private:
269  friend class IndexedList;
270  ValueIterator(ProtoNode *base): Super(base) {}
271  ValueIterator(Node *node): Super(&node->linkage_) {}
272  };
273 
284  class ConstValueIterator: public IteratorBase<ConstValueIterator, const Value, const ProtoNode*> {
285  typedef IteratorBase<ConstValueIterator, const Value, const ProtoNode*> Super;
286  public:
287  ConstValueIterator() {}
288  ConstValueIterator(const ConstValueIterator &other): Super(other) {}
289  ConstValueIterator(const NodeIterator &other): Super(other.base()) {}
290  ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
291  ConstValueIterator(const ValueIterator &other): Super(other.base()) {}
292  const Value& operator*() const { return this->base()->dereference().value(); }
293  const Value* operator->() const { return &this->base()->dereference().value(); }
294  private:
295  friend class IndexedList;
296  ConstValueIterator(const ProtoNode *base): Super(base) {}
297  ConstValueIterator(const Node *node): Super(&node->linkage_) {}
298  };
301 private:
302  Allocator allocator_; // provided allocator for list nodes
303  ProtoNode *head_; // always point to a list head, not a true node (normal allocator)
304  typedef std::vector<Node*> Index; // allocated with provided allocator
305  Index index_; // allocated with normal allocator
306 
308  // Serialization
310 private:
311  friend class boost::serialization::access;
312 
313  template<class S>
314  void save(S &s, const unsigned /*version*/) const {
315  size_t n = size();
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);
323  }
324  }
325 
326  template<class S>
327  void load(S &s, const unsigned /*version*/) {
328  clear();
329  size_t n = 0;
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) {
334  size_t id = 0;
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());
338 
339  ASSERT_require(id < index_.size());
340  ASSERT_require(index_[id] == NULL);
341  index_[id] = node;
342 
343  head_->insert(node->linkage_); // append to end of node list
344  }
345  }
346 
347  BOOST_SERIALIZATION_SPLIT_MEMBER();
348 
349 
351  // Initialization
353 public:
354 
358  explicit IndexedList(const Allocator &allocator = Allocator())
359  : allocator_(allocator), head_(new ProtoNode) {}
360 
365  IndexedList(const IndexedList &other): allocator_(other.allocator_), head_(new ProtoNode) {
366  for (ConstValueIterator otherIter=other.values().begin(); otherIter!=other.values().end(); ++otherIter)
367  pushBack(*otherIter);
368  }
369 
371  template<class T2, class Alloc2>
372  IndexedList(const IndexedList<T2, Alloc2> &other, const Allocator &/*allocator*/ = Allocator())
373  : allocator_(Allocator()), head_(new ProtoNode) {
374  typedef typename IndexedList<T2>::ConstValueIterator OtherIter;
375  for (OtherIter otherIter=other.values().begin(); otherIter!=other.values().end(); ++otherIter)
376  pushBack(Value(*otherIter));
377  }
378 
382  explicit IndexedList(size_t nElmts, const Value &val = Value(), const Allocator &allocator = Allocator())
383  : allocator_(allocator), head_(new ProtoNode) {
384  index_.reserve(nElmts);
385  for (size_t i=0; i<nElmts; ++i)
386  pushBack(val);
387  }
388 
394  clear();
395  insertMultiple(nodes().begin(), other.values());
396  return *this;
397  }
398 
403  template<class T2>
405  clear();
406  insert(nodes().begin(), other.values());
407  return *this;
408  }
409 
410  ~IndexedList() {
411  clear();
412  delete head_;
413  }
414 
418  const Allocator& allocator() const {
419  return allocator_;
420  }
421 
423  // Iteration
425 public:
426 
432  boost::iterator_range<NodeIterator> nodes() {
433  return boost::iterator_range<NodeIterator>(NodeIterator(head_->next), NodeIterator(head_));
434  }
435  boost::iterator_range<ConstNodeIterator> nodes() const {
436  return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(head_->next), ConstNodeIterator(head_));
437  }
438  boost::iterator_range<ValueIterator> values() {
439  return boost::iterator_range<ValueIterator>(ValueIterator(head_->next), ValueIterator(head_));
440  }
441  boost::iterator_range<ConstValueIterator> values() const {
442  return boost::iterator_range<ConstValueIterator>(ConstValueIterator(head_->next), ConstValueIterator(head_));
443  }
446 private:
447  bool isLocalIterator(const ConstValueIterator &iter) const {
448  const ProtoNode *pn = iter.base();
449  ASSERT_not_null(pn);
450  if (pn == head_)
451  return true; // local end iterator
452  const Node *node = &pn->dereference();
453  size_t id = node->id();
454  return id<index_.size() && node==index_[id];
455  }
456 
457 
459  // Size and capacity
461 public:
462 
466  bool isEmpty() const {
467  return index_.empty();
468  }
469 
473  size_t size() const {
474  return index_.size();
475  }
476 
484  size_t capacity() const {
485  return index_.capacity();
486  }
487  void capacity(size_t n) {
488  index_.reserve(n);
489  }
493  // Searching
496 public:
497 
504  NodeIterator find(size_t id) {
505  ASSERT_require(id < index_.size());
506  ASSERT_not_null(index_[id]);
507  return NodeIterator(index_[id]);
508  }
509  ConstNodeIterator find(size_t id) const {
510  ASSERT_require(id < index_.size());
511  ASSERT_not_null(index_[id]);
512  return ConstNodeIterator(index_[id]);
513  }
517  // Accessors
520 public:
521 
527  Node& frontNode() {
528  ASSERT_forbid(isEmpty());
529  return head_->next->dereference();
530  }
531  const Node& frontNode() const {
532  ASSERT_forbid(isEmpty());
533  return head_->next->dereference();
534  }
535  Value& frontValue() {
536  return frontNode().value();
537  }
538  const Value& frontValue() const {
539  return frontNode().value();
540  }
548  Node& backNode() {
549  ASSERT_forbid(isEmpty());
550  return head_->prev->dereference();
551  }
552  const Node& backNode() const {
553  ASSERT_forbid(isEmpty());
554  return head_->prev->dereference();
555  }
556  Value& backValue() {
557  return backNode().value();
558  }
559  const Value& backValue() const {
560  return backNode().value();
561  }
570  Node& indexedNode(size_t id) {
571  ASSERT_require(id < size());
572  ASSERT_not_null(index_[id]);
573  return *index_[id];
574  }
575  const Node& indexedNode(size_t id) const {
576  ASSERT_require(id < size());
577  ASSERT_not_null(index_[id]);
578  return *index_[id];
579  }
580  Value& indexedValue(size_t id) {
581  return indexedNode(id).value();
582  }
583  const Value& indexedValue(size_t id) const {
584  return indexedNode(id).value();
585  }
586  Value& operator[](size_t id) {
587  return indexedValue(id);
588  }
589  const Value& operator[](size_t id) const {
590  return indexedValue(id);
591  }
592 
593  Optional<Value> getOptional(size_t id) const {
594  return id < size() ? Optional<Value>(indexedValue(id)) : Optional<Value>();
595  }
596 
597  Value& getOrElse(size_t id, Value &dflt) {
598  return id < size() ? indexedValue(id) : dflt;
599  }
600  const Value& getOrElse(size_t id, const Value &dflt) const {
601  return id < size() ? indexedValue(id) : dflt;
602  }
603 
604  const Value& getOrDefault(size_t id) const {
605  static const Value dflt;
606  return id < size() ? indexedValue(id) : dflt;
607  }
610  // Mutators
613 public:
614 
619  IndexedList& pushFront(const Value &value) {
620  insert(nodes().begin(), value);
621  return *this;
622  }
623 
628  IndexedList& pushBack(const Value &value) {
629  insert(nodes().end(), value);
630  return *this;
631  }
632 
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);
643  }
644 
650  IndexedList& insert(const ValueIterator &position, size_t nElmts, const Value &value) {
651  for (size_t i=0; i<nElmts; ++i)
652  insert(position, value);
653  return *this;
654  }
655 
662  template<class OtherValueIterator>
663  IndexedList& insertMultiple(const ValueIterator &position, const boost::iterator_range<OtherValueIterator> &range) {
664  for (OtherValueIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
665  insert(position, Value(*otherIter));
666  return *this;
667  }
668 
669 
673  void clear() {
674  for (size_t i=0; i<index_.size(); ++i) {
675  index_[i]->~Node();
676  allocator_.deallocate((void*)index_[i], sizeof(Node));
677  }
678  index_.clear();
679  head_->next = head_->prev = head_;
680  }
681 
685  NodeIterator erase(size_t id) {
686  ASSERT_require(id < size());
687  return eraseAt(find(id));
688  }
689 
694  NodeIterator eraseAt(const ValueIterator &position) {
695  ASSERT_require(isLocalIterator(position));
696  ProtoNode *pos = position.base();
697  ProtoNode *next = pos->next; // to build the return value
698  pos->remove(); // remove node from the doubly linked list w/out deleting
699  size_t id = pos->id;
700  if (id + 1 < index_.size()) {
701  std::swap(index_.back(), index_[id]);
702  index_[id]->linkage_.id = id;
703  }
704  index_.back()->~Node();
705  allocator_.deallocate(index_.back(), sizeof(Node));
706  index_.pop_back();
707  return NodeIterator(next);
708  }
709 
710  // range must be a range within this container
711  NodeIterator eraseAtMultiple(const boost::iterator_range<NodeIterator> &range) {
712  boost::iterator_range<ValueIterator> valueRange(range.begin(), range.end());
713  return eraseAtMultiple(valueRange);
714  }
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());
720  }
721 
722  // debugging
723  void dump(std::ostream &o) const {
724  o <<"list contents:\n"
725  <<" index:\n";
726  for (size_t i=0; i<index_.size(); ++i)
727  o <<" [" <<i <<"]=" <<index_[i] <<"\n";
728  o <<" list:\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);
735  }
736  }
737 };
738 
739 } // namespace
740 } // namespace
741 
742 #endif
size_t size() const
Number of elements in list.
Definition: IndexedList.h:473
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:575
Node & backNode()
Last element of list.
Definition: IndexedList.h:548
IndexedList(const Allocator &allocator=Allocator())
Default constructor.
Definition: IndexedList.h:358
size_t capacity() const
Allocated capacity of the index.
Definition: IndexedList.h:484
bool isEmpty() const
Determines if this list is empty.
Definition: IndexedList.h:466
IndexedList & operator=(const IndexedList &other)
Assignment from another list.
Definition: IndexedList.h:393
Node & indexedNode(size_t id)
Element reference by ID.
Definition: IndexedList.h:570
Value & backValue()
Last element of list.
Definition: IndexedList.h:556
boost::iterator_range< ConstValueIterator > values() const
All elements.
Definition: IndexedList.h:441
const Value & indexedValue(size_t id) const
Element reference by ID.
Definition: IndexedList.h:583
IndexedList & insertMultiple(const ValueIterator &position, const boost::iterator_range< OtherValueIterator > &range)
Insert elements at position.
Definition: IndexedList.h:663
boost::iterator_range< ValueIterator > values()
All elements.
Definition: IndexedList.h:438
Value & getOrElse(size_t id, Value &dflt)
Element reference by ID.
Definition: IndexedList.h:597
Alloc Allocator
Allocator for the storage nodes.
Definition: IndexedList.h:81
NodeIterator erase(size_t id)
Erase one element.
Definition: IndexedList.h:685
List const value bidirectional iterator.
Definition: IndexedList.h:284
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:650
Value & indexedValue(size_t id)
Element reference by ID.
Definition: IndexedList.h:580
const Value & getOrDefault(size_t id) const
Element reference by ID.
Definition: IndexedList.h:604
Node & frontNode()
First element of list.
Definition: IndexedList.h:527
const Allocator & allocator() const
Allocator.
Definition: IndexedList.h:418
Name space for the entire library.
Definition: FeasiblePath.h:773
boost::iterator_range< NodeIterator > nodes()
All elements.
Definition: IndexedList.h:432
NodeIterator find(size_t id)
Lookup by ID.
Definition: IndexedList.h:504
const Value & getOrElse(size_t id, const Value &dflt) const
Element reference by ID.
Definition: IndexedList.h:600
void clear()
Empties the list.
Definition: IndexedList.h:673
void capacity(size_t n)
Allocated capacity of the index.
Definition: IndexedList.h:487
IndexedList & pushBack(const Value &value)
Insert at the back of the list.
Definition: IndexedList.h:628
IndexedList(const IndexedList< T2, Alloc2 > &other, const Allocator &=Allocator())
Copy constructor.
Definition: IndexedList.h:372
List const node bidirectional iterator.
Definition: IndexedList.h:236
IndexedList(const IndexedList &other)
Copy constructor.
Definition: IndexedList.h:365
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:535
List value bidirectional iterator.
Definition: IndexedList.h:260
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:382
Value & operator*()
Accessor for user-defined value.
Definition: IndexedList.h:153
const Node & frontNode() const
First element of list.
Definition: IndexedList.h:531
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:637
const Value & frontValue() const
First element of list.
Definition: IndexedList.h:538
const size_t & id() const
Unique identification number.
Definition: IndexedList.h:143
Value & operator[](size_t id)
Element reference by ID.
Definition: IndexedList.h:586
NodeIterator eraseAt(const ValueIterator &position)
Remove one element.
Definition: IndexedList.h:694
Optional< Value > getOptional(size_t id) const
Element reference by ID.
Definition: IndexedList.h:593
ConstNodeIterator find(size_t id) const
Lookup by ID.
Definition: IndexedList.h:509
Traits for indexed lists.
Definition: IndexedList.h:28
const Value & backValue() const
Last element of list.
Definition: IndexedList.h:559
boost::iterator_range< ConstNodeIterator > nodes() const
All elements.
Definition: IndexedList.h:435
const Value & operator[](size_t id) const
Element reference by ID.
Definition: IndexedList.h:589
IndexedList & operator=(const IndexedList< T2 > &other)
Assignment from another list.
Definition: IndexedList.h:404
List node bidirectional iterator.
Definition: IndexedList.h:209
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:619
const Node & backNode() const
Last element of list.
Definition: IndexedList.h:552
const Value & value() const
Accessor for user-defined value.
Definition: IndexedList.h:152