/*
    gll.h
    CIS 250
    2016-03-22
    David Klick

    Templated linked list specification. This implementation
    uses reference variables.
*/

#ifndef __GLL_H__
#define __GLL_H__
#include <cassert>
#include <iostream>
#include <string>
using std::string;
using std::ostream;

template<typename T>
class gll {
public:
    class node {
    public:
        T data;
        node *next;
    };
private:
    node *head;
    int count;
public:
    gll() : head(NULL), count(0) {}
    ~gll();
    int length() const;
    bool search(T& val) const;
    T front() const;
    T back() const;
    T removeFirst();
    T removeLast();
    bool isEmpty() const;
    void addFirst(T& val);
    void addLast(T& val);
    void add(T& val);
    bool remove(T& val);
    friend ostream& operator<<(ostream& out, const gll<T>& lst) {
        node* current = lst.head;
        while (current != NULL) {
            out << current->data << " ";
            current = current->next;
        }
        return out;
    }
};

template<typename T>
gll<T>::~gll() {
    while (head != NULL) {
        node* hold = head->next;
        delete head;
        head = hold;
        count--;
    }
}

template<typename T>
int gll<T>::length() const {
    return count;
}

template<typename T>
bool gll<T>::search(T& val) const {
    bool found = false;
    node* pos = head;
    while (pos != NULL) {
        if (*(pos->data) == val) {
            found = true;
            break;
        }
        pos = pos->next;
    }
    return found;
}

template<typename T>
T gll<T>::removeFirst() {
    if (head == NULL) throw string("Error: Accessing empty list");
    T data = head->data;
    node* leaving = head;
    head = head->next;
    delete leaving;
    count--;
    return data;
}

template<typename T>
T gll<T>::removeLast() {
    if (head == NULL) throw string("Error: Accessing empty list");
    node *prev = NULL, *curr = head;
    while (curr->next != NULL) {
        prev = curr;
        curr = curr->next;
    }
    T data = curr->data;
    if (prev != NULL) prev->next = NULL;
    head = prev;
    delete curr;
    count--;
    return data;
}

template<typename T>
T gll<T>::front() const {
    if (head == NULL) throw string("Error: Accessing empty list");
    return head->data;
}

template<typename T>
T gll<T>::back() const {
    if (head == NULL) throw string("Error: Accessing empty list");
    node* pos = head;
    while (pos->next != NULL) pos = pos->next;
    return pos->data;
}

template<typename T>
bool gll<T>::isEmpty() const {
    return head == NULL;
}

template<typename T>
void gll<T>::addFirst(T& obj) {
    node *newnode = new node;
    assert (newnode != NULL);
    newnode->data = obj;
    newnode->next = head;
    head = newnode;
    count++;
}

template<typename T>
void gll<T>::addLast(T& obj) {
    node *newnode = new node;
    assert (newnode != NULL);
    newnode->data = obj;
    newnode->next = NULL;
    if (head == NULL) {
        head = newnode;
    } else {
        node *pos = head;
        while (pos->next != NULL) pos = pos->next;
        pos->next = newnode;
    }
    count++;
}

template<typename T>
void gll<T>::add(T& obj) {
    addLast(obj);
}

template<typename T>
bool gll<T>::remove(T& obj) {
    if (head == NULL) return false;
    if (head->data == obj) {
        node *temp = head;
        head = head->next;
        delete temp;
        count--;
        return true;
    }
    node* prev = head;
    node* curr = prev->next;
    while (curr != NULL) {
        if (curr->data == obj) {
            prev->next = curr->next;
            delete curr;
            count--;
            return true;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }
    return false;
}

#endif