#pragma once
/**
 * @file skyline_allocator.h
 * @brief 天际线纹理分配算法
 */
#include "atlas_allocator.h"
#include <vector>
#include <unordered_map>

/**
 * @class skyline_allocator
 * @brief 天际线纹理分配算法
 *
 * 天际线算法通过维护一系列水平线段来跟踪已分配区域的上边界。
 * 它在分配效率和空间利用率之间取得了良好的平衡。
 */
class skyline_allocator : public atlas_allocator {
public:
	/**
	 * @brief 构造函数
	 * @param size 分配区域的总大小
	 */
	explicit skyline_allocator(const Eigen::Vector2i& size);
	~skyline_allocator() override = default;

	std::optional<rect_t<int32_t>> allocate(const Eigen::Vector2i& size) override;
	bool free(const rect_t<int32_t>& rect) override;
	void reset() override;
	void resize(const Eigen::Vector2i& new_size) override;
	int total_area() const override;
	int allocated_area() const override;

private:
	/**
	 * @struct Segment
	 * @brief 表示天际线的一个水平线段
	 */
	struct Segment {
		int x;      ///< 线段起始x坐标
		int y;      ///< 线段的y坐标(高度)
		int width;  ///< 线段宽度
	};

	Eigen::Vector2i size_;               ///< 总区域大小
	std::vector<Segment> skyline_;       ///< 天际线段集合
	int allocated_area_ = 0;             ///< 已分配的面积
	std::unordered_map<int, rect_t<int32_t>> allocated_rects_; ///< 已分配的矩形，按ID索引
	int next_id_ = 1;                    ///< 下一个分配的ID

	/**
	 * @brief 查找可放置位置
	 * @param size 要分配的大小
	 * @return 可放置的位置，如果没有足够空间则返回std::nullopt
	 */
	std::optional<Eigen::Vector2i> find_position(const Eigen::Vector2i& size);

	/**
	 * @brief 更新天际线
	 * @param pos 分配区域的位置
	 * @param size 分配区域的大小
	 */
	void update_skyline(const Eigen::Vector2i& pos, const Eigen::Vector2i& size);
};
