Tree.h

// WARNING: Changes to this file must be contributed back to Sawyer or else they will
//          be clobbered by the next update from Sawyer.  The Sawyer repository is at
//          https://gitlab.com/charger7534/sawyer.git.
 
 
 
 
#ifndef Sawyer_TreeVertex_H
#define Sawyer_TreeVertex_H
 
#include <Sawyer/Assert.h>
#include <Sawyer/Exception.h>
 
#include <boost/lexical_cast.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/signals2/signal.hpp>
#include <memory>
#include <string>
#include <vector>
 
#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
#include <boost/serialization/shared_ptr.hpp>
#include <boost/serialization/vector.hpp>
#endif
 
#ifdef SAWYER_HAVE_CEREAL
#include <cereal/types/memory.hpp>
#include <cereal/types/vector.hpp>
#endif
 
namespace Sawyer {
 
namespace Tree {
 
enum class TraversalEvent {
    ENTER,                                          
    LEAVE                                           
};
 
template<class B>
class Vertex: public std::enable_shared_from_this<Vertex<B>> {
public:
 
    using UserBase = B;
 
    using UserBasePtr = std::shared_ptr<UserBase>;
 
    using TraversalEvent = Sawyer::Tree::TraversalEvent;
 
public:
    template<class T> class Edge;
    template<class T> class EdgeVector;
 
    // Errors and exceptions
 
    class Exception: public Sawyer::Exception::RuntimeError {
    public:
        UserBasePtr vertex;
 
        Exception(const std::string &mesg, const UserBasePtr &vertex)
            : Sawyer::Exception::RuntimeError(mesg), vertex(vertex) {}
 
        ~Exception() {}
    };
 
    class InsertionError: public Exception {
    public:
        explicit InsertionError(const UserBasePtr &vertex)
            : Exception("vertex is already attached to a tree", vertex) {}
    };
 
    class CycleError: public Exception {
    public:
        explicit CycleError(const UserBasePtr &vertex)
            : Exception("insertion of vertex would cause a cycle in the tree", vertex) {}
    };
 
    // Child-to-parent edges
 
    class ReverseEdge {
    private:
        Vertex &child_;                                 // required child vertex owning this edge
 
        // The parent pointer is a raw pointer because it is safe to do so, and because we need to know the pointer before the
        // parent is fully constructed.
        //
        // It is safe (never dangling) because the pointer can only be changed by a forward edge, which is always a member of a
        // vertex, and the parent pointer is only set to point to that vertex. When the parent is deleted the edge is deleted and
        // its destructor changes the parent pointer back to null.
        //
        // The parent pointer is needed during construction of the parent when the parent has some edge data members that are being
        // initialized to point to non-null children. This happens during the parent's construction, before the parent has any
        // shared or weak pointers.
        UserBase *parent_ = nullptr;                    // optional parent to which this edge points
 
    public:
        // No default constructor and not copyable.
        ReverseEdge() = delete;
        explicit ReverseEdge(const ReverseEdge&) = delete;
        ReverseEdge& operator=(const ReverseEdge&) = delete;
 
    public:
        ~ReverseEdge();                                 // internal use only
        explicit ReverseEdge(Vertex &child);            // internal use only
 
    public:
        UserBasePtr operator()() const;
        UserBasePtr operator->() const;
        bool operator==(const UserBasePtr&) const;
        bool operator!=(const UserBasePtr&) const;
        bool operator==(const ReverseEdge&) const;
        bool operator!=(const ReverseEdge&) const;
        template<class T> bool operator==(const Edge<T>&) const;
        template<class T> bool operator!=(const Edge<T>&) const;
        explicit operator bool() const {
            return parent_ != nullptr;
        }
 
    private:
        // Used internally through ReverseEdgeAccess when a Edge<T> adjusts the ReverseEdge
        template<class T> friend class Edge;
        void reset();
        void set(UserBase &parent);
    };
 
    // Base class for parent-to-child edges
private:
    enum class Link { NO, YES };
 
    // Used internally as the non-template abstract base class for all parent-to-child edge types.
    class EdgeBase {
    public:
        // Previous edge in this object, including edges defined in base classes. Edges in this linked list are ordered so that
        // if edge A was initialized before edge B, then edge A will appear earlier in the list. The "prev" pointers in the list
        // point backward through the list.
        EdgeBase *prev;
 
