#include <iostream>
#include "stack.h"
int main() {
    Stack<int> a;
    try {
        a.top();
    } catch (std::exception& e) {
        std::cerr << e.what() << "\n";
    }
    a.push(10);
    a.push(100);
    a.push(1000);
    a.push(10000);
    a.pop();
    std::cout << a.top() << " " << a.size() << "\n";
    Stack<int> b;
    b.push(1);
    b.pop();
    b.push(2);
    b = a;
    a.pop();
    std::cout << b.top() << " " << b.size() << "\n";
    Stack<int> c;
    Stack<int> d;
    d = c;
    c.push(1);
    c.stack_print();
    Stack<int> e(c);
    e.push(80);
    e = a;
    e.stack_print();
}

#pragma once
#include <iostream>
#include <cstddef>
#include <stdexcept>
#include "doubly_linked_list.h"
template <typename T>   
class Stack {
   private:
      DoublyLinkedList<T> m_data;
   public:
      Stack()
      : m_data() {}
      Stack(const Stack& stack)
      : m_data(stack.items()) {}
      ~Stack() {
         m_data.clear();
      }
      Stack& operator=(const Stack& rhs) {
         if (&rhs == this)
            return *this;
         m_data = rhs.items();
         return *this;
      }
      void push(const T& item) {
         m_data.push_back(item);
      }
      void pop() {
         if (m_data.size() == 0)
            throw std::out_of_range("stack is empty");
         m_data.remove(m_data.size() - 1);
      }
      
      T& top() {
         if (m_data.size() == 0)
            throw std::out_of_range("stack is empty");
         return m_data[m_data.size() - 1];
      }
      const DoublyLinkedList<T>& items() const {
         return m_data;
      }
      std::size_t size() const {
         return m_data.size();
      }
      void stack_print() const {
         m_data.print();
      }
};

#include <iostream>
#include "queue.h"
int main() {
    Queue<int> a;
    a.enqueue(1);
    a.enqueue(2);
    a.enqueue(3);
    a.enqueue(4);
    Queue<int> b(a);
    b.dequeue();
    b.enqueue(5);
    a.dequeue();
    a.enqueue(5);
    Queue<int> c;
    c = b;
    c.dequeue();
    c.enqueue(9);
    b.queue_print();
    c.queue_print();
    b.dequeue();
    b.dequeue();
    std::cout << b.size() << "\n";
    std::cout << c.front() << " " << c.size() << "\n";
}

#pragma once
#include <iostream>
#include <stdexcept>
#include "doubly_linked_list.h"
template <typename T>
class Queue {
    private:
        DoublyLinkedList<T> m_data;
    
    public:
        Queue() : m_data() {}
        Queue(const Queue& queue)
        : m_data(queue.items()) {
        }
        ~Queue() {
            m_data.clear();
        }
        Queue& operator=(const Queue& rhs) {
            if (&rhs == this)
                return *this;
            m_data = rhs.items();
            return *this;
        }
        void enqueue(const T& item) {
            m_data.push_back(item);
        }
        T dequeue() {
            if (m_data.size() == 0)
                throw std::out_of_range("cannot dequeue empty queue");
            T res = m_data[0];  
            m_data.remove(0);
            return res;
        }
        T& front() {
            if (m_data.size() == 0)
                throw std::out_of_range("cannot dequeue empty queue");
            
            return m_data[0];
        }
        const DoublyLinkedList<T>& items() const {
            return m_data;
        }
        std::size_t size() const {
            return m_data.size();
        }
        void queue_print() const {
            m_data.print();
        }
};

#include <iostream>
#include "doubly_linked_list.h"
int main() {
    DoublyLinkedList<int> A;
    A.insert(0, 1);
    A.remove(0);
    A.insert(0, 2);
    A.insert(1, 5);
    A.insert(2, 6);
    DoublyLinkedList<int> B;
    B.insert(0, 10);
    B = A;
    B.insert(0,9);
    DoublyLinkedList<int> C(B);
    B.insert(2,8);
    C.insert(0,10);
    C.remove(0);
    C.remove(2);
    A.print();
    B.print();
    C.print();
    std::cout << C[2] << "\n";
    
}

#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";
        }
};

