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_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 <memory>
#include <string>
#include <vector>

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;

        virtual ~EdgeBase() {}
        EdgeBase() = delete;
        EdgeBase(const EdgeBase&) = delete;
        EdgeBase& operator=(const EdgeBase&) = delete;
        explicit EdgeBase(EdgeBase *prev)
            : prev(prev) {}

        // 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 Vertex* 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))();
        }
    };

    // 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:
        UserBase &parent_;                              // required parent owning this child edge
        ChildPtr child_;                                // optional child to which this edge points

    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 &child) {
            if (child != child_) {
                checkChildInsertion(child);

                // 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 (child) {
                    child->parent.set(parent_);
                    child_ = child;
                }
            }
            return *this;
        }

        Edge& operator=(const ReverseEdge &parent) {
            return (*this) = parent();
        }
        explicit operator bool() const {
            return child_ != nullptr;
        }

    private:
        void checkChildInsertion(const ChildPtr &child) const;

        size_t size() const override {
            return 1;
        }

        Vertex* pointer(size_t i) const override {
            ASSERT_always_require(0 == i);
            return child_.get();
        }
    };

    // 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>>>;

    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:
        UserBase &parent_;                              // required parent owning this child edge
        Vector edges_;

    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) {
            auto edge = std::unique_ptr<Edge<Child>>(new Edge<Child>(Link::NO, parent_, elmt));
            edges_.push_back(std::move(edge));
        }

        void pop_back() {
            ASSERT_forbid(edges_.empty());
            edges_.pop_back();
        }

        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());
        }

    protected:
        Vertex* pointer(size_t i) const override {
            return at(i)().get();
        }
    };

    // Vertex
public:
    ReverseEdge parent;
    EdgeBase *treeEdges_ = nullptr;

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_(parent) {
    parent_.treeEdges_ = this;
}

template<class B>
template<class T>
Vertex<B>::Edge<T>::Edge(UserBase &parent, const std::shared_ptr<T> &child)
    : EdgeBase(parent.treeEdges_), parent_(parent), child_(child) {
    checkChildInsertion(child);
    parent_.treeEdges_ = this;                          // must be after checkChildInsertin for exception safety
    if (child)
        child->parent.set(parent);
}

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_(parent), child_(child) {
    checkChildInsertion(child);
    if (Link::YES == link)
        parent_.treeEdges_ = this;                      // must be after checkChildInsertin for exception safety
    if (child)
        child->parent.set(parent);
}

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 = &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_(parent) {
    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