#ifndef Toolbox_Circular_Linked_List_H
#define Toolbox_Circular_Linked_List_H
#include <vector>
namespace Toolbox {
    template<typename T>
    struct Circular_Linked_List_Node {
        Circular_Linked_List_Node *prev = nullptr, *next = nullptr;
        T data;
    };
    template<typename T>
    class Circular_Linked_List {
    public:
        Circular_Linked_List_Node<T> *head = nullptr;
        Circular_Linked_List_Node<T> *cur = nullptr;
        void init(const std::vector<T> &data_list) {
            head = new Circular_Linked_List_Node<T>();
            head->data = data_list.front();
            Circular_Linked_List_Node<T> *prev = head;
            int n = data_list.size();
            for (int i = 1; i < n - 1; i++) {
                auto node = new Circular_Linked_List_Node<T>();
                node->data = data_list[i];
                node->prev = prev;
                prev->next = node;
                prev = node;
            }
            auto tail = new Circular_Linked_List_Node<T>();
            tail->data = data_list.back();
            tail->prev = prev;
            prev->next = tail;
            tail->next = head;
            head->prev = tail;
            cur = head;
        }
        Circular_Linked_List_Node<T> *move(int step = 1) {
            if (step == 0) return nullptr;
            return step > 0 ? next(step) : prev(-step);
        }
        Circular_Linked_List_Node<T> *next(int step = 1) {
            if (step <= 0) return nullptr;
            for (int i = 0; i < step; i++) {
                cur = cur->next;
            }
            return cur;
        }
        Circular_Linked_List_Node<T> *prev(int step = 1) {
            if (step <= 0) return nullptr;
            for (int i = 0; i < step; i++) {
                cur = cur->prev;
            }
            return cur;
        }
        void insert_next(const T &t, Circular_Linked_List_Node<T> *that = nullptr) {
            if (that == nullptr) that = cur;
            auto node = new Circular_Linked_List_Node<T>();
            node->data = t;
            node->next = that->next;
            node->prev = that;
            that->next = node;
        }
        void insert_prev(const T &t, Circular_Linked_List_Node<T> *that = nullptr) {
            if (that == nullptr) that = cur;
            auto node = new Circular_Linked_List_Node<T>();
            node->data = t;
            node->prev = that->prev;
            node->next = that;
            that->prev = node;
        }
        std::vector<Circular_Linked_List_Node<T> *> to_vector() {
            if (head == nullptr) return {};
            std::vector<Circular_Linked_List_Node<T> *> ret;
            Circular_Linked_List_Node<T> *cur = head;
            do {
                ret.push_back(cur);
                cur = cur->next;
            } while (cur != head);
            return ret;
        }
        void clear() {
            if (head == nullptr) return;
            Circular_Linked_List_Node<T> *cur = head;
            do {
                Circular_Linked_List_Node<T> *temp = cur;
                cur = cur->next;
                delete temp;
            } while (cur != head);
            head = nullptr;
        }
        ~Circular_Linked_List() {
            clear();
        }
    };
}
#endif