#include <iostream>
#include "array_list.h"
int main() {
    ArrayList<int> a;
    std::cout << a.size() << "\n";
    try {
        a[0];
    } catch (std::exception& e) {
        std::cerr << e.what() << "\n";
    }
    for (std::size_t i = 0; i < 100; i++) {
        a.insert(i, i);
    }
    std::cout << a.size() << "\n";
    ArrayList<int> b;
    b = a;
    std::cout << b.size() << "\n";
    for (std::size_t i = 0; i < 15; i++) {
        b.remove(50);
    }
    std::cout << b.size() << "\n";
    b.insert(80, 100);
    a.remove(0);
    ArrayList<int> c(b);
    c.insert(14, 100000);
    c.remove(20);
    b.remove(1);
    b.insert(1, 12039812);
    std::cout << c.size() << "\n";
    a.print();
    b.print();
    c.print();
    // ArrayList<int> list;
    // list.insert(0,1);
    // list.insert(1,2);
    // list.insert(2,3);
    // list.insert(3,4);
    // list.insert(4,5);
    // list.remove(2);
    // list.print();
    // ArrayList<int> listB(list);
    // listB.insert(4,6);
    // listB.print();
    // ArrayList<int> listC(2);
    // listC.insert(0,10);
    // listC = listB;
    // listC.remove(1);
    // listC.print();
}

#pragma once
#include <utility>
#include <cstddef>
#include <stdexcept>
#include <iostream>
template <typename T>
class ArrayList {
    private:
        std::size_t m_length;
        T* m_data;
    public:
        ArrayList() : m_length(0),  m_data(static_cast<T*>(::operator new(0))) {}
        explicit ArrayList(std::size_t capacity) : m_length(0), m_data(static_cast<T*>(::operator new(sizeof(T) * capacity))) {}
        ArrayList(const ArrayList& rhs)
        : m_length(rhs.size())
        , m_data(static_cast<T*>(::operator new(sizeof(T) * m_length))) {
            for (std::size_t i = 0; i < rhs.size(); i++) {
                m_data[i] = rhs[i];
            }
        }
        ~ArrayList() {
            destruct_current();
            ::operator delete(m_data); 
        }
        
        ArrayList& operator=(const ArrayList& rhs) {
            if (&rhs == this) 
                return *this;
            destruct_current();
            ::operator delete(m_data);
            m_length = rhs.size();
            m_data = static_cast<T*>(::operator new(sizeof(T) * m_length));
            for (std::size_t i = 0; i < m_length; i++) {
                m_data[i] = rhs[i];
            }
          
            return *this;
        }
        T& operator[](std::size_t index) {
            if (index < 0 || index >= m_length) {
                throw std::out_of_range("index out of range");
            }
            return m_data[index];
        }
        const T& operator[](std::size_t index) const {
            if (index < 0 || index >= m_length) {
                throw std::out_of_range("index out of range");
            }
            return m_data[index];
        }
        T* items() const {
            return m_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 is out of range");
            }
            T* temp = static_cast<T*>(::operator new(sizeof(T) * (m_length + 1)));
            for (std::size_t i = 0; i < index; i++) {
                temp[i] = std::move(m_data[i]);
            }
            temp[index] = item;
            for (std::size_t i = index; i < m_length; i++) {
                temp[i + 1] = std::move(m_data[i]);
            }
            m_length++;
            destruct_current();
            ::operator delete(m_data);
            m_data = temp;
        }
        void remove(std::size_t index) {
            if (m_length == 0 || index < 0 || index >= m_length) {
                throw std::out_of_range("index is out of range");
            }
            T* temp = static_cast<T*>(::operator new(sizeof(T) * m_length - 1));
            for (std::size_t i = 0; i < index; i++) {
                temp[i] = std::move(m_data[i]);
            }
            for (std::size_t i = index + 1; i < m_length; i++) {
                temp[i - 1] = std::move(m_data[i]);
            }
            destruct_current();
            ::operator delete(m_data);
            m_data = temp;
            m_length--;
        }
        void destruct_current() {
            for (std::size_t i = 0; i < m_length; i++) {
                m_data[i].~T();
            }
        }
        void print() const {
            for (std::size_t i = 0; i < m_length; i++) {
                std::cout << m_data[i] << " ";
            }
            std::cout << "\n";
        }
};

all: array_list linked_list stack queue
clean: 
	rm -f *.gcov *.gcda *.gcno a.out
array_list: clean array_list.h array_list_tests.cpp
	g++ -std=c++17 -Wall -Wextra -Weffc++ -g --coverage array_list_tests.cpp && ./a.out && gcov -mr array_list_tests.cpp
linked_list: clean doubly_linked_list.h doubly_linked_list_tests.cpp
	g++ -std=c++17 -Wall -Wextra -Weffc++ -g --coverage doubly_linked_list_tests.cpp && ./a.out && gcov -mr doubly_linked_list_tests.cpp
stack: clean stack.h stack_tests.cpp
	g++ -std=c++17 -Wall -Wextra -Weffc++ -g --coverage stack_tests.cpp && ./a.out && gcov -mr stack_tests.cpp
	
queue: clean queue.h queue_tests.cpp
	g++ -std=c++17 -Wall -Wextra -Weffc++ -g --coverage queue_tests.cpp && ./a.out && gcov -mr queue_tests.cpp