DoublyCircularList

//  Copyright [2017] <Jean Leopoldo>
#ifndef STRUCTURES_DOUBLY_CIRCULAR_LIST_H
#define STRUCTURES_DOUBLY_CIRCULAR_LIST_H

#include <cstdint>
#include <stdexcept>
#include <iostream>

namespace structures {

template<typename T>
class DoublyCircularList {
 public:
    DoublyCircularList() {
        size_ = 0;
        head = nullptr;
        tail = nullptr;
    }

    ~DoublyCircularList() {
        clear();
    }

    void clear() {
        while (!empty()) {
            pop_front();
        }
    }

    void push_back(const T& data) {
        if (empty()) {
            push_front(data);
        } else {
            Node *node = new Node(data, head, tail);
            if (node == nullptr) {
                throw std::out_of_range("full");
            } else {
                size_++;
                Node *aux = tail;
                aux->next(node);
                delete aux;
            }
        }
    }
    void push_front(const T& data) {
        Node *node = new Node(data, head);
        if (node == nullptr) {
            throw std::out_of_range("full");
        } else if (size_ == 0) {
            size_++;
            head = node;
            tail = node;
            node->next(head);
            node->prev(head);
        } else {
            size_++;
            node->next(head);
            node->prev(tail);
            head = node;
        }
    }
    void insert(const T& data, std::size_t index) {
        if (indexOut(index)) {
            throw std::out_of_range("invalid index");
        } else if (index == 0) {
            push_front(data);
        } else if (index == size_) {
            push_back(data);
        } else {
            Node *node = new Node(data);
            if (node == nullptr) {
                throw std::out_of_range("full");
            } else {
                size_++;
                Node *aux = head;
                for (int i = 0; i < index-1; i++) {
                    aux = aux->next();
                }
                node->next(aux->next());
                node->prev(aux);
                aux->next(node);
                aux->next()->prev(node);
                delete aux;
            }
        }
    }
    void insert_sorted(const T& data) {
        if (empty()) {
            push_front(data);
        } else {
            // sortList();
            Node *aux = head;
            for (int i = 0; i < size_-1; i++) {
                if (data < aux->data()) {
                    delete aux;
                    insert(data, i);
                } else {
                    aux = aux->next();
                }
            }
        }
    }

    T pop(std::size_t index) {
        if (indexOut(index)) {
            throw std::out_of_range("invalid index");
        } else if (empty()) {
            throw std::out_of_range("empty");
        } else if (index == 1 || size_ == 1) {
            return pop_front();
        } else if (index == size_) {
            return pop_back();
        } else {
            size_--;
            Node *aux = head;
            for (int i = 0; i < index-2; i++) {
                aux = aux->next();
            }
            Node *del = aux->next();
            T data = del->data();
            del->next()->prev(aux);
            aux->next(del->next());
            delete aux;
            delete del;
            return data;
        }
    }
    T pop_back() {
        if (size_ == 1) {
            return pop_front();
        } else if (empty()) {
            throw std::out_of_range("empty");
        } else {
            size_--;
            Node *aux = tail->prev();
            Node *del = tail;
            T data = del->data();
            head->prev(aux);
            aux->next(head);
            delete aux;
            delete del;
            return data;
        }
    }
    T pop_front() {
        if (empty()) {
            throw std::out_of_range("empty");
        } else {
            size_--;
            Node *aux = head;
            T data = aux->data();
            tail->next(aux->next());
            head->next()->prev(tail);
            delete aux;
            return data;
        }
    }
    void remove(const T& data) {
        if (empty()) {
            throw std::out_of_range("empty");
        } else {
            Node *aux = head;
            for (int i = 1; i < size_-1; i++) {
                if (aux->data() == data) {
                    pop(i);
                }
                aux = aux->next();
            }
        }
    }

    bool empty() const {
        if (size_ == 0) {
            return true;
        } else {
            return false;
        }
    }
    bool contains(const T& data) const {
        if (empty()) {
            throw std::out_of_range("empty");
        } else {
            Node *aux = head;
            for (int i = 0; i < size_-1; i++) {
                if (aux->data() == data) {
                    delete aux;
                    return true;
                }
                aux = aux->next();
            }
            delete aux;
            return false;
        }
    }

    T& at(std::size_t index) {
        if (indexOut(index)) {
            throw std::out_of_range("invalid index");
        } else if (empty()) {
            throw std::out_of_range("empty");
        } else {
            Node *aux = head;
            for (int i = 0; i < index-1; i++) {
                aux = aux->next();
            }
            T& data = aux->data();
            delete aux;
            return data;
        }
    }
    const T& at(std::size_t index) const {
        if (indexOut(index)) {
            throw std::out_of_range("invalid index");
        } else if (empty()) {
            throw std::out_of_range("empty");
        } else {
            Node *aux = head;
            T& data;
            for (int i = 0; i < index-1; i++) {
                aux = aux->next();
            }
            data = aux->data();
            delete aux;
            return data;
        }
    }

    std::size_t find(const T& data) const {
        if (empty()) {
            throw std::out_of_range("empty");
        } else {
            Node *aux = head;
            for (int i = 0; i < size_-1; i++) {
                if (aux->data() == data) {
                    delete aux;
                    return i;
                }
            }
            delete aux;
            throw std::out_of_range("data has not been found");
        }
    }
    std::size_t size() const {
        return size_;
    }

 private:
    class Node {
     public:
        explicit Node(const T& data) {
            data_ = data;
            next_ = nullptr;
            prev_ = nullptr;
        }
        Node(const T& data, Node* next) {
            data_ = data;
            next_ = next;
            prev_ = nullptr;
        }
        Node(const T& data, Node* prev, Node* next) {
            data_ = data;
            next_ = next;
            prev_ = prev;
        }

        T& data() {
            return data_;
        }
        const T& data() const {
            return data_;
        }

        Node* prev() {
            return prev_;
        }
        const Node* prev() const {
            return prev_;
        }

        void prev(Node* node) {
            prev_ = node;
        }

        Node* next() {
            return next_;
        }
        const Node* next() const {
            return next_;
        }

        void next(Node* node) {
            next_ = node;
        }

     private:
        T data_;
        Node* prev_;
        Node* next_;
    };

    Node *head;
    Node *tail;
    std::size_t size_;

    bool indexOut(std::size_t index) {
        if (index < 0 || index > size_) {
            return true;
        } else {
            return false;
        }
    }
};

}  //  namespace structures

#endif