    protected:
        UserBase &parent_;                              // required parent owning this child edge
 
    public:
        virtual ~EdgeBase() {}
        EdgeBase() = delete;
        EdgeBase(const EdgeBase&) = delete;
        EdgeBase& operator=(const EdgeBase&) = delete;
        explicit EdgeBase(EdgeBase *prev, UserBase &parent)
            : prev(prev), parent_(parent) {}
 
        // Number of child pointers in this edge. Edges are either 1:1 or 1:N. Some of the child pointers could be null.
        virtual size_t size() const = 0;
 
        // Return the i'th pointer. The argument is expected to be in the domain.
        virtual UserBasePtr pointer(size_t i) const = 0;
 
        // Traverse through all the non-null children of appropriate type pointed to by all edges in the order that the edges were
        // initialized. The visitor is invoked with two arguments: a non-null shared pointer to the child, and an indication of
        // whether this is a pre- or post-order visit. The first visitor call that returns a value that is true in a Boolean context
        // short circuits the traversal and that value becomes the return value of the traversal.
        template<class T, class Visitor>
        auto traverse(Visitor visitor) -> decltype(visitor(std::shared_ptr<T>(), TraversalEvent::ENTER)) {
            if (prev) {
                if (auto retval = prev->traverse<T>(visitor))
                    return retval;
            }
            for (size_t i = 0; i < size(); ++i) {
                if (auto child = pointer(i)) {
                    if (auto retval = child->template traverse<T>(visitor))
                        return retval;
                }
            }
            return decltype(visitor(std::shared_ptr<T>(), TraversalEvent::ENTER))();
        }
 
        // Return the list of child pointers for this edge. An `Edge` will have exactly one pointer, and an `EdgeVector` will
        // have any number of pointers. The pointers may be null.
        std::vector<UserBasePtr> immediateChildren() const {
            std::vector<UserBasePtr> retval;
            retval.reserve(size());
            for (size_t i = 0; i < size(); ++i)
                retval.push_back(pointer(i));
            return retval;
        }
 
    protected:
        // Return this edge and the previous edges in the order they were initialized. Each member is either a non-null pointer to
        // an `Edge` or a non-null pointer to an `EdgeVector`.
        std::vector<EdgeBase*> baseEdgeList() const {
            std::vector<EdgeBase*> retval;
            for (EdgeBase *child = this; child; child = prev)
                retval.push_back(child);
            std::reverse(retval.begin(), retval.end());
            return retval;
        }
 
    };
 
    // 1:1 parent-to-child edge
public:
    template<class T>
    class Edge: public EdgeBase {
    public:
        using Child = T;
 
        using ChildPtr = std::shared_ptr<Child>;
 
    private:
        using ChangeSignal = boost::signals2::signal<void(ChildPtr, ChildPtr)>;
 
    private:
        ChildPtr child_;                                // optional child to which this edge points
        ChangeSignal beforeChange_;                     // signal emitted before the child pointer is changed
        ChangeSignal afterChange_;                      // signal emitted after the child pointer is changed
 
#ifdef SAWYER_HAVE_CEREAL
    private:
        friend class cereal::access;
 
        template<class Archive>
        void CEREAL_SERIALIZE_FUNCTION_NAME(Archive &archive) {
            archive(cereal::make_nvp("child", child_));
        }
#endif
 
#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
    private:
        friend class boost::serialization::access;
 
        template<class Archive>
        void serialize(Archive &archive, const unsigned /*version*/) {
            archive & boost::serialization::make_nvp("child", child_);
        }
#endif
 
    public:
        ~Edge();
 
        explicit Edge(UserBase &parent);
        Edge(UserBase &parent, const ChildPtr &child);
    private:
        template<class U> friend class EdgeVector;
        // Used internally to initialize an edge without linking it to prior edges
        Edge(Link, UserBase &parent, const ChildPtr &child);
 
