/**
 * @file skyline_allocator.cpp
 * @brief 天际线纹理分配算法实现
 */
#include "skyline_allocator.h"
#include <algorithm>
#include <limits>

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

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

    // 查找可用位置
    auto pos_opt = find_position(size);
    if (!pos_opt) {
        return std::nullopt;  // 没有找到合适的位置
    }

    // 分配成功，更新天际线
    Eigen::Vector2i pos = *pos_opt;
    update_skyline(pos, size);

    // 创建矩形并存储
    rect_t<int32_t> rect({pos.x(), pos.y()}, {size.x(), size.y()});
    int id = next_id_++;
    allocated_rects_[id] = rect;

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

    return rect;
}

bool skyline_allocator::free(const rect_t<int32_t>& rect) {
    // 在已分配矩形中查找匹配的矩形
    for (auto it = allocated_rects_.begin(); it != allocated_rects_.end(); ++it) {
        if (it->second == rect) {
            // 找到了匹配的矩形，从分配表中移除
            allocated_area_ -= rect.width() * rect.height();
            allocated_rects_.erase(it);

            // 注意：天际线分配器不支持单个矩形的高效释放
            // 我们需要重建整个天际线，这是一种折衷
            reset();

            // 重新分配所有剩余的矩形
            std::vector<rect_t<int32_t>> rects_to_reallocate;
            for (const auto& [id, r] : allocated_rects_) {
                rects_to_reallocate.push_back(r);
            }

            // 清空已分配记录，因为我们要重新分配
            allocated_rects_.clear();
            allocated_area_ = 0;
            next_id_ = 1;

            // 重新分配所有矩形
            for (const auto& r : rects_to_reallocate) {
                Eigen::Vector2i r_size(r.width(), r.height());
                auto pos_opt = find_position(r_size);
                if (pos_opt) {
                    update_skyline(*pos_opt, r_size);
                    int id = next_id_++;
                    allocated_rects_[id] = rect_t<int32_t>(*pos_opt, r_size);
                    allocated_area_ += r_size.x() * r_size.y();
                }
            }

            return true;
        }
    }

    return false;  // 没有找到匹配的矩形
}

void skyline_allocator::reset() {
    // 初始状态只有一条线段：沿着底部的一条水平线
    skyline_.clear();
    skyline_.push_back({0, 0, size_.x()});
    allocated_area_ = 0;
    allocated_rects_.clear();
    next_id_ = 1;
}

void skyline_allocator::resize(const Eigen::Vector2i& new_size) {
    size_ = new_size;
    reset();  // 调整大小会导致所有分配失效
}

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

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

std::optional<Eigen::Vector2i> skyline_allocator::find_position(const Eigen::Vector2i& size) {
    int best_height = std::numeric_limits<int>::max();
    int best_width = std::numeric_limits<int>::max();
    int best_index = -1;
    Eigen::Vector2i best_pos;

    // 遍历所有天际线段，查找最佳放置位置
    for (size_t i = 0; i < skyline_.size(); ++i) {
        auto& segment = skyline_[i];

        // 尝试将矩形放在当前线段上
        Eigen::Vector2i pos(segment.x, segment.y);

        // 检查宽度是否足够
        if (segment.width < size.x()) {
            continue;
        }

        // 计算放置此矩形后的高度
        int height = segment.y + size.y();

        // 检查高度是否超出边界
        if (height > size_.y()) {
            continue;
        }

        // 使用"最低高度优先"的策略
        // 如果有多个相同高度的位置，选择宽度最小的
        if (height < best_height || (height == best_height && segment.width < best_width)) {
            best_height = height;
            best_index = static_cast<int>(i);
            best_pos = pos;
            best_width = segment.width;
        }
    }

    if (best_index == -1) {
        return std::nullopt;  // 没有找到合适的位置
    }

    return best_pos;
}

void skyline_allocator::update_skyline(const Eigen::Vector2i& pos, const Eigen::Vector2i& size) {
    // 找到受影响的线段范围
    int start_index = -1;
    int end_index = -1;

    for (size_t i = 0; i < skyline_.size(); ++i) {
        auto& segment = skyline_[i];

        // 找到第一个与分配区域重叠的线段
        if (start_index == -1) {
            if (segment.x + segment.width > pos.x()) {
                start_index = static_cast<int>(i);
            }
        }

        // 找到最后一个与分配区域重叠的线段
        if (start_index != -1 && segment.x >= pos.x() + size.x()) {
            end_index = static_cast<int>(i);
            break;
        }
    }

    if (end_index == -1) {
        end_index = static_cast<int>(skyline_.size());
    }

    // 计算新的天际线段
    int new_y = pos.y() + size.y();
    int new_start_x = pos.x();
    int new_end_x = pos.x() + size.x();

    // 处理受影响区域的前一个线段
    if (start_index > 0 && skyline_[start_index - 1].x + skyline_[start_index - 1].width > pos.x()) {
        // 如果前一个线段与分配区域重叠，截断它
        skyline_[start_index - 1].width = pos.x() - skyline_[start_index - 1].x;
    }

    // 创建新的线段
    Segment new_segment = {new_start_x, new_y, new_end_x - new_start_x};

    // 处理受影响区域的下一个线段
    if (end_index < static_cast<int>(skyline_.size()) && skyline_[end_index].x < new_end_x) {
        // 如果下一个线段与分配区域重叠，调整它
        int width_diff = (skyline_[end_index].x + skyline_[end_index].width) - new_end_x;
        if (width_diff > 0) {
            // 截断这个线段，使其从new_end_x开始
            skyline_[end_index].x = new_end_x;
            skyline_[end_index].width = width_diff;

            // 插入新的线段
            skyline_.insert(skyline_.begin() + start_index, new_segment);
        } else {
            // 下一个线段完全被新线段覆盖，替换它
            skyline_[start_index] = new_segment;
            // 删除被完全覆盖的线段
            if (end_index > start_index) {
                skyline_.erase(skyline_.begin() + start_index + 1, skyline_.begin() + end_index + 1);
            }
        }
    } else {
        // 没有与下一个线段重叠
        skyline_[start_index] = new_segment;
        // 删除被完全覆盖的线段
        if (end_index > start_index + 1) {
            skyline_.erase(skyline_.begin() + start_index + 1, skyline_.begin() + end_index);
        }
    }

    // 合并相邻的相同高度线段
    for (size_t i = 0; i < skyline_.size() - 1; ++i) {
        if (skyline_[i].y == skyline_[i + 1].y) {
            skyline_[i].width += skyline_[i + 1].width;
            skyline_.erase(skyline_.begin() + i + 1);
            --i;
        }
    }
}
