/**
 * @file bin_packing_allocator.cpp
 * @brief 二叉树分割纹理分配算法实现
 */
#include "bin_packing_allocator.h"

bin_packing_allocator::bin_packing_allocator(const Eigen::Vector2i& size)
    : size_(size)
{
    reset();
}

std::optional<rect_t<int32_t>> bin_packing_allocator::allocate(const Eigen::Vector2i& size) {
    // 检查尺寸是否有效
    if (size.x() <= 0 || size.y() <= 0 || size.x() > size_.x() || size.y() > size_.y()) {
        return std::nullopt;
    }

    // 寻找可以容纳的节点
    Node* node = find_node(root_.get(), size);
    if (!node) {
        return std::nullopt;  // 没有足够空间
    }

    // 分割该节点以最佳利用空间
    node = split_node(node, size);
    node->used = true;

    // 更新已分配区域
    allocated_area_ += size.x() * size.y();

    // 返回分配的矩形
    return node->rect;
}

bool bin_packing_allocator::free(const rect_t<int32_t>& rect) {
    // 二叉树分配算法不支持单个矩形的释放
    return false;
}

void bin_packing_allocator::reset() {
    // 重新创建根节点
    root_ = std::make_unique<Node>(rect_t<int32_t>({0, 0}, {size_.x(), size_.y()}));
    allocated_area_ = 0;
}

void bin_packing_allocator::resize(const Eigen::Vector2i& new_size) {
    size_ = new_size;
    reset();
}

int bin_packing_allocator::total_area() const {
    return size_.x() * size_.y();
}

int bin_packing_allocator::allocated_area() const {
    return allocated_area_;
}

bin_packing_allocator::Node* bin_packing_allocator::find_node(Node* node, const Eigen::Vector2i& size) {
    if (!node) {
        return nullptr;
    }

    // 如果节点已被使用或大小不足，继续搜索
    if (node->used) {
        // 尝试右侧节点
        if (auto found = find_node(node->right.get(), size)) {
            return found;
        }
        // 尝试下方节点
        return find_node(node->down.get(), size);
    }
    else if (size.x() <= node->rect.width() && size.y() <= node->rect.height()) {
        // 找到合适的未使用节点
        return node;
    }

    return nullptr;
}

bin_packing_allocator::Node* bin_packing_allocator::split_node(Node* node, const Eigen::Vector2i& size) {
    // 标记当前节点为已使用
    node->used = true;

    // 创建右侧剩余空间节点
    if (node->rect.width() > size.x()) {
        int right_width = node->rect.width() - size.x();
        node->right = std::make_unique<Node>(
            rect_t<int32_t>({node->rect.left() + size.x(), node->rect.top()},
                          {right_width, size.y()}));
    }

    // 创建底部剩余空间节点
    if (node->rect.height() > size.y()) {
        int bottom_height = node->rect.height() - size.y();
        node->down = std::make_unique<Node>(
            rect_t<int32_t>({node->rect.left(), node->rect.top() + size.y()},
                          {node->rect.width(), bottom_height}));
    }

    // 调整当前节点的大小为请求的大小
    node->rect = rect_t<int32_t>({node->rect.left(), node->rect.top()}, {size.x(), size.y()});

    return node;
}
