ROSE  0.11.131.0
Tree.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_TreeVertex_H
9 #define Sawyer_TreeVertex_H
10 
11 #include <Sawyer/Assert.h>
12 #include <Sawyer/Exception.h>
13 
14 #include <boost/lexical_cast.hpp>
15 #include <boost/range/adaptor/reversed.hpp>
16 #include <memory>
17 #include <string>
18 #include <vector>
19 
20 namespace Sawyer {
21 
23 namespace Tree {
24 
29 enum class TraversalEvent {
30  ENTER,
31  LEAVE
32 };
33 
109 template<class B>
110 class Vertex: public std::enable_shared_from_this<Vertex<B>> {
111 public:
112 
114  using UserBase = B;
115 
117  using UserBasePtr = std::shared_ptr<UserBase>;
118 
121 
122 public:
123  template<class T> class Edge;
124  template<class T> class EdgeVector;
125 
127  // Errors and exceptions
129 
132  public:
135 
137  Exception(const std::string &mesg, const UserBasePtr &vertex)
138  : Sawyer::Exception::RuntimeError(mesg), vertex(vertex) {}
139 
140  ~Exception() {}
141  };
142 
146  class InsertionError: public Exception {
147  public:
150  : Exception("vertex is already attached to a tree", vertex) {}
151  };
152 
156  class CycleError: public Exception {
157  public:
159  explicit CycleError(const UserBasePtr &vertex)
160  : Exception("insertion of vertex would cause a cycle in the tree", vertex) {}
161  };
162 
164  // Child-to-parent edges
166 
176  class ReverseEdge {
177  private:
178  Vertex &child_; // required child vertex owning this edge
179 
180  // The parent pointer is a raw pointer because it is safe to do so, and because we need to know the pointer before the
181  // parent is fully constructed.
182  //
183  // It is safe (never dangling) because the pointer can only be changed by a forward edge, which is always a member of a
184  // vertex, and the parent pointer is only set to point to that vertex. When the parent is deleted the edge is deleted and
185  // its destructor changes the parent pointer back to null.
186  //
187  // The parent pointer is needed during construction of the parent when the parent has some edge data members that are being
188  // initialized to point to non-null children. This happens during the parent's construction, before the parent has any
189  // shared or weak pointers.
190  UserBase *parent_ = nullptr; // optional parent to which this edge points
191 
192  public:
193  // No default constructor and not copyable.
194  ReverseEdge() = delete;
195  explicit ReverseEdge(const ReverseEdge&) = delete;
196  ReverseEdge& operator=(const ReverseEdge&) = delete;
197 
198  public:
199  ~ReverseEdge(); // internal use only
200  explicit ReverseEdge(Vertex &child); // internal use only
201 
202  public:
206  UserBasePtr operator()() const;
207  UserBasePtr operator->() const;
213  bool operator==(const UserBasePtr&) const;
214  bool operator!=(const UserBasePtr&) const;
215  bool operator==(const ReverseEdge&) const;
216  bool operator!=(const ReverseEdge&) const;
217  template<class T> bool operator==(const Edge<T>&) const;
218  template<class T> bool operator!=(const Edge<T>&) const;
222  explicit operator bool() const {
223  return parent_ != nullptr;
224  }
225 
226  private:
227  // Used internally through ReverseEdgeAccess when a Edge<T> adjusts the ReverseEdge
228  template<class T> friend class Edge;
229  void reset();
230  void set(UserBase &parent);
231  };
232 
234  // Base class for parent-to-child edges
236 private:
237  enum class Link { NO, YES };
238 
239  // Used internally as the non-template abstract base class for all parent-to-child edge types.
240  class EdgeBase {
241  public:
242  // Previous edge in this object, including edges defined in base classes. Edges in this linked list are ordered so that
243  // if edge A was initialized before edge B, then edge A will appear earlier in the list. The "prev" pointers in the list
244  // point backward through the list.
245  EdgeBase *prev;
246 
247  virtual ~EdgeBase() {}
248  EdgeBase() = delete;
249  EdgeBase(const EdgeBase&) = delete;
250  EdgeBase& operator=(const EdgeBase&) = delete;
251  explicit EdgeBase(EdgeBase *prev)
252  : prev(prev) {}
253 
254  // Number of child pointers in this edge. Edges are either 1:1 or 1:N. Some of the child pointers could be null.
255  virtual size_t size() const = 0;
256 
257  // Return the i'th pointer. The argument is expected to be in the domain.
258  virtual Vertex* pointer(size_t i) const = 0;
259 
260  // Traverse through all the non-null children of appropriate type pointed to by all edges in the order that the edges were
261  // initialized. The visitor is invoked with two arguments: a non-null shared pointer to the child, and an indication of
262  // whether this is a pre- or post-order visit. The first visitor call that returns a value that is true in a Boolean context
263  // short circuits the traversal and that value becomes the return value of the traversal.
264  template<class T, class Visitor>
265  auto traverse(Visitor visitor) -> decltype(visitor(std::shared_ptr<T>(), TraversalEvent::ENTER)) {
266  if (prev) {
267  if (auto retval = prev->traverse<T>(visitor))
268  return retval;
269  }
270  for (size_t i = 0; i < size(); ++i) {
271  if (auto child = pointer(i)) {
272  if (auto retval = child->template traverse<T>(visitor))
273  return retval;
274  }
275  }
276  return decltype(visitor(std::shared_ptr<T>(), TraversalEvent::ENTER))();
277  }
278  };
279 
281  // 1:1 parent-to-child edge
283 public:
316  template<class T>
317  class Edge: public EdgeBase {
318  public:
320  using Child = T;
321 
323  using ChildPtr = std::shared_ptr<Child>;
324 
325  private:
326  UserBase &parent_; // required parent owning this child edge
327  ChildPtr child_; // optional child to which this edge points
328 
329  public:
331  ~Edge();
332 
343  explicit Edge(UserBase &parent);
344  Edge(UserBase &parent, const ChildPtr &child);
347  private:
348  template<class U> friend class EdgeVector;
349  // Used internally to initialize an edge without linking it to prior edges
350  Edge(Link, UserBase &parent, const ChildPtr &child);
351 
352  public:
356  const ChildPtr& operator->() const;
357  const ChildPtr& operator()() const;
363  bool operator==(const UserBasePtr&) const;
364  bool operator!=(const UserBasePtr&) const;
365  bool operator==(const ReverseEdge&) const;
366  bool operator!=(const ReverseEdge&) const;
367  template<class U> bool operator==(const Edge<U>&) const;
368  template<class U> bool operator!=(const Edge<U>&) const;
388  if (child != child_) {
389  checkChildInsertion(child);
390 
391  // Unlink the child from the tree
392  if (child_) {
393  child_->parent.reset(); // child-to-parent edge
394  child_.reset(); // parent-to-child edge
395  }
396 
397  // Link new child into the tree
398  if (child) {
399  child->parent.set(parent_);
400  child_ = child;
401  }
402  }
403  return *this;
404  }
405 
407  return (*this) = parent();
408  }
412  explicit operator bool() const {
413  return child_ != nullptr;
414  }
415 
416  private:
417  void checkChildInsertion(const ChildPtr &child) const;
418 
419  size_t size() const override {
420  return 1;
421  }
422 
423  Vertex* pointer(size_t i) const override {
424  ASSERT_always_require(0 == i);
425  return child_.get();
426  }
427  };
428 
430  // 1:N parent-to-child edge
432 public:
436  template<class T>
437  class EdgeVector: public EdgeBase {
438  public:
440  using Child = T;
441 
443  using ChildPtr = std::shared_ptr<Child>;
444 
445  private:
446  using Vector = std::vector<std::unique_ptr<Edge<Child>>>;
447 
448  public:
449  using value_type = Edge<Child>;
450  using size_type = typename Vector::size_type;
451  using difference_type = typename Vector::difference_type;
452  using reference = value_type&;
453  using const_reference = const value_type&;
454 
455  public:
456  template<class BaseIterator>
457  class Iterator {
458  BaseIterator baseIterator_;
459 
460  public:
461  Iterator() = delete;
462  Iterator(const BaseIterator &baseIterator)
463  : baseIterator_(baseIterator) {}
464 
465  Iterator(const Iterator &other)
466  : baseIterator_(other.baseIterator_) {}
467 
468  Iterator& operator=(const Iterator &other) {
469  baseIterator_ = other.baseIterator_;
470  return *this;
471  }
472 
473  Iterator& operator++() {
474  ++baseIterator_;
475  return *this;
476  }
477 
478  Iterator operator++(int) {
479  Iterator temp = *this;
480  ++baseIterator_;
481  return temp;
482  }
483 
484  Iterator& operator--() {
485  --baseIterator_;
486  return *this;
487  }
488 
489  Iterator operator--(int) {
490  Iterator temp = *this;
491  --baseIterator_;
492  return temp;
493  }
494 
495  Iterator& operator+=(difference_type n) {
496  baseIterator_ += n;
497  return *this;
498  }
499 
500  Iterator operator+(difference_type n) const {
501  Iterator retval = *this;
502  retval += n;
503  return retval;
504  }
505 
506  Iterator& operator-=(difference_type n) {
507  baseIterator_ -= n;
508  return *this;
509  }
510 
511  Iterator operator-(difference_type n) const {
512  Iterator retval = *this;
513  retval -= n;
514  return retval;
515  }
516 
517  difference_type operator-(const Iterator &other) const {
518  return other.baseIterator_ - baseIterator_;
519  }
520 
521  auto& operator*() const {
522  ASSERT_not_null(*baseIterator_);
523  return **baseIterator_;
524  }
525 
526  auto& operator->() const {
527  ASSERT_not_null(*baseIterator_);
528  return &**baseIterator_;
529  }
530 
531  auto& operator[](difference_type i) const {
532  ASSERT_not_null(baseIterator_[i]);
533  return *baseIterator_[i];
534  }
535 
536  bool operator==(const Iterator &other) const {
537  return baseIterator_ == other.baseIterator_;
538  }
539 
540  bool operator!=(const Iterator &other) const {
541  return baseIterator_ != other.baseIterator_;
542  }
543 
544  bool operator<(const Iterator &other) const {
545  return baseIterator_ < other.baseIterator_;
546  }
547 
548  bool operator<=(const Iterator &other) const {
549  return baseIterator_ <= other.baseIterator_;
550  }
551 
552  bool operator>(const Iterator &other) const {
553  return baseIterator_ > other.baseIterator_;
554  }
555 
556  bool operator>=(const Iterator &other) const {
557  return baseIterator_ >= other.baseIterator_;
558  }
559  };
560 
561  public:
563 
564  private:
565  UserBase &parent_; // required parent owning this child edge
566  Vector edges_;
567 
568  public:
571 
577  explicit EdgeVector(UserBase &parent);
578 
579  public:
583  bool empty() const {
584  return edges_.empty();
585  }
586 
590  size_t size() const override {
591  return edges_.size();
592  }
593 
595  void reserve(size_t n) {
596  edges_.reserve(n);
597  }
598 
600  size_t capacity() const {
601  return edges_.capacity();
602  }
603 
608  void push_back(const ChildPtr& elmt) {
609  auto edge = std::unique_ptr<Edge<Child>>(new Edge<Child>(Link::NO, parent_, elmt));
610  edges_.push_back(std::move(edge));
611  }
612 
616  void pop_back() {
617  ASSERT_forbid(edges_.empty());
618  edges_.pop_back();
619  }
620 
624  const Edge<Child>& at(size_t i) const {
625  ASSERT_require(i < edges_.size());
626  return *edges_.at(i);
627  }
628  Edge<Child>& at(size_t i) {
629  ASSERT_require(i < edges_.size());
630  return *edges_.at(i);
631  }
632  const Edge<Child>& operator[](size_t i) const {
633  return at(i);
634  }
635  Edge<Child>& operator[](size_t i) {
636  return at(i);
637  }
643  const Edge<Child>& front() const {
644  ASSERT_forbid(empty());
645  return at(0);
646  }
648  ASSERT_forbid(empty());
649  return at(0);
650  }
656  const Edge<Child>& back() const {
657  ASSERT_forbid(empty());
658  return at(size() - 1);
659  }
661  ASSERT_forbid(empty());
662  return at(size() - 1);
663  }
668  return iterator(edges_.begin());
669  }
670 
673  return iterator(edges_.end());
674  }
675 
676  protected:
677  Vertex* pointer(size_t i) const override {
678  return at(i)().get();
679  }
680  };
681 
683  // Vertex
685 public:
690  ReverseEdge parent;
691  EdgeBase *treeEdges_ = nullptr;
692 
693 protected:
694  virtual void destructorHelper() {}
695  Vertex();
696 
697 public:
700 
704  template<class T>
705  std::shared_ptr<T> isa();
706 
738  template<class T, class Visitor>
739  auto traverseReverse(const Visitor &visitor) {
740  auto vertex = std::dynamic_pointer_cast<T>(this->pointer());
741  if (vertex) {
742  if (auto result = visitor(vertex, TraversalEvent::ENTER))
743  return result;
744  }
745 
746  if (parent) {
747  if (auto result = parent()->template traverseReverse<T>(visitor))
748  return result;
749  }
750 
751  if (vertex) {
752  return visitor(vertex, TraversalEvent::LEAVE);
753  } else {
754  return decltype(visitor(vertex, TraversalEvent::ENTER))();
755  }
756  }
757 
766  template<class T, class Visitor>
767  auto traverse(const Visitor &visitor) {
768  auto vertex = std::dynamic_pointer_cast<T>(this->pointer());
769  if (vertex) {
770  if (auto retval = visitor(vertex, TraversalEvent::ENTER))
771  return retval;
772  }
773  if (treeEdges_) {
774  if (auto retval = treeEdges_->template traverse<T>(visitor))
775  return retval;
776  }
777  if (vertex) {
778  return visitor(vertex, TraversalEvent::LEAVE);
779  } else {
780  return decltype(visitor(vertex, TraversalEvent::ENTER))();
781  }
782  }
783 
791  template<class T, class Visitor>
792  auto traversePre(const Visitor &visitor) {
793  return traverse<T>([&visitor] (const std::shared_ptr<T> &vertex, TraversalEvent event) {
794  if (TraversalEvent::ENTER == event) {
795  return visitor(vertex);
796  } else {
797  return decltype(visitor(vertex))();
798  }
799  });
800  }
801 
809  template<class T, class Visitor>
810  auto traversePost(const Visitor &visitor) {
811  return traverse<T>([&visitor] (const std::shared_ptr<T> &vertex, TraversalEvent event) {
812  if (TraversalEvent::LEAVE == event) {
813  return visitor(vertex);
814  } else {
815  return decltype(visitor(vertex))();
816  }
817  });
818  }
819 
821  template<class T>
822  std::shared_ptr<T> findFirstAncestor() {
823  return traverseReverse<T>([](const std::shared_ptr<T> &vertex, TraversalEvent event) {
824  return TraversalEvent::ENTER == event ? vertex : nullptr;
825  });
826  };
827 
829  template<class T>
830  std::shared_ptr<T> findLastAncestor() {
831  return traverseReverse<T>([](const std::shared_ptr<T> &vertex, TraversalEvent event) {
832  return TraversalEvent::LEAVE == event ? vertex : nullptr;
833  });
834  };
835 
840  template<class T>
841  std::vector<std::shared_ptr<T>> findDescendants() {
842  std::vector<std::shared_ptr<T>> retval;
843  traverse<T>([&retval](const std::shared_ptr<T> &vertex, TraversalEvent event) {
844  if (TraversalEvent::ENTER == event)
845  retval.push_back(vertex);
846  });
847  return retval;
848  }
849 
854  UserBasePtr child(size_t i) const;
855 
859  size_t nChildren() const;
860 };
861 
863 // Implementations for ReverseEdge
865 
866 template<class B>
868  ASSERT_require(this->parent_ == nullptr);
869 }
870 
871 template<class B>
873  : child_(child) {}
874 
875 template<class B>
876 typename Vertex<B>::UserBasePtr
878  if (parent_) {
879  return parent_->pointer();
880  } else {
881  return {};
882  }
883 }
884 
885 template<class B>
886 typename Vertex<B>::UserBasePtr
888  ASSERT_not_null(parent_);
889  return parent_->pointer();
890 }
891 
892 template<class B>
893 bool
895  return ptr.get() == parent_;
896 }
897 
898 template<class B>
899 bool
901  return ptr.get() != parent_;
902 }
903 
904 template<class B>
905 bool
907  return parent_ == other.parent_;
908 }
909 
910 template<class B>
911 bool
913  return parent_ != other.parent_;
914 }
915 
916 template<class B>
917 template<class T>
918 bool
920  return parent_ == other();
921 }
922 
923 template<class B>
924 template<class T>
925 bool
927  return parent_ != other();
928 }
929 
930 template<class B>
931 void
933  parent_ = nullptr;
934 }
935 
936 template<class B>
937 void
938 Vertex<B>::ReverseEdge::set(UserBase &parent) {
939  parent_ = &parent;
940 }
941 
943 // Implementations for Edge<T>
945 
946 template<class B>
947 template<class T>
949  if (child_)
950  child_->parent.reset();
951 }
952 
953 template<class B>
954 template<class T>
956  : EdgeBase(parent.treeEdges_), parent_(parent) {
957  parent_.treeEdges_ = this;
958 }
959 
960 template<class B>
961 template<class T>
962 Vertex<B>::Edge<T>::Edge(UserBase &parent, const std::shared_ptr<T> &child)
963  : EdgeBase(parent.treeEdges_), parent_(parent), child_(child) {
964  checkChildInsertion(child);
965  parent_.treeEdges_ = this; // must be after checkChildInsertin for exception safety
966  if (child)
967  child->parent.set(parent);
968 }
969 
970 template<class B>
971 template<class T>
972 Vertex<B>::Edge<T>::Edge(Link link, UserBase &parent, const std::shared_ptr<T> &child)
973  : EdgeBase(Link::YES == link ? parent.treeEdges_ : nullptr), parent_(parent), child_(child) {
974  checkChildInsertion(child);
975  if (Link::YES == link)
976  parent_.treeEdges_ = this; // must be after checkChildInsertin for exception safety
977  if (child)
978  child->parent.set(parent);
979 }
980 
981 template<class B>
982 template<class T>
983 void
984 Vertex<B>::Edge<T>::checkChildInsertion(const std::shared_ptr<T> &child) const {
985  if (child) {
986  if (child->parent)
987  throw InsertionError(child);
988 #ifndef NDEBUG
989  for (const UserBase *p = &parent_; p; p = p->parent().get()) {
990  if (p == child.get())
991  throw CycleError(child);
992  }
993 #endif
994  }
995 }
996 
997 template<class B>
998 template<class T>
999 const std::shared_ptr<T>&
1001  ASSERT_not_null(child_);
1002  return child_;
1003 }
1004 
1005 template<class B>
1006 template<class T>
1007 const std::shared_ptr<T>&
1009  return child_;
1010 }
1011 
1012 template<class B>
1013 template<class T>
1014 bool
1016  return child_ == ptr;
1017 }
1018 
1019 template<class B>
1020 template<class T>
1021 bool
1023  return child_ != ptr;
1024 }
1025 
1026 template<class B>
1027 template<class T>
1028 bool
1030  return child_ == other();
1031 }
1032 
1033 template<class B>
1034 template<class T>
1035 bool
1037  return child_.get() != other();
1038 }
1039 
1040 template<class B>
1041 template<class T>
1042 template<class U>
1043 bool
1045  return child_.get() == other.get();
1046 }
1047 
1048 template<class B>
1049 template<class T>
1050 template<class U>
1051 bool
1053  return child_.get() != other.get();
1054 }
1055 
1057 // Implementations for EdgeVector<T>
1059 
1060 template<class B>
1061 template<class T>
1063  : EdgeBase(parent.treeEdges_), parent_(parent) {
1064  parent_.treeEdges_ = this;
1065 }
1066 
1068 // Implementations for Vertex<B>
1070 
1071 template<class B>
1073  : parent(*this) {}
1074 
1075 template<class B>
1076 typename Vertex<B>::UserBasePtr
1078  auto retval = std::dynamic_pointer_cast<UserBase>(this->shared_from_this());
1079  ASSERT_not_null(retval);
1080  return retval;
1081 }
1082 
1083 template<class B>
1084 template<class T>
1085 std::shared_ptr<T>
1087  return std::dynamic_pointer_cast<T>(this->shared_from_this());
1088 }
1089 
1090 template<class B>
1091 typename Vertex<B>::UserBasePtr
1092 Vertex<B>::child(size_t i) const {
1093  std::vector<EdgeBase*> edges;
1094  for (const EdgeBase *edge = treeEdges_; edge; edge = edge->prev)
1095  edges.push_back(edge);
1096  for (const EdgeBase *edge: boost::adaptors::reverse(edges)) {
1097  if (i < edge->size()) {
1098  return edge->pointer(i);
1099  } else {
1100  i -= edge->size();
1101  }
1102  }
1103  return {};
1104 }
1105 
1106 template<class B>
1107 size_t
1109  size_t n = 0;
1110  for (const EdgeBase *edge = treeEdges_; edge; edge = edge->prev)
1111  n += edge->size();
1112  return n;
1113 }
1114 
1115 } // namespace
1116 } // namespace
1117 #endif
size_t nChildren() const
Returns the number of children.
Definition: Tree.h:1108
void push_back(const ChildPtr &elmt)
Insert a child pointer at the end of this vertex.
Definition: Tree.h:608
auto traverseReverse(const Visitor &visitor)
Traverse in reverse direction from children to parents.
Definition: Tree.h:739
Exception(const std::string &mesg, const UserBasePtr &vertex)
Construct a new error with the specified message and the causing vertex.
Definition: Tree.h:137
iterator end()
Return an iterator to one past the last edge.
Definition: Tree.h:672
std::shared_ptr< Child > ChildPtr
Type of pointers to children.
Definition: Tree.h:443
std::shared_ptr< Child > ChildPtr
Type of pointer to the child.
Definition: Tree.h:323
RuntimeError(const std::string &mesg)
Constructor taking a description of the error.
bool empty() const
Test whether vector is empty.
Definition: Tree.h:583
iterator begin()
Return an iterator to the first edge.
Definition: Tree.h:667
size_t capacity() const
Reserved capacity.
Definition: Tree.h:600
bool operator!=(const UserBasePtr &) const
Compare the child pointer to another pointer.
Definition: Tree.h:1022
const ChildPtr & operator()() const
Return the child if there is one, else null.
Definition: Tree.h:1008
Edge< Child > & back()
Return the last edge.
Definition: Tree.h:660
EdgeVector(UserBase &parent)
Construct a child edge that belongs to the specified parent.
Definition: Tree.h:1062
A parent-to-child edge in a tree.
Definition: Tree.h:123
void pop_back()
Erase a child edge from the end of this vertex.
Definition: Tree.h:616
std::shared_ptr< T > findLastAncestor()
Traversal that finds the farthest ancestor of type T or derived from T.
Definition: Tree.h:830
Edge< Child > & operator[](size_t i)
Return the i'th edge.
Definition: Tree.h:635
const Edge< Child > & front() const
Return the first edge.
Definition: Tree.h:643
InsertionError(const UserBasePtr &vertex)
Construct a new error with the vertex that caused the error.
Definition: Tree.h:149
Edge & operator=(const ChildPtr &child)
Assign a pointer to a child.
Definition: Tree.h:387
const Edge< Child > & operator[](size_t i) const
Return the i'th edge.
Definition: Tree.h:632
Base class for Sawyer runtime errors.
CycleError(const UserBasePtr &vertex)
Construct a new error with the vertex that caused the error.
Definition: Tree.h:159
UserBasePtr vertex
Vertex that caused the error.
Definition: Tree.h:134
Name space for the entire library.
Definition: FeasiblePath.h:767
Error when attaching a vertex to a tree and the vertex is already attached somewhere else...
Definition: Tree.h:146
Edge(UserBase &parent)
Construct a child edge that belongs to the specified parent.
Definition: Tree.h:955
const Edge< Child > & at(size_t i) const
Return the i'th edge.
Definition: Tree.h:624
Edge< Child > & at(size_t i)
Return the i'th edge.
Definition: Tree.h:628
std::shared_ptr< UserBase > UserBasePtr
Pointer to user's base class.
Definition: Tree.h:117
~EdgeVector()
Destructor clears children's parents.
Definition: Tree.h:570
Edge< Child > & front()
Return the first edge.
Definition: Tree.h:647
ReverseEdge parent
Pointer to the parent in the tree.
Definition: Tree.h:690
std::shared_ptr< T > isa()
Tests whether this object is a certain type.
Definition: Tree.h:1086
~Edge()
Destructor clears child's parent.
Definition: Tree.h:948
Edge & operator=(const ReverseEdge &parent)
Assign a pointer to a child.
Definition: Tree.h:406
void reserve(size_t n)
Reserve space so the child edge vector can grow without being reallocated.
Definition: Tree.h:595
UserBasePtr child(size_t i) const
Returns the pointer for a child.
Definition: Tree.h:1092
TraversalEvent
Traversal event.
Definition: Tree.h:29
Node UserBase
User's base class.
Definition: Tree.h:114
Base class for tree vertices.
Definition: Tree.h:110
Base class for errors and exceptions for this vertex type.
Definition: Tree.h:131
Error when attaching a vertex to a tree would cause a cycle.
Definition: Tree.h:156
bool operator==(const UserBasePtr &) const
Compare the child pointer to another pointer.
Definition: Tree.h:1015
auto traversePre(const Visitor &visitor)
Pre-order forward traversal.
Definition: Tree.h:792
auto traverse(const Visitor &visitor)
Traverse in forward direction from parents to children.
Definition: Tree.h:767
bool operator!=(const UserBasePtr &) const
Compare the parent pointer to another pointer.
Definition: Tree.h:900
bool operator==(const UserBasePtr &) const
Compare the parent pointer to another pointer.
Definition: Tree.h:894
UserBasePtr operator->() const
Return the parent if there is one, else null.
Definition: Tree.h:887
const Edge< Child > & back() const
Return the last edge.
Definition: Tree.h:656
size_t size() const override
Number of child edges.
Definition: Tree.h:590
A 1:N tree edge from parent to children.
Definition: Tree.h:124
const ChildPtr & operator->() const
Return the child if there is one, else null.
Definition: Tree.h:1000
T Child
Type of children being pointed to.
Definition: Tree.h:440
std::shared_ptr< T > findFirstAncestor()
Traversal that finds the closest ancestor of type T or derived from T.
Definition: Tree.h:822
T Child
Type of child being pointed to.
Definition: Tree.h:320
UserBasePtr operator()() const
Return the parent if there is one, else null.
Definition: Tree.h:877
std::vector< std::shared_ptr< T > > findDescendants()
Traversal that finds all the descendants of a particular type.
Definition: Tree.h:841
auto traversePost(const Visitor &visitor)
Post-order forward traversal.
Definition: Tree.h:810
Points from a child to a parent in the tree.
Definition: Tree.h:176
UserBasePtr pointer()
Returns a shared pointer to this vertex.
Definition: Tree.h:1077