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://github.com/matzke1/sawyer.
 
 
 
 
#ifndef Sawyer_Tree_H
#define Sawyer_Tree_H
 
#include <Sawyer/Assert.h>
#include <Sawyer/Optional.h>
 
#include <memory>
#include <stdexcept>
#include <vector>
 
#if 1 // DEBUGGING [Robb Matzke 2019-02-18]
#include <iostream>
#endif
 
namespace Sawyer {
 
namespace Tree {
 
class Node;
class Children;
 
using NodePtr = std::shared_ptr<Node>;
using ConstNodePtr = std::shared_ptr<const Node>;
//                   ____            _                 _   _
//                  |  _ \  ___  ___| | __ _ _ __ __ _| |_(_) ___  _ __  ___
//                  | | | |/ _ \/ __| |/ _` | '__/ _` | __| |/ _ \| '_ \/ __|
//                  | |_| |  __/ (__| | (_| | | | (_| | |_| | (_) | | | \__ |
//                  |____/ \___|\___|_|\__,_|_|  \__,_|\__|_|\___/|_| |_|___/
//
 
enum TraversalEvent {
    ENTER = 0x1,                                        
    LEAVE = 0x2                                         
};
 
enum TraversalAction {
    CONTINUE,                                           
    SKIP_CHILDREN,                                      
    ABORT                                               
};
 
// Exception declarations
 
class Exception: public std::runtime_error {
public:
    Exception(const std::string &mesg)
        : std::runtime_error(mesg) {}
};
 
class ConsistencyException: public Exception {
public:
    NodePtr child;                        
    ConsistencyException(const NodePtr &child,
                         const std::string &mesg = "attempt to attach child that already has a different parent")
        : Exception(mesg), child(child) {}
};
 
// ChildEdge declaration
 
template<class T>
class ChildEdge final {
private:
    Node *container_;                                   // non-null ptr to node that's the source of this edge
    const size_t idx_;                                  // index of the child edge from the parent's perspective
 
public:
    explicit ChildEdge(Node *container);
 
    ChildEdge(Node *container, const std::shared_ptr<T> &child);
 
    ChildEdge(const ChildEdge&) = delete;               // just for now
 
    ChildEdge& operator=(const std::shared_ptr<T> &child) {
        assign(child);
        return *this;
    }
 
    void reset() {
        assign(nullptr);
    }
 
    std::shared_ptr<T> operator->() const {
        return shared();
    }
 
    T& operator*() const {
        ASSERT_not_null(shared());
        return *shared();
    }
    
    explicit operator bool() const {
        return shared() != nullptr;
    }
 
    std::shared_ptr<T> shared() const;
 
    operator std::shared_ptr<T>() const {
        return shared();
    }
 
private:
    // Assign a new child to this edge.
    void assign(const NodePtr &child);
};
 
// ParentEdge
 
class ParentEdge final {
private:
    Node* parent_;
 
public:
    ParentEdge()
        : parent_(nullptr) {}
 
    NodePtr operator->() const {
        return shared();
    }
 
    Node& operator*() const {
        ASSERT_not_null(parent_);
        return *shared();
    }
 
    NodePtr shared() const;
 
    explicit operator bool() const {
        return parent_ != nullptr;
    }
 
#if 0 // [Robb Matzke 2019-02-18]: Node is not declared yet?
 
    operator std::shared_ptr<Node> const {
        return shared();
    }
#endif
    
    bool operator==(const ParentEdge &other) const { return parent_ == other.parent_; }
    bool operator!=(const ParentEdge &other) const { return parent_ != other.parent_; }
    bool operator< (const ParentEdge &other) const { return parent_ <  other.parent_; }
    bool operator<=(const ParentEdge &other) const { return parent_ <= other.parent_; }
    bool operator> (const ParentEdge &other) const { return parent_ >  other.parent_; }
    bool operator>=(const ParentEdge &other) const { return parent_ >= other.parent_; }
private:
    friend class Children;
 
