/**
 * @file Vector.h
 * @brief 自定义动态数组容器实现
 * 
 * @details
 * 该容器提供与 std::vector 相似的功能，同时支持可选的析构策略。
 * 设计目标是在性能敏感场景下提供更精细的内存管理控制。
 *
 * ## 核心特性
 *
 * - **动态扩容**：自动管理内存，支持预留容量避免频繁分配
 * - **连续内存**：元素在内存中连续存储，缓存友好
 * - **可选析构**：通过模板参数控制是否在删除时调用元素析构函数
 * - **迭代器支持**：提供 begin()/end() 支持范围 for 循环
 *
 * ## 与 std::vector 的区别
 *
 * | 特性 | utl::vector | std::vector |
 * |------|-------------|-------------|
 * | 析构控制 | 可选模板参数 | 始终析构 |
 * | 内存分配 | realloc | allocator |
 * | 无序删除 | erase_unordered | 无 |
 *
 * ## 析构策略
 *
 * 模板参数 `destruct` 控制元素析构行为：
 * - `destruct = true`（默认）：删除元素时调用析构函数
 * - `destruct = false`：跳过析构，适用于 POD 类型或外部管理生命周期
 *
 * ## 扩容策略
 *
 * 当容量不足时，按 `(capacity + 1) * 1.5` 扩容：
 * - 初始容量 0 → 1
 * - 容量 4 → 6
 * - 容量 10 → 15
 *
 * ## 无序删除优化
 *
 * `erase_unordered()` 通过将末尾元素移动到删除位置实现 O(1) 删除，
 * 适用于元素顺序不重要的场景。
 *
 * @example
 * @code
 * // 基本使用
 * utl::vector<int> nums;
 * nums.push_back(1);
 * nums.push_back(2);
 * nums.emplace_back(3);
 * 
 * // 遍历
 * for (int& n : nums) {
 *     n *= 2;
 * }
 * 
 * // 无序删除（高效但不保证顺序）
 * nums.erase_unordered(0);  // 用末尾元素替换位置 0
 * 
 * // POD 类型优化（跳过析构）
 * utl::vector<float, false> vertices;
 * vertices.resize(1000);  // 不调用析构函数
 * @endcode
 *
 * @see utl::free_list
 */
#pragma once
#include "CommonHeader.h"

namespace XEngine::utl {

/**
 * @class vector
 * @brief 自定义连续内存动态数组
 * 
 * @tparam T 元素类型
 * @tparam destruct 是否在删除时调用析构函数，默认为 true
 * 
 * @details
 * 提供动态数组的完整功能，包括动态扩容、插入、删除等操作。
 * 通过模板参数控制析构行为，适用于不同性能需求场景。
 */
template<typename T, bool destruct = true>
class vector
{

public:
	/**
	 * @brief 默认构造函数，创建空容器
	 * 
	 * @details
	 * 创建一个空的 vector，不分配任何内存。
	 * 首次添加元素时会触发内存分配。
	 */
	vector() = default;

	/**
	 * @brief 构造并调整到指定元素数量
	 * 
	 * @param count 目标元素数量
	 * 
	 * @details
	 * 创建包含 count 个默认构造元素的容器。
	 * 要求类型 T 必须可默认构造。
	 * 
	 * @pre T 必须满足 is_default_constructible
	 */
	constexpr explicit vector(u64 count)
	{
		resize(count);
	}

	/**
	 * @brief 构造并填充指定数量元素
	 * 
	 * @param count 目标元素数量
	 * @param value 用于填充的值
	 * 
	 * @details
	 * 创建包含 count 个元素副本的容器。
	 * 要求类型 T 必须可拷贝构造。
	 * 
	 * @pre T 必须满足 is_copy_constructible
	 */
	constexpr explicit vector(u64 count, const T& value)
	{
		resize(count, value);
	}

	/**
	 * @brief 拷贝构造函数
	 * 
	 * @param o 要拷贝的源容器
	 * 
	 * @details
	 * 创建源容器的深拷贝，包括所有元素。
	 * 新容器具有独立的内存空间。
	 */
	constexpr vector(const vector& o)
	{
		*this = o;
	}

	/**
	 * @brief 移动构造函数
	 * 
	 * @param o 要移动的源容器
	 * 
	 * @details
	 * 转移源容器的所有权，不进行元素拷贝。
	 * 移动后源容器处于空状态。
	 */
	constexpr vector(vector&& o)
		:_capacity{o._capacity},
		_size{o._size},
		_data{o._data}
	{
		o.reset();
	}

