#pragma once

#include <iostream>
#include <cstddef>
#include <stdexcept>

template <typename T>
class DoublyLinkedList {
    private:
        struct Node {
            Node* next;
            Node* prev;
            T data;
        };
        Node* m_head;
        Node* m_tail;
        std::size_t m_length;

    public:
        DoublyLinkedList()
        : m_head(nullptr)
        , m_tail(nullptr)
        , m_length(0) {}

        DoublyLinkedList(const DoublyLinkedList& rhs) 
        : m_head(nullptr)
        , m_tail(nullptr)
        , m_length(0) {
            Node* temp = rhs.head();
            while (temp != nullptr) {
                push_back(temp->data);
                temp = temp->next;
            }
            delete temp;
            m_length = rhs.size();
        }

        ~DoublyLinkedList() {
            clear();
        }

        DoublyLinkedList& operator=(const DoublyLinkedList& rhs) {
            if (&rhs == this)
                return *this;

            clear();
            Node* temp = rhs.head();

            while (temp != nullptr) {
                push_back(temp->data);
                temp = temp->next;
            }
            delete temp;
            m_length = rhs.size();
            return *this;
        }

        T& operator[](std::size_t index) {
            if (index < 0 || index >= m_length) {
                throw std::out_of_range("index out of range");
            }

            std::size_t curr_index = 0;
            Node* temp = m_head;

            while (temp != nullptr) {
                if (curr_index == index) {
                    break;
                }

                temp = temp->next;
                curr_index++;       
            }
            return temp->data;
        }

        std::size_t size() const {
            return m_length;
        }

        void insert(std::size_t index, const T& item) {
            if (index < 0 || index > m_length) {
                throw std::out_of_range("index out of range");
            }

            if (index == 0) {
                push_front(item);
            } else if (index == m_length) {
                push_back(item);
            } else {
                Node* new_node = new Node;
                new_node->data = item;
                Node* temp = m_head;
                std::size_t curr_index = 0;

                while (temp != nullptr) {
                    if (curr_index == index) {
                        new_node->next = temp;
                        new_node->prev = temp->prev;
                        new_node->prev->next = new_node;
                        new_node->next->prev = new_node;
                        break;
                    }

                    temp = temp->next;
                    curr_index++;
                }
                m_length++;
            }
        }

        void remove(std::size_t index) {
            if (index < 0 || index >= m_length) {
                throw std::out_of_range("index out of range");
            }

            if (index == 0) {
                Node* temp = m_head;
                m_head = temp->next;
                m_length--;
                delete temp;
            } else if (index == m_length - 1) {
                m_tail = m_tail->prev;
                delete m_tail->next;
                m_tail->next = nullptr;
                m_length--;

            } else {
                Node* temp = m_head;
                std::size_t curr_index = 0;

                while (temp != nullptr) {
                    if (curr_index == index) {
                        temp->prev->next = temp->next;
                        delete temp;
                        m_length--;
                        break;
                    }

                    temp = temp->next;
                    curr_index++;
                }
            }
        }

        Node* head() const {
            return m_head;
        }

        void push_back(const T& item) {
            Node* new_node = new Node;
            new_node->data = item;
            new_node->next = nullptr;

            if (m_head == nullptr) {
                new_node->prev = nullptr;
                m_head = new_node;
                m_tail = new_node;
            } else {
                new_node->prev = m_tail;
                m_tail->next = new_node;
                m_tail = new_node;
            }
            m_length++;
        }

        void push_front(const T& item) {
            Node* new_node = new Node;
            new_node->data = item;
            new_node->prev = nullptr;

            if (m_head == nullptr) {
                new_node->next = nullptr;
                m_head = new_node;
                m_tail = new_node;
            } else {
                new_node->next = m_head;
                m_head->prev = new_node;
                m_head = new_node;
            }
            m_length++;
        }

        void clear() {
            Node* curr_node = m_head;
            
            while (curr_node != nullptr) {
                Node* temp = curr_node->next;
                delete curr_node;
                curr_node = temp;
            }

            m_head = nullptr;
            m_tail = nullptr;
            m_length = 0;
        }

        void print() const {
            Node* temp = m_head;

            while (temp != nullptr) {
                std::cout << temp->data << " ";
                temp = temp->next;
            }

            std::cout << "\n";
        }
};