    // Set the parent
    void set(Node *parent) {
        parent_ = parent;
    }
 
    // Clear the parent
    void reset() {
        parent_ = nullptr;
    }
};
 
// Children declaration
 
class Children final {
private:
    Node *container_;
    std::vector<NodePtr > children_;
 
public:
    Children(Node *container);
    Children(const Children&) = delete;
    Children& operator=(const Children&) = delete;
 
    //----------------------------------------
    //           Read-only API
    //----------------------------------------
public:
    size_t size() const {
        return children_.size();
    }
 
    size_t max_size() const {
        return children_.max_size();
    }
 
    size_t capacity() const {
        return children_.capacity();
    }
 
    bool empty() const {
        return children_.empty();
    }
 
    void reserve(size_t n) {
        children_.reserve(n);
    }
 
    void shrink_to_fit() {
        children_.shrink_to_fit();
    }
 
    const NodePtr at(size_t idx) const {
        ASSERT_require(idx < children_.size());
        return children_.at(idx);
    }
 
    const NodePtr operator[](size_t idx) const {
        ASSERT_require(idx < children_.size());
        return children_[idx];
    }
 
    const NodePtr front() const {
        ASSERT_forbid(empty());
        return children_.front();
    }
 
    const NodePtr back() const {
        ASSERT_forbid(empty());
        return children_.back();
    }
 
    const std::vector<NodePtr >& elmts() const {
        return children_;
    }
 
    bool operator==(const Children &other) const { return children_ == other.children_; }
    bool operator!=(const Children &other) const { return children_ != other.children_; }
    bool operator< (const Children &other) const { return children_ <  other.children_; }
    bool operator<=(const Children &other) const { return children_ <= other.children_; }
    bool operator> (const Children &other) const { return children_ >  other.children_; }
    bool operator>=(const Children &other) const { return children_ >= other.children_; }
    //----------------------------------------
    //              Internal stuff
    //----------------------------------------
private:
    template<class T> friend class ListNode;
    template<class T> friend class ChildEdge;
 
    // Cause the indicated parent-child edge to point to a new child. The old value, if any will be removed from the tree and
    // its parent pointer reset. The new child will be added to the tree at the specified parent-to-child edge and its parent
    // pointer adjusted to point to the node that now owns it. As with direct assignment of pointers to the parent-to-child
    // 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,
    // and in such cases no changes are made an an exception is thrown.
    void setAt(size_t idx, const NodePtr &newChild);
    void setAt(size_t idx, std::nullptr_t) {
        setAt(idx, NodePtr());
    }
 
    // Check that the newChild is able to be inserted replacing the oldChild. If not, throw exception. Either or both of the
    // children may be null pointers, but 'parent' must be non-null.
    void checkInsertionConsistency(const NodePtr &newChild, const NodePtr &oldChild, Node *parent);
 
    // Insert a new child edge at the specified position in the list. Consistency checks are performed and the child's parent
    // pointer is adjusted.
    void insertAt(size_t idx, const NodePtr &child);
 
    // Remove one of the child edges. If the edge pointed to a non-null child node, then that child's parent pointer is reset.
    void eraseAt(size_t idx);
 
    // Remove all children.
    void clear();
 
    // Add a new parent-child-edge and return its index
    size_t appendEdge(const NodePtr &child);
};
 
// Node declaration
 
class Node: public std::enable_shared_from_this<Node> {
private:
    enum TraversalDirection { TRAVERSE_UPWARD, TRAVERSE_DOWNWARD };
 
public:
    ParentEdge parent;                                  
    Children children;                                  
public:
    Node(): children(this) {}
 
    virtual ~Node() {}
 
    // Nodes are not copyable since doing so would cause the children (which are not copied) to have two parents. Instead, we
    // will provide mechanisms for copying nodes without their children (shallow copy) or recursively copying an entire tree
    // (deep copy).
    Node(const Node&) = delete;
    Node& operator=(const Node&) = delete;
 