	/**
	 * @brief 拷贝赋值运算符
	 * 
	 * @param o 要拷贝的源容器
	 * @return 当前容器的引用
	 * 
	 * @details
	 * 清空当前容器，然后深拷贝源容器的所有元素。
	 */
	constexpr vector& operator=(const vector& o)
	{
		assert(this != std::addressof(o));
		if (this != std::addressof(o))
		{
			clear();
			reserve(o._size);
			for (auto& item : o)
			{
				emplace_back(item);
			}
			assert(_size == o._size);
		}

		return *this;
	}

	/**
	 * @brief 移动赋值运算符
	 * 
	 * @param o 要移动的源容器
	 * @return 当前容器的引用
	 * 
	 * @details
	 * 销毁当前容器的资源，然后转移源容器的所有权。
	 */
	constexpr vector& operator=(vector&& o)
	{
		assert(this != std::addressof(o));
		if (this != std::addressof(o))
		{
			destroy();
			move(o);
		}

		return *this;
	}

	/**
	 * @brief 析构函数，释放所有资源
	 */
	~vector() { destroy(); }

	/**
	 * @brief 在末尾追加元素的拷贝
	 * 
	 * @param value 要追加的元素值
	 * 
	 * @details
	 * 如果容量不足，会自动扩容。
	 * 内部调用 emplace_back 实现。
	 */
	constexpr void push_back(const T& value)
	{
		emplace_back(value);
	}

	/**
	 * @brief 在末尾追加元素的右值引用
	 * 
	 * @param value 要追加的元素值（右值）
	 * 
	 * @details
	 * 使用移动语义追加元素，避免不必要的拷贝。
	 */
	constexpr void push_back(const T&& value)
	{
		emplace_back(std::move(value));
	}

	/**
	 * @brief 原位构造并追加元素
	 * 
	 * @tparam params 构造参数类型包
	 * @param p 传递给元素构造函数的参数
	 * @return 新构造元素的引用
	 * 
	 * @details
	 * 在容器末尾原位构造新元素，避免额外的拷贝或移动操作。
	 * 如果容量不足，按 1.5 倍扩容。
	 * 
	 * @note 扩容公式：`new_capacity = (old_capacity + 1) * 3 / 2`
	 */
	template<typename... params>
	constexpr decltype(auto) emplace_back(params&&... p)
	{
		if (_size == _capacity)
		{
			reserve(((_capacity + 1) * 3) >> 1);
		}
		assert(_size < _capacity);

		T *const item{ new (std::addressof(_data[_size])) T(std::forward<params>(p)...) };
		++_size;
		return *item;
	}

	/**
	 * @brief 调整元素数量，新增元素默认构造
	 * 
	 * @param new_size 目标元素数量
	 * 
	 * @details
	 * - 如果 new_size > 当前大小，在末尾默认构造新元素
	 * - 如果 new_size < 当前大小，删除末尾多余元素
	 * 
	 * @pre T 必须满足 is_default_constructible
	 */
	constexpr void resize(u64 new_size)
	{
		static_assert(std::is_default_constructible<T>::value,
			"Type must be default-constructible.");

		if (new_size > _size)
		{
			reserve(new_size);
			while (_size < new_size)
			{
				emplace_back();
			}
		}
		else if (new_size < _size)
		{
			if constexpr (destruct)
			{
				destruct_range(new_size, _size);
			}

			_size = new_size;
		}


		assert(new_size == _size);
	}

	/**
	 * @brief 调整元素数量，新增元素使用给定值填充
	 * 
	 * @param new_size 目标元素数量
	 * @param value 用于填充新元素的值
	 * 
	 * @details
	 * - 如果 new_size > 当前大小，在末尾拷贝构造新元素
	 * - 如果 new_size < 当前大小，删除末尾多余元素
	 * 
	 * @pre T 必须满足 is_copy_constructible
	 */
	constexpr void resize(u64 new_size, const T& value)
	{
		static_assert(std::is_copy_constructible<T>::value,
			"Type must be copy-constructible.");

		if (new_size > _size)
		{
			reserve(new_size);
			while (_size < new_size)
			{
				emplace_back(value);
			}
		}
		else if (new_size < _size)
		{
			if constexpr (destruct)
			{
				destruct_range(new_size, _size);
			}

			_size = new_size;
		}


		assert(new_size == _size);
	}

	/**
	 * @brief 预留最小容量
	 * 
	 * @param new_capacity 目标容量
	 * 
	 * @details
	 * 如果 new_capacity > 当前容量，重新分配更大的内存块。
	 * 使用 realloc 实现，会自动复制原有数据。
	 * 
	 * @note 此函数只会增加容量，不会减少
	 */
	constexpr void reserve(u64 new_capacity)
	{
		if (new_capacity > _capacity)
		{
			void* new_buffer{ realloc(_data, new_capacity * sizeof(T)) };
			assert(new_buffer);
			if (new_buffer)
			{
				_data = static_cast<T*>(new_buffer);
				_capacity = new_capacity;
			}
		}
	}

