// Copyright (c) 2023 刻BITTER
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.


#pragma once

#include <algorithm>
#include <cstdint>
#include <cstdlib>

namespace data_basic {

namespace _hide {
template <bool fit_in_8, bool fit_in_16, bool fit_in_32>
struct _enough_index_type {
};


template <>
struct _enough_index_type<true, true, true> {
    using type = uint8_t;
};


template <>
struct _enough_index_type<false, true, true> {
    using type = uint16_t;
};


template <>
struct _enough_index_type<false, false, true> {
    using type = uint32_t;
};


template <>
struct _enough_index_type<false, false, false> {
    using type = uint64_t;
};
}


template <size_t Count>
struct enough_index_type {
    using type = typename _hide::_enough_index_type<Count <= 8, Count <= 16, Count <= 32>::type;
};

template<size_t Count>
using enough_index_type_t = typename enough_index_type<Count>::type;

/**
     * @brief 单向链表节点
     *
     * 注意，next 指针必须放在第一个成员位置。
     *
     * @tparam NodeDataType
     */
template <typename NodeDataType>
struct LinkNode {
    LinkNode *next;
    NodeDataType data;
};


template <typename T>
void swap(LinkNode<T> &lhs, LinkNode<T> &rhs) {
    // 链表节点的交换应该只交换内部值，不改变节点在表中的位置，也就是不交换next 指针
    // 因为存在指向这个节点的上一个节点。
    // 比如，若有四个节点 <1> <2> <3> <4>， 若只交换<2> <3> 节点中的next 指针，由于节点<1> 没变，结构就变成：
    // <1> <2> <4>
    // <2> 本来指向<3> ，交换后改为指向<4>，节点<3> 自己指向自己，没有其他节点持有指向<3> 指针，于是<3> 就从链表中消失了。
    swap(lhs.data, rhs.data);
}


// 可以把另一个结构体嵌入LinkNode 中，将其扩展成双向节点, 这样做的目的是复用LinkNode 的基础设施
// template <typename NodeDataType>
// struct _NestedBackwardNode {
//     LinkNode<_NestedBackwardNode<NodeDataType>> *prev;
//     NodeDataType data;
// };


// template <typename T>
// void swap(LinkNode<_NestedBackwardNode<T>> &lhs, LinkNode<_NestedBackwardNode<T>> &rhs) {
//     swap(lhs.data.data, rhs.data.data);
// }


template <typename AnyNode>
class NodeIterator {
private:
    AnyNode *_ptr;

public:
    NodeIterator(AnyNode *ptr = nullptr) :
        _ptr(ptr) {}

    void operator++() {
        this->_ptr = this->_ptr->next;
    }

    bool operator!=(const NodeIterator &it) {
        return this->_ptr != it._ptr;
    }

    // TODO: 检测是否存在嵌套的data
    AnyNode &operator*() {
        return this->_ptr->data;
    }

    AnyNode *operator->() {
        return _ptr;
    }
};


template <typename NodeDataType, size_t PoolSize>
class LinkedMemoryPool {
public:
    using NodeTypeInPool = LinkNode<NodeDataType>;

private:
    NodeTypeInPool *_free_list = nullptr;
    NodeTypeInPool _memory_pool[PoolSize];


    void _init_free_list() {
        // 初始化后内存池中的节点按从后往前的顺序排列，free_list 指向数组中最后一个元素
        // 经过使用后，由于节点归还的顺序不固定，所以链表的顺序与数组顺序不再相关
        for (size_t i = 0; i < PoolSize; i++) {
            this->_memory_pool[i].next = this->_free_list;  // 从末端节点开始逐步初始化空闲链表
            this->_free_list = &_memory_pool[i];
        }
    }


public:
    LinkedMemoryPool() {
        this->_init_free_list();
    }

    size_t pool_size() const {
        return PoolSize;
    }

    bool has_free_node() const {
        return _free_list != nullptr;
    }

    NodeTypeInPool *get_node_from_pool() {
        NodeTypeInPool *node = _free_list;
        if (_free_list != nullptr) {
            _free_list = _free_list->next;  // 空闲链表的节点存取都发生在头节点
        }
        return node;
    }

    void return_node_to_pool(NodeTypeInPool *node) {
        node->next = this->_free_list;
        this->_free_list = node;
    }

