#ifndef LINKEDLIST_H_

#include <iostream>
//#include <stdio>

using namespace std;

template <class T>
class LinkedList;

template <class T>
class ListElement
{
    //T datum;
    ListElement* next;

    ListElement (T const&, ListElement*);
public:
    T datum;
    T const& Datum () const;
    ListElement const* Next () const;

    friend class LinkedList<T>;
};

template <class T>
class LinkedList
{
    ListElement<T>* head;
    ListElement<T>* tail;
public:
    LinkedList ();
    ~LinkedList ();
    int size;
    LinkedList (LinkedList const&);
    LinkedList<T>& operator = (LinkedList<T> const&);
    LinkedList<T>& operator += (LinkedList<T> const&);
    bool operator == (LinkedList<T> const&);
    ListElement<T> const* Head () const;
    ListElement<T> const* Tail () const;
    bool IsEmpty () const;
    T const& First () const;
    T const& Last () const;
    bool contains(T const&);
    void Prepend (T const&);
    void Append (T const&);
    void Extract (T const&);
    void Purge ();
    void InsertAfter (ListElement<T> const*, T const&);
    void InsertBefore (ListElement<T> const*, T const&);
};
template <class T>
ListElement<T>::ListElement (
    T const& _datum, ListElement<T>* _next) :
    datum (_datum), next (_next)
    {}


template <class T>
T const& ListElement<T>::Datum () const
    { return datum; }


template <class T>
ListElement<T> const* ListElement<T>::Next () const
    { return next; }


template <class T>
LinkedList<T>::LinkedList () :
    head (0),
    tail (0),
	size (0)
    {}

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

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

template <class T>
ListElement<T> const* LinkedList<T>::Head () const
    { return head; }

template <class T>
ListElement<T> const* LinkedList<T>::Tail () const
    { return tail; }

template <class T>
bool LinkedList<T>::IsEmpty () const
    { return head == 0; }

template <class T>
T const& LinkedList<T>::First () const
{
    if (head == 0)
	   printf("list is empty");
    return head->datum;
}

template <class T>
T const& LinkedList<T>::Last () const
{
    if (tail == 0)
	   printf("list is empty");
    return tail->datum;
}


template <class T>
void LinkedList<T>::Prepend (T const& item)
{
    ListElement<T>* const tmp = new ListElement<T> (item, head);
    if (head == 0)
	tail = tmp;
    head = tmp;
	size = size+1;
}
template <class T>
bool LinkedList<T>::contains(T const& item)
{
    ListElement<T>* tmp = head;
    bool result = false;
    while (tmp != 0){
        if(tmp->datum == item)
            result = true;
        tmp = tmp->next;
    }
    return result; 
}

template <class T>
void LinkedList<T>::Append (T const& item)
{
    ListElement<T>* const tmp = new ListElement<T> (item, 0);
    if (head == 0)
	head = tmp;
    else
	tail->next = tmp;
    tail = tmp;
	size = size+1;
}

template <class T>
LinkedList<T>::LinkedList (LinkedList<T> const& linkedList) :
    head (0),
    tail (0),
	size (0)
{
    ListElement<T> const* ptr;
    for (ptr = linkedList.head; ptr != 0; ptr = ptr->next)
	Append (ptr->datum);
}

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

template <class T>
LinkedList<T>& LinkedList<T>::operator += (LinkedList<T> const& other){
	if(&other != this){
		ListElement<T> const* ptr;
		for (ptr = other.head; ptr != 0; ptr = ptr->next){
			if(!contains(ptr->datum))
		    	Append (ptr->datum);
		}
    }
    return *this;
}

template <class T>
bool LinkedList<T>::operator == (
			LinkedList<T> const& other){
	 bool result = true;
	 int len= size > other.size ? other.size : size;
	 if(&other != this){
	 	int count =0;
	 	ListElement<T> const* ptr;
	 	for (ptr = other.head; ptr != 0 && count < len; ptr = ptr->next){
	    	if(!contains(ptr->datum)){
	    		return false;		
	    	}
    	}
	 }
	 return result;
}

template <class T>
void LinkedList<T>::Extract (T const& item)
{
    ListElement<T>* ptr = head;
    ListElement<T>* prevPtr = 0;
    while (ptr != 0 && ptr->datum != item)
    {
	prevPtr = ptr;
	ptr = ptr->next;
    }
    if (ptr == 0)
	//throw invalid_argument ("item not found");
	cout <<"item not found"<<endl;
    if (ptr == head)
	head = ptr->next;
    else
	prevPtr->next = ptr->next;
    if (ptr == tail)
	tail = prevPtr;
    delete ptr;
	size = size-1;
}

template <class T>
void LinkedList<T>::InsertAfter (
    ListElement<T> const* arg, T const& item)
{
    ListElement<T>* ptr = const_cast<ListElement<T>*> (arg);
    if (ptr == 0)
	//throw invalid_argument ("invalid position");
	   cout<<"invalid position"<<endl;
    ListElement<T>* const tmp =
	new ListElement<T> (item, ptr->next);
    ptr->next = tmp;
    if (tail == ptr)
	tail = tmp;
	size = size+1;
}


template <class T>
void LinkedList<T>::InsertBefore (
    ListElement<T> const* arg, T const& item)
{
    ListElement<T>* ptr = const_cast<ListElement<T>*> (arg);
    if (ptr == 0)
		printf("invalid position");
    ListElement<T>* const tmp = new ListElement<T> (item, ptr);
    if (head == ptr)
	head = tmp;
    else
    {
	ListElement<T>* prevPtr = head;
	while (prevPtr != 0 && prevPtr->next != ptr)
	    prevPtr = prevPtr->next;
	if (prevPtr == 0)
	    printf("invalid position");
	prevPtr->next = tmp;
    }
	size = size+1;
}

/*int main(){
   LinkedList <int> list1;
   for (int i=0; i< 10; i++){
      list1.Append(i);
   }
   //ListElement<int> temp = (ListElement<int>)list1.Head();
   cout<<"Head = "<<(list1.Head()->datum)<<endl;
   cout<<"Size = "<<list1.size<<endl;
}*/


#define LINKEDLIST_H_

#endif /*LINKEDLIST_H_*/