    public:
        const ChildPtr& operator->() const;
        const ChildPtr& operator()() const;
        bool operator==(const UserBasePtr&) const;
        bool operator!=(const UserBasePtr&) const;
        bool operator==(const ReverseEdge&) const;
        bool operator!=(const ReverseEdge&) const;
        template<class U> bool operator==(const Edge<U>&) const;
        template<class U> bool operator!=(const Edge<U>&) const;
        Edge& operator=(const ChildPtr &newChild) {
            if (newChild != child_) {
                checkChildInsertion(newChild);
 
                const ChildPtr oldChild = child_;
                beforeChange_(oldChild, newChild);
 
                // Unlink the child from the tree
                if (child_) {
                    child_->parent.reset();                     // child-to-parent edge
                    child_.reset();                             // parent-to-child edge
                }
 
                // Link new child into the tree
                if (newChild) {
                    newChild->parent.set(this->parent_);
                    child_ = newChild;
                }
 
                afterChange_(oldChild, newChild);
            }
            return *this;
        }
 
        Edge& operator=(const ReverseEdge &parent) {
            return (*this) = parent();
        }
        explicit operator bool() const {
            return child_ != nullptr;
        }
 
        boost::signals2::connection beforeChange(const typename ChangeSignal::slot_type &slot) {
            return beforeChange_.connect(slot);
        }
 
        boost::signals2::connection afterChange(const typename ChangeSignal::slot_type &slot) {
            return afterChange_.connect(slot);
        }
 
    private:
        void checkChildInsertion(const ChildPtr &child) const;
 
        size_t size() const override {
            return 1;
        }
 
        UserBasePtr pointer(size_t i) const override {
            ASSERT_always_require(0 == i);
            return child_;
        }
    };
 
    // 1:N parent-to-child edge
public:
    template<class T>
    class EdgeVector: public EdgeBase {
    public:
        using Child = T;
 
        using ChildPtr = std::shared_ptr<Child>;
 
    private:
        using Vector = std::vector<std::unique_ptr<Edge<Child>>>;
        using ResizeSignal = boost::signals2::signal<void(int, ChildPtr)>;
 
    public:
        using value_type = Edge<Child>;
        using size_type = typename Vector::size_type;
        using difference_type = typename Vector::difference_type;
        using reference = value_type&;
        using const_reference = const value_type&;
 
    public:
        template<class BaseIterator>
        class Iterator {
            BaseIterator baseIterator_;
 
        public:
            Iterator() = delete;
            Iterator(const BaseIterator &baseIterator)
                : baseIterator_(baseIterator) {}
 
            Iterator(const Iterator &other)
                : baseIterator_(other.baseIterator_) {}
 
            Iterator& operator=(const Iterator &other) {
                baseIterator_ = other.baseIterator_;
                return *this;
            }
 
            Iterator& operator++() {
                ++baseIterator_;
                return *this;
            }
 
            Iterator operator++(int) {
                Iterator temp = *this;
                ++baseIterator_;
                return temp;
            }
 
            Iterator& operator--() {
                --baseIterator_;
                return *this;
            }
 
            Iterator operator--(int) {
                Iterator temp = *this;
                --baseIterator_;
                return temp;
            }
 
            Iterator& operator+=(difference_type n) {
                baseIterator_ += n;
                return *this;
            }
 
            Iterator operator+(difference_type n) const {
                Iterator retval = *this;
                retval += n;
                return retval;
            }
 
            Iterator& operator-=(difference_type n) {
                baseIterator_ -= n;
                return *this;
            }
 
            Iterator operator-(difference_type n) const {
                Iterator retval = *this;
                retval -= n;
                return retval;
            }
 
            difference_type operator-(const Iterator &other) const {
                return other.baseIterator_ - baseIterator_;
            }
 
            auto& operator*() const {
                ASSERT_not_null(*baseIterator_);
                return **baseIterator_;
            }
 
            auto& operator->() const {
                ASSERT_not_null(*baseIterator_);
                return &**baseIterator_;
            }
 
            auto& operator[](difference_type i) const {
                ASSERT_not_null(baseIterator_[i]);
                return *baseIterator_[i];
            }
 
            bool operator==(const Iterator &other) const {
                return baseIterator_ == other.baseIterator_;
            }
 
            bool operator!=(const Iterator &other) const {
                return baseIterator_ != other.baseIterator_;
            }
 
            bool operator<(const Iterator &other) const {
                return baseIterator_ < other.baseIterator_;
            }
 
            bool operator<=(const Iterator &other) const {
                return baseIterator_ <= other.baseIterator_;
            }
 
            bool operator>(const Iterator &other) const {
                return baseIterator_ > other.baseIterator_;
            }
 
