Kylin/DataStructure/GeneralTree.h

#ifndef GENERALTREE_H
#define GENERALTREE_H

#include "LinkedList.h"
#include "LinkedQueue.h"
#include "Tree.h"

namespace Kylin {

template <typename T>
class GeneralTreeNode : public TreeNode<T> {
public:
    GeneralTreeNode(const T &value, TreeNode<T> *parent = nullptr) : TreeNode<T>(value, parent) {}
    LinkedList<GeneralTreeNode<T> *> children;
};

template <typename T>
class GeneralTree : public Tree<T> {
public:
    class Iterator {
    public:
        Iterator(GeneralTreeNode<T> *pos) : m_pos(pos) {}
        bool operator!=(const Iterator &other) { return (m_pos != other.m_pos); }
        T &operator*() { return m_pos->value; }
        Iterator &operator++() {
            auto &children = m_pos->children;
            for (auto &child : children) {
                m_queue.enqueue(child);
            }
            m_pos = m_queue.empty() ? nullptr : m_queue.dequeue();
            return *this;
        }

    private:
        GeneralTreeNode<T> *m_pos = nullptr;
        LinkedQueue<GeneralTreeNode<T> *> m_queue;
    };

    GeneralTree() = default;

    GeneralTree(GeneralTree &&other) {
        this->m_root = other.m_root;
        other.m_root = nullptr;
    }

    ~GeneralTree() { clear(); }

    bool insert(TreeNode<T> *node) {
        bool ret = false;
        auto n = dynamic_cast<GeneralTreeNode<T> *>(node);
        if (n == nullptr) THROW_EXCEPTION(InvalidParameterException, "the node must is GeneralTreeNode.");
        if (this->m_root == nullptr) {
            this->m_root = node;
            node->parent = nullptr;
            ret = true;
        } else {
            if (!find(n->parent)) return false;
            auto parent = dynamic_cast<GeneralTreeNode<T> *>(node->parent);
            parent->children.append(n);
            ret = true;
        }
        return ret;
    }

    /**
     * @brief 插入成功返回TreeNode的地址，否则nullptr
     */
    GeneralTreeNode<T> *insert(const T &value, TreeNode<T> *parent) {
        auto ret = new GeneralTreeNode<T>(value, parent);
        if (ret == nullptr)
            THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to insert an element.");
        bool status = insert(ret);
        if (!status) {
            delete ret;
            ret = nullptr;
        }
        return ret;
    }

    GeneralTree<T> remove(const T &value) {
        auto node = find(value);
        return node == nullptr ? GeneralTree<T>() : remove(node);
    }

    GeneralTree<T> remove(const GeneralTreeNode<T> *node) {
        if (node == nullptr) return GeneralTree<T>();
        GeneralTree<T> tree;
        auto n = const_cast<GeneralTreeNode<T> *>(node);
        if (n == this->m_root) {
            this->m_root = nullptr;
            tree.m_root = n;
            return tree;
        }
        auto parent = dynamic_cast<GeneralTreeNode<T> *>(n->parent);
        auto &children = parent->children;
        auto pos = children.indexOf(n);
        if (pos == LinkedList<T>::npos) return GeneralTree<T>();
        children.removeAt(pos);
        tree.m_root = n;
        return tree;
    }

    GeneralTreeNode<T> *find(const T &value) const {
        return find(dynamic_cast<GeneralTreeNode<T> *>(this->m_root), value);
    }

    bool find(TreeNode<T> *node) const override {
        return find(dynamic_cast<GeneralTreeNode<T> *>(this->m_root),
                    dynamic_cast<GeneralTreeNode<T> *>(node));
    }

    GeneralTreeNode<T> *root() const { return dynamic_cast<GeneralTreeNode<T> *>(this->m_root); }

    int count() const { return count(dynamic_cast<GeneralTreeNode<T> *>(this->m_root)); }

    int degree() const { return degree(dynamic_cast<GeneralTreeNode<T> *>(this->m_root)); }

    int height() const { return height(dynamic_cast<GeneralTreeNode<T> *>(this->m_root)); }

    void clear() {
        destroy(dynamic_cast<GeneralTreeNode<T> *>(this->m_root));
        this->m_root = nullptr;
    }

    Iterator begin() { return Iterator(dynamic_cast<GeneralTreeNode<T> *>(this->m_root)); }
    Iterator end() { return Iterator(nullptr); }

    GeneralTree &operator=(GeneralTree &&other) {
        if (&other != this) {
            auto root(this->m_root);
            this->m_root = other.m_root;
            other.m_root = root;
        }
        return *this;
    }

protected:
    /**
     * @brief 以Node为根节点的GeneralTree,查找的值为value的GeneralTreeNode
     */
    GeneralTreeNode<T> *find(const GeneralTreeNode<T> *node, const T &value) const {
        if (node == nullptr) return nullptr;
        if (node->value == value) return const_cast<GeneralTreeNode<T> *>(node);
        GeneralTreeNode<T> *ret = nullptr;
        auto &children = const_cast<LinkedList<GeneralTreeNode<T> *> &>(node->children);
        for (auto &child : children) {
            ret = find(child, value);
            if (ret != nullptr) break;
        }
        return ret;
    }

    /**
     * @brief find 在node子树中查找obj
     */
    GeneralTreeNode<T> *find(const GeneralTreeNode<T> *node, const GeneralTreeNode<T> *obj) const {
        if (node == nullptr) return nullptr;
        if (node == obj) return const_cast<GeneralTreeNode<T> *>(node);
        GeneralTreeNode<T> *result = nullptr;
        auto &children = const_cast<LinkedList<GeneralTreeNode<T> *> &>(node->children);
        for (auto &child : children) {
            result = find(child, obj);
            if (result != nullptr) break;
        }
        return result;
    }

    void destroy(GeneralTreeNode<T> *node) {
        if (node == nullptr) return;
        auto &children = node->children;
        for (auto &child : children) {
            destroy(child);
        }
        delete node;
    }

    int count(const GeneralTreeNode<T> *node) const {
        if (node == nullptr) return 0;
        int ret = 1;
        auto &children = const_cast<LinkedList<GeneralTreeNode<T> *> &>(node->children);
        for (auto &child : children) {
            ret += count(child);
        }
        return ret;
    }

    int height(const GeneralTreeNode<T> *node) const {
        if (node == nullptr) return 0;
        int ret = 0;
        auto &children = const_cast<LinkedList<GeneralTreeNode<T> *> &>(node->children);
        for (auto &child : children) {
            int h = height(child);
            if (ret < h) ret = h;
        }
        return ret + 1;
    }

    int degree(const GeneralTreeNode<T> *node) const {
        if (node == nullptr) return 0;
        int ret = node->children.length();
        auto &children = const_cast<LinkedList<GeneralTreeNode<T> *> &>(node->children);
        for (auto &child : children) {
            int d = degree(child);
            if (d > ret) ret = d;
        }

        return ret;
    }
};

} // namespace Kylin
#endif // GENERALTREE_H