/***********************************************************************
* linkedlist.h
*
* Header file for a simple inplementation of a singly-linked list,
* updated to use templates.
*
* Templates allow the list to be used, without modification, for any
* type on which can be compared using <, >, ==
*
* Note that there is no corresponding .cpp file. Templates must be
* implemented in a single file.
*
* Written by Paul Bonamy - 30 September 2009
* Updated to use templates - 2 November 2009
* Updated to include << - 4 November 2009
************************************************************************/

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>

using namespace std;

/***********************************************************************
 * Really, really simple node class
 * Store a node value and a pointer to the next node
 ***********************************************************************/

template <typename T> class Node {
// this ^ tells the compiler that this is a template, and we'll be
// receiving a type, named T, to be used throughout the class
    public:
        T value;      // value stored in the list
        // Note the T. value will be of whatever type the user specifies
        Node<T> * next;    // next node in the list. set to 0 if last node
        Node<T>() { next = 0; } // default constructor. pretty trivial
};

/***********************************************************************
 * Simple linked list class.
 * Implements basic insert, remove, empty, and print
 ***********************************************************************/
template <typename T> class LinkedList {
// this ^ tells the compiler that this is a template, and we'll be
// receiving a type, named T, to be used throughout the class
    private:
        // Node is also a templated class, so we have to define
        // what type it will be storing. That's what the <T> does.
        Node<T> * head;    // address of first node in the list
    
    public:
        LinkedList();   // default constructor
        ~LinkedList();  // destructor
        // Ts below to allow for the use of the user-specified type
        void insert(T v); // do a sorted insert of v into the list
        bool lookup(T v); // check to see if a given value is in the list
        void remove(T v); // remove all instances of v from the list
        void empty();   // delete all nodes in the list
        void print();   // print contents of list
        
        // Overloading friend functions is tricky.
        // You need them to be templates (obviously), but they
        // aren't directly aware of the type of the rest of the class.
        // Explicitely declare them templates with a different
        // typename to get around this.
        template<typename U>
        friend ostream & operator<< (ostream & out, const LinkedList<U>& l);
};


/***********************************************************************
 * template <typename T> LinkedList<T>::LinkedList()
 *
 * default constructor for the LinkedList class.
 * Only needs to initialize head to 0
 *
 * no parameters / no return
 ***********************************************************************/
template <typename T> LinkedList<T>::LinkedList() {
// This ^ and the angle brackets ^ are required for member functions
// of templated classes
    head = 0; // set head to 0 aka NULL, so we can detect empty lists
    return;
}

/***********************************************************************
 * template <typename T> LinkedList<T>::~LinkedList() 
 *
 * destructor for the LinkedList class.
 * Delete all nodes in the list and return
 *
 * no parameters / no return
 ***********************************************************************/
template <typename T> LinkedList<T>::~LinkedList() {
    empty(); // we could code the delete here, but let's use empty()
    return;
}

/***********************************************************************
 * template <typename T> void LinkedList<T>::insert(T v)
 *
 * Insert a given value into the list in sorted order
 *
 * v -> value to add to list / no return
 ***********************************************************************/
template <typename T> void LinkedList<T>::insert(T v) {
    // Note that the input parameter is of type T
    // set up the new node and assign it the correct value
    Node<T> * newbie = new Node<T>();
    newbie->value = v;
    
    if (head == 0) {
        // the list is empty, so insert is trivially easy
        head = newbie;
    }
    else {
        // the list isn't empty, so we'll have to be careful
        if (head->value > newbie->value) {
            // the inserted value should be at the beginning
            newbie->next = head;
            head = newbie;
        }
        else {
            // we'll be inserting somewhere in the middle of the list
            Node<T> * curr = head; // start from the beginning of the list

            while (curr->next != 0) {
                // run through the list looking for boundary between
                // values <= newbie->value and values > newbie->value
                if (curr->next->value > newbie->value) {
                    break;
                }
                curr = curr->next;
            }

            // at this point, we know curr is the last node with value <=
            // the value of newbie (it may be the last node)
            newbie->next = curr->next; // don't lose things after curr
            curr->next = newbie; // add the new node after curr
        }
    }    
    
    return;
}

