#include <memory> // std::unique_ptr
#include <vector>
using std::vector;

// abstract visitor
struct visitor {
    virtual ~visitor(void) {};
    virtual void visit(struct realConstantNode &) = 0;
    virtual void visit(struct sinNode &) = 0;
};

// node hierarchy
struct node {
    node() {};
    virtual ~node(void) {};
    virtual void accept(visitor &) = 0;
};
struct terminalNode : public virtual node {
};
struct nonterminalNode : public virtual node {
    virtual void add_child(node* child) = 0;
};
struct unaryNode : public virtual nonterminalNode {
    std::unique_ptr<node> child;
    void add_child(node * child) {
        this->child = std::unique_ptr<node>(child);
    };
};

// sample terminal node
struct realConstantNode : public terminalNode {
    realConstantNode(double value) : value(value) {};
    double value;
    void accept(visitor & vis) {
        vis.visit(*this);
    };
};

// sample nonterminal node
struct sinNode : public unaryNode {
    void accept(visitor & vis) {
        vis.visit(*this);
    };
};

// copy visitor
template<typename copyNodeType>
struct copyCreator : public visitor {
    copyCreator() {}
    copyCreator(node * firstVisit) {
        firstVisit->accept(*this);
    }
    ~copyCreator() {
        copy.reset();
        for(auto ptr : openList) {
            delete ptr;
        }
    }

    std::unique_ptr<copyNodeType> copy = 0;
    vector<nonterminalNode *> openList;
    bool error = true;

    // push to tree
    template<typename nodeType> // templated bc we want a specific handle, not
    bool push(nodeType * ptr) { // a generic node * that we need to cast!
        if (copy) {
            openList.back()->add_child(ptr); // if root is set, append to tree
        }
        else {
            //setCopy<nodeType>(ptr);
            auto temp = dynamic_cast<copyNodeType *>(ptr);
            if(temp) {
                copy = std::unique_ptr<copyNodeType>(temp);
                error = false;
            }
            else {
                /*
                 Is there a nicer way to dispose of the newly created node `ptr`
                 or `next` other than checking the return value and wrapping the
                 entire visit method of all nodes in an if statement?
                */
                return false;
            }
        }
        return true;
    }

    void visit(struct realConstantNode & nod) {
        auto next = new realConstantNode(nod.value);
        if(!push(next)) {
            delete next;
        }
    }

    void visit(struct sinNode & nod) {
        auto next = new sinNode;
        if(push(next)) {
            openList.push_back(next);
            nod.child->accept(*this);
            openList.pop_back();
        }
        else {
            delete next;
        }
    };
};

int main(int argc, const char * argv[]) {

    sinNode s;
    auto pi = new realConstantNode(3.141);
    s.add_child(pi); // s.child now owns pi

    // These three versions of calling the copyCreator are possible!
    copyCreator<sinNode> cpy0;
    s.accept(cpy0);

    copyCreator<sinNode> cpy1;
    cpy1.visit(s);

    copyCreator<sinNode> cpy2(&s);

    // If we visit pi directly, we cannot create a copy of a sinNode!
    copyCreator<sinNode> cpy3(pi);
    return 0;
};

// copy visitor
template<typename copyNodeType>
struct copyCreator : public visitor {
    copyCreator() {}
    copyCreator(node * firstVisit) {
        firstVisit->accept(*this);
    }
    ~copyCreator() {}

    std::unique_ptr<copyNodeType> copy = nullptr;
    vector<nonterminalNode *> openList;
    bool error = true;

    bool has_root()
    {
        return copy != nullptr;
    }

    template<typename node_type>
    bool check_is_root(node_type *ptr)
    {
        if (has_root()) return false; // already found root

        return std::is_base_of<copyNodeType, node_type>::value;
    }

    template<typename node_type>
    void set_root(std::unique_ptr<node_type> ptr)
    {
        copy = std::unique_ptr<copyNodeType>(ptr.release());
        error = false;
    }

    template<typename node_type>
    void push_terminal(std::unique_ptr<node_type> ptr)
    {
        if (has_root() && openList.back() != nullptr)
        {
            openList.back()->add_child(ptr.release());
        }
        else if(check_is_root(ptr.get())) {
            set_root(std::move(ptr));
        }
    }

    template<typename node_type>
    bool push_nonterminal(std::unique_ptr<node_type> ptr)
    {
        if (has_root() && openList.back() != nullptr) {
            auto raw_ptr = ptr.release();

            openList.back()->add_child(raw_ptr);
            openList.push_back(raw_ptr);

            return true;
        }
        else if (check_is_root(ptr.get()))
        {
            set_root(std::move(ptr));

            openList.push_back(copy.get());

            return true;
        }

        return false;
    }

    void pop_nonterminal()
    {
        openList.pop_back();
    }

    void visit(realConstantNode& nod) override {
        auto next = std::make_unique<realConstantNode>(nod.value);
        push_terminal(std::move(next));
    }

    void visit(sinNode& nod) override {
        auto next = std::make_unique<sinNode>();

        if (push_nonterminal(std::move(next))) {
            nod.child->accept(*this);
            pop_nonterminal();
        }
    };
};