Tree/Base.h

#ifndef ROSE_Tree_Base_H
#define ROSE_Tree_Base_H
#include <Rose/Tree/Exception.h>

#include <Sawyer/Assert.h>

#include <boost/lexical_cast.hpp>
#include <memory>
#include <string>
#include <vector>

namespace Rose {
namespace Tree {

// ReverseEdge

// Internal. The only purpose of this class is so that the a forward edge has permission to change the parent pointer in an
// reverse edge.
class ReverseEdgeAccess {
protected:
    void resetParent(ReverseEdge&);
    void setParent(ReverseEdge&, Base&);
};

class ReverseEdge {
    Base &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.
    Base *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(Base &child);                  // internal use only

public:
    BasePtr operator()() const;
    BasePtr operator->() const;
    bool operator==(const BasePtr&) const;
    bool operator!=(const BasePtr&) 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
    friend class ReverseEdgeAccess;
    void reset();
    void set(Base&);
};

// Edge

template<class T>
class Edge: protected ReverseEdgeAccess {
public:
    using Child = T;

    using ChildPtr = std::shared_ptr<T>;

private:
    Base &parent_;                                      // required parent owning this child edge
    ChildPtr child_;                                    // optional child to which this edge points

public:
    // No default constructor and not copyable.
    Edge() = delete;
    Edge(const Edge&) = delete;
    Edge& operator=(const Edge&) = delete;

public:
    ~Edge();

    explicit Edge(Base &parent);
    Edge(Base &parent, const ChildPtr &child);
    const ChildPtr& operator->() const;
    const ChildPtr& operator()() const;
    bool operator==(const std::shared_ptr<Base>&) const;
    bool operator!=(const std::shared_ptr<Base>&) 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);
    Edge& operator=(const ReverseEdge&);
    explicit operator bool() const {
        return child_ != nullptr;
    }
};

// Base

class Base: public std::enable_shared_from_this<Base> {
public:
    using Ptr = BasePtr;

    enum class Traversal {
        ENTER,                                          
        LEAVE                                           
    };

protected:
    struct ChildDescriptor {
        size_t i;                                       
        std::string name;                               
        Ptr value;                                      
    };

public:
    ReverseEdge parent;

public:
    virtual ~Base() {}

protected:
    virtual void destructorHelper() {}

protected:
    Base();

public:
    Ptr pointer();

    template<class Visitor>
    auto traverseReverse(const Visitor &visitor) {
        for (auto node = pointer(); node; node = node->parent()) {
            if (auto result = visitor(node))
                return result;
        }
        return decltype(visitor(BasePtr()))();
    }

    template<class Visitor>
    auto traverse(const Visitor &visitor) {
        if (auto retval = visitor(this->pointer(), Traversal::ENTER))
            return retval;
        for (size_t i = 0; true; ++i) {
            const ChildDescriptor child = findChild(i);
            if (child.i < i) {
                break;
            } else if (child.value) {
                if (auto retval = child.value->traverse(visitor))
                    return retval;
            }
        }
        return visitor(this->pointer(), Traversal::LEAVE);
    }

    template<class T>
    std::shared_ptr<T> findAncestor() {
        return visitParents([](const BasePtr &vertex) -> std::shared_ptr<T> {
                return std::dynamic_pointer_cast<T>(vertex);
            });
    };

    template<class T>
    std::vector<std::shared_ptr<T>> findDescendants() {
        std::vector<std::shared_ptr<T>> retval;
        traverse([&retval](const BasePtr &vertex, Traversal event) {
            if (Traversal::ENTER == event) {
                if (auto found = std::dynamic_pointer_cast<T>(vertex))
                    retval.push_back(found);
            }
        });
        return retval;
    }

    std::string childName(size_t i);

    Ptr child(size_t i);

    size_t nChildren(size_t i);

protected:
    virtual ChildDescriptor findChild(size_t i) const;
};

// Template implementations

template<class T>
bool
ReverseEdge::operator==(const Edge<T> &other) const {
    return parent_ == other();
}

template<class T>
bool
ReverseEdge::operator!=(const Edge<T> &other) const {
    return parent_ != other();
}

template<class T>
Edge<T>::~Edge() {
    if (child_)
        resetParent(child_->parent);
}

template<class T>
Edge<T>::Edge(Base &parent)
    : parent_(parent) {}

template<class T>
Edge<T>::Edge(Base &parent, const std::shared_ptr<T> &child)
    : parent_(parent), child_(child) {
    if (child) {
        if (child->parent)
            throw InsertionError(child);
        setParent(child->parent, parent);
    }
}

template<class T>
const std::shared_ptr<T>&
Edge<T>::operator->() const {
    ASSERT_not_null(child_);
    return child_;
}

template<class T>
const std::shared_ptr<T>&
Edge<T>::operator()() const {
    return child_;
}

template<class T>
bool
Edge<T>::operator==(const BasePtr &ptr) const {
    return child_ == ptr;
}

template<class T>
bool
Edge<T>::operator!=(const BasePtr &ptr) const {
    return child_ != ptr;
}

template<class T>
bool
Edge<T>::operator==(const ReverseEdge &other) const {
    return child_ == other();
}

template<class T>
bool
Edge<T>::operator!=(const ReverseEdge &other) const {
    return child_.get() != other();
}

template<class T>
template<class U>
bool
Edge<T>::operator==(const Edge<U> &other) const {
    return child_.get() == other.get();
}

template<class T>
template<class U>
bool
Edge<T>::operator!=(const Edge<U> &other) const {
    return child_.get() != other.get();
}

template<class T>
Edge<T>&
Edge<T>::operator=(const std::shared_ptr<T> &child) {
    if (child != child_) {
        // Check for errors
        if (child) {
            if (child->parent)
                throw InsertionError(child);
#ifndef NDEBUG
            parent_.traverseReverse([&child](const BasePtr &node) {
                if (child == node) {
                    throw CycleError(child);
                } else {
                    return false;
                }
            });
#endif
        }

        // Unlink the child from the tree
        if (child_) {
            resetParent(child_->parent);
            child_.reset();                             // parent-to-child edge
        }

        // Link new child into the tree
        if (child) {
            setParent(child->parent, parent_);
            child_ = child;
        }
    }
    return *this;
}

template<class T>
Edge<T>&
Edge<T>::operator=(const ReverseEdge &parent) {
    return (*this) = parent();
}

} // namespace
} // namespace
#endif