#pragma once

#include "DepthInTree.h"

#include "detect_utils.h"

#include <type_traits>
#include <stack>

namespace xxx::traverse_detail {

template <typename T>
T stack_extract(std::stack<T> & stack) {
    auto r = stack.top();
    stack.pop();
    return r;
}

template <typename node_t>
auto get_neighbours(const node_t node) {
    return std::pair{node->child(), node->sibling()};
}

class Depth {
    DepthInTree::value_type       m_value = 0;
    std::stack<decltype(m_value)> m_stack;

public:
    template <typename node_t>
    inline auto operator() (const node_t node) noexcept {
        auto [child, sibling] = get_neighbours(node);
        const auto depth = m_value;
        if (child) {
            if (sibling) m_stack.push(m_value);
            return DepthInTree{m_value++};
        }

        if (!(sibling || m_stack.empty()))
            m_value = stack_extract(m_stack);

        return DepthInTree{depth};
    }
};

template <typename node_t>
class PostProcess {
    std::stack<node_t> m_stack;

public:
    template <typename Action>
    inline auto operator() (const node_t node, Action & action) noexcept {
        m_stack.push(node);
        if (node->child())
            return;

        while (!m_stack.empty()) {
            action.post_process(m_stack.top());
            if (stack_extract(m_stack)->sibling())
                break;
        }
    }
};

template <typename T, typename node_t>
struct action_traits {
private:
    template <typename U>
    using is_mem_fn_ptr = std::is_member_function_pointer<U>;

    template <typename U>
    using interrupt = decltype(is_mem_fn_ptr<decltype(&U::interrupt)>::value);

    template <typename U>
    using skip = decltype(is_mem_fn_ptr<decltype(&U::skip)>::value);

    template <typename U>
    using result = decltype(is_mem_fn_ptr<decltype(&U::result)>::value);

    template <typename U>
    using process = decltype(is_mem_fn_ptr<decltype(&U::process)>::value);

    template <typename U>
    using post_process = decltype(is_mem_fn_ptr<decltype(&U::post_process)>::value);

    template <typename U>
    using depth = decltype(is_mem_fn_ptr<decltype(&U::set_depth)>::value);

public:
    static constexpr const bool processible      = is_detected<process, T>;
    static constexpr const bool post_processible = is_detected<post_process, T>;
    static constexpr const bool require_depth    = is_detected<depth, T>;
    static constexpr const bool interruptable    = is_detected<interrupt, T>;
    static constexpr const bool skippable        = is_detected<skip, T>;
    static constexpr const bool returns_result   = is_detected<result, T>;
    static constexpr const bool is_lambda        = std::is_invocable_v<T, node_t>;

    using depth_t = std::conditional_t<
        require_depth,
        Depth, void
    >;

    using post_process_t = std::conditional_t<
        post_processible,
        PostProcess<node_t>, void
    >;

    static_assert(is_lambda || processible || post_processible, "");

    static_assert(!(is_lambda && (processible || post_processible)), "");
};


template <typename node_t>
class event_tree_adapter {
    class iterator;

    mutable std::stack<node_t> m_stack;

    const node_t   m_front;
    const iterator m_begin;
    const iterator m_end;

public:
    explicit event_tree_adapter (const node_t front) :
        m_front {front},
        m_begin {iterator{m_front, m_stack}},
        m_end   {iterator{nullptr, m_stack}}
    {}

    auto begin() const noexcept {
        return m_begin;
    }

    auto end() const noexcept {
        return m_end;
    }
};

template <typename node_t>
class event_tree_adapter<node_t>::iterator :
        public std::iterator<std::forward_iterator_tag, node_t>
{
    node_t               m_current;
    std::stack<node_t> & m_stack;

public:
    explicit iterator (const node_t node, std::stack<node_t> & stack) noexcept :
        m_current {node},
        m_stack   {stack}
    {}

    auto operator * () const noexcept {
        return m_current;
    }

    auto operator -> () const noexcept {
        return **this;
    }
     // prefix
    auto operator ++ () {
        if (auto [child, sibling] = get_neighbours(m_current); child) {
            m_current = child;
            if (sibling) m_stack.push(sibling);
        }
        else if (sibling)           m_current = sibling;
        else if (!m_stack.empty())  m_current = stack_extract(m_stack);
        else                        m_current = nullptr;
        return *this;
    }

     // postfix
    auto operator ++ (int) noexcept {
        return iterator{*this++};
    }

    auto next() const noexcept {
        return ++iterator{*this};
    }

    bool operator == (const iterator & other) const noexcept {
        return m_current == other.m_current;
    }

    bool operator != (const iterator & other) const noexcept {
        return ! operator == (other);
    }

};

} // namespace xxx::traverse_detail