/*
LinkedList.h
Written by Matthew Fisher

The LinkedList class contains linked lists of a template type.  There is also a STL equivalent that I
choose not to use.  Only the LinkedList class should be referenced directly.
*/

#ifndef __LL

#define __LL

//The LinkedItem class is rather trivial.  It is a single element in a linked list and 
//stores the data at the element and a pointer to the next element.  Also initalizes the pointer to NULL.
template <class type> class LinkedItem
{
public:
    LinkedItem();

    type Data;
    LinkedItem *Next;
};

template <class type> class LinkedList
{
public:
    //Initalization
    LinkedList();
    LinkedList(const LinkedList<type> &LL);

    //Destruction
    ~LinkedList();
    void FreeMemory();

    /* Parser */
    //The Parser functions allow fast and easy iteration through all elements of the linked list
    //by moving a pointer along the list.  For example:
    //LinkedList<double> LL;
    //(initalize LL with things)
    //LL.Reset();
    //while(!LL.AtEnd()) {
    //  cout << LL.GetCurrent() << endl;
    //  LL.GoNext();
    //}
    //Displays every element in the linked list.

    __forceinline void Reset()
    {
        Current = Root;     //resets the current pointer to the beginning of the list
    }
    __forceinline void GoNext()
    {
        Current = Current->Next;    //advances to the next element in the list
    }
    __forceinline type& GetCurrent()
    {
        return Current->Data;   //gets the current element by reference
    }
    __forceinline type* GetCurrentPointer()
    {
        return &(Current->Data);    //gets a pointer to the current element
    }
    __forceinline bool AtEnd()
    {
        return (Current == NULL);   //true if we have gotten every element (and are currently sitting on a NULL pointer.)
    }

    //Accessors
    __forceinline int Length()
    {
        return Size;
    }
    type& operator [] (int k);  //returns the k'th element in the linked list.  Note that this is O(n), not O(1)
    LinkedList<type>& operator = (const LinkedList<type> &LL);

    void Push();                //pushes a new element at the beginning of the list
    void Push(const type &t);   //pushes t at the beginning of the list
    void Pop();                 //removes the initial element in the list
    void Pop(type &t);          //pops the initial element and stores it in t
    void Remove(int i);         //removes the i'th element in the list.  Remove(0) is equivalent to Pop.

    type* Dump();               //dumps, as a leaked pointer, all data in the linked list into an array
    void Dump(Vector<type> &V); //dumps this linked list into a Vector

private:
    LinkedItem<type>* GetPtr(int k);    //gets a pointer to the k'th element

    int Size;
    LinkedItem<type> *Root;     //the initial node in the list
    LinkedItem<type> *Current;  //the current node in the parsing of the list
};

#include "LinkedList.cpp"

#endif