    // 禁止拷贝
    LinkedMemoryPool(const LinkedMemoryPool &) = delete;
    LinkedMemoryPool &operator=(const LinkedMemoryPool &) = delete;
};


// TODO: 再设计个全动态的伪内存池，新增节点用malloc，释放用free
//       以及动态膨胀的内存池，新增的节点用malloc，回收节点用链表串起来备用，只获取内存，不释放，从而不会产生内存碎片
//       动态膨胀的内存池可以打印日志，用来分析程序需要的内存池最大尺寸

// TODO: DynamicMemoryPool
// 动态内存池，有一个“不收缩”的选项，即内存池容量只增不减。内存池内只存储一种数据类型。
//


template <typename LinkedPool>
class SimpleForwardList {
public:
    using NodeType = typename LinkedPool::NodeTypeInPool;
    using DataType = decltype(NodeType::data);


private:
    LinkedPool &_pool;
    NodeType *_list_head = nullptr;


public:
    explicit SimpleForwardList(LinkedPool &memory_pool) :
        _pool(memory_pool) {}

    // explicit SimpleForwardList() : _pool(LinkedPool{}){}

    size_t max_size() const { return this->_pool.pool_size(); }

    size_t has_free_space() const { return this->_pool.has_free_node(); }

    size_t size() const {
        if (this->_list_head == nullptr)
            return 0;

        NodeType *temp_ptr = this->_list_head;
        size_t count = 1;
        while (temp_ptr->next != nullptr) {
            ++count;
            temp_ptr = temp_ptr->next;
        }
        return count;
    }

    bool empty() const { return this->_list_head == nullptr; }

    NodeType &front() { return *_list_head; }

    const NodeType &front() const { return *_list_head; }

    void pop_front() { this->remove(this->_list_head); }

    NodeType *find_prev_by_ptr(NodeType *target) {
        NodeType *temp_ptr = this->_list_head;

        while (temp_ptr != nullptr) {
            if (temp_ptr->next == target) {
                return temp_ptr;
            }
            temp_ptr = temp_ptr->next;
        }

        return nullptr;
    }

    NodeType *find_prev_by_value(DataType &target_value) {
        NodeType *temp_ptr = this->_list_head;

        while (temp_ptr != nullptr) {
            if (temp_ptr->next->data == *target_value) {
                return temp_ptr;
            }
            temp_ptr = temp_ptr->next;
        }

        return nullptr;
    }

    /**
         * @brief 删除指针指向的节点，需要遍历链表查找该节点的前驱节点
         *
         * @param that
         */
    void remove(NodeType *that) {
        NodeType *prev = find_prev_by_ptr(that);
        remove(that, prev);
    }


    void remove(const DataType &that_value) {
        NodeType *prev = find_prev_by_value(that_value);
        remove(prev->next, prev);
    }


    /**
         * @brief 用交换数据的方法快速删除节点，但只能用遍历的方式删除最后一个节点。
         *
         * 先把后一节点的数据复制到要删除的目标节点，然后删除后一节点。
         * 注意：如果外部持有列表中节点的引用或指针，这种删除方式可能会把外部持有的节点删除掉，产生野指针。
         *
         * @param that
         */
    void remove_fast_except_end(NodeType *that) {
        if (that->next == nullptr) {
            remove(that);
        }
        that->data = that->next->data;
        remove(that->next, that);
    }


    /**
         * @brief 效率较高的删除target 指针指向的节点，回收内存
         *
         * @param target 指针指向要删除的节点，可以是第一个节点
         * @param prev   指向目标节点的前一个节点，若要删除第一个节点，则prev 必须为head_ptr() 的返回值
         */
    void remove(NodeType *target, NodeType *prev) {
        prev->next = target->next;
        this->_pool.return_node_to_pool(target);
    }


    /**
         * @brief 效率较高的删除target 指针指向的节点，但不回收内存，用于将一个节点转移到其他共用内存池的表中
         *
         * @param target 指针指向要删除的节点，可以是第一个节点
         * @param prev   指向目标节点的前一个节点，若要删除第一个节点，则prev 必须为head_ptr() 的返回值
         */
    void remove_no_recycle(NodeType *target, NodeType *prev) {
        prev->next = target->next;
    }


    /**
         * @brief 清空链表，将所有节点逐个归还到内存池
         *
         */
    void clear() {
        while (!this->empty()) {
            this->remove(this->_list_head, this->head_ptr);
        }
    }


    // 在链表头部插入一个新节点，若剩余空闲空间不足，则函数不做任何操作，可用has_free_space 函数在插入元素前检查
    NodeType *push_front(const DataType &data) {
        NodeType *new_node = this->_pool.get_node_from_pool();
        if (new_node == NULL)
            return nullptr;
        new_node->data = data;
        new_node->next = this->_list_head;
        this->_list_head = new_node;
        return new_node;
    }