            bool operator>=(const Iterator &other) const {
                return baseIterator_ >= other.baseIterator_;
            }
        };
 
    public:
        using iterator = Iterator<typename Vector::iterator>;
 
    private:
        Vector edges_;
        ResizeSignal beforeResize_;                     // signal emitted before a resize operation
        ResizeSignal afterResize_;                      // signal emitted after a resize operation
 
#ifdef SAWYER_HAVE_CEREAL
    private:
        friend class cereal::access;
 
        template<class Archive>
        void CEREAL_SAVE_FUNCTION_NAME(Archive &archive) const {
            const size_t nEdges = edges_.size();
            archive(CEREAL_NVP(nEdges));
            for (size_t i = 0; i < nEdges; ++i) {
                ChildPtr child = at(i)();
                archive(CEREAL_NVP(child));
            }
        }
 
        template<class Archive>
        void CEREAL_LOAD_FUNCTION_NAME(Archive &archive) {
            size_t nEdges = 0;
            archive(CEREAL_NVP(nEdges));
            for (size_t i = 0; i < nEdges; ++i) {
                ChildPtr child;
                archive(CEREAL_NVP(child));
                push_back(child);
            }
        }
#endif
 
#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
    private:
        friend class boost::serialization::access;
 
        template<class Archive>
        void save(Archive &archive, const unsigned /*version*/) const {
            const size_t nEdges = edges_.size();
            archive <<BOOST_SERIALIZATION_NVP(nEdges);
            for (size_t i = 0; i < nEdges; ++i) {
                ChildPtr child = at(i)();
                archive <<BOOST_SERIALIZATION_NVP(child);
            }
        }
 
        template<class Archive>
        void load(Archive &archive, const unsigned /*version*/) {
            size_t nEdges = 0;
            archive >>BOOST_SERIALIZATION_NVP(nEdges);
            for (size_t i = 0; i < nEdges; ++i) {
                ChildPtr child;
                archive >>BOOST_SERIALIZATION_NVP(child);
                push_back(child);
            }
        }
 
        BOOST_SERIALIZATION_SPLIT_MEMBER();
#endif
 
    public:
        ~EdgeVector() {}
 
        explicit EdgeVector(UserBase &parent);
 
    public:
        bool empty() const {
            return edges_.empty();
        }
 
        size_t size() const override {
            return edges_.size();
        }
 
        void reserve(size_t n) {
            edges_.reserve(n);
        }
 
        size_t capacity() const {
            return edges_.capacity();
        }
 
        void push_back(const ChildPtr& elmt) {
            beforeResize_(+1, elmt);
            auto edge = std::unique_ptr<Edge<Child>>(new Edge<Child>(Link::NO, this->parent_, elmt));
            edges_.push_back(std::move(edge));
            afterResize_(+1, elmt);
        }
 
        void pop_back() {
            ASSERT_forbid(edges_.empty());
            ChildPtr removed = (*edges_.back())();
            beforeResize_(-1, removed);
            edges_.pop_back();
            afterResize_(-1, removed);
        }
 
        const Edge<Child>& at(size_t i) const {
            ASSERT_require(i < edges_.size());
            return *edges_.at(i);
        }
        Edge<Child>& at(size_t i) {
            ASSERT_require(i < edges_.size());
            return *edges_.at(i);
        }
        const Edge<Child>& operator[](size_t i) const {
            return at(i);
        }
        Edge<Child>& operator[](size_t i) {
            return at(i);
        }
        const Edge<Child>& front() const {
            ASSERT_forbid(empty());
            return at(0);
        }
        Edge<Child>& front() {
            ASSERT_forbid(empty());
            return at(0);
        }
        const Edge<Child>& back() const {
            ASSERT_forbid(empty());
            return at(size() - 1);
        }
        Edge<Child>& back() {
            ASSERT_forbid(empty());
            return at(size() - 1);
        }
        iterator begin() {
            return iterator(edges_.begin());
        }
 
        iterator end() {
            return iterator(edges_.end());
        }
 
        boost::signals2::connection beforeResize(const typename ResizeSignal::slot_type &slot) {
            return beforeResize_.connect(slot);
        }
 
        boost::signals2::connection afterResize(const typename ResizeSignal::slot_type &slot) {
            return afterResize_.connect(slot);
        }
 
