8 #ifndef Sawyer_TreeVertex_H
9 #define Sawyer_TreeVertex_H
11 #include <Sawyer/Assert.h>
12 #include <Sawyer/Exception.h>
14 #include <boost/lexical_cast.hpp>
15 #include <boost/range/adaptor/reversed.hpp>
110 class Vertex:
public std::enable_shared_from_this<Vertex<B>> {
150 :
Exception(
"vertex is already attached to a tree", vertex) {}
160 :
Exception(
"insertion of vertex would cause a cycle in the tree", vertex) {}
222 explicit operator bool()
const {
223 return parent_ !=
nullptr;
228 template<
class T>
friend class Edge;
237 enum class Link { NO, YES };
247 virtual ~EdgeBase() {}
249 EdgeBase(
const EdgeBase&) =
delete;
250 EdgeBase& operator=(
const EdgeBase&) =
delete;
251 explicit EdgeBase(EdgeBase *prev)
255 virtual size_t size()
const = 0;
264 template<
class T,
class Visitor>
267 if (
auto retval = prev->traverse<T>(visitor))
270 for (
size_t i = 0; i < size(); ++i) {
272 if (
auto retval =
child->template traverse<T>(visitor))
317 class Edge:
public EdgeBase {
388 if (child != child_) {
389 checkChildInsertion(child);
393 child_->parent.reset();
399 child->parent.set(parent_);
407 return (*
this) =
parent();
412 explicit operator bool()
const {
413 return child_ !=
nullptr;
419 size_t size()
const override {
423 Vertex* pointer(
size_t i)
const override {
424 ASSERT_always_require(0 == i);
437 class EdgeVector:
public EdgeBase {
446 using Vector = std::vector<std::unique_ptr<Edge<Child>>>;
450 using size_type =
typename Vector::size_type;
451 using difference_type =
typename Vector::difference_type;
456 template<
class BaseIterator>
458 BaseIterator baseIterator_;
462 Iterator(
const BaseIterator &baseIterator)
463 : baseIterator_(baseIterator) {}
466 : baseIterator_(other.baseIterator_) {}
469 baseIterator_ = other.baseIterator_;
495 Iterator& operator+=(difference_type n) {
500 Iterator operator+(difference_type n)
const {
506 Iterator& operator-=(difference_type n) {
511 Iterator operator-(difference_type n)
const {
517 difference_type operator-(
const Iterator &other)
const {
518 return other.baseIterator_ - baseIterator_;
521 auto& operator*()
const {
522 ASSERT_not_null(*baseIterator_);
523 return **baseIterator_;
526 auto& operator->()
const {
527 ASSERT_not_null(*baseIterator_);
528 return &**baseIterator_;
531 auto& operator[](difference_type i)
const {
532 ASSERT_not_null(baseIterator_[i]);
533 return *baseIterator_[i];
536 bool operator==(
const Iterator &other)
const {
537 return baseIterator_ == other.baseIterator_;
540 bool operator!=(
const Iterator &other)
const {
541 return baseIterator_ != other.baseIterator_;
544 bool operator<(
const Iterator &other)
const {
545 return baseIterator_ < other.baseIterator_;
548 bool operator<=(
const Iterator &other)
const {
549 return baseIterator_ <= other.baseIterator_;
552 bool operator>(
const Iterator &other)
const {
553 return baseIterator_ > other.baseIterator_;
556 bool operator>=(
const Iterator &other)
const {
557 return baseIterator_ >= other.baseIterator_;
584 return edges_.empty();
591 return edges_.size();
601 return edges_.capacity();
609 auto edge = std::unique_ptr<Edge<Child>>(
new Edge<Child>(Link::NO, parent_, elmt));
610 edges_.push_back(std::move(edge));
617 ASSERT_forbid(edges_.empty());
625 ASSERT_require(i < edges_.size());
626 return *edges_.at(i);
629 ASSERT_require(i < edges_.size());
630 return *edges_.at(i);
644 ASSERT_forbid(
empty());
648 ASSERT_forbid(
empty());
657 ASSERT_forbid(
empty());
661 ASSERT_forbid(
empty());
677 Vertex* pointer(
size_t i)
const override {
678 return at(i)().
get();
691 EdgeBase *treeEdges_ =
nullptr;
694 virtual void destructorHelper() {}
705 std::shared_ptr<T>
isa();
738 template<
class T,
class Visitor>
740 auto vertex = std::dynamic_pointer_cast<T>(this->
pointer());
747 if (
auto result =
parent()->template traverseReverse<T>(visitor))
766 template<
class T,
class Visitor>
768 auto vertex = std::dynamic_pointer_cast<T>(this->
pointer());
774 if (
auto retval = treeEdges_->template traverse<T>(visitor))
791 template<
class T,
class Visitor>
793 return traverse<T>([&visitor] (
const std::shared_ptr<T> &vertex,
TraversalEvent event) {
795 return visitor(vertex);
797 return decltype(visitor(vertex))();
809 template<
class T,
class Visitor>
811 return traverse<T>([&visitor] (
const std::shared_ptr<T> &vertex,
TraversalEvent event) {
813 return visitor(vertex);
815 return decltype(visitor(vertex))();
823 return traverseReverse<T>([](
const std::shared_ptr<T> &vertex,
TraversalEvent event) {
831 return traverseReverse<T>([](
const std::shared_ptr<T> &vertex,
TraversalEvent event) {
842 std::vector<std::shared_ptr<T>> retval;
843 traverse<T>([&retval](
const std::shared_ptr<T> &vertex,
TraversalEvent event) {
845 retval.push_back(vertex);
868 ASSERT_require(this->parent_ ==
nullptr);
888 ASSERT_not_null(parent_);
889 return parent_->pointer();
895 return ptr.get() == parent_;
901 return ptr.get() != parent_;
907 return parent_ == other.parent_;
913 return parent_ != other.parent_;
920 return parent_ == other();
927 return parent_ != other();
956 : EdgeBase(parent.treeEdges_), parent_(parent) {
957 parent_.treeEdges_ =
this;
963 : EdgeBase(parent.treeEdges_), parent_(parent), child_(child) {
964 checkChildInsertion(child);
965 parent_.treeEdges_ =
this;
967 child->parent.set(parent);
973 : EdgeBase(Link::YES == link ? parent.treeEdges_ : nullptr), parent_(parent), child_(child) {
974 checkChildInsertion(child);
975 if (Link::YES == link)
976 parent_.treeEdges_ =
this;
978 child->parent.set(parent);
987 throw InsertionError(child);
989 for (
const UserBase *p = &parent_; p; p = p->parent().get()) {
990 if (p == child.get())
991 throw CycleError(child);
999 const std::shared_ptr<T>&
1001 ASSERT_not_null(child_);
1007 const std::shared_ptr<T>&
1016 return child_ == ptr;
1023 return child_ != ptr;
1030 return child_ == other();
1037 return child_.get() != other();
1045 return child_.get() == other.get();
1053 return child_.get() != other.get();
1063 : EdgeBase(parent.treeEdges_), parent_(parent) {
1064 parent_.treeEdges_ =
this;
1078 auto retval = std::dynamic_pointer_cast<
UserBase>(this->shared_from_this());
1079 ASSERT_not_null(retval);
1087 return std::dynamic_pointer_cast<T>(this->shared_from_this());
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);
1110 for (
const EdgeBase *edge = treeEdges_; edge; edge = edge->prev)
size_t nChildren() const
Returns the number of children.
void push_back(const ChildPtr &elmt)
Insert a child pointer at the end of this vertex.
auto traverseReverse(const Visitor &visitor)
Traverse in reverse direction from children to parents.
Exception(const std::string &mesg, const UserBasePtr &vertex)
Construct a new error with the specified message and the causing vertex.
iterator end()
Return an iterator to one past the last edge.
std::shared_ptr< Child > ChildPtr
Type of pointers to children.
std::shared_ptr< Child > ChildPtr
Type of pointer to the child.
RuntimeError(const std::string &mesg)
Constructor taking a description of the error.
bool empty() const
Test whether vector is empty.
iterator begin()
Return an iterator to the first edge.
size_t capacity() const
Reserved capacity.
bool operator!=(const UserBasePtr &) const
Compare the child pointer to another pointer.
const ChildPtr & operator()() const
Return the child if there is one, else null.
Edge< Child > & back()
Return the last edge.
EdgeVector(UserBase &parent)
Construct a child edge that belongs to the specified parent.
A parent-to-child edge in a tree.
void pop_back()
Erase a child edge from the end of this vertex.
std::shared_ptr< T > findLastAncestor()
Traversal that finds the farthest ancestor of type T or derived from T.
Edge< Child > & operator[](size_t i)
Return the i'th edge.
const Edge< Child > & front() const
Return the first edge.
InsertionError(const UserBasePtr &vertex)
Construct a new error with the vertex that caused the error.
Edge & operator=(const ChildPtr &child)
Assign a pointer to a child.
const Edge< Child > & operator[](size_t i) const
Return the i'th edge.
Base class for Sawyer runtime errors.
CycleError(const UserBasePtr &vertex)
Construct a new error with the vertex that caused the error.
UserBasePtr vertex
Vertex that caused the error.
Name space for the entire library.
Error when attaching a vertex to a tree and the vertex is already attached somewhere else...
Edge(UserBase &parent)
Construct a child edge that belongs to the specified parent.
const Edge< Child > & at(size_t i) const
Return the i'th edge.
Edge< Child > & at(size_t i)
Return the i'th edge.
std::shared_ptr< UserBase > UserBasePtr
Pointer to user's base class.
~EdgeVector()
Destructor clears children's parents.
Edge< Child > & front()
Return the first edge.
ReverseEdge parent
Pointer to the parent in the tree.
std::shared_ptr< T > isa()
Tests whether this object is a certain type.
~Edge()
Destructor clears child's parent.
Edge & operator=(const ReverseEdge &parent)
Assign a pointer to a child.
void reserve(size_t n)
Reserve space so the child edge vector can grow without being reallocated.
UserBasePtr child(size_t i) const
Returns the pointer for a child.
TraversalEvent
Traversal event.
Node UserBase
User's base class.
Base class for tree vertices.
Base class for errors and exceptions for this vertex type.
Error when attaching a vertex to a tree would cause a cycle.
bool operator==(const UserBasePtr &) const
Compare the child pointer to another pointer.
auto traversePre(const Visitor &visitor)
Pre-order forward traversal.
auto traverse(const Visitor &visitor)
Traverse in forward direction from parents to children.
bool operator!=(const UserBasePtr &) const
Compare the parent pointer to another pointer.
bool operator==(const UserBasePtr &) const
Compare the parent pointer to another pointer.
UserBasePtr operator->() const
Return the parent if there is one, else null.
const Edge< Child > & back() const
Return the last edge.
size_t size() const override
Number of child edges.
A 1:N tree edge from parent to children.
const ChildPtr & operator->() const
Return the child if there is one, else null.
T Child
Type of children being pointed to.
std::shared_ptr< T > findFirstAncestor()
Traversal that finds the closest ancestor of type T or derived from T.
T Child
Type of child being pointed to.
UserBasePtr operator()() const
Return the parent if there is one, else null.
std::vector< std::shared_ptr< T > > findDescendants()
Traversal that finds all the descendants of a particular type.
auto traversePost(const Visitor &visitor)
Post-order forward traversal.
Points from a child to a parent in the tree.
UserBasePtr pointer()
Returns a shared pointer to this vertex.