LinkedList

// Copyright [2017 <Jean Leopoldo]
#ifndef STRUCTURES_LINKED_LIST_H
#define STRUCTURES_LINKED_LIST_H

#include <cstdint>
#include <stdexcept>

namespace structures {

template<typename T>
//! class LinkedList
/*
*  class LinkedList
*/
class LinkedList {
 public:
//! constructor
/*
*  constructor
*/

    LinkedList() {
        head = nullptr;
        size_ = 0;
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    ~LinkedList() {
        clear();
    }
//! clear
/*
*  verifies if list is empty. if not, destruct list
*/
    void clear() {
        while (!empty()) {
            pop_front();
        }
        head = nullptr;
        size_ = 0;
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    void push_back(const T& data) {
        insert(data, size_);
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    void push_front(const T& data) {
        Node *node = new Node(data);
        if (node == nullptr)
            throw std::out_of_range("full");
        insert(data, 0);
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    void insert(const T& data, std::size_t index) {
        if (indexOut(index))
            throw std::out_of_range("invalid index");
        Node *node = new Node(data);
        if (node == nullptr)
            throw std::out_of_range("full");
        if (index == 0) {
            size_++;
            head = node;
        }
        Node *aux = head;
        if (index == size_-1) {
            size_++;
            for (int i = 0; i < size_-1; i++)
                aux = aux->next();
            aux->next(node);
            node->next(nullptr);
            delete aux;
        }
        size_++;
        for (int i = 0; i < index-1; i++)
            aux = aux->next();
        size_++;
        aux->next(node);
        delete aux;
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    void insert_sorted(const T& data) {
        Node *node = new Node(data);
        if (node == nullptr)
            throw std::out_of_range("full");
        Node *aux = head;
        for (int i = 0; i < size_-1; i++) {
            if (aux->data() < data)
                aux = aux->next();
            insert(data, i);
          }
        delete aux;
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    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;
        T& data;
        for (int i = 0; i < index -1; i++) {
            aux = aux->next();
            if (index == i) {
                data = aux->data();
                delete aux;
                return data;
            }
        }
        throw "not found";
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    T pop(std::size_t index) {
        if (empty())
            throw std::out_of_range("empty");
        if (indexOut(index))
            throw std::out_of_range("invalid index");
        Node *aux = head;
        Node *del;
        T data;
        for (int i = 0; i < index -2; i++)
            aux = aux->next();
        size_--;
        del = aux->next();
        data = del->data();
        aux = del->next();
        delete del;
        delete aux;
        return data;
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    T pop_back() {
        if (empty())
            throw std::out_of_range("empty");
        Node *aux = head, *del;
        T data;
        for (int i = 0; i < size_ -1; i++)
            aux = aux->next();
        del = aux->next();
        data = del->data();
        aux->next(nullptr);
        size_--;
        delete del;
        delete aux;
        return data;
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    T pop_front() {
        if (empty())
            throw std::out_of_range("empty");
        Node *aux = head;
        for (int i = 0; i < size_-1; i++)
            aux = aux->next();
        size_--;
        T data = aux->data();
        head = aux->next();
        delete aux;
        return data;
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    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);
            aux = aux->next();
        delete aux;
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    bool empty() const {
        if (size_ == 0)
            return true;
        return false;
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    bool contains(const T& data) const {
        Node *aux = head;
        for (int i = 0; i < size_-1; i++) {
            aux = aux->next();
            if (aux->data() == data)
                return true;
        }
        return false;
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    std::size_t find(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)
                return i;
        return -1;
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    std::size_t size() const {
        return size_;
    }

 private:
    class Node {
     public:
        explicit Node(const T& data) {
            data_ = data;
            next_ = nullptr;
        }

        Node(const T& data, Node* next) {
            data_ = data;
            next_ = next;
        }

        T& data() {
            return data_;
        }

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

        Node* next() {
            return next_;
        }

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

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

     private:
        T data_;
        Node* next_;
    };
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    Node* end() {
        auto it = head;
        for (auto i = 1u; i < size(); ++i) {
            it = it->next();
        }
        return it;
    }
//! destructor
/*
*  verifies if list is empty. if not, destruct list
*/
    bool indexOut(std::size_t index) {
        if (index < 0 || index > size_)
            return true;
        return false;
    }

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

}  //  namespace structures

#endif