    protected:
        UserBasePtr pointer(size_t i) const override {
            return at(i)();
        }
    };
 
    // Vertex
public:
    ReverseEdge parent;
 
private:
    EdgeBase *treeEdges_ = nullptr;
 
#ifdef SAWYER_HAVE_CEREAL
private:
    friend class cereal::access;
 
    // This base class is responsible for serializing the parts of the EdgeBase data members pointed to by `treeEdges_`, but not
    // their child pointers. The child pointers are serialized by the derived classes where those data members are defined.
    template<class Archive>
    void
    CEREAL_SAVE_FUNCTION_NAME(Archive &archive) const {
        const std::vector<EdgeBase*> baseEdgeList = [this]() {
            if (treeEdges_) {
                return treeEdges_->baseEdgeList();
            } else {
                return std::vector<EdgeBase*>();
            }
        }();
 
        const size_t nBases = baseEdgeList.size();
        archive(CEREAL_NVP(nBases));
        for (const EdgeBase *baseEdge: baseEdgeList) {
            const size_t baseOffset = (char*)baseEdge - (char*)this;
            archive(CEREAL_NVP(baseOffset));
        }
    }
 
    template<class Archive>
    void
    CEREAL_LOAD_FUNCTION_NAME(Archive &archive) const {
        const size_t nBases = 0;
        archive(CEREAL_NVP(nBases));
        for (size_t i = 0; i < nBases; ++i) {
            size_t baseOffset = 0;
            archive(CEREAL_NVP(baseOffset));
            EdgeBase *baseEdge = (EdgeBase*)((char*)this + baseOffset);
            baseEdge->reset(treeEdges_);
            treeEdges_ = baseEdge;
        }
    }
#endif
 
#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
private:
    friend class boost::serialization::access;
 
    // This base class is responsible for serializing the parts of the EdgeBase data members pointed to by `treeEdges_`, but not
    // their child pointers. The child pointers are serialized by the derived classes where those data members are defined.
    template<class Archive>
    void
    save(Archive &archive, const unsigned /*version*/) const {
        const std::vector<EdgeBase*> baseEdgeList = [this]() {
            if (treeEdges_) {
                return treeEdges_->baseEdgeList();
            } else {
                return std::vector<EdgeBase*>();
            }
        }();
 
        const size_t nBases = baseEdgeList.size();
        archive <<BOOST_SERIALIZATION_NVP(nBases);
        for (const EdgeBase *baseEdge: baseEdgeList) {
            const size_t baseOffset = (char*)baseEdge - (char*)this;
            archive <<BOOST_SERIALIZATION_NVP(baseOffset);
        }
    }
 
    template<class Archive>
    void
    load(Archive &archive, const unsigned /*version*/) {
        const size_t nBases = 0;
        archive >>BOOST_SERIALIZATION_NVP(nBases);
        for (size_t i = 0; i < nBases; ++i) {
            size_t baseOffset = 0;
            archive >>BOOST_SERIALIZATION_NVP(baseOffset);
            EdgeBase *baseEdge = (EdgeBase*)((char*)this + baseOffset);
            baseEdge->reset(treeEdges_);
            treeEdges_ = baseEdge;
        }
    }
 
    BOOST_SERIALIZATION_SPLIT_MEMBER();
#endif
 
protected:
    virtual void destructorHelper() {}
    Vertex();
 
public:
    UserBasePtr pointer();
 
    template<class T>
    std::shared_ptr<T> isa();
 
    template<class T, class Visitor>
    auto traverseReverse(const Visitor &visitor) {
        auto vertex = std::dynamic_pointer_cast<T>(this->pointer());
        if (vertex) {
            if (auto result = visitor(vertex, TraversalEvent::ENTER))
                return result;
        }
 
        if (parent) {
            if (auto result = parent()->template traverseReverse<T>(visitor))
                return result;
        }
 
        if (vertex) {
            return visitor(vertex, TraversalEvent::LEAVE);
        } else {
            return decltype(visitor(vertex, TraversalEvent::ENTER))();
        }
    }
 
    template<class T, class Visitor>
    auto traverse(const Visitor &visitor) {
        auto vertex = std::dynamic_pointer_cast<T>(this->pointer());
        if (vertex) {
            if (auto retval = visitor(vertex, TraversalEvent::ENTER))
                return retval;
        }
        if (treeEdges_) {
            if (auto retval = treeEdges_->template traverse<T>(visitor))
                return retval;
        }
        if (vertex) {
            return visitor(vertex, TraversalEvent::LEAVE);
        } else {
            return decltype(visitor(vertex, TraversalEvent::ENTER))();
        }
    }
 
