#ifndef LIST_HPP
#define LIST_HPP

#include <iostream>
#include <exception>
#include <cstdlib>

#define EXIT 1

namespace LinkedList{


template<class T>
class List;
template<class T>
class ListIterator;

/******************************************************************************************************
 *                                                                                                    *
 *          Exceptions                                                                                *
 *                                                                                                    *
 ******************************************************************************************************/


class excp1:std::exception
{
    public:
    virtual const char* what() const throw()
    {
        return "Must be two lists, or two list nodes !";
    }
};

class excp2:std::exception
{
    public:
    virtual const char* what() const throw()
    {
        return "Index out of list bounds !";
    }
};

class excp3:std::exception
{
    public:
    virtual const char* what() const throw()
    {
        return "Cannot resize the list to a negative size !";
    }
};

class excp4:std::exception
{
    public:
    virtual const char* what() const throw()
    {
        return "This object is not a list !";
    }
};

class excp5:std::exception
{
    public:
    virtual const char* what() const throw()
    {
        return "This is a list, not a single object !";
    }
};

class excp6:std::exception
{
    public:
    virtual const char* what() const throw()
    {
        return "The iterator has not been assigned yet !";
    }
};

class excp7:std::exception
{
    public:
    virtual const char* what() const throw()
    {
        return "The iterator has reached the end !";
    }
};

/********************************************************************************************************
 *                                                                                                      *
 *        List                                                                                          *
 *                                                                                                      *
 ********************************************************************************************************/


template <class T>
class List
{
    public:
    List();
    List (const T& info);
    List (const List<T>& item);
    ~List();
    int size();
    void resize(int length) throw();
    void add(T info,int i) throw();
    void push_back(T info);
    void push_front(T info);
    void remove(int i);
    void swap(int i,int j) throw();
    void swap(List<T>& a, List<T>& b) throw();
    bool in(T info);
    T pop_back();
    T pop_front();
    bool empty();
    T& get(int i) throw();
    T& get() throw();
    void set(T info);
    template <class T1>
    friend std::ostream& operator<< (std::ostream& out, List<T1>& l);
    template<class T1>
    friend std::istream& operator>> (std::istream& in, List<T1>& l);
    template <class T1>
    friend List<T1>& operator+(List<T1>& l1, List<T1>& l2);
    template <class T1>
    friend List<T1>& operator&(List<T1>& l1, List<T1>& l2) throw();
    template<class T1>
    friend List<T1>& operator| (List<T1>& l1, List<T1>& l2) throw();
    List<T>& operator[] (int i) throw();
    List<T>& operator=(List<T>& l) throw();
    List<T>& operator=(const T& info);
    List<T>& operator+= (List<T>& l);
    bool operator== (List<T>& l) throw();
    bool operator!= (List<T>&l);
    bool operator< (List<T>&l) throw();
    bool operator>= (List<T>&l);
    bool operator > (List<T>&l) throw();
    bool operator <= (List<T>& l);
    typedef ListIterator<T> iterator;
    template<class T1>
    friend class ListIterator;
    ListIterator<T>& front() throw();
    ListIterator<T>& back() throw();
    ListIterator<T>& ending() throw();
    protected:
    static ListIterator<T> iter;
    T info;
    bool end;
    int length;
    List<T>* next;
    List<T>* prev;
};

template<class T>
ListIterator<T> List<T>::iter;


template <class T>
List<T>::List()
{
    end=true;
    length=0;
    next=prev=this;
}

template <class T>
List<T>::List(const T& info)
{
    end=false;
    next=prev=this;
    this->info=info;
}

template<class T>
List<T>::List(const List<T>& item)
{
    List<T>* ptr;
    ptr=item.next;
    prev=next=this;
    end=true;
    length=0;
    for(int i=0;i<item.length;i++)
    {
        push_back(ptr->info);
        ptr=ptr->next;
    }
}

template<class T>
List<T>::~List()
{
    List<T>* ptr,*temp;
    ptr=next;
    if(end)
    {
        while(!ptr->end)
        {
            temp=ptr->next;
            delete ptr;
            ptr=temp;
        }
    }
}

template<class T>
int List<T>::size()
{
    return length;
}

template<class T>
void List<T>::resize(int length) throw()
{
    T obj;
    try
    {
        if(length<0)
            throw excp3();
    }
    catch (excp3& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    for(int i=this->length;i<length;i++)
        push_back(obj);
    for(int i=this->length;i>length;i--)
        pop_back();
}


template <class T>
T& List<T>::get(int i) throw()
{
    try
    {
        if(!end)
            throw excp4();
    }
    catch(excp4& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    return (*this)[i].info;
}

template<class T>
T& List<T>::get() throw()
{
    try
    {
        if(end)
            throw excp5();
    }
    catch(excp5& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    return this->info;
}

template<class T>
void List<T>::set(T info)
{
    List<T>* ptr;
    ptr=next;
    if(end)
    {
        while(!ptr->end)
        {
            ptr->set(info);
            ptr=ptr->next;
        }
    }
    else
    {
        this->info=info;
    }
}


template<class T>
void List<T>::add(T info,int i) throw()
{
    List<T>* p1,*p2,*temp;
    temp=new List<T>(info);
    try
    {
        if(i>length)
            throw excp2();
    }
    catch (excp2& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    p2=this->next;
    for(int j=0;j<i;j++)
        p2=p2->next;
    p1=p2->prev;
    p1->next=temp;
    temp->prev=p1;
    p2->prev=temp;
    temp->next=p2;
    length++;
}

template<class T>
void List<T>::push_back(T info)
{
    add(info,length);
}

template<class T>
void List<T>::push_front(T info)
{
    add(info,0);
}

template<class T>
void List<T>::remove(int i)
{
    List<T>* temp,*p1,*p2;
    temp=&(*this)[i];
    p1=temp->prev;
    p2=temp->next;
    delete temp;
    p1->next=p2;
    p2->prev=p1;
    length--;
}

template<class T>
void List<T>::swap(int i,int j) throw()
{
    List<T>* ptr=next,*pi=NULL,*pj=NULL;
    T temp;
    try
    {
        if(i>=length || j>=length)
            throw excp2();
    }
    catch(excp2& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    for(int k=0; k<length && (pi==NULL || pj==NULL) && i!=j; k++)
    {
        if(i==k)
            pi=ptr;
        else if(j==k)
            pj=ptr;
        ptr=ptr->next;
    }
    temp=pi->info;
    pi->info=pj->info;
    pj->info=temp;
}

template<class T>
void List<T>::swap(List<T>& a, List<T>& b) throw()
{
    List<T> *temp;
    T temp_value;
    try
    {
        if(a.end ^ b.end)
            throw excp1();
    }
    catch(excp1& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    if(a.end)
    {
        temp=new List<T> (a);
        a=b;
        b=*temp;
        delete temp;
    }
    else
    {
        temp_value=a.info;
        a.info=b.info;
        b.info=temp_value;
    }
}


template <class T>
bool List<T>::in(T info)
{
    List<T>* ptr;
    bool result=false;
    ptr=next;
    if(end)
    {
        while(!ptr->end && !result)
        {
            result=(ptr->info == info);
            ptr=ptr->next;
        }
    }
    else
    {
        result=(this->info==info);
    }
    return result;
}

template<class T>
T List<T>::pop_back()
{
    T info=(*this)[length-1].info;
    remove(length-1);
    return info;
}

template<class T>
T List<T>::pop_front()
{
    T info=(*this)[0].info;
    remove(0);
    return info;
}

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


template<class T>
std::ostream& operator<< (std::ostream& out, List<T>& l)
{
    List<T>* ptr;
    if(l.end)
    {
        ptr=l.next;
        while(!ptr->end)
        {
            out << ptr->info<<"\t";
            ptr=ptr->next;
        }
    }
    else
    {
        ptr=&l;
        out << ptr->info;
    }
    return out;
}

template<class T>
std::istream& operator>> (std::istream& in, List<T>& l)
{
    List<T>* ptr=l.next;
    if(l.end)
    {
        while(!ptr->end)
        {
            in >> ptr->info;
            ptr=ptr->next;
        }
    }
    else
    {
        in>>l.info;
    }
    return in;
}

template <class T>
List<T>& operator+ (List<T>& l1, List<T>& l2)
{
    List<T>* temp=new List<T>(l1);
    (*temp)+=l2;
    return (*temp);
}

template <class T>
List<T>& operator& (List<T>& l1, List<T>& l2) throw()
{
    List<T>* temp,*ptr=l1.next;
    temp=new List<T>();
    try
    {
        if( (l1.end)^(l2.end) )
            throw excp1();
    }
    catch (excp1& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    if(l1.end)
    {
        while(!ptr->end)
        {
            if(l2.in(ptr->info))
                temp->push_back(ptr->info);
            ptr=ptr->next;
        }
    }
    else
    {
        if(l1.info==l2.info)
            temp->push_back(l1.info);
    }
    return *temp;
}

template<class T>
List<T>& operator| (List<T>& l1, List<T>& l2) throw()
{
    List<T>* temp,*ptr;
    ptr=l2.next;
    try
    {
        if( (l1.end)^(l2.end) )
            throw excp1();
    }
    catch(excp1& e)
    {
        std::cerr << e.what() << std::endl;
        exit(EXIT);
    }
    if(l1.end)
    {
        temp=new List<T> (l1);
        for(int i=0;i<l2.length;i++)
        {
            if(!l1.in(ptr->info))
                temp->add(ptr->info,i);
            ptr=ptr->next;
        }
    }
    else
    {
        temp->push_back(l1.info);
        if(l1.info!=l2.info)
            temp->push_back(l2.info);
    }
    return *temp;
}

template<class T>
List<T>& List<T>::operator[] (int i) throw()
{
    List<T>* ptr;
    try
    {
        if(!end)
            throw excp4();
        else if(i>=length || -i>=length)
            throw excp2();
    }
    catch(excp4& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    catch (excp2& e)
    {
        std::cerr << "Exception: "<< e.what() <<std::endl;
        exit(EXIT);
    }
    ptr=this->next;
    if(i>0)
    {
        for(int j=0;j<i;j++)
            ptr=ptr->next;
    }
    else
    {
        for(int j=0;j<-i;j++)
            ptr=ptr->prev;
    }
    return *ptr;
}



template<class T>
List<T>& List<T>::operator= (List<T>& l) throw()
{
    List<T>* ptr=l.next;
    try
    {
        if( (end)^(l.end) )
            throw excp1();
    }
    catch(excp1& e)
    {
        std::cerr <<"Exception: "<< e.what() <<std::endl;
        exit(EXIT);
    }
    if(this!=&l)
    {
        if(end)
        {
            resize(0);
            while(!ptr->end)
            {
                push_back(ptr->info);
                ptr=ptr->next;
            }
        }
        else
        {
            info=l.info;
        }
    }
    return *this;
}

template <class T>
List<T>& List<T>::operator=(const T& info)
{
    List<T>* ptr;
    ptr=next;
    if(end)
    {
        while(!ptr->end)
        {
            ptr->info=info;
            ptr=ptr->next;
        }
    }
    else
    {
        this->info=info;
    }
    return *this;
}

template <class T>
List<T>& List<T>::operator+= (List<T>& l)
{
    int length=l.length;
    List<T>* ptr=l.next;
    try
    {
        if ( (end)^(l.end) )
            throw excp1();
    }
    catch(excp1 e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    if(end)
    {
        for(int i=0;i<length;i++)
        {
            push_back(ptr->info);
            ptr=ptr->next;
        }
    }
    else
    {
        info+=l.info;
    }
    return *this;
}

template <class T>
bool List<T>::operator== (List<T>& l) throw ()
{
    bool result=true;
    List<T>* p1,*p2;
    p1=next;
    p2=l.next;
    try
    {
        if( (end)^(l.end) )
            throw excp1();
    }
    catch (excp1& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    if(this!=&l)
    {
        if(l.end)
        {
            result=(length==l.length);
            while(!p1->end && result)
            {
                result=(p1->info == p2->info);
                p1=p1->next;
                p2=p2->next;
            }
        }
        else
        {
            result=(p1->info == p2->info);
        }
    }
    return result;
}

template<class T>
bool List<T>::operator!= (List<T>& l)
{
    return (!(*this == l));
}

template<class T>
bool List<T>::operator< (List<T>& l) throw()
{
    List<T>* p1,*p2;
    p1=this->next;
    p2=l.next;
    bool result=true;
    try
    {
        if( (end)^(l.end) )
            throw excp1();
    }
    catch(excp1& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    if(!this->end)
    {
        result=(this->info < l.info);
    }
    else
    {
        while(result && !p1->end && !p2->end)
        {
            result=(p1->info < p2->info);
            p1=p1->next;
            p2=p2->next;
        }
    }
    return result;
}

template <class T>
bool List<T>::operator>=(List<T>& l)
{
    return !((*this)<(l));
}

template<class T>
bool List<T>::operator> (List<T>& l) throw()
{
    List<T>* p1,*p2;
    p1=this->next;
    p2=l.next;
    bool result=true;
    try
    {
        if( (end)^(l.end) )
            throw excp1();
    }
    catch(excp1& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    if(!this->end)
    {
        result=(this->info > l.info);
    }
    else
    {
        while(result && !p1->end && !p2->end)
        {
            result=(p1->info > p2->info);
            p1=p1->next;
            p2=p2->next;
        }
    }
    return result;
}

template<class T>
bool List<T>::operator<=(List<T>& l)
{
    return !( (*this)>l );
}

template<class T>
ListIterator<T>& List<T>:: front() throw()
{
    try
    {
        if(!end)
            throw excp2();
    }
    catch(excp2& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    if(length==0)
        iter.ptr=this;
    else
        iter.ptr= &(*this)[0];
    return iter;
}

template<class T>
ListIterator<T>& List<T>:: back() throw()
{
    try
    {
        if(!end)
            throw excp2();
    }
    catch(excp2& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    if(length==0)
        iter.ptr=this;
    else
        iter.ptr= this->prev;
    return iter;
}

template<class T>
ListIterator<T>& List<T>:: ending() throw()
{
    try
    {
        if(!end)
            throw excp2();
    }
    catch(excp2& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    iter.ptr=this;
    return iter;
}

/***********************************************************************************************************
 *                                                                                                         *
 *         Iterator                                                                                        *
 *                                                                                                         *
 ***********************************************************************************************************/


template<class T>
class ListIterator
{
    public:
    ListIterator();
    ListIterator(const ListIterator<T>& i);
    ListIterator<T>& operator= (const List<T>& l);
    ListIterator<T>& operator= (const ListIterator<T>& i);
    ListIterator<T>& operator++ (int) throw();
    ListIterator<T>& operator-- (int) throw();
    ListIterator<T>& operator++ ();
    ListIterator<T>& operator-- ();
    bool operator== (ListIterator<T>& i);
    bool operator!= (ListIterator<T>& i);
    List<T>& operator* () throw();
    template<class T1>
    friend class List;
    protected:
    List<T>* ptr;
};

template<class T>
ListIterator<T>::ListIterator ()
{
    ptr=NULL;
}

template<class T>
ListIterator<T>::ListIterator (const ListIterator<T>& i)
{
    ptr=i.ptr;
}

template<class T>
ListIterator<T>& ListIterator<T>:: operator= (const List<T>& l)
{
    ptr=&l;
}

template<class T>
ListIterator<T>& ListIterator<T>:: operator= (const ListIterator<T>& i)
{
    ptr=i.ptr;
    return *this;
}


template<class T>
ListIterator<T>& ListIterator<T>:: operator++ (int) throw()
{
    try
    {
        if(ptr==NULL)
            throw excp6();
        else if(ptr->end)
            throw excp7();
    }
    catch(excp6& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    catch(excp7& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    ptr=ptr->next;
    return *this;
}

template<class T>
ListIterator<T>& ListIterator<T>:: operator-- (int) throw()
{
    try
    {
        if(ptr==NULL)
            throw excp6();
        else if(ptr->end)
            throw excp7();
    }
    catch(excp6& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    catch(excp7& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    ptr=ptr->prev;
    return *this;
}

template<class T>
ListIterator<T>& ListIterator<T>:: operator++ ()
{
    return *this++;
}

template<class T>
ListIterator<T>& ListIterator<T>:: operator-- ()
{
    return *this--;
}


template<class T>
List<T>& ListIterator<T>::operator* () throw()
{
    try
    {
        if(ptr==NULL)
            throw excp6();
        else if(ptr->end)
            throw excp7();
    }
    catch(excp6& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    catch(excp7& e)
    {
        std::cerr << "Exception: " << e.what() << std::endl;
        exit(EXIT);
    }
    return *ptr;
}

template<class T>
bool ListIterator<T>:: operator== (ListIterator<T>& i)
{
    return ptr==i.ptr;
}

template<class T>
bool ListIterator<T>:: operator!= (ListIterator<T>& i)
{
    return ptr!=i.ptr;
}

}


#endif