	/**
	 * @brief 删除指定下标元素并保持顺序
	 * 
	 * @param index 要删除元素的下标
	 * @return 指向删除位置后一个元素的指针
	 * 
	 * @details
	 * 删除元素后，将后续所有元素向前移动一位。
	 * 时间复杂度 O(n)。
	 * 
	 * @pre index 必须小于当前元素数量
	 */
	constexpr T *const erase(u64 index)
	{
		assert(_data && index < _size);
		return erase(std::addressof(_data[index]));
	}

	/**
	 * @brief 删除指定位置元素并保持顺序
	 * 
	 * @param item 指向要删除元素的指针
	 * @return 指向删除位置后一个元素的指针
	 * 
	 * @details
	 * 删除元素后，将后续所有元素向前移动一位。
	 * 时间复杂度 O(n)。
	 * 
	 * @pre item 必须指向容器内的有效元素
	 */
	constexpr T *const erase(T *const item)
	{
		assert(_data && item >= std::addressof(_data[0]) &&
			item < std::addressof(_data[_size]));

		if constexpr (destruct) item->~T();
		--_size;
		if (item < std::addressof(_data[_size]))
		{
			memcpy(item, item + 1, (std::addressof(_data[_size]) - item) * sizeof(T));
		}

		return item;
	}

	/**
	 * @brief 无序删除指定下标元素
	 * 
	 * @param index 要删除元素的下标
	 * @return 指向删除位置的指针
	 * 
	 * @details
	 * 用末尾元素替换被删除元素，然后减少大小。
	 * 时间复杂度 O(1)，但不保证元素顺序。
	 * 
	 * @pre index 必须小于当前元素数量
	 * 
	 * @note 适用于元素顺序不重要的场景
	 */
	constexpr T *const erase_unordered(u64 index)
	{
		assert(_data && index < _size);
		return erase_unordered(std::addressof(_data[index]));
	}

	/**
	 * @brief 无序删除指定位置元素
	 * 
	 * @param item 指向要删除元素的指针
	 * @return 指向删除位置的指针
	 * 
	 * @details
	 * 用末尾元素替换被删除元素，然后减少大小。
	 * 时间复杂度 O(1)，但不保证元素顺序。
	 * 
	 * @pre item 必须指向容器内的有效元素
	 * 
	 * @note 适用于元素顺序不重要的场景
	 */
	constexpr T *const erase_unordered(T *const item)
	{
		assert(_data && item >= std::addressof(_data[0]) &&
			item < std::addressof(_data[_size]));

		if constexpr (destruct) item->~T();
		--_size;

		if (item < std::addressof(_data[_size]))
		{
			memcpy(item, std::addressof(_data[_size]), sizeof(T));
		}

		return item;
	}

	/**
	 * @brief 清空容器中的所有元素
	 * 
	 * @details
	 * 调用所有元素的析构函数（如果 destruct = true），
	 * 然后将大小设为 0。不释放底层内存。
	 */
	constexpr void clear()
	{
		if constexpr (destruct)
		{
			destruct_range(0, _size);
		}
		_size = 0;
	}

	/**
	 * @brief 与另一个容器交换内容
	 * 
	 * @param o 目标容器
	 * 
	 * @details
	 * 交换两个容器的所有权，不进行元素拷贝。
	 * 时间复杂度 O(1)。
	 */
	constexpr void swap(vector& o)
	{
		if (this != std::addressof(o))
		{
			auto temp(std::move(o));
			o.move(*this);
			move(temp);
		}
	}

	/**
	 * @brief 返回底层数据指针
	 * 
	 * @return 指向第一个元素的指针
	 */
	[[nodiscard]] constexpr T* data()
	{
		return _data;
	}

	/**
	 * @brief 返回只读底层数据指针
	 * 
	 * @return 指向第一个元素的常量指针
	 */
	[[nodiscard]] constexpr T *const data() const
	{
		return _data;
	}

	/**
	 * @brief 判断容器是否为空
	 * 
	 * @return 如果容器中没有元素则返回 true
	 */
	[[nodiscard]] constexpr bool empty() const
	{
		return _size == 0;
	}

	/**
	 * @brief 获取元素个数
	 * 
	 * @return 容器中当前存储的元素数量
	 */
	[[nodiscard]] constexpr u64 size() const
	{
		return _size;
	}

	/**
	 * @brief 获取当前容量
	 * 
	 * @return 容器当前分配的存储空间可容纳的元素数量
	 */
	[[nodiscard]] constexpr u64 capacity() const
	{
		return _capacity;
	}