    // 这个插入不会新创建节点，而是直接复用输入的节点，所以要保证输入的节点来自目标链表，或来自与目标链表关联的内存池，否则内存池的管理将发生混乱。
    // 这个函数可用于手动回收、移动链表内节点，或在修改节点数据后重新插入链表，还可以在多个共用内存池的链表间移动节点
    NodeType *push_front(NodeType *new_node) {
        new_node->next = this->_list_head;
        this->_list_head = new_node;
    }


    // 将节点插入到大于等于该元素的元素之前, 使链表保持从小到大的顺序, 内部数据类型要支持小于号 < 运算
    // 自始至终只使用insert_sorted 插入元素，可保证链表从小到大顺序，否则结果随机
    // 这个插入不会新创建节点，而是直接复用输入的节点，所以要保证输入的节点来自目标链表，或来自与目标链表关联的内存池，否则内存池的管理将发生混乱。
    // 这个函数可用于手动回收、移动链表内节点，或在修改节点数据后重新插入链表，还可以在多个共用内存池的链表间移动节点
    NodeType *insert_sorted(NodeType *new_node) {
        // 查找插入位置
        NodeType *current = this->_list_head, *prev = head_ptr();
        while (current != nullptr && current->data < new_node->data) {  // 找到一个比新节点大的节点，把新节点插在前面，实现从小到大排序
            prev = current;
            current = current->next;
        }
        // 插入新节点
        // if (prev == nullptr) {  // 表示head == NULL 或头部第一个节点就比新节点大，所以让head 指向新节点，新节点的next 是原来的head
        //     new_node->next = this->_list_head;
        //     this->_list_head = new_node;
        // }
        // else {                            // prev 指向比新节点大的节点的前一个节点，所以就是要把新节点插进prev 和current 中间
        //     new_node->next = prev->next;  // 也可以写成 new_node->next = current;
        //     prev->next = new_node;
        // }
        new_node->next = prev->next;
        prev->next = new_node;
        return new_node;
    }


    // 用输入的data 创建新节点，将其插入到大于等于该元素的元素之前, 使链表保持从小到大的顺序, 内部数据类型要支持小于号 < 运算
    // 若剩余空闲空间不足，则函数不做任何操作，可用has_free_space 函数在插入元素前检查
    NodeType *insert_sorted(const DataType &data) {
        NodeType *new_node = this->_pool.get_node_from_pool();
        if (new_node == nullptr)
            return nullptr;
        new_node->data = data;
        return insert_sorted(new_node);
    }


    /**
         * @brief 返回指向第一个节点前的虚拟头节点的指针，只能对其使用->next 操作，无data 成员
         *
         * @return NodeType* 实际上是指向指向第一节点的指针的指针，即指向成员变量list_head 的指针，
         *         可以对返回值使用ptr->next = node_ptr 赋值语句修改list_head，使其指向node_ptr。
         *         由于LinkNode 中第一个成员就是next 指针，所以指向节点的指针也可以看作指向next 指针的指针，即指向下一个节点的二极指针。
         *         使用这种技巧的目的是在删除节点时，不用特殊对待表中的第一个节点，可以和其他节点一样修改prev->next。
         */
    NodeType *head_ptr() { return reinterpret_cast<NodeType *>(&_list_head); }

    const NodeType *chead_ptr() const {
        return reinterpret_cast<const NodeType *>(&_list_head);
    }

    /**
         * @brief 返回指向第一个节点的指针
         *
         * @return NodeType* 指向第一个节点的指针
         */
    NodeType *begin_ptr() { return this->_list_head; }

    const NodeType *begin_ptr() const {
        return this->_list_head;
    }

    const NodeType *cbegin_ptr() const {
        return this->_list_head;
    }

    NodeType *end_ptr() const {
        return nullptr;
    }

    const NodeType *cend_ptr() const {
        return nullptr;
    }
};


template <typename T>
class PtrToObject {
private:
    T *_ptr;

public:
    PtrToObject(T *ptr = nullptr) :
        _ptr(ptr) {}

    bool operator!=(const PtrToObject<T> &it) { return this->_ptr != it._ptr; }

    T &operator*() { return *_ptr; }

    const T &operator*() const { return *_ptr; }

    T *operator->() { return _ptr; }

    const T *operator->() const { return _ptr; }

    void swap(PtrToObject<T> &another) {
        swap(this->_ptr, another.ptr);
    }

    bool is_nullptr() const {
        return _ptr == nullptr;
    }

    const T &to_object() const {
        return *_ptr;
    }

    T &to_object() {
        return *_ptr;
    }
};


template <typename T>
bool operator<(const PtrToObject<T> &left, const PtrToObject<T> &right) {
    return *left < *right;
}


/**
     * @brief 用来存储指向较大结构体或对象的指针，然后可以对指针排序
     *
     * 主要适用于只增不减的场合, 或一次性全部清除然后重新从头加入数据
     *
     * @tparam T
     * @tparam N
     */
template <typename T, size_t N>
class PointerList {
public:
    using SizeType = enough_index_type_t<N>;
private:
    PtrToObject<T> _ptr_list[N];