    template<class Functor>
    TraversalAction traverse(Functor functor) {
        return traverseImpl<Functor>(TRAVERSE_DOWNWARD, functor);
    }
    template<class Functor>
    TraversalAction traverse(Functor functor) const {
        return traverseImpl<Functor>(TRAVERSE_DOWNWARD, functor);
    }
    template<class T, class Functor>
    TraversalAction traverseType(Functor functor);
    template<class T, class Functor>
    TraversalAction traverseType(Functor functor) const;
    template<class Functor>
    TraversalAction traverseParents(Functor functor) {
        return traverseImpl<Functor>(TRAVERSE_UPWARD, functor);
    }
    template<class Functor>
    TraversalAction traverseParents(Functor functor) const {
        return traverseImpl<Functor>(TRAVERSE_UPWARD, functor);
    }
    template<class Predicate>
    NodePtr find(Predicate predicate) {
        return findImpl<Node, Predicate>(TRAVERSE_DOWNWARD, predicate);
    }
    template<class Predicate>
    NodePtr find(Predicate predicate) const {
        return findImpl<Node, Predicate>(TRAVERSE_DOWNWARD, predicate);
    }
    template<class T>
    std::shared_ptr<T> findType() {
        return findImpl<T>(TRAVERSE_DOWNWARD, [](const std::shared_ptr<T>&) { return true; });
    }
    template<class T>
    std::shared_ptr<T> findType() const {
        return findImpl<T>(TRAVERSE_DOWNWARD, [](const std::shared_ptr<T>&) { return true; });
    }
    template<class T, class Predicate>
    std::shared_ptr<T> findType(Predicate predicate) {
        return findImpl<T, Predicate>(TRAVERSE_DOWNWARD, predicate);
    }
    template<class T, class Predicate>
    std::shared_ptr<T> findType(Predicate predicate) const {
        return findImpl<T, Predicate>(TRAVERSE_DOWNWARD, predicate);
    }
    template<class Predicate>
    NodePtr findParent(Predicate predicate) {
        return findImpl<Node, Predicate>(TRAVERSE_UPWARD, predicate);
    }
    template<class Predicate>
    NodePtr findParent(Predicate predicate) const {
        return findImpl<Node, Predicate>(TRAVERSE_UPWARD, predicate);
    }
    template<class T>
    std::shared_ptr<T> findParentType() {
        return findImpl<T>(TRAVERSE_UPWARD, [](const std::shared_ptr<T>&) { return true; });
    }
    template<class T>
    std::shared_ptr<T> findParentType() const {
        return findImpl<T>(TRAVERSE_UPWARD, [](const std::shared_ptr<T>&) { return true; });
    }
    template<class T, class Predicate>
    std::shared_ptr<T> findParentType(Predicate predicate) {
        return findImpl<T, Predicate>(TRAVERSE_UPWARD, predicate);
    }
    template<class T, class Predicate>
    std::shared_ptr<T> findParentType(Predicate predicate) const {
        return findImpl<T, Predicate>(TRAVERSE_UPWARD, predicate);
    }
private:
    // implementation for all the traversals
    template<class Functor>
    TraversalAction traverseImpl(TraversalDirection, Functor);
    template<class Functor>
    TraversalAction traverseImpl(TraversalDirection, Functor) const;
 
    // implementation for traversals whose purpose is to find something
    template<class T, class Predicate>
    std::shared_ptr<T> findImpl(TraversalDirection, Predicate);
    template<class T, class Predicate>
    std::shared_ptr<T> findImpl(TraversalDirection, Predicate) const;
};
 
// ListNode declaration
 
template<class T>
class ListNode final: public Node {
public:
    //----------------------------------------
    // Read-only API delegated to 'children'
    //----------------------------------------
 
    size_t size() const {
        return children.size();
    }
 
    size_t max_size() const {
        return children.max_size();
    }
 
    size_t capacity() const {
        return children.capacity();
    }
 
    bool empty() const {
        return children.empty();
    }
 
