/**
 * @file grid_allocator.cpp
 * @brief 网格式纹理分配算法实现
 */
#include "grid_allocator.h"

grid_allocator::grid_allocator(const Eigen::Vector2i& size, const Eigen::Vector2i& cell_size)
    : size_(size), cell_size_(cell_size)
{
    // 计算网格维度
    grid_dims_.x() = (size.x() + cell_size.x() - 1) / cell_size.x();
    grid_dims_.y() = (size.y() + cell_size.y() - 1) / cell_size.y();

    // 初始化所有单元格为未使用
    cells_.resize(grid_dims_.x() * grid_dims_.y(), false);
    allocated_cells_ = 0;
}

std::optional<rect_t<int32_t>> grid_allocator::allocate(const Eigen::Vector2i& size) {
    // 计算需要多少个单元格来容纳请求的大小
    Eigen::Vector2i num_cells(
        (size.x() + cell_size_.x() - 1) / cell_size_.x(),
        (size.y() + cell_size_.y() - 1) / cell_size_.y()
    );

    // 如果请求的大小超过整个网格，返回失败
    if (num_cells.x() > grid_dims_.x() || num_cells.y() > grid_dims_.y()) {
        return std::nullopt;
    }

    // 查找足够的连续单元格
    auto start_cell_opt = find_free_cells(num_cells);
    if (!start_cell_opt) {
        return std::nullopt;  // 没有足够的空间
    }

    // 找到了合适的位置，标记这些单元格为已使用
    Eigen::Vector2i start_cell = *start_cell_opt;
    for (int y = 0; y < num_cells.y(); ++y) {
        for (int x = 0; x < num_cells.x(); ++x) {
            cells_[cell_index(start_cell.x() + x, start_cell.y() + y)] = true;
        }
    }

    // 更新已分配的单元格数量
    allocated_cells_ += num_cells.x() * num_cells.y();

    // 计算实际像素矩形
    Eigen::Vector2i position = start_cell.cwiseProduct(cell_size_);
    return rect_t<int32_t>(position, size);
}

bool grid_allocator::free(const rect_t<int32_t>& rect) {
    // 计算对应的单元格范围
    Eigen::Vector2i start_cell(
        rect.left() / cell_size_.x(),
        rect.top() / cell_size_.y()
    );

    Eigen::Vector2i num_cells(
        (rect.width() + cell_size_.x() - 1) / cell_size_.x(),
        (rect.height() + cell_size_.y() - 1) / cell_size_.y()
    );

    // 验证单元格范围是否有效
    if (start_cell.x() < 0 || start_cell.y() < 0 ||
        start_cell.x() + num_cells.x() > grid_dims_.x() ||
        start_cell.y() + num_cells.y() > grid_dims_.y()) {
        return false;
    }

    // 检查所有单元格是否都是已分配的
    for (int y = 0; y < num_cells.y(); ++y) {
        for (int x = 0; x < num_cells.x(); ++x) {
            int idx = cell_index(start_cell.x() + x, start_cell.y() + y);
            if (!cells_[idx]) {
                return false;  // 至少有一个单元格未被分配
            }
        }
    }

    // 释放这些单元格
    for (int y = 0; y < num_cells.y(); ++y) {
        for (int x = 0; x < num_cells.x(); ++x) {
            cells_[cell_index(start_cell.x() + x, start_cell.y() + y)] = false;
        }
    }

    // 更新已分配的单元格数量
    allocated_cells_ -= num_cells.x() * num_cells.y();
    return true;
}

void grid_allocator::reset() {
    // 将所有单元格重置为未使用
    std::fill(cells_.begin(), cells_.end(), false);
    allocated_cells_ = 0;
}

void grid_allocator::resize(const Eigen::Vector2i& new_size) {
    size_ = new_size;

    // 重新计算网格维度
    Eigen::Vector2i new_grid_dims(
        (new_size.x() + cell_size_.x() - 1) / cell_size_.x(),
        (new_size.y() + cell_size_.y() - 1) / cell_size_.y()
    );

    // 如果网格维度没有变化，不需要重新分配
    if (new_grid_dims == grid_dims_) {
        return;
    }

    // 更新网格维度并重置单元格
    grid_dims_ = new_grid_dims;
    cells_.resize(grid_dims_.x() * grid_dims_.y());
    reset();
}

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

int grid_allocator::allocated_area() const {
    return allocated_cells_ * cell_size_.x() * cell_size_.y();
}

int grid_allocator::cell_index(int x, int y) const {
    return y * grid_dims_.x() + x;
}

std::optional<Eigen::Vector2i> grid_allocator::find_free_cells(const Eigen::Vector2i& num_cells) {
    // 遍历整个网格，寻找能容纳请求大小的连续空闲单元格
    for (int y = 0; y <= grid_dims_.y() - num_cells.y(); ++y) {
        for (int x = 0; x <= grid_dims_.x() - num_cells.x(); ++x) {
            bool can_fit = true;

            // 检查这块区域的所有单元格是否都是空闲的
            for (int cy = 0; cy < num_cells.y() && can_fit; ++cy) {
                for (int cx = 0; cx < num_cells.x() && can_fit; ++cx) {
                    if (cells_[cell_index(x + cx, y + cy)]) {
                        can_fit = false;
                    }
                }
            }

            if (can_fit) {
                return Eigen::Vector2i(x, y);
            }
        }
    }

    return std::nullopt;  // 没有找到合适的空间
}
