#pragma once
/**
 * @file bin_packing_allocator.h
 * @brief 二叉树分割纹理分配算法
 */
#include "atlas_allocator.h"
#include <memory>

/**
 * @class bin_packing_allocator
 * @brief 二叉树分割纹理分配算法
 */
class bin_packing_allocator : public atlas_allocator {
public:
	/**
	 * @brief 构造函数
	 * @param size 分配区域的总大小
	 */
	explicit bin_packing_allocator(const Eigen::Vector2i& size);
	~bin_packing_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 Node {
		rect_t<int32_t> rect;
		bool used = false;
		std::unique_ptr<Node> right;
		std::unique_ptr<Node> down;

		Node() = default;
		explicit Node(const rect_t<int32_t>& r) : rect(r) {}
	};

	std::unique_ptr<Node> root_;
	Eigen::Vector2i size_;
	int allocated_area_ = 0;

	// 在给定节点中递归查找可放置位置
	Node* find_node(Node* node, const Eigen::Vector2i& size);

	// 分割节点
	Node* split_node(Node* node, const Eigen::Vector2i& size);
};