    void reserve(size_t n) {
        children.reserve(n);
    }
 
    void shrink_to_fit() {
        children.shrink_to_fit();
    }
 
    const std::shared_ptr<T> at(size_t i) const {
        return std::dynamic_pointer_cast<T>(children.at(i));
    }
 
    const std::shared_ptr<T> operator[](size_t i) const {
        return std::dynamic_pointer_cast<T>(children[i]);
    }
 
    const std::shared_ptr<T> front() const {
        return std::dynamic_pointer_cast<T>(children.front());
    }
 
    const std::shared_ptr<T> back() const {
        return std::dynamic_pointer_cast<T>(children.back());
    }
 
    std::vector<std::shared_ptr<T> > elmts() const;
 
    Optional<size_t> index(const std::shared_ptr<T> &node, size_t startAt = 0) const;
 
    //----------------------------------------
    //              Modifying API
    //----------------------------------------
 
    void clear() {
        children.clear();
    }
    
    void push_back(const std::shared_ptr<T> &newChild) {
        children.insertAt(children.size(), newChild);
    }
 
    void setAt(size_t i, const std::shared_ptr<T> &child) {
        children.setAt(i, child);
    }
    void setAt(size_t i, std::nullptr_t) {
        children.setAt(i, nullptr);
    }
    void insertAt(size_t i, const std::shared_ptr<T> &newChild) {
        children.insertAt(i, newChild);
    }
 
    void eraseAt(size_t i) {
        children.eraseAt(i);
    }
 