    SizeType _size = 0;

public:
    bool empty() const {
        return _size == 0;
    }

    bool full() const {
        return _size == N;
    }

    SizeType size() const {
        return _size;
    }

    bool max_size() const {
        return N;
    }

    void clear() {
        _size = 0;
    }

    bool push_back(T *obj) {
        if (_size < N) {
            _ptr_list[_size] = obj;
            ++_size;
            return true;
        } else {
            return false;
        }
    }

    void sort() {
        auto start_it = &_ptr_list[0];
        auto end_it = &_ptr_list[_size];

        std::sort(start_it, end_it);
    }

    PtrToObject<T> &back() {
        return _ptr_list[_size - 1];
    }

    const PtrToObject<T> &back() const {
        return _ptr_list[_size - 1];
    }

    PtrToObject<T> *begin() {
        return &_ptr_list[0];
    }

    PtrToObject<T> *end() {
        return &_ptr_list[_size];
    }

    const PtrToObject<T> *begin() const {
        return &_ptr_list[0];
    }

    const PtrToObject<T> *end() const {
        return &_ptr_list[_size];
    }

    auto &get_ptr_list() {
        return _ptr_list;
    }

    const auto &get_ptr_list() const {
        return _ptr_list;
    }
};


template <typename T>
struct to_signed {
};


template <>
struct to_signed<uint8_t> {
    using type = int8_t;
};


template <>
struct to_signed<uint16_t> {
    using type = int16_t;
};


template <>
struct to_signed<uint32_t> {
    using type = int32_t;
};


template <>
struct to_signed<uint64_t> {
    using type = int64_t;
};


template <typename T>
using to_signed_t = typename to_signed<T>::type;


/**
     * @brief 精简的环形队列实现
     *
     * @tparam T 数据类型
     * @tparam N 数组长度
     */
template <typename T, size_t N>
class RingBuffer {
public:
    using IndexType = enough_index_type_t<N>;

private:
    T _buf[N];
    IndexType _index_back = 0;
    IndexType _index_front = _dec_index(0);
    IndexType _size = 0;

    constexpr IndexType _inc_index(IndexType i) {
        if (i == N - 1)
            return 0;

        return i + 1;
    }

    constexpr IndexType _dec_index(IndexType i) {
        if (i == 0)
            return N - 1;

        return i - 1;
    }

public:
    bool empty() const {
        return _size == 0;
    }

    /**
         * @brief 填入缓冲区的数据个数
         *
         * 返回值有可能大于N，表示有旧数据被覆盖。
         *
         * @return IndexType
         */
    IndexType size() const {
        // 由于允许头尾指针各自独立生长或收缩，只靠两个指针的相对位置不可能绝对计算出准确的缓冲区尺寸
        return _size;
    }

    size_t max_size() const {
        return N;
    }

    /**
         * @brief 缓冲区是否已满
         *
         * @return true   填入的数据个数大于或等于缓冲区尺寸
         * @return false  可以继续安全的填入数据
         */
    bool full() const {
        return size() >= N;
    }

    void clear() {
        _index_front = _dec_index(_index_back);
        _size = 0;
    }

    /**
         * @brief 尾部追加一个元素
         *
         * 不检查剩余可用空间，当空间不足时将发生数据覆盖，此时size() 的返回值可能大于N。
         *
         * @param val
         */
    void push_back(T val) {
        _buf[_index_back] = val;
        _index_back = _inc_index(_index_back);
        ++_size;
    }

    T pop_back() {
        _index_back = _dec_index(_index_back);
        --_size;
        return _buf[_index_back];
    }

    void push_front(T val) {
        _buf[_index_front] = val;
        _index_front = _dec_index(_index_front);
        ++_size;
    }

    T pop_front() {
        _index_front = _inc_index(_index_front);
        --_size;
        return _buf[_index_front];
    }

    /**
         * @brief 将一个数据重复填入缓冲区指定的次数
         *
         * @param val
         * @param count
         */
    void init(T val, size_t count) {
        // assert(count <= N, 'Max Size N Can Not Be Exceeded');
        while (count--) {
            push_back(val);
        }
    }

    T &back() {
        return _buf[_dec_index(_index_back)];
    }

    T &front() {
        return _buf[_inc_index(_index_front)];
    }


    // auto begin() {
    //     return _buf.begin();
    // }

    // auto end() {
    //     return _buf.end();
    // }
};


}  // namespace data_basic