treenode.hpp

#pragma once

#include <algorithm>
#include <memory>
#include <type_traits>
#include <vector>

template<typename T, typename N>
class TreeView;

template<typename T, typename N>
class TreeNode
{
    static_assert(std::is_unsigned_v<N>, "N must be an unsigned type");

    using NodeType = TreeNode<T, N>;
    using NodePtr = NodeType*;
    using NodeUniquePtr = std::unique_ptr<NodeType>;

    friend class TreeView<T, N>;

public:
    // Default constructor, destructor
    TreeNode() = default;
    ~TreeNode() = default;

    // Move constructor and move assignment operator
    TreeNode(TreeNode&&) = default;
    TreeNode& operator=(TreeNode&&) = default;

    // Delete copy constructor and copy assignment operator to prevent copying
    TreeNode(const TreeNode&) = delete;
    TreeNode& operator=(const TreeNode&) = delete;

    // Constructor to initialize a TreeNode with value, level, index, and optional parent
    TreeNode(T val, N lvl, N idx, NodePtr par = nullptr)
        : value(val), level(lvl), index(idx), parent(par) {}

    // Method to add a child node and return the new node for immediate use
    NodePtr addChild(T val)
    {
        NodeUniquePtr child = std::make_unique<TreeNode<T, N>>(val, level + 1, children.size(), this);
        NodePtr raw = child.get();
        children.push_back(std::move(child));
        return raw;
    }

    // Method to emplace-construct a child node and return the new node
    NodePtr emplaceChild(T val)
    {
        return addChild(val);
    }

    // Method to emplace-construct a child node with perfect forwarding of arguments
    template<typename... Args>
    NodePtr emplaceChild(Args&&... args)
    {
        NodeUniquePtr child = std::make_unique<TreeNode<T, N>>(std::forward<Args>(args)...);
        child->level = level + 1;
        child->index = children.size();
        child->parent = this;
        NodePtr raw = child.get();
        children.push_back(std::move(child));
        return raw;
    }

    // Getters for value, level, index, parent, and children
    T getValue() const { return value; }
    N getLevel() const { return level; }
    N getIndex() const { return index; }
    NodePtr getParent() const { return parent; }
    std::vector<NodePtr> getChildren() const
    {
        std::vector<NodePtr> childPointers;
        childPointers.reserve(children.size());
        for (const auto& child : children)
        {
            childPointers.push_back(child.get());
        }
        return childPointers;
    }

    // setters for value, level, index, and parent
    void setValue(T val) { value = val; }
    void setLevel(N lvl) { level = lvl; }
    void setIndex(N idx) { index = idx; }
    void setParent(NodePtr par) { parent = par; }

    // Method to get a child node by index
    NodePtr getChild(N childIndex) const
    {
        if (childIndex < children.size())
        {
            return children[childIndex].get();
        }
        return nullptr;
    }

    // Method to get the number of children
    N getChildCount() const { return static_cast<N>(children.size()); }

    // Method to get the next sibling node
    NodePtr getNextSibling() const
    {
        if (parent)
        {
            auto& siblings = parent->children;
            for (N i = 0; i < siblings.size(); ++i)
            {
                if (siblings[i].get() == this && i + 1 < siblings.size())
                {
                    return siblings[i + 1].get();
                }
            }
        }
        return nullptr;
    }

    // Method to get the previous sibling node
    NodePtr getPreviousSibling() const
    {
        if (parent)
        {
            auto& siblings = parent->children;
            for (N i = 0; i < siblings.size(); ++i)
            {
                if (siblings[i].get() == this && i > 0)
                {
                    return siblings[i - 1].get();
                }
            }
        }
        return nullptr;
    }

    // Method to get the first child node
    NodePtr getFirstChild() const
    {
        if (!children.empty())
        {
            return children[0].get();
        }
        return nullptr;
    }

    // Method to get the last child node
    NodePtr getLastChild() const
    {
        if (!children.empty())
        {
            return children.back().get();
        }
        return nullptr;
    }

    // Method to check if the node is a leaf (has no children)
    bool isLeaf() const { return children.empty(); }

    // Method to check if the node is the root (has no parent)
    bool isRoot() const { return parent == nullptr; }

    // Method to get the depth of the node in the tree
    N getDepth() const
    {
        N depth = 0;
        NodePtr current = parent;
        while (current)
        {
            ++depth;
            current = current->parent;
        }
        return depth;
    }

    // Method to get the path from the root to this node as a vector of values
    std::vector<T> getPath() const
    {
        std::vector<T> path;
        NodePtr current = const_cast<NodePtr>(this);
        while (current)
        {
            path.push_back(current->value);
            current = current->parent;
        }
        std::reverse(path.begin(), path.end());
        return path;
    }

    // Method to find a node by value in the subtree rooted at this node
    NodePtr findNodeByValue(const T& val) const
    {
        if (value == val)
        {
            return const_cast<NodePtr>(this);
        }
        for (const auto& child : children)
        {
            NodePtr found = child->findNodeByValue(val);
            if (found)
            {
                return found;
            }
        }
        return nullptr;
    }

    // Boolean helper for subtree membership by value
    bool containsValue(const T& val) const
    {
        return findNodeByValue(val) != nullptr;
    }

    // Method to get the number of descendants (children, grandchildren, etc.) of this node
    N getDescendantCount() const
    {
        N count = static_cast<N>(children.size());
        for (const auto& child : children)
        {
            count += child->getDescendantCount();
        }
        return count;
    }

    // Method to remove a child node by index
    bool removeChild(N childIndex)
    {
        if (childIndex < children.size())
        {
            children.erase(children.begin() + childIndex);
            // Update the indices of the remaining children
            for (N i = childIndex; i < children.size(); ++i)
            {
                children[i]->index = i;
            }
            return true;
        }
        return false;
    }

    // Method to clear all children of this node
    void clearChildren()
    {
        children.clear();
    }

    // Method to replace a child node at a specific index with a new value
    bool replaceChild(N childIndex, T newValue)
    {
        if (childIndex < children.size())
        {
            children[childIndex]->value = newValue;
            return true;
        }
        return false;
    }

    // Method to replace the current node's value and return the node itself
    NodePtr updateValue(T newValue)
    {
        value = newValue;
        return this;
    }


private:
    T value{};
    N level{};
    N index{};
    NodePtr parent{};
    std::vector<NodeUniquePtr> children;
};