ROSE  0.9.11.145
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_Tree_H
9 #define Sawyer_Tree_H
10 
11 #include <Sawyer/Assert.h>
12 #include <Sawyer/Optional.h>
13 
14 #include <memory>
15 #include <stdexcept>
16 #include <vector>
17 
18 #if 1 // DEBUGGING [Robb Matzke 2019-02-18]
19 #include <iostream>
20 #endif
21 
22 namespace Sawyer {
23 
95 namespace Tree {
96 
97 class Node;
98 class Children;
99 
105 using NodePtr = std::shared_ptr<Node>;
106 using ConstNodePtr = std::shared_ptr<const Node>;
109 // ____ _ _ _
111 // | _ \ ___ ___| | __ _ _ __ __ _| |_(_) ___ _ __ ___
112 // | | | |/ _ \/ __| |/ _` | '__/ _` | __| |/ _ \| '_ \/ __|
113 // | |_| | __/ (__| | (_| | | | (_| | |_| | (_) | | | \__ |
114 // |____/ \___|\___|_|\__,_|_| \__,_|\__|_|\___/|_| |_|___/
115 //
117 
120  ENTER = 0x1,
121  LEAVE = 0x2
122 };
123 
129 };
130 
132 // Exception declarations
134 
136 class Exception: public std::runtime_error {
137 public:
138  Exception(const std::string &mesg)
139  : std::runtime_error(mesg) {}
140 };
141 
155 public:
158  ConsistencyException(const NodePtr &child,
159  const std::string &mesg = "attempt to attach child that already has a different parent")
160  : Exception(mesg), child(child) {}
161 };
162 
164 // ChildEdge declaration
166 
204 template<class T>
205 class ChildEdge final {
206 private:
207  Node *container_; // non-null ptr to node that's the source of this edge
208  const size_t idx_; // index of the child edge from the parent's perspective
209 
210 public:
212  explicit ChildEdge(Node *container);
213 
215  ChildEdge(Node *container, const std::shared_ptr<T> &child);
216 
217  ChildEdge(const ChildEdge&) = delete; // just for now
218 
220  ChildEdge& operator=(const std::shared_ptr<T> &child) {
221  assign(child);
222  return *this;
223  }
224 
226  void reset() {
227  assign(nullptr);
228  }
229 
231  std::shared_ptr<T> operator->() const {
232  return shared();
233  }
234 
236  T& operator*() const {
237  ASSERT_not_null(shared());
238  return *shared();
239  }
240 
242  explicit operator bool() const {
243  return shared() != nullptr;
244  }
245 
247  std::shared_ptr<T> shared() const;
248 
250  operator std::shared_ptr<T>() const {
251  return shared();
252  }
253 
254 private:
255  // Assign a new child to this edge.
256  void assign(const NodePtr &child);
257 };
258 
260 // ParentEdge
262 
268 class ParentEdge final {
269 private:
270  Node* parent_;
271 
272 public:
273  ParentEdge()
274  : parent_(nullptr) {}
275 
277  NodePtr operator->() const {
278  return shared();
279  }
280 
282  Node& operator*() const {
283  ASSERT_not_null(parent_);
284  return *shared();
285  }
286 
288  NodePtr shared() const;
289 
291  explicit operator bool() const {
292  return parent_ != nullptr;
293  }
294 
295 #if 0 // [Robb Matzke 2019-02-18]: Node is not declared yet?
296 
297  operator std::shared_ptr<Node> const {
298  return shared();
299  }
300 #endif
301 
305  bool operator==(const ParentEdge &other) const { return parent_ == other.parent_; }
306  bool operator!=(const ParentEdge &other) const { return parent_ != other.parent_; }
307  bool operator< (const ParentEdge &other) const { return parent_ < other.parent_; }
308  bool operator<=(const ParentEdge &other) const { return parent_ <= other.parent_; }
309  bool operator> (const ParentEdge &other) const { return parent_ > other.parent_; }
310  bool operator>=(const ParentEdge &other) const { return parent_ >= other.parent_; }
313 private:
314  friend class Children;
315 
316  // Set the parent
317  void set(Node *parent) {
318  parent_ = parent;
319  }
320 
321  // Clear the parent
322  void reset() {
323  parent_ = nullptr;
324  }
325 };
326 
328 // Children declaration
330 
337 class Children final {
338 private:
339  Node *container_;
340  std::vector<NodePtr > children_;
341 
342 public:
343  Children(Node *container);
344  Children(const Children&) = delete;
345  Children& operator=(const Children&) = delete;
346 
347  //----------------------------------------
348  // Read-only API
349  //----------------------------------------
350 public:
352  size_t size() const {
353  return children_.size();
354  }
355 
357  size_t max_size() const {
358  return children_.max_size();
359  }
360 
362  size_t capacity() const {
363  return children_.capacity();
364  }
365 
367  bool empty() const {
368  return children_.empty();
369  }
370 
372  void reserve(size_t n) {
373  children_.reserve(n);
374  }
375 
377  void shrink_to_fit() {
378  children_.shrink_to_fit();
379  }
380 
382  const NodePtr at(size_t idx) const {
383  ASSERT_require(idx < children_.size());
384  return children_.at(idx);
385  }
386 
388  const NodePtr operator[](size_t idx) const {
389  ASSERT_require(idx < children_.size());
390  return children_[idx];
391  }
392 
394  const NodePtr front() const {
395  ASSERT_forbid(empty());
396  return children_.front();
397  }
398 
400  const NodePtr back() const {
401  ASSERT_forbid(empty());
402  return children_.back();
403  }
404 
406  const std::vector<NodePtr >& elmts() const {
407  return children_;
408  }
409 
413  bool operator==(const Children &other) const { return children_ == other.children_; }
414  bool operator!=(const Children &other) const { return children_ != other.children_; }
415  bool operator< (const Children &other) const { return children_ < other.children_; }
416  bool operator<=(const Children &other) const { return children_ <= other.children_; }
417  bool operator> (const Children &other) const { return children_ > other.children_; }
418  bool operator>=(const Children &other) const { return children_ >= other.children_; }
421  //----------------------------------------
422  // Internal stuff
423  //----------------------------------------
424 private:
425  template<class T> friend class ListNode;
426  template<class T> friend class ChildEdge;
427 
428  // Cause the indicated parent-child edge to point to a new child. The old value, if any will be removed from the tree and
429  // its parent pointer reset. The new child will be added to the tree at the specified parent-to-child edge and its parent
430  // pointer adjusted to point to the node that now owns it. As with direct assignment of pointers to the parent-to-child
431  // edge data members, it is illegal to attach a node to a tree in such a way that the structure would no longer be a tree,
432  // and in such cases no changes are made an an exception is thrown.
433  void setAt(size_t idx, const NodePtr &newChild);
434  void setAt(size_t idx, nullptr_t) {
435  setAt(idx, NodePtr());
436  }
437 
438  // Check that the newChild is able to be inserted replacing the oldChild. If not, throw exception. Either or both of the
439  // children may be null pointers, but 'parent' must be non-null.
440  void checkInsertionConsistency(const NodePtr &newChild, const NodePtr &oldChild, Node *parent);
441 
442  // Insert a new child edge at the specified position in the list. Consistency checks are performed and the child's parent
443  // pointer is adjusted.
444  void insertAt(size_t idx, const NodePtr &child);
445 
446  // Remove one of the child edges. If the edge pointed to a non-null child node, then that child's parent pointer is reset.
447  void eraseAt(size_t idx);
448 
449  // Remove all children.
450  void clear();
451 
452  // Add a new parent-child-edge and return its index
453  size_t appendEdge(const NodePtr &child);
454 };
455 
457 // Node declaration
459 
479 class Node: public std::enable_shared_from_this<Node> {
480 private:
481  enum TraversalDirection { TRAVERSE_UPWARD, TRAVERSE_DOWNWARD };
482 
483 public:
487 public:
489  Node(): children(this) {}
490 
492  virtual ~Node() {}
493 
494  // Nodes are not copyable since doing so would cause the children (which are not copied) to have two parents. Instead, we
495  // will provide mechanisms for copying nodes without their children (shallow copy) or recursively copying an entire tree
496  // (deep copy).
497  Node(const Node&) = delete;
498  Node& operator=(const Node&) = delete;
499 
515  template<class Functor>
516  TraversalAction traverse(Functor functor) {
517  return traverseImpl<Functor>(TRAVERSE_DOWNWARD, functor);
518  }
519  template<class Functor>
520  TraversalAction traverse(Functor functor) const {
521  return traverseImpl<Functor>(TRAVERSE_DOWNWARD, functor);
522  }
530  template<class T, class Functor>
531  TraversalAction traverseType(Functor functor);
532  template<class T, class Functor>
533  TraversalAction traverseType(Functor functor) const;
542  template<class Functor>
543  TraversalAction traverseParents(Functor functor) {
544  return traverseImpl<Functor>(TRAVERSE_UPWARD, functor);
545  }
546  template<class Functor>
547  TraversalAction traverseParents(Functor functor) const {
548  return traverseImpl<Functor>(TRAVERSE_UPWARD, functor);
549  }
555  template<class Predicate>
556  NodePtr find(Predicate predicate) {
557  return findImpl<Node, Predicate>(TRAVERSE_DOWNWARD, predicate);
558  }
559  template<class Predicate>
560  NodePtr find(Predicate predicate) const {
561  return findImpl<Node, Predicate>(TRAVERSE_DOWNWARD, predicate);
562  }
568  template<class T>
569  std::shared_ptr<T> findType() {
570  return findImpl<T>(TRAVERSE_DOWNWARD, [](const std::shared_ptr<T>&) { return true; });
571  }
572  template<class T>
573  std::shared_ptr<T> findType() const {
574  return findImpl<T>(TRAVERSE_DOWNWARD, [](const std::shared_ptr<T>&) { return true; });
575  }
581  template<class T, class Predicate>
582  std::shared_ptr<T> findType(Predicate predicate) {
583  return findImpl<T, Predicate>(TRAVERSE_DOWNWARD, predicate);
584  }
585  template<class T, class Predicate>
586  std::shared_ptr<T> findType(Predicate predicate) const {
587  return findImpl<T, Predicate>(TRAVERSE_DOWNWARD, predicate);
588  }
594  template<class Predicate>
595  NodePtr findParent(Predicate predicate) {
596  return findImpl<Node, Predicate>(TRAVERSE_UPWARD, predicate);
597  }
598  template<class Predicate>
599  NodePtr findParent(Predicate predicate) const {
600  return findImpl<Node, Predicate>(TRAVERSE_UPWARD, predicate);
601  }
607  template<class T>
608  std::shared_ptr<T> findParentType() {
609  return findImpl<T>(TRAVERSE_UPWARD, [](const std::shared_ptr<T>&) { return true; });
610  }
611  template<class T>
612  std::shared_ptr<T> findParentType() const {
613  return findImpl<T>(TRAVERSE_UPWARD, [](const std::shared_ptr<T>&) { return true; });
614  }
620  template<class T, class Predicate>
621  std::shared_ptr<T> findParentType(Predicate predicate) {
622  return findImpl<T, Predicate>(TRAVERSE_UPWARD, predicate);
623  }
624  template<class T, class Predicate>
625  std::shared_ptr<T> findParentType(Predicate predicate) const {
626  return findImpl<T, Predicate>(TRAVERSE_UPWARD, predicate);
627  }
630 private:
631  // implementation for all the traversals
632  template<class Functor>
633  TraversalAction traverseImpl(TraversalDirection, Functor);
634  template<class Functor>
635  TraversalAction traverseImpl(TraversalDirection, Functor) const;
636 
637  // implementation for traversals whose purpose is to find something
638  template<class T, class Predicate>
639  std::shared_ptr<T> findImpl(TraversalDirection, Predicate);
640  template<class T, class Predicate>
641  std::shared_ptr<T> findImpl(TraversalDirection, Predicate) const;
642 };
643 
645 // ListNode declaration
647 
698 template<class T>
699 class ListNode final: public Node {
700 public:
701  //----------------------------------------
702  // Read-only API delegated to 'children'
703  //----------------------------------------
704 
706  size_t size() const {
707  return children.size();
708  }
709 
711  size_t max_size() const {
712  return children.max_size();
713  }
714 
716  size_t capacity() const {
717  return children.capacity();
718  }
719 
721  bool empty() const {
722  return children.empty();
723  }
724 
726  void reserve(size_t n) {
727  children.reserve(n);
728  }
729 
731  void shrink_to_fit() {
733  }
734 
736  const std::shared_ptr<T> at(size_t i) const {
737  return std::dynamic_pointer_cast<T>(children.at(i));
738  }
739 
741  const std::shared_ptr<T> operator[](size_t i) const {
742  return std::dynamic_pointer_cast<T>(children[i]);
743  }
744 
746  const std::shared_ptr<T> front() const {
747  return std::dynamic_pointer_cast<T>(children.front());
748  }
749 
751  const std::shared_ptr<T> back() const {
752  return std::dynamic_pointer_cast<T>(children.back());
753  }
754 
756  std::vector<std::shared_ptr<T> > elmts() const;
757 
762  Optional<size_t> index(const std::shared_ptr<T> &node, size_t startAt = 0) const;
763 
764  //----------------------------------------
765  // Modifying API
766  //----------------------------------------
767 
769  void clear() {
770  children.clear();
771  }
772 
774  void push_back(const std::shared_ptr<T> &newChild) {
775  children.insertAt(children.size(), newChild);
776  }
777 
781  void setAt(size_t i, const std::shared_ptr<T> &child) {
782  children.setAt(i, child);
783  }
784  void setAt(size_t i, nullptr_t) {
785  children.setAt(i, nullptr);
786  }
794  void insertAt(size_t i, const std::shared_ptr<T> &newChild) {
795  children.insertAt(i, newChild);
796  }
797 
801  void eraseAt(size_t i) {
802  children.eraseAt(i);
803  }
804 
810  Optional<size_t> erase(const std::shared_ptr<T> &toErase, size_t startAt = 0);
811 };
812 
814 // ____ _ _ _
815 // | _ \ ___| | __ _| |_(_) ___ _ __ ___
816 // | |_) / _ \ |/ _` | __| |/ _ \| '_ \/ __|
817 // | _ < __/ | (_| | |_| | (_) | | | \__ |
818 // |_| \_\___|_|\__,_|\__|_|\___/|_| |_|___/
819 //
821 
822 // ChildEdge<T> and ChildEdge<U>
823 template<class T, class U> bool operator==(const ChildEdge<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs.shared() == rhs.shared(); }
824 template<class T, class U> bool operator!=(const ChildEdge<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs.shared() != rhs.shared(); }
825 template<class T, class U> bool operator< (const ChildEdge<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs.shared() < rhs.shared(); }
826 template<class T, class U> bool operator<=(const ChildEdge<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs.shared() <= rhs.shared(); }
827 template<class T, class U> bool operator> (const ChildEdge<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs.shared() > rhs.shared(); }
828 template<class T, class U> bool operator>=(const ChildEdge<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs.shared() >= rhs.shared(); }
829 
830 // ChildEdge<T> and nullptr
831 template<class T> bool operator==(const ChildEdge<T> &lhs, nullptr_t) noexcept { return lhs.shared() == nullptr; }
832 template<class T> bool operator!=(const ChildEdge<T> &lhs, nullptr_t) noexcept { return lhs.shared() != nullptr; }
833 template<class T> bool operator< (const ChildEdge<T> &lhs, nullptr_t) noexcept { return lhs.shared() < nullptr; }
834 template<class T> bool operator<=(const ChildEdge<T> &lhs, nullptr_t) noexcept { return lhs.shared() <= nullptr; }
835 template<class T> bool operator> (const ChildEdge<T> &lhs, nullptr_t) noexcept { return lhs.shared() > nullptr; }
836 template<class T> bool operator>=(const ChildEdge<T> &lhs, nullptr_t) noexcept { return lhs.shared() >= nullptr; }
837 
838 // nullptr and ChildEdge<T>
839 template<class T> bool operator==(nullptr_t, const ChildEdge<T> &rhs) noexcept { return nullptr == rhs.shared(); }
840 template<class T> bool operator!=(nullptr_t, const ChildEdge<T> &rhs) noexcept { return nullptr != rhs.shared(); }
841 template<class T> bool operator< (nullptr_t, const ChildEdge<T> &rhs) noexcept { return nullptr < rhs.shared(); }
842 template<class T> bool operator<=(nullptr_t, const ChildEdge<T> &rhs) noexcept { return nullptr <= rhs.shared(); }
843 template<class T> bool operator> (nullptr_t, const ChildEdge<T> &rhs) noexcept { return nullptr > rhs.shared(); }
844 template<class T> bool operator>=(nullptr_t, const ChildEdge<T> &rhs) noexcept { return nullptr >= rhs.shared(); }
845 
846 // ChildEdge<T> and std::shared_ptr<U>
847 template<class T, class U> bool operator==(const ChildEdge<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.shared() == rhs; }
848 template<class T, class U> bool operator!=(const ChildEdge<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.shared() != rhs; }
849 template<class T, class U> bool operator< (const ChildEdge<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.shared() < rhs; }
850 template<class T, class U> bool operator<=(const ChildEdge<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.shared() <= rhs; }
851 template<class T, class U> bool operator> (const ChildEdge<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.shared() > rhs; }
852 template<class T, class U> bool operator>=(const ChildEdge<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.shared() >= rhs; }
853 
854 // std::shared_ptr<T> and ChildEdge<U>
855 template<class T, class U> bool operator==(const std::shared_ptr<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs == rhs.shared(); }
856 template<class T, class U> bool operator!=(const std::shared_ptr<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs != rhs.shared(); }
857 template<class T, class U> bool operator< (const std::shared_ptr<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs < rhs.shared(); }
858 template<class T, class U> bool operator<=(const std::shared_ptr<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs <= rhs.shared(); }
859 template<class T, class U> bool operator> (const std::shared_ptr<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs > rhs.shared(); }
860 template<class T, class U> bool operator>=(const std::shared_ptr<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs >= rhs.shared(); }
861 
862 // ParentEdge and nullptr
863 inline bool operator==(const ParentEdge &lhs, nullptr_t) noexcept { return lhs.shared() == nullptr; }
864 inline bool operator!=(const ParentEdge &lhs, nullptr_t) noexcept { return lhs.shared() != nullptr; }
865 inline bool operator< (const ParentEdge &lhs, nullptr_t) noexcept { return lhs.shared() < nullptr; }
866 inline bool operator<=(const ParentEdge &lhs, nullptr_t) noexcept { return lhs.shared() <= nullptr; }
867 inline bool operator> (const ParentEdge &lhs, nullptr_t) noexcept { return lhs.shared() > nullptr; }
868 inline bool operator>=(const ParentEdge &lhs, nullptr_t) noexcept { return lhs.shared() >= nullptr; }
869 
870 // nullptr and ParentEdge
871 inline bool operator==(nullptr_t, const ParentEdge &rhs) noexcept { return nullptr == rhs.shared(); }
872 inline bool operator!=(nullptr_t, const ParentEdge &rhs) noexcept { return nullptr != rhs.shared(); }
873 inline bool operator< (nullptr_t, const ParentEdge &rhs) noexcept { return nullptr < rhs.shared(); }
874 inline bool operator<=(nullptr_t, const ParentEdge &rhs) noexcept { return nullptr <= rhs.shared(); }
875 inline bool operator> (nullptr_t, const ParentEdge &rhs) noexcept { return nullptr > rhs.shared(); }
876 inline bool operator>=(nullptr_t, const ParentEdge &rhs) noexcept { return nullptr >= rhs.shared(); }
877 
878 // ParentEdge and std::shared_ptr<T>
879 template<class T> bool operator==(const ParentEdge &lhs, const std::shared_ptr<T> &rhs) noexcept { return lhs.shared() == rhs; }
880 template<class T> bool operator!=(const ParentEdge &lhs, const std::shared_ptr<T> &rhs) noexcept { return lhs.shared() != rhs; }
881 template<class T> bool operator< (const ParentEdge &lhs, const std::shared_ptr<T> &rhs) noexcept { return lhs.shared() < rhs; }
882 template<class T> bool operator<=(const ParentEdge &lhs, const std::shared_ptr<T> &rhs) noexcept { return lhs.shared() <= rhs; }
883 template<class T> bool operator> (const ParentEdge &lhs, const std::shared_ptr<T> &rhs) noexcept { return lhs.shared() > rhs; }
884 template<class T> bool operator>=(const ParentEdge &lhs, const std::shared_ptr<T> &rhs) noexcept { return lhs.shared() >= rhs; }
885 
886 // std::shared_ptr<T> and ParentEdge
887 template<class T> bool operator==(const std::shared_ptr<T> &lhs, const ParentEdge &rhs) noexcept { return lhs == rhs.shared(); }
888 template<class T> bool operator!=(const std::shared_ptr<T> &lhs, const ParentEdge &rhs) noexcept { return lhs != rhs.shared(); }
889 template<class T> bool operator< (const std::shared_ptr<T> &lhs, const ParentEdge &rhs) noexcept { return lhs < rhs.shared(); }
890 template<class T> bool operator<=(const std::shared_ptr<T> &lhs, const ParentEdge &rhs) noexcept { return lhs <= rhs.shared(); }
891 template<class T> bool operator> (const std::shared_ptr<T> &lhs, const ParentEdge &rhs) noexcept { return lhs > rhs.shared(); }
892 template<class T> bool operator>=(const std::shared_ptr<T> &lhs, const ParentEdge &rhs) noexcept { return lhs >= rhs.shared(); }
893 
894 // ParentEdge and ChildEdge<T>
895 template<class T> bool operator==(const ParentEdge &lhs, const ChildEdge<T> &rhs) noexcept { return lhs.shared() == rhs.shared(); }
896 template<class T> bool operator!=(const ParentEdge &lhs, const ChildEdge<T> &rhs) noexcept { return lhs.shared() != rhs.shared(); }
897 template<class T> bool operator< (const ParentEdge &lhs, const ChildEdge<T> &rhs) noexcept { return lhs.shared() < rhs.shared(); }
898 template<class T> bool operator<=(const ParentEdge &lhs, const ChildEdge<T> &rhs) noexcept { return lhs.shared() <= rhs.shared(); }
899 template<class T> bool operator> (const ParentEdge &lhs, const ChildEdge<T> &rhs) noexcept { return lhs.shared() > rhs.shared(); }
900 template<class T> bool operator>=(const ParentEdge &lhs, const ChildEdge<T> &rhs) noexcept { return lhs.shared() >= rhs.shared(); }
901 
902 // ChildEdge<T> and ParentEdge
903 template<class T> bool operator==(const ChildEdge<T> &lhs, const ParentEdge &rhs) noexcept { return lhs.shared() == rhs.shared(); }
904 template<class T> bool operator!=(const ChildEdge<T> &lhs, const ParentEdge &rhs) noexcept { return lhs.shared() != rhs.shared(); }
905 template<class T> bool operator< (const ChildEdge<T> &lhs, const ParentEdge &rhs) noexcept { return lhs.shared() < rhs.shared(); }
906 template<class T> bool operator<=(const ChildEdge<T> &lhs, const ParentEdge &rhs) noexcept { return lhs.shared() <= rhs.shared(); }
907 template<class T> bool operator> (const ChildEdge<T> &lhs, const ParentEdge &rhs) noexcept { return lhs.shared() > rhs.shared(); }
908 template<class T> bool operator>=(const ChildEdge<T> &lhs, const ParentEdge &rhs) noexcept { return lhs.shared() >= rhs.shared(); }
909 
911 // ___ _ _ _ _
912 // |_ _|_ __ ___ _ __ | | ___ _ __ ___ ___ _ __ | |_ __ _| |_(_) ___ _ __ ___
913 // | || '_ ` _ \| '_ \| |/ _ \ '_ ` _ \ / _ \ '_ \| __/ _` | __| |/ _ \| '_ \/ __|
914 // | || | | | | | |_) | | __/ | | | | | __/ | | | || (_| | |_| | (_) | | | \__ |
915 // |___|_| |_| |_| .__/|_|\___|_| |_| |_|\___|_| |_|\__\__,_|\__|_|\___/|_| |_|___/
916 // |_|
917 //
919 
921 // ChildEdge implementation
923 
924 template<class T>
926  : container_(container), idx_(container->children.appendEdge(nullptr)) {
927  ASSERT_not_null(container_);
928 }
929 
930 template<class T>
931 ChildEdge<T>::ChildEdge(Node *container, const std::shared_ptr<T> &child)
932  : container_(container), idx_(container->children.appendEdge(child)) {
933  ASSERT_not_null(container_);
934 }
935 
936 template<class T>
937 std::shared_ptr<T>
939  return std::dynamic_pointer_cast<T>(container_->children[this->idx_]);
940 }
941 
942 template<class T>
943 void
944 ChildEdge<T>::assign(const NodePtr &newChild) {
945  container_->children.setAt(idx_, newChild);
946 }
947 
949 // ParentEdge implementation
951 
952 NodePtr
954  return parent_ ? parent_->shared_from_this() : NodePtr();
955 }
956 
958 // Children implementation
960 
961 Children::Children(Node *container)
962  : container_(container) {
963  ASSERT_not_null(container);
964 }
965 
966 size_t
967 Children::appendEdge(const NodePtr &child) {
968  size_t idx = children_.size();
969  children_.push_back(nullptr);
970  setAt(idx, child);
971  return idx;
972 }
973 
974 void
975 Children::checkInsertionConsistency(const NodePtr &newChild, const NodePtr &oldChild, Node *parent) {
976  ASSERT_not_null(parent);
977 
978  if (newChild && newChild != oldChild) {
979  if (newChild->parent != nullptr) {
980  if (newChild->parent.shared().get() == parent) {
981  throw ConsistencyException(newChild, "node is already a child of the parent");
982  } else {
983  throw ConsistencyException(newChild, "node is already attached to a tree");
984  }
985  }
986 
987  for (Node *ancestor = parent; ancestor; ancestor = ancestor->parent.parent_) {
988  if (newChild.get() == ancestor)
989  throw ConsistencyException(newChild, "node insertion would introduce a cycle");
990  }
991  }
992 }
993 
994 void
995 Children::setAt(size_t idx, const NodePtr &newChild) {
996  ASSERT_require(idx < children_.size());
997  NodePtr oldChild = children_[idx];
998  checkInsertionConsistency(newChild, oldChild, container_);
999  if (oldChild)
1000  oldChild->parent.reset();
1001  children_[idx] = newChild;
1002  if (newChild)
1003  newChild->parent.set(container_);
1004 }
1005 
1006 void
1007 Children::insertAt(size_t idx, const NodePtr &child) {
1008  ASSERT_require(idx <= children_.size());
1009  checkInsertionConsistency(child, nullptr, container_);
1010  children_.insert(children_.begin() + idx, child);
1011  if (child)
1012  child->parent.set(container_);
1013 }
1014 
1015 void
1016 Children::eraseAt(size_t idx) {
1017  ASSERT_require(idx < children_.size());
1018  if (children_[idx])
1019  children_[idx]->parent.reset();
1020  children_.erase(children_.begin() + idx);
1021 }
1022 
1023 void
1024 Children::clear() {
1025  while (!children_.empty()) {
1026  if (children_.back())
1027  children_.back()->parent.reset();
1028  children_.pop_back();
1029  }
1030 }
1031 
1033 // Node implementation
1035 
1036 //----------------------------------------
1037 // traverseImpl
1038 //----------------------------------------
1039 template<class Functor>
1041 Node::traverseImpl(TraversalDirection direction, Functor functor) {
1042  switch (TraversalAction action = functor(this->shared_from_this(), ENTER)) {
1043  case CONTINUE:
1044  if (TRAVERSE_DOWNWARD == direction) {
1045  for (size_t i=0; i<children.size() && CONTINUE==action; ++i) {
1046  if (children[i])
1047  action = children[i]->traverseImpl<Functor>(direction, functor);
1048  }
1049  } else if (parent) {
1050  action = parent->traverseImpl<Functor>(direction, functor);
1051  }
1052  // fall through
1053  case SKIP_CHILDREN:
1054  if (ABORT != action && (action = functor(this->shared_from_this(), LEAVE)) == SKIP_CHILDREN)
1055  action = CONTINUE;
1056  // fall through
1057  default:
1058  return action;
1059  }
1060 }
1061 
1062 template<class Functor>
1064 Node::traverseImpl(TraversalDirection direction, Functor functor) const {
1065  switch (TraversalAction action = functor(this->shared_from_this(), ENTER)) {
1066  case CONTINUE:
1067  if (TRAVERSE_DOWNWARD == direction) {
1068  for (size_t i=0; i<children.size() && CONTINUE==action; ++i) {
1069  if (children[i])
1070  action = children[i]->traverseImpl<Functor>(direction, functor);
1071  }
1072  } else if (parent) {
1073  action = parent->traverseImpl<Functor>(direction, functor);
1074  }
1075  // fall through
1076  case SKIP_CHILDREN:
1077  if (ABORT != action && (action = functor(this->shared_from_this(), LEAVE)) == SKIP_CHILDREN)
1078  action = CONTINUE;
1079  // fall through
1080  default:
1081  return action;
1082  }
1083 }
1084 
1085 //----------------------------------------
1086 // traverseType
1087 //----------------------------------------
1088 
1089 template<class T, class Functor>
1091  Functor functor;
1092 
1093  TraverseTypeHelper(Functor functor)
1094  : functor(functor) {}
1095 
1096  TraversalAction operator()(const NodePtr &node, TraversalEvent event) {
1097  if (std::shared_ptr<T> typed = std::dynamic_pointer_cast<T>(node)) {
1098  return functor(typed, event);
1099  } else {
1100  return CONTINUE;
1101  }
1102  }
1103 };
1104 
1105 template<class T, class Functor>
1107 Node::traverseType(Functor functor) {
1108  return traverseImpl(TRAVERSE_DOWNWARD, TraverseTypeHelper<T, Functor>(functor));
1109 }
1110 
1111 template<class T, class Functor>
1113 Node::traverseType(Functor functor) const {
1114  return traverseImpl(TRAVERSE_DOWNWARD, TraverseTypeHelper<T, Functor>(functor));
1115 }
1116 
1117 //----------------------------------------
1118 // findImpl
1119 //----------------------------------------
1120 template<class T, class Predicate>
1121 std::shared_ptr<T>
1122 Node::findImpl(TraversalDirection direction, Predicate predicate) {
1123  std::shared_ptr<T> found;
1124  traverseImpl(direction,
1125  [&predicate, &found](const NodePtr &node, TraversalEvent event) {
1126  if (ENTER == event) {
1127  std::shared_ptr<T> typedNode = std::dynamic_pointer_cast<T>(node);
1128  if (typedNode && predicate(typedNode)) {
1129  found = typedNode;
1130  return ABORT;
1131  }
1132  }
1133  return CONTINUE;
1134  });
1135  return found;
1136 }
1137 
1138 template<class T, class Predicate>
1139 std::shared_ptr<T>
1140 Node::findImpl(TraversalDirection direction, Predicate predicate) const {
1141  std::shared_ptr<T> found;
1142  traverseImpl(direction,
1143  [&predicate, &found](const ConstNodePtr &node, TraversalEvent event) {
1144  if (ENTER == event) {
1145  std::shared_ptr<const T> typedNode = std::dynamic_pointer_cast<const T>(node);
1146  if (typedNode && predicate(typedNode)) {
1147  found = typedNode;
1148  return ABORT;
1149  }
1150  }
1151  return CONTINUE;
1152  });
1153  return found;
1154 }
1155 
1157 // ListNode implementation
1159 
1160 template<class T>
1161 std::vector<std::shared_ptr<T> >
1163  std::vector<std::shared_ptr<T> > retval;
1164  retval.reserve(children.size());
1165  for (size_t i = 0; i < children.size(); ++i)
1166  retval.push_back(std::dynamic_pointer_cast<T>(children[i]));
1167  return retval;
1168 }
1169 
1170 template<class T>
1172 ListNode<T>::index(const std::shared_ptr<T> &node, size_t startAt) const {
1173  for (size_t i = startAt; i < children.size(); ++i) {
1174  if (children[i] == node)
1175  return i;
1176  }
1177  return Nothing();
1178 }
1179 
1180 template<class T>
1182 ListNode<T>::erase(const std::shared_ptr<T> &toErase, size_t startAt) {
1183  Optional<size_t> where = index(toErase, startAt);
1184  if (where)
1185  children.eraseAt(*where);
1186  return where;
1187 }
1188 
1189 } // namespace
1190 } // namespace
1191 
1192 #endif
void clear()
Remove all children.
Definition: Tree.h:769
std::shared_ptr< T > shared() const
Pointer to the child.
Definition: Tree.h:938
bool operator>=(const Children &other) const
Relations.
Definition: Tree.h:418
bool empty() const
Empty predicate.
Definition: Tree.h:367
size_t max_size() const
Maximum size.
Definition: Tree.h:711
Edge pointing from child to parent.
Definition: Tree.h:268
void shrink_to_fit()
Shrink reservation.
Definition: Tree.h:731
const NodePtr front() const
First child pointer.
Definition: Tree.h:394
const std::vector< NodePtr > & elmts() const
The actual underlying vector of child pointers.
Definition: Tree.h:406
void shrink_to_fit()
Request container to reduce capacity.
Definition: Tree.h:377
NodePtr shared() const
Return the parent as a shared-ownership pointer.
Definition: Tree.h:953
ParentEdge parent
Pointer to the parent node, if any.
Definition: Tree.h:484
ChildEdge & operator=(const std::shared_ptr< T > &child)
Point to a child node.
Definition: Tree.h:220
const std::shared_ptr< T > back() const
Last child, if any.
Definition: Tree.h:751
TraversalAction traverseParents(Functor functor) const
Traverse the tree by following parent pointers.
Definition: Tree.h:547
void insertAt(size_t i, const std::shared_ptr< T > &newChild)
Insert the node at the specified index.
Definition: Tree.h:794
TraversalAction traverseParents(Functor functor)
Traverse the tree by following parent pointers.
Definition: Tree.h:543
bool operator<(const ParentEdge &other) const
Relation.
Definition: Tree.h:307
bool empty() const
Empty predicate.
Definition: Tree.h:721
For enter events, do not traverse into the node's children.
Definition: Tree.h:127
Children children
Vector of pointers to children.
Definition: Tree.h:485
std::shared_ptr< T > findType()
Find first child that's the specified type.
Definition: Tree.h:569
T & operator*() const
Obtain pointed-to node.
Definition: Tree.h:236
void reserve(size_t n)
Reserve space for more children.
Definition: Tree.h:726
bool operator>=(const ParentEdge &other) const
Relation.
Definition: Tree.h:310
Vector of parent-to-child pointers.
Definition: Tree.h:337
NodePtr operator->() const
Obtain shared pointer.
Definition: Tree.h:277
size_t capacity() const
Size of allocated storage.
Definition: Tree.h:362
size_t max_size() const
Maximum potential size.
Definition: Tree.h:357
void setAt(size_t i, const std::shared_ptr< T > &child)
Make child edge point to a different child.
Definition: Tree.h:781
std::shared_ptr< T > findParentType() const
Find closest ancestor of specified type.
Definition: Tree.h:612
Optional< size_t > index(const std::shared_ptr< T > &node, size_t startAt=0) const
Find the index for the specified node.
Definition: Tree.h:1172
const NodePtr back() const
Last child pointer.
Definition: Tree.h:400
Node & operator*() const
Obtain pointed-to node.
Definition: Tree.h:282
Name space for the entire library.
TraversalAction traverse(Functor functor) const
Traverse the tree starting at this node and following child pointers.
Definition: Tree.h:520
size_t size() const
Number of nodes in vector.
Definition: Tree.h:352
std::shared_ptr< T > findParentType(Predicate predicate) const
Find closest ancestor of specified type that satisfies the predicate.
Definition: Tree.h:625
std::shared_ptr< T > findType(Predicate predicate) const
Find first child of specified type satisfying the predicate.
Definition: Tree.h:586
const NodePtr at(size_t idx) const
Child pointer at index, checked.
Definition: Tree.h:382
Exceptions for tree-related operations.
Definition: Tree.h:136
bool operator!=(const ParentEdge &other) const
Relation.
Definition: Tree.h:306
Exception if tree consistency would be violated.
Definition: Tree.h:154
NodePtr find(Predicate predicate)
Traverse an tree to find the first node satisfying the predicate.
Definition: Tree.h:556
const NodePtr operator[](size_t idx) const
Child pointer at index, unchecked.
Definition: Tree.h:388
Base class for Tree nodes.
Definition: Tree.h:479
std::shared_ptr< const Node > ConstNodePtr
Short name for node pointers.
Definition: Tree.h:106
std::shared_ptr< Node > NodePtr
Short name for node pointers.
Definition: Tree.h:105
std::shared_ptr< T > findParentType(Predicate predicate)
Find closest ancestor of specified type that satisfies the predicate.
Definition: Tree.h:621
Traversal has just entered the node under consideration.
Definition: Tree.h:120
TraversalEvent
Traversal event bit flags.
Definition: Tree.h:119
bool operator==(const ParentEdge &other) const
Relation.
Definition: Tree.h:305
ChildEdge(Node *container)
Points to no child.
Definition: Tree.h:925
size_t capacity() const
Capacity.
Definition: Tree.h:716
TraversalAction traverse(Functor functor)
Traverse the tree starting at this node and following child pointers.
Definition: Tree.h:516
std::shared_ptr< T > findType() const
Find first child that's the specified type.
Definition: Tree.h:573
void reserve(size_t n)
Request change in capacity.
Definition: Tree.h:372
std::shared_ptr< T > findParentType()
Find closest ancestor of specified type.
Definition: Tree.h:608
bool operator<=(const Children &other) const
Relations.
Definition: Tree.h:416
bool operator==(const Children &other) const
Relations.
Definition: Tree.h:413
NodePtr findParent(Predicate predicate) const
Find closest ancestor that satifies the predicate.
Definition: Tree.h:599
virtual ~Node()
Nodes are polymorphic.
Definition: Tree.h:492
A node containing only a list of children.
Definition: Tree.h:699
bool operator!=(const Children &other) const
Relations.
Definition: Tree.h:414
void eraseAt(size_t i)
Erase node at specified index.
Definition: Tree.h:801
An edge from a parent to a child.
Definition: Tree.h:205
NodePtr find(Predicate predicate) const
Traverse an tree to find the first node satisfying the predicate.
Definition: Tree.h:560
bool operator<=(const ParentEdge &other) const
Relation.
Definition: Tree.h:308
Continue with the traversal.
Definition: Tree.h:126
bool operator<(const Children &other) const
Relations.
Definition: Tree.h:415
bool operator>(const Children &other) const
Relations.
Definition: Tree.h:417
void push_back(const std::shared_ptr< T > &newChild)
Append a child pointer.
Definition: Tree.h:774
std::vector< std::shared_ptr< T > > elmts() const
Vector of all children.
Definition: Tree.h:1162
TraversalAction traverseType(Functor functor)
Traverse the tree restricted by type.
Definition: Tree.h:1107
NodePtr child
Child node that was being modified.
Definition: Tree.h:156
Abort the traversal immediately.
Definition: Tree.h:128
void setAt(size_t i, nullptr_t)
Make child edge point to a different child.
Definition: Tree.h:784
std::shared_ptr< T > findType(Predicate predicate)
Find first child of specified type satisfying the predicate.
Definition: Tree.h:582
Represents no value.
Definition: Optional.h:32
void reset()
Cause this edge to point to no child.
Definition: Tree.h:226
Optional< size_t > erase(const std::shared_ptr< T > &toErase, size_t startAt=0)
Erase the first occurrence of the specified child.
Definition: Tree.h:1182
const std::shared_ptr< T > operator[](size_t i) const
Child at specified index.
Definition: Tree.h:741
Node()
Construct an empty node.
Definition: Tree.h:489
const std::shared_ptr< T > front() const
First child, if any.
Definition: Tree.h:746
bool operator>(const ParentEdge &other) const
Relation.
Definition: Tree.h:309
NodePtr findParent(Predicate predicate)
Find closest ancestor that satifies the predicate.
Definition: Tree.h:595
TraversalAction
Traversal actions.
Definition: Tree.h:125
std::shared_ptr< T > operator->() const
Obtain shared pointer.
Definition: Tree.h:231
size_t size() const
Number of children.
Definition: Tree.h:706
const std::shared_ptr< T > at(size_t i) const
Child at specified index.
Definition: Tree.h:736
Traversal has just left the node under consideration.
Definition: Tree.h:121