#include <iostream>
using namespace std;

bool charcmp(char, char);

template <class T>
struct Elt_t
{
        T data;
        Elt_t<T> * Pred;
        Elt_t<T> * Link;

};//NODES

template <class T>
class LinkedList
{
        private:
        Elt_t<T> * Head;
        Elt_t<T> * Tail;
        Elt_t<T> * Curs;
        int total;
        public:
        LinkedList();
        LinkedList(const LinkedList & );
        void pushfront(T);
        void pushback(T);
        int size();
        void begin();
        void next();
        void previous();
        void clear();
        void erase();
        bool empty();
        T popback();
        T popfront();
        void remove(T);
        void insert(T);
        void insertInOrder(T, bool (*charcmp)(char a, char b));
        T operator *();
        void operator ++(int);
        void operator --(int);

};//List

template <class T>
LinkedList<T>::LinkedList()
{
        Head = Tail = NULL;
        Curs = NULL;
        total = 0;
}//List

template <class T>
LinkedList<T>::LinkedList(const LinkedList & ListA)
{
    if(ListA.total == 0) //if list empty
    {
        Head = Tail = NULL;
        total = 0;
    }
    else
    {
        Elt_t<T> * Curr = ListA.Head;
        Head = Tail = NULL;
        total = 0;
        while(Curr != NULL)
        {
            Elt_t<T> *Temp = new Elt_t<T>;
            Temp -> Pred = NULL;
            Temp -> Link = NULL;
            Temp -> data = Curr -> data;
            if(total == 0)
                Head = Tail = Temp;
            else
            {
                Tail -> Link = Temp;
                Temp -> Pred = Tail;
                Tail = Tail -> Link;
            }
            total++;
            Curr = Curr -> Link;
        }
    }
}


template <class T>
void LinkedList<T>::insert(T newvalue)
{total++;
    if(!empty())
    {
        Elt_t<T> * Temp;
        Temp = new Elt_t<T>;
        Temp -> data = newvalue;

        if((Curs -> Link != NULL)&&(Curs -> Pred !=NULL))
        {
        Temp -> Link = Curs -> Link;
        Temp -> Pred = Curs;
        Curs -> Link = Temp;
        Curs = Temp -> Link;
        Curs ->Pred = Temp;

        }//inside list

        else if(Curs -> Pred ==NULL)
        pushfront(newvalue);

        else if(Curs -> Link == NULL)
        pushback(newvalue);
    }//list not empty
    else
        pushback(newvalue);

}//insert



template <class T>
void LinkedList<T>::insertInOrder(T value, bool (*charcmp)(char, char))
{
    if(!empty())
    {
            Elt_t<T> * Temp;
            Temp = new Elt_t<T>;
            Temp -> data = value;
        begin();
        while(Curs != NULL && charcmp(Curs ->data, Temp ->data))
        {
            Curs = Curs -> Link;
        }
        if(Curs == NULL)
        pushback(value);
        else if(Curs -> Pred != NULL)
        {
            Temp -> Link = Curs;
            Temp -> Pred = Curs -> Pred;
            Curs -> Pred = Temp;
            Curs = Temp ->Pred;
            Curs -> Link = Temp;
            total++;
        }//inserts if not at end of list

        else if(Curs ->Pred == NULL)
            pushfront(value);

    }
    else
        pushfront(value);
}









template <class T>
void LinkedList<T>::remove(T value)
{
    if(!empty())
    {
        bool Done = false;
        bool Found = false;
        Curs = Head;
        while((!Done)&&(Curs != NULL))
        {
            if(Curs -> data != value)
            Curs = Curs -> Link;
            else
            {
                Done = true;
                Found = true;
            }
        }//while
        if(Found == true)
        erase();
        else
        cout<<"Item not found."<<endl;
    }//if not empty
    else
    cout<<"List Empty"<<endl;
}//Remove


template <class T>
void LinkedList<T>::operator --(int)
{
    Curs = Curs -> Pred;
}//overloaded -- operator