/***********************************************************************
 * template <typename T> bool LinkedList<T>::lookup(T v) 
 *
 * Check to see if a given value is present in the list. Return
 * a boolean with the answer
 *
 * v -> value we're looking for
 * return: bool answer to "is v in the list?"
 ***********************************************************************/
template <typename T> bool LinkedList<T>::lookup(T v) {
    Node<T> * curr;        // current place in the list
    
    curr = head;        // begin at the beginning
    
    while(curr != 0) {  // and when you get to the end, stop
        if(curr->value == v) {  
            return true;    // we hit the value we want, return true
        }
        if(curr->value > v) {
            break;      // values are in order, break if we passed it
        }
        curr = curr->next;
    }
    
    return false;       // we didn't find it, so return false
}

/***********************************************************************
 * template <typename T> void LinkedList<T>::remove(T v)
 *
 * Remove all instances of a given value from the list
 *
 * v -> value to delete from list / no return
 ***********************************************************************/
template <typename T> void LinkedList<T>::remove(T v) {
    Node<T> * curr;        // current place in the list
    Node<T> * prev;        // previous place in the list
    
    // start by dealing with the case of v being the first value
    while(head != 0) {
        if (head->value != v) {
            break;          // head->value no longer equals v, so stor
        }
        curr = head->next;  // don't lose the rest of the list
        delete head;        // delete the head node
        head = curr;        // update the head pointer
    }
    
    // list is (now) empty, so return
    if (head == 0) { return;}
    
    // we know the head node doesn't have the value we need
    // so start with the next one and hunt through the list
    prev = head;
    curr = head->next;
    while (curr != 0) {
        if(curr->value == v) {
            // we need to delete this node
            prev->next = curr->next;    // remove curr from the list
            delete curr;                // delete curr
            curr = prev->next;          // point curr at the next value
        }
        else {
            // this is not the node you're looking for
            prev = curr;                // update prev
            curr = curr->next;          // update curr
        }
    }
    
    return;
}

/***********************************************************************
 * template <typename T> void LinkedList<T>::empty() 
 *
 * Delete all nodes in the list and return
 *
 * no parameters / no return
 ***********************************************************************/
template <typename T> void LinkedList<T>::empty() {
    Node<T> * curr = head; // start from the beginning of the list
    head = 0;           // no need for the head pointer any more
    Node<T> * next;        // use this to not get lost in the list
    
    // start at the beginning of the list and delete to the end
    while (curr != 0) {     // note that while (curr) would also work here
        next = curr->next;  // figure out the next node
        delete curr;        // delete the current node
        curr = next;        // make the next node the current node
    }
    
    return;
}

/***********************************************************************
 * template <typename T> void LinkedList<T>::print()
 *
 * Print the contents of all nodes, in the order in which they appear
 *
 * no parameters / no return
 ***********************************************************************/
template <typename T> void LinkedList<T>::print() {
    Node<T> * curr = head; // start from the beginning of the list
    
    // start at the beginning of the list and print to the end
    while (curr != 0) {     // note that while (curr) would also work here
        cout << curr->value << " ";
        curr = curr->next;        // make the next node the current node
    }
    
    if (head == 0) {
        cout << "empty";
    }
    
    cout << endl; // print a newline when we're done
    
    return;
}

/***********************************************************************
 * template <typename U> ostream & operator<< (ostream & out, const LinkedList<U>& l)
 *
 * Print the contents of all nodes, in the order in which they appear,
 * but do so using << rather than an explicit call to print
 *
 * no parameters / no return
 ***********************************************************************/
// Note that the typename associated with the class itself (T) doesn't
// appear in this function. Instead, we use the special other typename,
// U, anywhere we might expect to see a T
template <typename U> ostream & operator<< (ostream & out, const LinkedList<U>& l) {
    Node<U>* curr = l.head; // start from the beginning of the list
    
    // start at the beginning of the list and print to the end
    while (curr != 0) {     // note that while (curr) would also work here
        out << curr->value << " ";
        curr = curr->next;        // make the next node the current node
    }
    
    if (l.head == 0) {
        out << "empty";
    }
    
    out << endl; // print a newline when we're done
    
    return out;
}
#endif