    Optional<size_t> erase(const std::shared_ptr<T> &toErase, size_t startAt = 0);
};
 
//                        ____      _       _   _
//                       |  _ \ ___| | __ _| |_(_) ___  _ __  ___
//                       | |_) / _ \ |/ _` | __| |/ _ \| '_ \/ __|
//                       |  _ <  __/ | (_| | |_| | (_) | | | \__ |
//                       |_| \_\___|_|\__,_|\__|_|\___/|_| |_|___/
//
 
// ChildEdge<T> and ChildEdge<U>
template<class T, class U> bool operator==(const ChildEdge<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs.shared() == rhs.shared(); }
template<class T, class U> bool operator!=(const ChildEdge<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs.shared() != rhs.shared(); }
template<class T, class U> bool operator< (const ChildEdge<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs.shared() <  rhs.shared(); }
template<class T, class U> bool operator<=(const ChildEdge<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs.shared() <= rhs.shared(); }
template<class T, class U> bool operator> (const ChildEdge<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs.shared() >  rhs.shared(); }
template<class T, class U> bool operator>=(const ChildEdge<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs.shared() >= rhs.shared(); }
 
// ChildEdge<T> and nullptr
template<class T> bool operator==(const ChildEdge<T> &lhs, std::nullptr_t) noexcept { return lhs.shared() == nullptr; }
template<class T> bool operator!=(const ChildEdge<T> &lhs, std::nullptr_t) noexcept { return lhs.shared() != nullptr; }
template<class T> bool operator< (const ChildEdge<T> &lhs, std::nullptr_t) noexcept { return lhs.shared() <  nullptr; }
template<class T> bool operator<=(const ChildEdge<T> &lhs, std::nullptr_t) noexcept { return lhs.shared() <= nullptr; }
template<class T> bool operator> (const ChildEdge<T> &lhs, std::nullptr_t) noexcept { return lhs.shared() >  nullptr; }
template<class T> bool operator>=(const ChildEdge<T> &lhs, std::nullptr_t) noexcept { return lhs.shared() >= nullptr; }
 
// nullptr and ChildEdge<T>
template<class T> bool operator==(std::nullptr_t, const ChildEdge<T> &rhs) noexcept { return nullptr == rhs.shared(); }
template<class T> bool operator!=(std::nullptr_t, const ChildEdge<T> &rhs) noexcept { return nullptr != rhs.shared(); }
template<class T> bool operator< (std::nullptr_t, const ChildEdge<T> &rhs) noexcept { return nullptr <  rhs.shared(); }
template<class T> bool operator<=(std::nullptr_t, const ChildEdge<T> &rhs) noexcept { return nullptr <= rhs.shared(); }
template<class T> bool operator> (std::nullptr_t, const ChildEdge<T> &rhs) noexcept { return nullptr >  rhs.shared(); }
template<class T> bool operator>=(std::nullptr_t, const ChildEdge<T> &rhs) noexcept { return nullptr >= rhs.shared(); }
 
// ChildEdge<T> and std::shared_ptr<U>
template<class T, class U> bool operator==(const ChildEdge<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.shared() == rhs; }
template<class T, class U> bool operator!=(const ChildEdge<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.shared() != rhs; }
template<class T, class U> bool operator< (const ChildEdge<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.shared() <  rhs; }
template<class T, class U> bool operator<=(const ChildEdge<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.shared() <= rhs; }
template<class T, class U> bool operator> (const ChildEdge<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.shared() >  rhs; }
template<class T, class U> bool operator>=(const ChildEdge<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.shared() >= rhs; }
 
// std::shared_ptr<T> and ChildEdge<U>
template<class T, class U> bool operator==(const std::shared_ptr<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs == rhs.shared(); }
template<class T, class U> bool operator!=(const std::shared_ptr<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs != rhs.shared(); }
template<class T, class U> bool operator< (const std::shared_ptr<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs <  rhs.shared(); }
template<class T, class U> bool operator<=(const std::shared_ptr<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs <= rhs.shared(); }
template<class T, class U> bool operator> (const std::shared_ptr<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs >  rhs.shared(); }
template<class T, class U> bool operator>=(const std::shared_ptr<T> &lhs, const ChildEdge<U> &rhs) noexcept { return lhs >= rhs.shared(); }
 
// ParentEdge and nullptr
inline bool operator==(const ParentEdge &lhs, std::nullptr_t) noexcept { return lhs.shared() == nullptr; }
inline bool operator!=(const ParentEdge &lhs, std::nullptr_t) noexcept { return lhs.shared() != nullptr; }
inline bool operator< (const ParentEdge &lhs, std::nullptr_t) noexcept { return lhs.shared() <  nullptr; }
inline bool operator<=(const ParentEdge &lhs, std::nullptr_t) noexcept { return lhs.shared() <= nullptr; }
inline bool operator> (const ParentEdge &lhs, std::nullptr_t) noexcept { return lhs.shared() >  nullptr; }
inline bool operator>=(const ParentEdge &lhs, std::nullptr_t) noexcept { return lhs.shared() >= nullptr; }
 
// nullptr and ParentEdge
inline bool operator==(std::nullptr_t, const ParentEdge &rhs) noexcept { return nullptr == rhs.shared(); }
inline bool operator!=(std::nullptr_t, const ParentEdge &rhs) noexcept { return nullptr != rhs.shared(); }
inline bool operator< (std::nullptr_t, const ParentEdge &rhs) noexcept { return nullptr <  rhs.shared(); }
inline bool operator<=(std::nullptr_t, const ParentEdge &rhs) noexcept { return nullptr <= rhs.shared(); }
inline bool operator> (std::nullptr_t, const ParentEdge &rhs) noexcept { return nullptr >  rhs.shared(); }
inline bool operator>=(std::nullptr_t, const ParentEdge &rhs) noexcept { return nullptr >= rhs.shared(); }
 
// ParentEdge and std::shared_ptr<T>
template<class T> bool operator==(const ParentEdge &lhs, const std::shared_ptr<T> &rhs) noexcept { return lhs.shared() == rhs; }
template<class T> bool operator!=(const ParentEdge &lhs, const std::shared_ptr<T> &rhs) noexcept { return lhs.shared() != rhs; }
template<class T> bool operator< (const ParentEdge &lhs, const std::shared_ptr<T> &rhs) noexcept { return lhs.shared() <  rhs; }
template<class T> bool operator<=(const ParentEdge &lhs, const std::shared_ptr<T> &rhs) noexcept { return lhs.shared() <= rhs; }
template<class T> bool operator> (const ParentEdge &lhs, const std::shared_ptr<T> &rhs) noexcept { return lhs.shared() >  rhs; }
template<class T> bool operator>=(const ParentEdge &lhs, const std::shared_ptr<T> &rhs) noexcept { return lhs.shared() >= rhs; }
 
// std::shared_ptr<T> and ParentEdge
template<class T> bool operator==(const std::shared_ptr<T> &lhs, const ParentEdge &rhs) noexcept { return lhs == rhs.shared(); }
template<class T> bool operator!=(const std::shared_ptr<T> &lhs, const ParentEdge &rhs) noexcept { return lhs != rhs.shared(); }
template<class T> bool operator< (const std::shared_ptr<T> &lhs, const ParentEdge &rhs) noexcept { return lhs <  rhs.shared(); }
template<class T> bool operator<=(const std::shared_ptr<T> &lhs, const ParentEdge &rhs) noexcept { return lhs <= rhs.shared(); }
template<class T> bool operator> (const std::shared_ptr<T> &lhs, const ParentEdge &rhs) noexcept { return lhs >  rhs.shared(); }
template<class T> bool operator>=(const std::shared_ptr<T> &lhs, const ParentEdge &rhs) noexcept { return lhs >= rhs.shared(); }
 
// ParentEdge and ChildEdge<T>
template<class T> bool operator==(const ParentEdge &lhs, const ChildEdge<T> &rhs) noexcept { return lhs.shared() == rhs.shared(); }
template<class T> bool operator!=(const ParentEdge &lhs, const ChildEdge<T> &rhs) noexcept { return lhs.shared() != rhs.shared(); }
template<class T> bool operator< (const ParentEdge &lhs, const ChildEdge<T> &rhs) noexcept { return lhs.shared() <  rhs.shared(); }
template<class T> bool operator<=(const ParentEdge &lhs, const ChildEdge<T> &rhs) noexcept { return lhs.shared() <= rhs.shared(); }
template<class T> bool operator> (const ParentEdge &lhs, const ChildEdge<T> &rhs) noexcept { return lhs.shared() >  rhs.shared(); }
template<class T> bool operator>=(const ParentEdge &lhs, const ChildEdge<T> &rhs) noexcept { return lhs.shared() >= rhs.shared(); }
 
// ChildEdge<T> and ParentEdge
template<class T> bool operator==(const ChildEdge<T> &lhs, const ParentEdge &rhs) noexcept { return lhs.shared() == rhs.shared(); }
template<class T> bool operator!=(const ChildEdge<T> &lhs, const ParentEdge &rhs) noexcept { return lhs.shared() != rhs.shared(); }
template<class T> bool operator< (const ChildEdge<T> &lhs, const ParentEdge &rhs) noexcept { return lhs.shared() <  rhs.shared(); }
template<class T> bool operator<=(const ChildEdge<T> &lhs, const ParentEdge &rhs) noexcept { return lhs.shared() <= rhs.shared(); }
template<class T> bool operator> (const ChildEdge<T> &lhs, const ParentEdge &rhs) noexcept { return lhs.shared() >  rhs.shared(); }
template<class T> bool operator>=(const ChildEdge<T> &lhs, const ParentEdge &rhs) noexcept { return lhs.shared() >= rhs.shared(); }
 
//                        ___                 _                           _        _   _
//                       |_ _|_ __ ___  _ __ | | ___ _ __ ___   ___ _ __ | |_ __ _| |_(_) ___  _ __  ___
//                        | || '_ ` _ \| '_ \| |/ _ \ '_ ` _ \ / _ \ '_ \| __/ _` | __| |/ _ \| '_ \/ __|
//                        | || | | | | | |_) | |  __/ | | | | |  __/ | | | || (_| | |_| | (_) | | | \__ |
//                       |___|_| |_| |_| .__/|_|\___|_| |_| |_|\___|_| |_|\__\__,_|\__|_|\___/|_| |_|___/
//                                     |_|
//
 
// ChildEdge implementation
 
template<class T>
ChildEdge<T>::ChildEdge(Node *container)
    : container_(container), idx_(container->children.appendEdge(nullptr)) {
    ASSERT_not_null(container_);
}
 
template<class T>
ChildEdge<T>::ChildEdge(Node *container, const std::shared_ptr<T> &child)
    : container_(container), idx_(container->children.appendEdge(child)) {
    ASSERT_not_null(container_);
}
 
template<class T>
std::shared_ptr<T>
ChildEdge<T>::shared() const {
    return std::dynamic_pointer_cast<T>(container_->children[this->idx_]);
}
 
template<class T>
void
ChildEdge<T>::assign(const NodePtr &newChild) {
    container_->children.setAt(idx_, newChild);
}
 
// ParentEdge implementation
 
NodePtr
ParentEdge::shared() const {
    return parent_ ? parent_->shared_from_this() : NodePtr();
}
 
// Children implementation
 
Children::Children(Node *container)
    : container_(container) {
    ASSERT_not_null(container);
}
 
size_t
Children::appendEdge(const NodePtr &child) {
    size_t idx = children_.size();
    children_.push_back(nullptr);
    setAt(idx, child);
    return idx;
}
 
void
Children::checkInsertionConsistency(const NodePtr &newChild, const NodePtr &oldChild, Node *parent) {
    ASSERT_not_null(parent);
 
    if (newChild && newChild != oldChild) {
        if (newChild->parent != nullptr) {
            if (newChild->parent.shared().get() == parent) {
                throw ConsistencyException(newChild, "node is already a child of the parent");
            } else {
                throw ConsistencyException(newChild, "node is already attached to a tree");
            }
        }
 
        for (Node *ancestor = parent; ancestor; ancestor = ancestor->parent.parent_) {
            if (newChild.get() == ancestor)
                throw ConsistencyException(newChild, "node insertion would introduce a cycle");
        }
    }
}
 
void
Children::setAt(size_t idx, const NodePtr &newChild) {
    ASSERT_require(idx < children_.size());
    NodePtr oldChild = children_[idx];
    checkInsertionConsistency(newChild, oldChild, container_);
    if (oldChild)
        oldChild->parent.reset();
    children_[idx] = newChild;
    if (newChild)
        newChild->parent.set(container_);
}
 
void
Children::insertAt(size_t idx, const NodePtr &child) {
    ASSERT_require(idx <= children_.size());
    checkInsertionConsistency(child, nullptr, container_);
    children_.insert(children_.begin() + idx, child);
    if (child)
        child->parent.set(container_);
}
 
void
Children::eraseAt(size_t idx) {
    ASSERT_require(idx < children_.size());
    if (children_[idx])
        children_[idx]->parent.reset();
    children_.erase(children_.begin() + idx);
}
 
void
Children::clear() {
    while (!children_.empty()) {
        if (children_.back())
            children_.back()->parent.reset();
        children_.pop_back();
    }
}
 
// Node implementation
 
//----------------------------------------
// traverseImpl
//----------------------------------------
template<class Functor>
TraversalAction
Node::traverseImpl(TraversalDirection direction, Functor functor) {
    switch (TraversalAction action = functor(this->shared_from_this(), ENTER)) {
        case CONTINUE:
            if (TRAVERSE_DOWNWARD == direction) {
                for (size_t i=0; i<children.size() && CONTINUE==action; ++i) {
                    if (children[i])
                        action = children[i]->traverseImpl<Functor>(direction, functor);
                }
            } else if (parent) {
                action = parent->traverseImpl<Functor>(direction, functor);
            }
            // fall through
        case SKIP_CHILDREN:
            if (ABORT != action && (action = functor(this->shared_from_this(), LEAVE)) == SKIP_CHILDREN)
                action = CONTINUE;
            // fall through
        default:
            return action;
    }
}
 
template<class Functor>
TraversalAction
Node::traverseImpl(TraversalDirection direction, Functor functor) const {
    switch (TraversalAction action = functor(this->shared_from_this(), ENTER)) {
        case CONTINUE:
            if (TRAVERSE_DOWNWARD == direction) {
                for (size_t i=0; i<children.size() && CONTINUE==action; ++i) {
                    if (children[i])
                        action = children[i]->traverseImpl<Functor>(direction, functor);
                }
            } else if (parent) {
                action = parent->traverseImpl<Functor>(direction, functor);
            }
            // fall through
        case SKIP_CHILDREN:
            if (ABORT != action && (action = functor(this->shared_from_this(), LEAVE)) == SKIP_CHILDREN)
                action = CONTINUE;
            // fall through
        default:
            return action;
    }
}
 
//----------------------------------------
// traverseType
//----------------------------------------
 
template<class T, class Functor>
struct TraverseTypeHelper {
    Functor functor;
 
