tree.hpp

//
// ツリー
//
 
#ifndef COLLECTION2_TREE_H
#define COLLECTION2_TREE_H
 
#include <stddef.h>
#include <stdint.h>
 
#include "common.hpp"
 
namespace collection2 {
 
template <typename Element, typename Size = size_t>
struct TreeNode {
    // 有効なノードか
    bool isEnabled = false;
 
    // 左側子ノードへのポインタ
    TreeNode* lhs = nullptr;
 
    // 右側子ノードへのポインタ
    TreeNode* rhs = nullptr;
 
    // ノードが持つ要素
    Element element;
 
    bool isLeaf() const {
        return (lhs == nullptr) && (rhs == nullptr);
    };
};
 
enum class TreeNodeSide : uint8_t {
    Left,
 
    Right
};
 
template <typename Element, typename Size = size_t>
class Tree {
   private:
    TreeNode<Element>* const internalData;
 
    Size internalDataSize;
 
   public:
    Tree(TreeNode<Element, Size>* const data, const Size& dataSize);
 
    Tree(const Tree&) = delete;
    Tree& operator=(const Tree&) = delete;
 
    ~Tree() = default;
 
    void initializeTreeNodePool();
 
    TreeNode<Element, Size>* retainNode() const;
 
    TreeNode<Element, Size>* retainNode(const Element& element) const;
 
    OperationResult appendChild(
        TreeNode<Element, Size>* parent,
        const Element& target,
        const TreeNodeSide side,
        TreeNode<Element, Size>** addedNodePtr = nullptr);
 
    OperationResult linkNode(
        TreeNode<Element, Size>& parent,
        TreeNode<Element, Size>* node,
        const TreeNodeSide side) const;
 
    void removeChild(TreeNode<Element, Size>* target);
 
    Size capacity() const {
        return internalDataSize;
    }
};
 
template <typename Element, typename Size>
Tree<Element, Size>::Tree(TreeNode<Element, Size>* const data, const Size& dataSize)
    : internalData(data), internalDataSize(dataSize) {
    initializeTreeNodePool();
};
 
template <typename Element, typename Size>
inline void Tree<Element, Size>::initializeTreeNodePool() {
    for (Size i = 0; i < internalDataSize; i++) {
        internalData[i].isEnabled = false;
    }
}
 
template <typename Element, typename Size>
inline TreeNode<Element, Size>* Tree<Element, Size>::retainNode() const {
    for (Size i = 0; i < internalDataSize; i++) {
        if (internalData[i].isEnabled) {
            continue;
        }
 
        // 見つかったらノードを初期化して返す
        internalData[i].isEnabled = true;
        internalData[i].lhs = nullptr;
        internalData[i].rhs = nullptr;
        return &(internalData[i]);
    }
    return nullptr;
}
 
template <typename Element, typename Size>
inline TreeNode<Element, Size>* collection2::Tree<Element, Size>::retainNode(const Element& element) const {
    // ノードを確保
    auto* node = retainNode();
    if (node == nullptr) {
        return nullptr;
    }
 
    // 値を設定して返す
    node->element = element;
    return node;
}
 
template <typename Element, typename Size>
inline OperationResult collection2::Tree<Element, Size>::appendChild(
    TreeNode<Element, Size>* parent,
    const Element& target,
    const TreeNodeSide side,
    TreeNode<Element, Size>** addedNodePtr) {
    // 親ノードがnullであってはならない(単純なノードの確保はretainNodeを使う)
    if (parent == nullptr) {
        return OperationResult::Empty;
    }
 
    // 新しいノードをもらってくる
    auto* newNode = retainNode();
    if (newNode == nullptr) {
        if (addedNodePtr != nullptr) {
            *addedNodePtr = nullptr;
        }
        return OperationResult::Overflow;
    }
 
    // 値をセット
    newNode->element = target;
 
    // 新規生成したノードへのポインタを渡す
    if (addedNodePtr != nullptr) {
        *addedNodePtr = newNode;
    }
 
    // 親ノードの追加したい方に追加するノードを接続する
    return linkNode(*parent, newNode, side);
}
 
template <typename Element, typename Size>
inline OperationResult collection2::Tree<Element, Size>::linkNode(TreeNode<Element, Size>& parent, TreeNode<Element, Size>* node, const TreeNodeSide side) const {
    if (node == nullptr) {
        return OperationResult::Empty;
    }
 
    // sideで指定された方にnodeを繋ぐ すでにある場合は書き換えない
    if (side == TreeNodeSide::Left) {
        if (parent.lhs != nullptr) {
            return OperationResult::Overflow;
        }
        parent.lhs = node;
    }
    if (side == TreeNodeSide::Right) {
        if (parent.rhs != nullptr) {
            return OperationResult::Overflow;
        }
        parent.rhs = node;
    }
    return OperationResult::Success;
}
 
template <typename Element, typename Size>
inline void collection2::Tree<Element, Size>::removeChild(TreeNode<Element, Size>* target) {
    // リーフならデアクティベートして終わり
    if (target->isLeaf()) {
        target->isEnabled = false;
        return;
    }
 
    // そうでなければ再帰的に削除
    if (target->lhs != nullptr) {
        removeChild(target->lhs);
        target->lhs = nullptr;
    }
    if (target->rhs != nullptr) {
        removeChild(target->rhs);
        target->rhs = nullptr;
    }
}
 
}  // namespace collection2
 
#endif