#ifndef Toolbox_Node_H
#define Toolbox_Node_H
#include <algorithm>
#include <queue>
#include <vector>
namespace Toolbox {
    template<typename That>
    class Node {
    public:
        explicit Node() = default;
        int index() {
            if (!father) return -1;
            auto it = std::find(father->sons.begin(), father->sons.end(), static_cast<That *>(this));
            if (it == father->sons.end()) return -1;
            return static_cast<int>(std::distance(father->sons.begin(), it));
        }
        bool root() { return !father; }
        bool leaf() { return sons.empty(); }
        bool first() {
            if (!father) return false;
            return this == father->sons.front();
        }
        bool last() {
            if (!father) return false;
            return this == father->sons.back();
        }
        That *previous() {
            if (!father) return nullptr;
            int i = index() - 1;
            if (i < 0) return nullptr;
            return father->sons[i];
        }
        That *next() {
            if (!father) return nullptr;
            int i = index() + 1;
            if (i <= 0 || i >= static_cast<int>(father->sons.size())) return nullptr;
            return father->sons[i];
        }
        That *last_child() {
            if (sons.empty()) return nullptr;
            return sons.back();
        }
        That *first_child() {
            if (sons.empty()) return nullptr;
            return sons.front();
        }
        That *root_node() {
            That *ret = static_cast<That *>(this);
            while (ret->father != nullptr) {
                ret = ret->father;
            }
            return ret;
        }
        int deep() {
            That *ret = static_cast<That *>(this);
            int depth = 0;
            while (ret->father != nullptr) {
                ret = ret->father;
                depth++;
            }
            return depth;
        }
        std::vector<That *> deep_traversed() {
            std::vector<That *> ret;
            ret.push_back(static_cast<That *>(this));
            for (auto &child: sons) {
                std::vector<That *> child_values = child->deep_traversed();
                ret.insert(ret.end(), child_values.begin(), child_values.end());
            }
            return ret;
        }
        std::vector<That *> sequence_traversed() {
            std::vector<That *> ret;
            std::queue<That *> que;
            That *that = static_cast<That *>(this);
            que.push(that);
            while (!que.empty()) {
                That *cur = que.front();
                que.pop();
                int n = static_cast<int>(cur->sons.size());
                ret.push_back(cur);
                for (int i = 0; i < n; ++i) {
                    que.push(cur->sons[i]);
                }
            }
            return ret;
        }
        std::vector<That *> descendants() {
            std::vector<That *> ret = sequence_traversed();
            if (!ret.empty()) ret.erase(ret.begin());
            return ret;
        }
        That *father = nullptr;
        std::vector<That *> sons;
    };
    template<typename NodeType>
    class Node_Manager {
    public:
        std::vector<NodeType *> roots;
    };
}
#endif
