#include <cstdlib>
#include <iostream>
using namespace std;
template <class T>
class ListElement;
template <class T>
class LinkedList;
template <class T>

class List
{
 protected:
     int count;
 public:
    List (){count=0;};
    ~List (){};
    //List operator = (List const&);
    bool IsEmpty (){ return count==0;} ;
    virtual T  First ()=0 ;
    virtual T Last ()=0;
    virtual  void Prepend (T &)=0;
    virtual  void Append (T &)=0;
    virtual  void Extract (T&)=0;
    virtual void Purge ()=0;
    virtual void InsertAfter (T&, T &){};
    virtual void InsertBefore (T&, T &){};
};

template <class T>
class ListElement {
    T datum;
    ListElement<T>* next;
    ListElement (T&, ListElement<T>*);
public:
    T Datum ();
    ListElement<T>* Next ();
    friend class LinkedList<T>;
};

template <class T>
class LinkedList:public List<T>{
    ListElement<T>* head;
    ListElement<T>* tail;
public:
    LinkedList ();
    ~LinkedList ();
    LinkedList<T> operator = (LinkedList<T>&);
    ListElement<T> * Head () ;
    ListElement<T> * Tail () ;
    T  First () ;
    T Last () ;
    void Prepend (T &);
    void Append (T &);
    void Extract (T&);
    void Purge ();
    void InsertAfter (ListElement<T> *, T &);
    void InsertBefore (ListElement<T> *, T &);
    void InsertAfterItem (T, T&);
    void InsertBeforeItem (T&, T&);
};

template <class T>
ListElement<T>::ListElement(T& _datum, ListElement<T>* _next)
{
    datum = _datum;
    next = _next;
}

template <class T>
T ListElement<T>::Datum ()
    { return datum; }
template <class T>
ListElement<T>* ListElement<T>::Next ()
    { return next; }
template <class T>
LinkedList<T>::LinkedList()
{
 head = tail = NULL;
}

template <class T>
void LinkedList<T>::Purge()
{
 ListElement<T>* tmp = head;
 if (tail!=NULL) tail->next = NULL;
 while (head!=NULL)
 {  tmp = head;
    head = head->next;
    delete tmp;
 }
  this->count = 0;
 tail = NULL;
}

template <class T>
LinkedList<T>::~LinkedList()
{
 Purge();
}

template <class T>
LinkedList<T> LinkedList<T>::operator = (LinkedList<T>& linkedList)
{
    if (&linkedList != this)
    {
    Purge ();
    ListElement<T>* ptr;
    for (ptr = linkedList.head; ptr != tail; ptr = ptr->next)
        Append (ptr->datum);
    }
    if (tail!=head)
        Append(tail->datum);
    return *this;
}

template <class T>
ListElement<T> * LinkedList<T>::Head ()
    { return head; }
template <class T>
ListElement<T> * LinkedList<T>::Tail ()
    { return tail; }
template <class T>
T LinkedList<T>::First ()
{
    if (head == NULL)
       cout<<"lista Vazia";//throw domain_error ("list is empty");
    return head->datum;
}

template <class T>
T LinkedList<T>::Last ()
{
    if (tail == NULL)
       cout<<"Lista Vazia";//throw domain_error ("list is empty");
    return tail->datum;
}

template <class T>
void LinkedList<T>::Prepend (T& item)
{
    ListElement<T>* tmp = new ListElement<T> (item, head);
    if (head == NULL)
        tail = tmp;
    head = tmp;
    this->count++;
}

template <class T>
void LinkedList<T>::Append (T &item)
{
     ListElement<T>* tmp=new ListElement<T> (item, head);
     if (head==NULL)
         head = tail = tmp;
     tail->next = tmp;
     tail = tmp;
     this->count++;
}

template <class T>
void LinkedList<T>::Extract (T& item)
{
 ListElement<T>* ptr = head;
 ListElement<T>* prevPtr = NULL;
 if (!this->IsEmpty())
 {
    do
    {
        prevPtr = ptr;
        ptr = ptr->next;
    }while (ptr != head && ptr->datum != item);
    if ((ptr == head) && (ptr->datum!=item))
         cout<<"\n item não encountrado";
    else
    {
      if (ptr == head && ptr==tail)
          head=tail=NULL;
      else if (ptr == head)
               head = tail->next = ptr->next;
           else
               prevPtr->next = ptr->next;
      if (ptr == tail)
      {
          tail = prevPtr;
          tail->next = head;
      }
      delete ptr;
      this->count--;
    }
  }
  else cout<<"\n Lista vazia\n";
}

template <class T>
void LinkedList<T>::InsertAfter (ListElement<T> *ptr, T & item)
{
    if (ptr!=NULL){
         ListElement<T>* tmp =new ListElement<T> (item, ptr->next);
         ptr->next = tmp;
         if (tail == ptr)
             tail = tmp;
    }
    else if (head == NULL)
    { head=tail=new ListElement<T> (item, NULL);
      tail->next=head;
    }
}

template <class T>
void LinkedList<T>::InsertBefore (ListElement<T> *ptr, T& item)
{
    if (ptr != NULL)
    {
        ListElement<T>* tmp = new ListElement<T> (item, ptr);
        if (head == ptr)
            head = tmp;
        else
        {
            ListElement<T>* prevPtr = head;
            while (prevPtr->next != head && prevPtr->next != ptr)
                   prevPtr = prevPtr->next;
            if (prevPtr->next == head)
            {       cout<<"\n Posição inválida";//throw invalid_argument
("invalid position");
                    delete tmp;
            }
            else prevPtr->next = tmp;
        }
    }
    else if (head == NULL)
    { head=tail=new ListElement<T> (item, NULL);
      tail->next=head;
    }
}

template <class T>
void LinkedList<T>::InsertAfterItem (T item, T& _dado){ //item -> item a ser procurado, dado -> dado que quer colocar depois do item

   ListElement<T>* ptr = head;
   if (!this->IsEmpty())
   {
      do
      {
          ptr = ptr->next;
      }while (ptr != head && ptr->datum != item);
      if ((ptr == head) && (ptr->datum!=item))
           cout<<"\n item não encountrado";
      else
        InsertAfter(ptr,_dado);
    }
    else cout<<"\n Lista vazia\n";
};

template <class T>
void LinkedList<T>::InsertBeforeItem (T& item, T &dado){}


int main(int argc, char *argv[])
{
    LinkedList<int> lista;
    int a=3;
    lista.Append(a);
    lista.Append(++a);
    lista.Append(++a);
    lista.Append(++a);
    int b=4;
    lista.Extract(b);
    lista.Append(++a);
    lista.Append(++a);
    cout<<"\n"<<lista.First();
    cout<<"\n"<<lista.Last();
    lista.InsertAfterItem(8,++a);
    cout<<"\n"<<lista.Last();
    system("PAUSE");
    return EXIT_SUCCESS;

}