    template<class T, class Visitor>
    auto traversePre(const Visitor &visitor) {
        return traverse<T>([&visitor] (const std::shared_ptr<T> &vertex, TraversalEvent event) {
            if (TraversalEvent::ENTER == event) {
                return visitor(vertex);
            } else {
                return decltype(visitor(vertex))();
            }
        });
    }
 
    template<class T, class Visitor>
    auto traversePost(const Visitor &visitor) {
        return traverse<T>([&visitor] (const std::shared_ptr<T> &vertex, TraversalEvent event) {
            if (TraversalEvent::LEAVE == event) {
                return visitor(vertex);
            } else {
                return decltype(visitor(vertex))();
            }
        });
    }
 
    template<class T>
    std::shared_ptr<T> findFirstAncestor() {
        return traverseReverse<T>([](const std::shared_ptr<T> &vertex, TraversalEvent event) {
            return TraversalEvent::ENTER == event ? vertex : nullptr;
        });
    };
 
    template<class T>
    std::shared_ptr<T> findLastAncestor() {
        return traverseReverse<T>([](const std::shared_ptr<T> &vertex, TraversalEvent event) {
            return TraversalEvent::LEAVE == event ? vertex : nullptr;
        });
    };
 
    template<class T>
    std::vector<std::shared_ptr<T>> findDescendants() {
        std::vector<std::shared_ptr<T>> retval;
        traverse<T>([&retval](const std::shared_ptr<T> &vertex, TraversalEvent event) {
            if (TraversalEvent::ENTER == event)
                retval.push_back(vertex);
        });
        return retval;
    }
 
    UserBasePtr child(size_t i) const;
 
