DoublyLinkedList

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

#include <cstdint>
#include <stdexcept>

namespace structures {

template<typename T>
//! class DoublyLinkedList
/*
*  class DoublyLinkedList
*/
class DoublyLinkedList {
 public:
//! constructor DoublyLinkedList
/*
*  constructor DoublyLinkedList
*/
    DoublyLinkedList() {
        head = nullptr;
        size_ = 0;
    }
//! constructor DoublyLinkedList
/*
*  constructor DoublyLinkedList
*/
    ~DoublyLinkedList() {
        clear();
    }
//! constructor DoublyLinkedList
/*
*  constructor DoublyLinkedList
*/
    void clear() {
        Node *aux;
        while (!empty()) {
            aux = head;
            head = head->next();
            delete aux;
        }
    }
//! pop_back DoublyLinkedList
/*
*  checks if list is empty
*/
    void push_back(const T& data) {
        Node *node = new Node(data);
        if (node == nullptr)
            throw std::out_of_range("full");
        size_++;
        Node *aux = head;
        for (int i = 0; i < size_-1; i++)
            aux = aux->next();
        node->prev(aux);
        aux->next(node);
        delete aux;
    }
//! pop_back DoublyLinkedList
/*
*  insert data at the front of the list
*/
    void push_front(const T& data) {
        Node *node = new Node(data, head);
        if (node == nullptr)
            throw std::out_of_range("full");
        size_++;
        head->prev(node);
        head = node;
    }
//! pop_back DoublyLinkedList
/*
*  insert data at a specified index on the list
*/
    void insert(const T& data, std::size_t index) {
        Node *node = new Node(data);
        if (node == nullptr)
            throw std::out_of_range("full");
        if (index == 1)
            push_front(data);
        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);
        node->next()->prev(node);
        delete aux;
    }
//! pop_back DoublyLinkedList
/*
*  checks if list is empty
*/
    void insert_sorted(const T& data) {
        Node *node = new Node(data, head);
        if (node == nullptr)
            throw std::out_of_range("full");
        Node *aux = head;
        for (int i = 0; i < size_-1; i++)
            if (data < aux->data())
                insert(data, i);
            aux = aux->next();
        delete aux;
    }
//! pop_back DoublyLinkedList
/*
*  checks if list is empty
*/
    T pop(std::size_t index) {
        if (empty())
            throw std::out_of_range("empty");
        if (indexOut(index))
            throw std::out_of_range("invalid index");
        size_--;
        Node *aux = head;
        Node *del;
        T data;
        for (int i = 0; i < index-1; i++)
            aux = aux->next();
        del = aux->next();
        data = del->data();
        aux->next(del->next());
        del->next()->prev(aux);
        delete aux;
        delete del;
        return data;
    }
//! pop_back DoublyLinkedList
/*
*  checks if list is empty
*/
    T pop_back() {
        return pop(size_);
    }
//! pop_front DoublyLinkedList
/*
*  checks if list is empty
*/
    T pop_front() {
        if (empty())
            throw std::out_of_range("empty");
        size_--;
        T data = head->data();
        head = head->next();
        return data;
    }
//! empty DoublyLinkedList
/*
*  checks if list is empty
*/
    void remove(const T& data) {
        if (empty())
            throw std::out_of_range("empty");
        Node *aux = head;
        for (int i = 0; i < size_-1; i++)
            if (aux->data() == data)
                pop(i);
        delete aux;
        throw std::out_of_range("data not found");
    }
//! empty DoublyLinkedList
/*
*  checks if list is empty
*/
    bool empty() const {
        if (size_ == 0)
            return true;
        return false;
    }
//! contains DoublyLinkedList
/*
*  checks if data exists in the list
*/
    bool contains(const T& data) const {
        if (empty())
            throw std::out_of_range("empty");
        Node *aux = head;
        for (int i = 0; i < size_-1; i++)
            if (aux->data() == data)
                return true;
            aux = aux->next();
        return false;
    }
//! at DoublyLinkedList
/*
*  returns data from the index
*/
    T& at(std::size_t index) {
        if (indexOut(index))
            throw std::out_of_range("invalid index");
        if (empty())
            throw std::out_of_range("empty");
        Node *aux = head;
        for (int i = 0; i < index-1; i++)
            aux = aux->next();
        return aux->data();
    }
//! at DoublyLinkedList
/*
*  returns data from the index
*/
    const T& at(std::size_t index) const {
        if (indexOut(index))
            throw std::out_of_range("invalid index");
        if (empty())
            throw std::out_of_range("empty");
        Node *aux = head;
        T data;
        for (int i = 0; i < index-1; i++)
            aux = aux->next();
        data = aux->data();
        delete aux;
        return data;
    }
//! find DoublyLinkedList
/*
*  returns the position where data is
*/
    std::size_t find(const T& data) const {
        if (empty())
            throw std::out_of_range("empty");
        Node *aux = head;
        for (int i = 0; i < size_-1; i++)
            if (aux->data() == data)
                return i;
            aux = aux->next();
        throw std::out_of_range("data not found");
    }
//! size DoublyLinkedList
/*
*  returns size of the list
*/
    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;
    std::size_t size_;

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

}  //  namespace structures

#endif