    TraverseTypeHelper(Functor functor)
        : functor(functor) {}
 
    TraversalAction operator()(const NodePtr &node, TraversalEvent event) {
        if (std::shared_ptr<T> typed = std::dynamic_pointer_cast<T>(node)) {
            return functor(typed, event);
        } else {
            return CONTINUE;
        }
    }
};
 
template<class T, class Functor>
TraversalAction
Node::traverseType(Functor functor) {
    return traverseImpl(TRAVERSE_DOWNWARD, TraverseTypeHelper<T, Functor>(functor));
}
 
template<class T, class Functor>
TraversalAction
Node::traverseType(Functor functor) const {
    return traverseImpl(TRAVERSE_DOWNWARD, TraverseTypeHelper<T, Functor>(functor));
}
 
//----------------------------------------
// findImpl
//----------------------------------------
template<class T, class Predicate>
std::shared_ptr<T>
Node::findImpl(TraversalDirection direction, Predicate predicate) {
    std::shared_ptr<T> found;
    traverseImpl(direction,
                 [&predicate, &found](const NodePtr &node, TraversalEvent event) {
                     if (ENTER == event) {
                         std::shared_ptr<T> typedNode = std::dynamic_pointer_cast<T>(node);
                         if (typedNode && predicate(typedNode)) {
                             found = typedNode;
                             return ABORT;
                         }
                     }
                     return CONTINUE;
                 });
    return found;
}
 
template<class T, class Predicate>
std::shared_ptr<T>
Node::findImpl(TraversalDirection direction, Predicate predicate) const {
    std::shared_ptr<T> found;
    traverseImpl(direction,
                 [&predicate, &found](const ConstNodePtr &node, TraversalEvent event) {
                     if (ENTER == event) {
                         std::shared_ptr<const T> typedNode = std::dynamic_pointer_cast<const T>(node);
                         if (typedNode && predicate(typedNode)) {
                             found = typedNode;
                             return ABORT;
                         }
                     }
                     return CONTINUE;
                 });
    return found;
}
 
// ListNode implementation
 
template<class T>
std::vector<std::shared_ptr<T> >
ListNode<T>::elmts() const {
    std::vector<std::shared_ptr<T> > retval;
    retval.reserve(children.size());
    for (size_t i = 0; i < children.size(); ++i)
        retval.push_back(std::dynamic_pointer_cast<T>(children[i]));
    return retval;
}
 
template<class T>
Optional<size_t>
ListNode<T>::index(const std::shared_ptr<T> &node, size_t startAt) const {
    for (size_t i = startAt; i < children.size(); ++i) {
        if (children[i] == node)
            return i;
    }
    return Nothing();
}
 
template<class T>
Optional<size_t>
ListNode<T>::erase(const std::shared_ptr<T> &toErase, size_t startAt) {
    Optional<size_t> where = index(toErase, startAt);
    if (where)
        children.eraseAt(*where);
    return where;
}
 
} // namespace
} // namespace
 
#endif