#ifndef _LIST_H
#define _LIST_H

#include <iostream>
#include <string>
using namespace std;

template <class Type> class CListIterator;
template <class Type> class CListPrinter;

// CList is a constant, or immutable list.  Once a
// list is created, neither the list nor its contents
// can be changed.  This means new lists can safely 
// share storage with existing lists since none will be
// changed during program execution.
//
// Head(), First()
//     return the first element of a list, error if IsEmpty()
// Tail()
//     returns a listi with all but first element
//     list.Tail() is empty if list is empty
// Last()
//     returns last element in list, constant time access
// Size()
//     returns # elements in list, constant time
// IsEmpty()
//     returns true if list is empty, else returns false
// Contains(Type t)
//     returns true iff list contains t
// Find(Type t)
//     returns a (sub)list with Head() == t, or EMPTY if !Contains(t)
// Address()
//     returns a string-ized form of the hex address of the first element
// Printer(), Printer(const string& delimiter)
//     effectively returns a stream manipulator, inserts the list
//     onto a stream with delimiter between elements, the
//     default/no-parameter function inserts newlines between elements
//
//     usage: cout << list.Printer(",") << end;
//
// static ConsCalls() -- returns # times cons called
// static EMPTY  -- effectively a constant for the empty list
//
// CListIterator is the standard tapestry iterator, constructed from
// a list

template <class Type>
class CList
{
  public:
    
    CList();                                // make an empty list
  
    // accessors, determine properties of list, get first/last values

    Type    Head()           const;        // abbreviation for First()
    Type    First()          const;        // return copy of first element
    Type    Last()           const;        // return copy of last element
    CList   Tail()           const;
    
    bool Contains(const Type & t) const;   // true if t in list
    int  Size()                   const;   // # of items in list
    bool IsEmpty()                const;   // true if Size() == 0
    CList<Type> Find(const Type& t) const; // return l with l.Head() == t

    string Address()               const;
    
    CListPrinter<Type> Printer() const;
    CListPrinter<Type> Printer(const string& delimiter) const;
    
	static 

    CList<Type> cons(const Type & s, const CList<Type>& slist);

    static CList<Type> EMPTY;
    
    static int ConsCalls();

    friend class CListIterator<Type>;

  private:
    CList(const Type& t, const CList<Type>& lst);  // make a new list
    
    struct TNode
    {
        // data members
        Type info;              // value stored
        TNode * next;           // link to next TNode
        
        // constructors 
        TNode()
            : next(0)                     
        { }
        TNode(const Type & val, TNode * link=0)
            : info(val),
              next(link)
        { }
    };
    
    TNode * myFirst;          // first node of list
    TNode * myLast;           // last node of list
    int myCount;              // # of items in list
    
    static int ourConsCount;  // # calls of cons
};


template <class Type> inline
CList<Type> cons(const Type& t, const CList<Type>& slist)
{
    return slist.cons(t,slist);
}

template <class Type>
CList<Type> append(const Type& t, const CList<Type>& slist);

template <class Type>
class CListPrinter
{
  public:
    CListPrinter(const CList<Type>& list);
    CListPrinter(const CList<Type>& list, const string& delimiter);
    CList<Type> myList;
    string      myDelimiter;
};

template <class Type>
ostream& operator << (ostream& output, const CListPrinter<Type>& p); 

template <class Type>
ostream& operator << (ostream& output, const CList<Type>& list);

template <class Type>
class CListIterator
{

  public:

    CListIterator(const CList<Type>& list);

	void Init()     const;
	bool HasMore()  const;
	void Next()     const;
	Type Current()  const;

  private:
      typedef CList<Type>::TNode Node;
	  Node * myFirst;
	  mutable  Node * myCurrent;
};

#include "clist.cpp"

typedef CList<string> StringList;
typedef CListIterator<string> StringListIterator;

#endif