template <class T>
void LinkedList<T>::operator ++(int)
{
    Curs = Curs -> Link;
}//overloaded ++ operator

template<class T>
T LinkedList<T>::operator *()
{
    T Temp;
    Temp = Curs -> data;
    return Temp;
}//* overload

template <class T>
void LinkedList<T>::previous()
{
    if(!empty())
    if(Curs -> Pred != NULL)
    Curs = Curs -> Pred;
}//Jump Previous

template <class T>
void LinkedList<T>::next()
{
    if(!empty())
    if(Curs ->Link != NULL)
    Curs = Curs -> Link;
}//Jump Next

template <class T>
T LinkedList<T>::popfront()
{
if(!empty())

    {
    T Temp;
    if(Head!=NULL)
        {
        Elt_t<T> * Curr;
        Curr = Head;
        Temp = Curr ->data;
        Head = Head -> Link;
        Head -> Pred =NULL;
        delete Curr;
        }
    else
        {
        Temp = Head -> data;
        delete Head;
        Head = Tail = NULL;
        }
    total = total -1;
    return Temp;
    }
    else
    cout<<"UnderFlow ERROR"<<endl;
    return NULL;
}

template <class T>
T LinkedList<T>::popback()
{   if(!empty())
    {
    T Temp;
    if(Head!=NULL)
        {
        Elt_t<T> * Curr;
        Curr = Tail;
        Temp = Curr ->data;
        Tail = Tail ->Pred;
        Tail -> Link =NULL;
        delete Curr;
        }
    else
        {
        Temp = Head -> data;
        delete Head;
        Head = Tail = NULL;
        }
    total = total -1;
    return Temp;
    }
    else
    cout<<"UnderFlow ERROR"<<endl;
    return NULL;
}


template <class T>
bool LinkedList<T>::empty()
{
return (total == 0);
}

template <class T>
void LinkedList<T>::erase()
{
    if(!empty())
    {
        if((Curs -> Pred != NULL)&&(Curs ->Link != NULL))
        {
        Elt_t<T> * Temp;
        Temp = Curs;
        Curs = Curs ->Pred;
        Curs->Link = Temp ->Link;
        Curs = Curs -> Link;
        Curs -> Pred = Temp ->Pred;
        delete Temp;
        }//Middle

        else if(Curs ->Pred == NULL)
        popfront(); //Head

        else if(Curs ->Link == NULL)
        popback(); //Tail

        total = total -1;
    }//List not empty

}




template <class T>
void LinkedList<T>::clear()
{
    if(!empty())
    {
    Elt_t<T> * Temp;
    Temp = new Elt_t<T>;

    while(Head!=NULL)
        {

        Temp = Head;
        Head = Head -> Link;
        delete Temp;
        }
    total = 0;
    Head = Tail = NULL;
    }

}//Clear


template <class T>
void LinkedList<T>::begin()
{
    Curs = Head;
}//Sets Cursor to begining




template <class T>
int LinkedList<T>::size()
{
    return total;
}//Returns # items in list

template <class T>
void LinkedList<T>::pushback(T newvalue)
{
        Elt_t<T> * Curr;
        Curr = new Elt_t<T>;
        Curr ->data = newvalue;

        if((Tail!=NULL)&&(Head!=NULL))
        {
            Curr -> Pred = Tail;
            Curr -> Link = NULL;
            Tail -> Link = Curr;
            Tail = Curr;
        }//List not Empty
        else
        {
             Curr -> Pred = NULL;
             Curr -> Link = NULL;
             Tail = Curr;
             Head = Curr;
        }//empty list
    total= total +1;

}//Add to End


template <class T>
void LinkedList<T>::pushfront(T newvalue)
{
                Elt_t<T> * Curr;
                Curr = new Elt_t<T>;
                Curr ->data = newvalue;
                if(Head!=NULL)
                {
                Curr -> Link = Head;
                Head -> Pred = Curr;
                Head = Curr;

                }
               else
                {
                        Curr -> Link = NULL;
                        Curr -> Pred = NULL;
                        Head = Curr;
                        Tail = Curr;
                }
                total = total+1;


}