    size_t nChildren() const;
};
 
// Implementations for ReverseEdge
 
template<class B>
Vertex<B>::ReverseEdge::~ReverseEdge() {
    ASSERT_require(this->parent_ == nullptr);
}
 
template<class B>
Vertex<B>::ReverseEdge::ReverseEdge(Vertex &child)
    : child_(child) {}
 
template<class B>
typename Vertex<B>::UserBasePtr
Vertex<B>::ReverseEdge::operator()() const {
    if (parent_) {
        return parent_->pointer();
    } else {
        return {};
    }
}
 
template<class B>
typename Vertex<B>::UserBasePtr
Vertex<B>::ReverseEdge::operator->() const {
    ASSERT_not_null(parent_);
    return parent_->pointer();
}
 
template<class B>
bool
Vertex<B>::ReverseEdge::operator==(const UserBasePtr &ptr) const {
    return ptr.get() == parent_;
}
 
template<class B>
bool
Vertex<B>::ReverseEdge::operator!=(const UserBasePtr &ptr) const {
    return ptr.get() != parent_;
}
 
template<class B>
bool
Vertex<B>::ReverseEdge::operator==(const ReverseEdge &other) const {
    return parent_ == other.parent_;
}
 
template<class B>
bool
Vertex<B>::ReverseEdge::operator!=(const ReverseEdge &other) const {
    return parent_ != other.parent_;
}
 
template<class B>
template<class T>
bool
Vertex<B>::ReverseEdge::operator==(const Edge<T> &other) const {
    return parent_ == other();
}
 
template<class B>
template<class T>
bool
Vertex<B>::ReverseEdge::operator!=(const Edge<T> &other) const {
    return parent_ != other();
}
 
template<class B>
void
Vertex<B>::ReverseEdge::reset() {
    parent_ = nullptr;
}
 
template<class B>
void
Vertex<B>::ReverseEdge::set(UserBase &parent) {
    parent_ = &parent;
}
 
// Implementations for Edge<T>
 
template<class B>
template<class T>
Vertex<B>::Edge<T>::~Edge() {
    if (child_)
        child_->parent.reset();
}
 
template<class B>
template<class T>
Vertex<B>::Edge<T>::Edge(UserBase &parent)
    : EdgeBase(parent.treeEdges_, parent) {
    this->parent_.treeEdges_ = this;
}
 
#ifndef DOCUMENTATION                                   // doxygen has problems with this
template<class B>
template<class T>
Vertex<B>::Edge<T>::Edge(UserBase &parent, const std::shared_ptr<T> &child)
    : EdgeBase(parent.treeEdges_, parent), child_(child) {
    checkChildInsertion(child);
    this->parent_.treeEdges_ = this;                    // must be after checkChildInsertin for exception safety
    if (child)
        child->parent.set(parent);
}
#endif
 
#ifndef DOCUMENTATION                                   // doxygen has problems with this
template<class B>
template<class T>
Vertex<B>::Edge<T>::Edge(Link link, UserBase &parent, const std::shared_ptr<T> &child)
    : EdgeBase(Link::YES == link ? parent.treeEdges_ : nullptr, parent), child_(child) {
    checkChildInsertion(child);
    if (Link::YES == link)
        this->parent_.treeEdges_ = this;                // must be after checkChildInsertin for exception safety
    if (child)
        child->parent.set(parent);
}
#endif
 
template<class B>
template<class T>
void
Vertex<B>::Edge<T>::checkChildInsertion(const std::shared_ptr<T> &child) const {
    if (child) {
        if (child->parent)
            throw InsertionError(child);
#ifndef NDEBUG
        for (const UserBase *p = &this->parent_; p; p = p->parent().get()) {
            if (p == child.get())
                throw CycleError(child);
        }
#endif
    }
}
 
template<class B>
template<class T>
const std::shared_ptr<T>&
Vertex<B>::Edge<T>::operator->() const {
    ASSERT_not_null(child_);
    return child_;
}
 
template<class B>
template<class T>
const std::shared_ptr<T>&
Vertex<B>::Edge<T>::operator()() const {
    return child_;
}
 
template<class B>
template<class T>
bool
Vertex<B>::Edge<T>::operator==(const UserBasePtr &ptr) const {
    return child_ == ptr;
}
 
template<class B>
template<class T>
bool
Vertex<B>::Edge<T>::operator!=(const UserBasePtr &ptr) const {
    return child_ != ptr;
}
 
template<class B>
template<class T>
bool
Vertex<B>::Edge<T>::operator==(const ReverseEdge &other) const {
    return child_ == other();
}
 
template<class B>
template<class T>
bool
Vertex<B>::Edge<T>::operator!=(const ReverseEdge &other) const {
    return child_.get() != other();
}
 
template<class B>
template<class T>
template<class U>
bool
Vertex<B>::Edge<T>::operator==(const Edge<U> &other) const {
    return child_.get() == other().get();
}
 
template<class B>
template<class T>
template<class U>
bool
Vertex<B>::Edge<T>::operator!=(const Edge<U> &other) const {
    return child_.get() != other().get();
}
 
// Implementations for EdgeVector<T>
 
template<class B>
template<class T>
Vertex<B>::EdgeVector<T>::EdgeVector(UserBase &parent)
    : EdgeBase(parent.treeEdges_, parent) {
    this->parent_.treeEdges_ = this;
}
 
// Implementations for Vertex<B>
 
template<class B>
Vertex<B>::Vertex()
    : parent(*this) {}
 
template<class B>
typename Vertex<B>::UserBasePtr
Vertex<B>::pointer() {
    auto retval = std::dynamic_pointer_cast<UserBase>(this->shared_from_this());
    ASSERT_not_null(retval);
    return retval;
}
 
template<class B>
template<class T>
std::shared_ptr<T>
Vertex<B>::isa() {
    return std::dynamic_pointer_cast<T>(this->shared_from_this());
}
 
template<class B>
typename Vertex<B>::UserBasePtr
Vertex<B>::child(size_t i) const {
    std::vector<EdgeBase*> edges;
    for (const EdgeBase *edge = treeEdges_; edge; edge = edge->prev)
        edges.push_back(edge);
    for (const EdgeBase *edge: boost::adaptors::reverse(edges)) {
        if (i < edge->size()) {
            return edge->pointer(i);
        } else {
            i -= edge->size();
        }
    }
    return {};
}
 
template<class B>
size_t
Vertex<B>::nChildren() const {
    size_t n = 0;
    for (const EdgeBase *edge = treeEdges_; edge; edge = edge->prev)
        n += edge->size();
    return n;
}
 
} // namespace
} // namespace
#endif