#ifndef PLIST_H
#define PLIST_H


//*****************************************************************************
//
//			PList.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.
//
//*****************************************************************************


//*****************************************************************************
//
// This class is a list of pointers which will automatically create a next
// pointer for any type by using the PListElement class. Users of this class
// should never need to directly access the PListElement class; instead, the
// functions provided here, or the PListIterator, should be used. Any function
// that inserts data will not copy the data pointers - it will just use that
// pointer as the data. So, if one element is copied from the other, both
// elements will point to the same data.
//
//*****************************************************************************

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

template<class T> class PListIterator ;


template<class TYPE> 
class PList
{

private:

    PListElement<TYPE>*		first ;
    PListElement<TYPE>*		last ;

    int				length ;


private:

    enum			{ REMOVE_ALL = -1 , EXTRACT_ALL = -1 } ;

    void			Copy   ( const PList<TYPE>& ) ;
    void			Reset  ( void ) ;
    void			Delete ( void ) ;


protected:

    PListElement<TYPE>*		Find_Previous ( int   ) ;
    PListElement<TYPE>*		Find_Previous ( TYPE* ) ;

    const TYPE*			Find_Element  ( const int ) const ;

    void			Insert_Element ( PListElement<TYPE>* , TYPE* ) ;
    void			Insert_List    ( PListElement<TYPE>* ,
							  const PList<TYPE>& ) ;

    void			Remove_Element ( PListElement<TYPE>* , const int ) ;

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


public:

				// special indices for index operators

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



				// default constructor

				PList ( void ) ;


				// user-defined constructors

				PList ( int   ) ;
				PList ( TYPE* ) ;


				// copy constructor

				PList ( const PList<TYPE>& ) ;


				// destructor

				~PList ( void )  ;


				// assignment operator

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


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

    PList<TYPE>&		operator, ( 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  ( TYPE* ) ;
    void			Append  ( const PList<TYPE>& ) ;


				//
				// all operations below operate on either the ith
				//  element in the list, or the element with data t
				//

				// insert data into list

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

    void			Insert  ( TYPE* t , TYPE* ) ;
    void			Insert  ( TYPE* t , const PList<TYPE>& ) ;


				// replace data

    void			Replace ( const int i , TYPE* ) ;
    void			Replace ( TYPE*     t , TYPE* ) ;


				// remove element i from list and delete the data

    void			Remove  ( const int i = REMOVE_ALL ) ;
    void			Remove  ( TYPE*     t ) ;


				// remove element i from list (do not delete data)

    void			Extract ( const int i = EXTRACT_ALL ) ;
    void			Extract ( TYPE*     t ) ;


				// I/O operators

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


    friend class PListIterator<TYPE> ;

} ;


//
// the two functions use the operator== function of the class TYPE
// to test compare two lists or search for some data
//

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

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


//
// search for the data in a list - if in list, get index
//

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

#include "PList.C"

#endif