#include <iostream>
#include <sstream>
#include <iomanip>
using namespace std;

template <class Type>
CList<Type>::CList()
// postcondition: empty list constructed     
   : myCount(0)
{
    myFirst = myLast = 0;
}


template <class Type>
CList<Type> CList<Type>::EMPTY = CList();

template <class Type>
int CList<Type>::ourConsCount = 0;

template <class Type>
int CList<Type>::ConsCalls()
{
    return ourConsCount;
}


template <class Type>
CList<Type>::CList(const Type& t, const CList<Type>& lst)
   : myCount(0)
{
    myFirst = new TNode(t,lst.myFirst);
    ourConsCount++;
    
    
    if (lst.Size() == 0)
    {
        myLast = myFirst;
    }
    else
    {
        myLast = lst.myLast;  
    }
    myCount = lst.Size() + 1;
}


template <class Type>
Type CList<Type>::First() const
{
    if (myFirst)
    {
        return myFirst->info;
    }
    cerr << "error: Front of empty list" << endl;
    return Type();
}

template <class Type>
Type CList<Type>::Head() const
{
   return First();
}

template <class Type>
CListPrinter<Type> CList<Type>::Printer() const
{
   return CListPrinter<Type>(*this);
}

template <class Type>
CListPrinter<Type> CList<Type>::Printer(const string& delimiter) const
{
   return CListPrinter<Type>(*this,delimiter);
}


template <class Type>
CList<Type> CList<Type>::Tail() const
{
    CList<Type> lst;
    if (myFirst == 0 || myFirst->next == 0)
    {
	    // return lst;
	    return EMPTY;
    }
    lst.myFirst = myFirst->next;
    lst.myLast = myLast;
    lst.myCount = Size() - 1;
    return lst;
}

template <class Type>
Type CList<Type>::Last() const
{
    if (myLast)
        return myLast->info;
    cerr << "error: Back of empty list" << endl;
    return Type();
}

template <class Type>
bool CList<Type>::Contains(const Type & t) const
// postcondition: returns true if t contained in list, else false
{
    TNode * temp = myFirst;        // start at front, search
    while (temp)                   // linearly
    {
        if (temp->info == t) return true;
        temp = temp->next;
    }
    return false;
}

template <class Type>
CList<Type> CList<Type>::Find(const Type & t) const
// postcondition: returns list such that list.Head() == t
//                or EMPTY if !Contains(t)
{
    if (IsEmpty())
    {   return EMPTY;
    }
    else if (First() == t)
    {   return *this;
    }
    else
    {   return Tail().Find(t);
    }
}

template <class Type>
int CList<Type>::Size() const
// postcondition: returns # of elements in list
{
    return myCount;
}

template <class Type>
bool CList<Type>::IsEmpty() const
// postcondition: returns true iff list is empty
{
    return Size() == 0;
}

template <class Type>
string CList<Type>::Address() const
{
    ostringstream out;
    out << hex << myFirst;
    return out.str();
}

template <class Type>
CList<Type> CList<Type>::cons(const Type& s,const CList<Type>& slist)
{
    CList<Type> temp(s,slist);
    return temp;
}

template <class Type>
CListIterator<Type>::CListIterator(const CList<Type>& list)
{
    myFirst = list.myFirst;
}

template <class Type>
void CListIterator<Type>::Init() const
{
    myCurrent = myFirst;
}

template <class Type>
bool CListIterator<Type>::HasMore() const
{
    return myCurrent != 0;
}

template <class Type>
void CListIterator<Type>::Next() const
{
    if (HasMore())
	{   myCurrent= myCurrent->next;
	}
}

template <class Type>
Type CListIterator<Type>::Current() const
{
    if (HasMore())
	{   return myCurrent->info;
	}
	cerr <<"error empty list iterator" << endl;
	return Type();
}

template <class Type>
CList<Type> append(const Type& s,const CList<Type>& slist)
{
    if (slist.IsEmpty()) return slist.cons(s,slist);
	return slist.cons(slist.First(),append(s,slist.Tail()));
}

template <class Type>
CList<Type> appendaux(const CList<Type>& slist,const CList<Type>& aux)
{
    if (slist.IsEmpty()) return aux;
	return cons(slist.Head(),appendaux(slist.Tail(), aux));
}

template <class Type>
CList<Type> oldappend(const Type& s,const CList<Type>& slist)
{
    return appendaux(slist,cons(s,CList<Type>()));
}

template <class Type>
ostream& operator << (ostream& output, const CListPrinter<Type>& p)
{
	CListIterator<Type> it(p.myList); 
	it.Init(); 
	if (it.HasMore())
	{   output << it.Current();
	}
	for(it.Next(); it.HasMore(); it.Next())
	{    output << p.myDelimiter << it.Current();
	}
	return output;
}

template <class Type>
CListPrinter<Type>::CListPrinter(const CList<Type>& slist)
  : myList(slist),
    myDelimiter("\n")
{

}

template <class Type>
CListPrinter<Type>::CListPrinter(const CList<Type>& slist, const string& delimiter)
  : myList(slist),
    myDelimiter(delimiter)
{

}

template <class Type>
ostream& operator << (ostream& output, const CList<Type>& list)
{
    output << "(" << list.Printer(",") << ")";
    return output;
}