/*
LinkedList.cpp
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.  See LinkedList.h for a
complete definition of the Linked List class.
*/

#ifndef __LL_CPP
#define __LL_CPP

#include "LinkedList.h"

template <class type> LinkedItem<type>::LinkedItem()
{
    Next = NULL;
}

template <class type> LinkedList<type>::LinkedList()
{
    Size = 0;
    Root = NULL;
}

template <class type> LinkedList<type>::LinkedList(const LinkedList<type> &LL)
{
    //to initalize ourselves as the data in LL, we need to parse over all entries in LL,
    //and copy each one into our own local data
    Size = 0;
    Root = NULL;
    LinkedItem<type>    *LLCurrent = LL.Root,   //start at LL's root
                        *MyFinalNode = NULL;    //we have no root node yet
    while(LLCurrent != NULL)
    {
        if(MyFinalNode == NULL)                 //if this is the 1st element,
        {
            MyFinalNode = new LinkedItem<type>;
            Root = MyFinalNode;                 //create a new root node for us
            MyFinalNode->Next = NULL;
            MyFinalNode->Data = LLCurrent->Data;    //the data in the root node equals the data in LL's root node
            Size++;                             //we're one element bigger now
        } else {
            MyFinalNode->Next = new LinkedItem<type>;
            MyFinalNode->Next->Data = LLCurrent->Data;
            MyFinalNode = MyFinalNode->Next;    //add the current data/node in LL to our list
            Size++;
        }
        LLCurrent = LLCurrent->Next;    //go to the next element in LL
    }
}

template <class type> LinkedList<type>::~LinkedList()
{
    FreeMemory();
}

template <class type> LinkedList<type>& LinkedList<type>::operator = (const LinkedList<type> &LL)
{
    //this is equivalent to initalization with LL, except we need to free our own memory first, if we have any
    FreeMemory();
    LinkedItem<type> *LLCurrent = LL.Root, *MyFinalNode = NULL;
    while(LLCurrent != NULL)
    {
        if(MyFinalNode == NULL)
        {
            MyFinalNode = new LinkedItem<type>;
            Root = MyFinalNode;
            MyFinalNode->Next = NULL;
            MyFinalNode->Data = LLCurrent->Data;
            Size++;
        } else {
            MyFinalNode->Next = new LinkedItem<type>;
            MyFinalNode->Next->Data = LLCurrent->Data;
            MyFinalNode = MyFinalNode->Next;
            Size++;
        }

        LLCurrent = LLCurrent->Next;
    }
    return *this;
}

template <class type> void LinkedList<type>::FreeMemory()
{
    if((Root) && (Size > 0))    //if we have any memory to free up
    {
        LinkedItem<type> *Stage=Root,*ToDie;
        for(int i = 0;i < Size;i++)         //iterate through each element
        {
            ToDie = Stage;
            Stage = Stage->Next;            //go to the next element
            delete ToDie;                   //delete the previous element
        }
        if(Stage) delete Stage;
    }
    Size = 0;
    Root = NULL;
}

template <class type> type* LinkedList<type>::Dump()
{
    if(Size > 0)
    {
        LinkedItem<type> *Stage=Root;
        type *Dumped = new type[Size];  //allocate space for the dumped data
        for(int i = 0;i < Size;i++)     //iterate through each element
        {
            Dumped[Size-i-1] = Stage->Data; //load the current element into the array
            Stage = Stage->Next;            //go to the next element
        }
        return Dumped;
    } else return NULL; //no data, so return a NULL pointer
}

template <class type> void LinkedList<type>::Dump(Vector<type> &V)
{
    //this is the exact same as Dump() for a standard array, except we put our data into the vector V instead.
    V.Allocate(Size);
    if(Size > 0)
    {
        LinkedItem<type> *Stage=Root;
        for(int i = 0;i < Size;i++)
        {
            V[Size-i-1] = Stage->Data;
            Stage = Stage->Next;
        }
    }
}

template <class type> LinkedItem<type>* LinkedList<type>::GetPtr(int k)
{
    //slow and inefficent, this function just starts at the root and progesses k times.
    LinkedItem<type>* Stage=Root;
    if(!Stage) return Stage;

    if(k >= Size)
    {   //normally I set a breakpoint here.
        cout << "Out of bounds Linked List access; Index = " << k << ", Size = " << Size << endl;
        exit(1);
    }

    for(int i = 0;i < k;i++)
        Stage = Stage->Next;
    return Stage;
}

template <class type> void LinkedList<type>::Remove(int i)
{
    if(Size > 0)
    {
        if(i == 0) Pop();
        else
        {
            LinkedItem<type> *Prev = GetPtr(i-1);   //store the (i-1)'th and the i'th,
            LinkedItem<type> *ToDie = Prev->Next;
            Prev->Next = ToDie->Next;               //and skip over the i'th
            Size--;
            delete ToDie;   //free the i'th from memory
        }
    }
}

template <class type> type& LinkedList<type>::operator [] (int k)
{
    return GetPtr(k)->Data;
}

template <class type> void LinkedList<type>::Push()
{
    LinkedItem<type> *Temp, *Store;
    Temp = new LinkedItem<type>;
    Store = Root;
    Root = Temp;
    Root->Next = Store;
    Size++;
}

template <class type> void LinkedList<type>::Pop()
{
    if(Size > 0)
    {
        LinkedItem<type> *Store = Root;
        Root = Root->Next;
        delete Store;
        Size--;
        if(Size == 0) Root = NULL;
    }
}

template <class type> void LinkedList<type>::Pop(type &t)
{
    t = (*this)[0];
    Pop();
}

template <class type> void LinkedList<type>::Push(const type &t)
{
    Push();
    Root->Data = t;
}

#endif