#ifndef LIST_H
#define LIST_H


//*****************************************************************************
//
//			List.h
//
//*****************************************************************************
//
//      Copyright (C) 1996 
//
//                      Ronald A. MacCracken
//			Graduate Student
//                      Computer Science Department
//                      University of California
//                      Davis, CA  95616
//
//      Permission is granted to use at your own risk and 
//      distribute this software in source and binary forms 
//      provided the above copyright notice and this paragraph 
//      are preserved on all copies.  This software is provided 
//      "as is" with no express or implied warranty.
//
//*****************************************************************************

#include <iostream.h>
#include "ListElement.h"

template<class T> class ListIterator ;


template<class TYPE> 
class List
{

private:

    ListElement<TYPE>*		first ;
    ListElement<TYPE>*		last ;

    int				length ;


private:

    enum			{ REMOVE_ALL = -1 } ;

    void			Copy   ( const List<TYPE>& ) ;
    void			Delete ( void ) ;


protected:

    const TYPE&			Find_Element  ( int ) const ;
    ListElement<TYPE>*		Find_Previous ( int ) const ;

    void			Remove_Element ( ListElement<TYPE>* ) ;

    void			Output ( ostream& ) const ;
    void			Input  ( istream& ) ;


public:

				// special indices for index operators

    enum			{ FIRST = -2 , LAST = -3 } ;


				// default constructor

				List ( void ) ;


				// user-defined constructors

				List ( int ) ;
				List ( const TYPE& ) ;


				// copy constructor

				List ( const List<TYPE>& ) ;


				// destructor

				~List ( void )  ;


				// assignment operator

    List<TYPE>&			operator= ( const List<TYPE>& ) ;


				// add elements to a list - use as follows:
				//	list = t1 , t2 , t3 , t4 ;

    List<TYPE>&			operator, ( const TYPE& ) ;


				// access data from element i

    const TYPE&			operator[] ( const int i ) const ;
    TYPE&			operator[] ( const int i ) ;


				// access functions

    int				Get_Length ( void ) const { return length ; }


				// append data to end of list

    void			Append  ( const TYPE& ) ;
    void			Append  ( const List<TYPE>& ) ;


				// insert data into list at ith location

    void			Insert  ( const int i , const TYPE& ) ;
    void			Insert  ( const int i , const List<TYPE>& ) ;


				// replace data at location i

    void			Replace ( const int i , const TYPE& ) ;


				// remove element i from list

    void			Remove  ( const int i = REMOVE_ALL ) ;


				// I/O operators

    friend ostream&		operator<< ( ostream& , const List<TYPE>& ) ;
    friend istream&		operator>> ( istream& , List<TYPE>& ) ;


    friend class ListIterator<TYPE> ;

} ;

//
// both functions below require TYPE::operator==
//

// search for an element in the list

template<class TYPE> int Search_List ( const List<TYPE>& , const TYPE& , int& ) ;

// compare the contents of two lists

template<class TYPE> int Compare_Lists ( const List<TYPE>& , const List<TYPE>& ) ;


#include "List.C"

#endif