	/**
	 * @brief 下标访问运算符（可修改）
	 * 
	 * @param index 元素下标
	 * @return 元素的引用
	 * 
	 * @pre index 必须小于当前元素数量
	 */
	[[nodiscard]] constexpr T& operator [](u64 index)
	{
		assert(_data && index < _size);
		return _data[index];
	}

	/**
	 * @brief 下标访问运算符（只读）
	 * 
	 * @param index 元素下标
	 * @return 元素的常量引用
	 * 
	 * @pre index 必须小于当前元素数量
	 */
	[[nodiscard]] constexpr const T& operator [](u64 index) const
	{
		assert(_data && index < _size);
		return _data[index];
	}

	/**
	 * @brief 访问第一个元素（可修改）
	 * 
	 * @return 第一个元素的引用
	 * 
	 * @pre 容器必须非空
	 */
	[[nodiscard]] constexpr T& front()
	{
		assert(_data && _size);
		return _data[0];
	}

	/**
	 * @brief 访问第一个元素（只读）
	 * 
	 * @return 第一个元素的常量引用
	 * 
	 * @pre 容器必须非空
	 */
	[[nodiscard]] constexpr const T& front() const
	{
		assert(_data && _size);
		return _data[0];
	}

	/**
	 * @brief 访问最后一个元素（可修改）
	 * 
	 * @return 最后一个元素的引用
	 * 
	 * @pre 容器必须非空
	 */
	[[nodiscard]] constexpr T& back()
	{
		assert(_data && _size);
		return _data[_size -1];
	}

	/**
	 * @brief 访问最后一个元素（只读）
	 * 
	 * @return 最后一个元素的常量引用
	 * 
	 * @pre 容器必须非空
	 */
	[[nodiscard]] constexpr const T& back() const
	{
		assert(_data && _size);
		return _data[_size - 1];
	}

	/**
	 * @brief 返回指向首元素的迭代器
	 * 
	 * @return 指向第一个元素的指针
	 * 
	 * @details 支持范围 for 循环
	 */
	[[nodiscard]] constexpr T* begin()
	{
		return std::addressof(_data[0]);
	}

	/**
	 * @brief 返回指向首元素的常量迭代器
	 * 
	 * @return 指向第一个元素的常量指针
	 */
	[[nodiscard]] constexpr const T* begin() const
	{
		return std::addressof(_data[0]);
	}

	/**
	 * @brief 返回指向尾后位置的迭代器
	 * 
	 * @return 指向最后一个元素之后位置的指针
	 * 
	 * @details 支持范围 for 循环
	 */
	[[nodiscard]] constexpr T* end()
	{
		assert(!(_data == nullptr && _size > 0));
		return std::addressof(_data[_size]);
	}

	/**
	 * @brief 返回指向尾后位置的常量迭代器
	 * 
	 * @return 指向最后一个元素之后位置的常量指针
	 */
	[[nodiscard]] constexpr const T* end() const
	{
		assert(!(_data == nullptr && _size > 0));
		return std::addressof(_data[_size]);
	}

private:
	/**
	 * @brief 从另一个容器转移所有权
	 * 
	 * @param o 源容器
	 * 
	 * @details
	 * 复制源容器的成员变量，然后将源容器重置为空状态。
	 */
	constexpr void move(vector& o)
	{
		_capacity = o._capacity;
		_size = o._size;
		_data = o._data;
		o.reset();
	}

	/**
	 * @brief 重置容器为空状态
	 * 
	 * @details
	 * 将所有成员变量设为初始值，不释放内存。
	 */
	constexpr void reset()
	{
		_capacity = 0;
		_size = 0;
		_data = nullptr;
	}

	/**
	 * @brief 析构指定范围内的元素
	 * 
	 * @param first 起始索引
	 * @param last 结束索引（不包含）
	 * 
	 * @details
	 * 对 [first, last) 范围内的每个元素调用析构函数。
	 * 仅在 destruct = true 时有效。
	 */
	constexpr void destruct_range(u64 first, u64 last)
	{
		assert(destruct);
		assert(first <= _size && last <= _size && first <= last);
		if (_data)
		{
			for (; first != last; ++first)
			{
				_data[first].~T();
			}
		}
	}

	/**
	 * @brief 销毁容器，释放所有资源
	 * 
	 * @details
	 * 清空所有元素，释放底层内存，重置容量为 0。
	 */
	constexpr void destroy()
	{
		assert([&] {return _capacity ? _data != nullptr : _data == nullptr; }());
		clear();
		_capacity = 0;
		if (_data) free(_data);
		_data = nullptr;
	}

	u64			_capacity{ 0 };
	u64			_size{ 0 };
	T*			_data{ nullptr };
};

}