#ifndef PLIST_C
#define PLIST_C


//*****************************************************************************
//
//			PList.C
//
//*****************************************************************************
//
//      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 <assert.h>
#include "PListIterator.h"
#include "PList.h"


//
// Constructors and Destructors
//

template<class TYPE>
PList<TYPE> :: PList ( void )
: first ( NULL ) , last ( NULL ) , length ( 0 )
{ }


template<class TYPE>
PList<TYPE> :: PList ( int s )
: first ( NULL ) , last ( NULL ) , length ( 0 )
{ }


template<class TYPE>
PList<TYPE> :: PList ( TYPE* t )
: first ( NULL ) , last ( NULL ) , length ( 0 )
{
    assert ( t != NULL ) ;

    first = last = new PListElement<TYPE> ( t ) ;

    length = 1 ;
}


template<class TYPE>
PList<TYPE> :: PList ( const PList<TYPE>& l )
{
    Copy ( l ) ;
}


template<class TYPE>
PList<TYPE> :: ~PList ( void )
{
    Delete ( ) ;
}


//
// Private Member Functions
//

template<class TYPE>
void	PList<TYPE> :: Copy ( const PList<TYPE>& l )
{
    length = l.length ;

    if ( l.Get_Length ( ) == 0 )
    {
	first = last = NULL ;
	return ;
    }

    PListElement<TYPE>*	element = l.first ;

    first = last = element->Get_Copy ( ) ;

    while ( element != l.last )
    {
	element = element->Get_Next ( ) ;

	last->Set_Next ( element->Get_Copy ( ) ) ;

	last = last->Get_Next ( ) ;
    }
}


template<class TYPE>
void	PList<TYPE> :: Reset ( void )
{
    PListElement<TYPE>*	element = first ;

    while ( element != NULL )
    {
	element->Set_Data ( NULL ) ;

	element = element->Get_Next ( ) ;
    }

    Delete ( ) ;
}


template<class TYPE>
void	PList<TYPE> :: Delete ( void )
{
    delete first ;

    first = last = NULL ;
    length = 0 ;
}


//
// Protected Member Functions
//

template<class TYPE>
PListElement<TYPE>*	PList<TYPE> :: Find_Previous ( int x )
{
    assert ( first != NULL ) ;


    // test for special cases

    if ( ( x < 0 ) || ( x >= length ) )
    {
	if ( x == FIRST )
	    x = 0 ;
	else if ( x == LAST )
	    x = length - 1 ;
	else
	    assert ( ( x >= 0 ) && ( x < length ) ) ;
    }


    // if looking for first element, return NULL

    if ( x == 0 )
	return ( NULL ) ;


    // look for i-1 element

    PListElement<TYPE>*	element = first ;

    for ( int i = 0 ; i < x - 1 ; ++i )
	element = element->Get_Next ( ) ;

    return ( element ) ;
}


template<class TYPE>
PListElement<TYPE>*	PList<TYPE> :: Find_Previous ( TYPE* t )
{
    assert ( first != NULL ) ;
    assert ( t     != NULL ) ;

    PListElement<TYPE>*	previous = NULL ;
    PListElement<TYPE>*	element  = first ;

    while ( element != NULL )
    {
	if ( element->Compare_Data ( t ) )
	    return ( previous ) ;

	previous = element ;

	element = element->Get_Next ( ) ;
    }

    assert ( 0 ) ;

    return ( NULL ) ;
}


template<class TYPE>
const TYPE*	PList<TYPE> :: Find_Element ( const int x ) const
{
    assert ( first != NULL ) ;


    // test for special cases

    if ( ( x < 0 ) || ( x >= length ) )
    {
	if ( x == FIRST )
	    return ( first->Get_Data ( ) ) ;
	else if ( x == LAST )
	    return ( last->Get_Data ( ) ) ;
	else
	    assert ( ( x >= 0 ) && ( x < length ) ) ;
    }


    // look for ith element

    PListElement<TYPE>*	element = first ;

    for ( int i = 0 ; i < x ; i++ )
	element = element->Get_Next ( ) ;


    return ( element->Get_Data ( ) ) ;
}


template<class TYPE>
void	PList<TYPE> :: Insert_Element ( PListElement<TYPE>* previous ,
						     TYPE*  new_data )
{
    assert ( new_data != NULL ) ;


    PListElement<TYPE>*	new_element = new PListElement<TYPE> ( new_data ) ;

    if ( previous == NULL )
    {
	new_element->Set_Next ( first ) ;

	first = new_element ;
    }
    else
    {
	PListElement<TYPE>*	next = previous->Get_Next ( ) ;

	previous->Set_Next ( new_element ) ;

	new_element->Set_Next ( next ) ;
    }

    ++length ;
}


template<class TYPE>
void	PList<TYPE> :: Insert_List ( PListElement<TYPE>* previous ,	
				     const PList<TYPE>&  new_list )
{
    if ( new_list.Get_Length ( ) == 0 )
	return ;


    // make copy of list

    PList<TYPE>		l = new_list ;


    // insert new_list into this list

    PListElement<TYPE>*	next_element ;

    if ( previous == NULL )
    {
	next_element = first ;

	first = l.first ;
    }
    else
    {
	next_element = previous->Get_Next ( ) ;

	previous->Set_Next ( l.first ) ;
    }

    l.last->Set_Next ( next_element ) ;

    length += l.Get_Length ( ) ;


    // make sure new_list is not deleted

    l.first = l.last = NULL ;
}


template<class TYPE>
void	PList<TYPE> :: Remove_Element ( PListElement<TYPE>* prev , const int d )
{
    assert ( first != NULL ) ;

    PListElement<TYPE>*	curr ;

    if ( prev == NULL )
	curr = first ;
    else
	curr = prev->Get_Next ( ) ;


    // make adjustments in list

    if ( curr == first )
    {
	first = first->Get_Next ( ) ;

	if ( curr == last )
	    last = NULL ;
    }
    else if ( curr == last )
    {
	prev->Set_Next ( NULL ) ;

	last = prev ;

	if ( curr == first )
	    curr = NULL ;
    }
    else
	prev->Set_Next ( curr->Get_Next ( ) ) ;


    // delete curr from list

    curr->Set_Next ( NULL ) ;

    if ( d )
	delete curr ;

    --length ;
}


template<class TYPE>
void	PList<TYPE> :: Output ( ostream& co ) const
{
    co << "List\n" ;

    co << "  Length: " << Get_Length ( ) << "\n" ;
    co << "  Data:\n" ;
    co << "  {\n" ;

    for ( PListIterator<TYPE> j = *this ; ! j.Is_Done ( ) ; ++j )
	co << "    " << *j.Get_Current ( ) << "\n" ;

    co << "  }" << endl ;
}


template<class TYPE>
void	PList<TYPE> :: Input ( istream& ci )
{
    TYPE*	t ;
    STring	s ;
    char	c ;
    int		l ;

    Delete ( ) ;

    ci >> s ;
    ci >> s >> l ;			// read length of list
    ci >> s >> c ;			// read data string and first bracket

    for ( int i = 0 ; i < l ; i++ )	// read in elements
    {
	t = new TYPE ;

	ci >> *t ;
	
	Append ( t ) ;
    }

    ci >> c ;
}


//
// Public Member Functions
//

template<class TYPE>
PList<TYPE>&	PList<TYPE> :: operator= ( const PList<TYPE>& l )
{
    if ( this == &l )
	return ( *this ) ;

    Delete ( ) ;

    Copy ( l ) ;

    return ( *this ) ;
}


template<class TYPE>
PList<TYPE>&	PList<TYPE> :: operator, ( TYPE* elmt )
{
    Append ( elmt ) ;

    return ( *this ) ;
}


template<class TYPE>
const TYPE*	PList<TYPE> :: operator[] ( const int x ) const
{
    return ( Find_Element ( x ) ) ;
}


template<class TYPE>
TYPE*	PList<TYPE> :: operator[] ( const int x )
{
    return ( (TYPE*) Find_Element ( x ) ) ;
}


template<class TYPE>
void	PList<TYPE> :: Append ( TYPE* t )
{
    assert ( t != NULL ) ;

    PListElement<TYPE>*	element = new PListElement<TYPE> ( t ) ;

    if ( first == NULL )
	first = last = element ;
    else
    {
	last->Set_Next ( element ) ;
	last = element ;
    }

    ++length ;
}


template<class TYPE>
void	PList<TYPE> :: Append ( const PList<TYPE>& l )
{
    if ( first == NULL )
    {
	operator= ( l ) ;
	return ;
    }


    for ( PListIterator<TYPE> i = l ; ! i.Is_Done ( ) ; ++i , ++length )
    {
	last->Set_Next ( new PListElement<TYPE> ( i.Get_Current ( ) ) ) ;

	last = last->Get_Next ( ) ;
    }
}


template<class TYPE>
void	PList<TYPE> :: Insert ( const int x , TYPE* new_data )
{
    if ( length == 0 )
	Append ( new_data ) ;
    else
	Insert_Element ( Find_Previous ( x ) , new_data ) ;
}


template<class TYPE>
void	PList<TYPE> :: Insert ( const int x , const PList<TYPE>& new_list )
{
    if ( length == 0 )
	Append ( new_list ) ;
    else
	Insert_List ( Find_Previous ( x ) , new_list ) ;
}


template<class TYPE>
void	PList<TYPE> :: Insert ( TYPE* t , TYPE* new_data )
{
    if ( length == 0 )
	Append ( new_data ) ;
    else
	Insert_Element ( Find_Previous ( t ) , new_data ) ;
}


template<class TYPE>
void	PList<TYPE> :: Insert ( TYPE* t , const PList<TYPE>& new_list )
{
    if ( length == 0 )
	Append ( new_list ) ;
    else
	Insert_List ( Find_Previous ( t ) , new_list ) ;
}


template<class TYPE>
void	PList<TYPE> :: Replace ( const int x , TYPE* new_data )
{
    assert ( new_data != NULL ) ;

    PListElement<TYPE>*	element = Find_Previous ( x ) ;

    if ( element == NULL )
	element = first ;
    else
	element = element->Get_Next ( ) ;

    element->Set_Data ( new_data ) ;
}


template<class TYPE>
void	PList<TYPE> :: Replace ( TYPE* t , TYPE* new_data )
{
    assert ( new_data != NULL ) ;

    PListElement<TYPE>*	element = Find_Previous ( t ) ;

    if ( element == NULL )
	element = first ;
    else
	element = element->Get_Next ( ) ;

    element->Set_Data ( new_data ) ;
}


template<class TYPE>
void	PList<TYPE> :: Extract ( const int x )
{
    if ( x == EXTRACT_ALL )
	Reset ( ) ;
    else
	Remove_Element ( Find_Previous ( x ) , 0 ) ;
}


template<class TYPE>
void	PList<TYPE> :: Extract ( TYPE* t )
{
    Remove_Element ( Find_Previous ( t ) , 0 ) ;
}


template<class TYPE>
void	PList<TYPE> :: Remove ( const int x )
{
    if ( x == REMOVE_ALL )
	Delete ( ) ;
    else
	Remove_Element ( Find_Previous ( x ) , 1 ) ;
}


template<class TYPE>
void	PList<TYPE> :: Remove ( TYPE* t )
{
    Remove_Element ( Find_Previous ( t ) , 1 ) ;
}


//
// Friend Functions
//

template<class TYPE>
ostream&	operator<< ( ostream& co , const PList<TYPE>& l )
{
    l.Output ( co ) ;

    return ( co ) ;
}


template<class TYPE>
istream&	operator>> ( istream& ci , PList<TYPE>& l )
{
    l.Input ( ci ) ;

    return ( ci ) ;
}


//
// Helper Functions
//

template<class TYPE>
int	Compare_Lists ( const PList<TYPE>& l1 , const PList<TYPE>& l2 )
{
    for ( PListIterator<TYPE> i = l1 , j = l2 ; ! i.Is_Done ( ) ; ++i , ++j )
    {
	if ( j.Is_Done ( ) )
	    return ( 0 ) ;

	if ( ! ( *i.Get_Current ( ) == *j.Get_Current ( ) ) )
	    return ( 0 ) ;
    }

    if ( j.Is_Done ( ) )
	return ( 1 ) ;

    return ( 0 ) ;
}


template<class TYPE>
int	Search_List ( const PList<TYPE>& l , const TYPE& data , int& index )
{
    index = 0 ;

    for ( PListIterator<TYPE> i = l ; ! i.Is_Done ( ) ; ++i )
    {
	if ( *i.Get_Current ( ) == data )
	    return ( 1 ) ;

	++index ;
    }

    return ( 0 ) ;
}


template<class TYPE>
int	Search_List ( const PList<TYPE>& l , const TYPE* data , int& index )
{
    index = 0 ;

    for ( PListIterator<TYPE> i = l ; ! i.Is_Done ( ) ; ++i )
    {
	if ( i.Get_Current ( ) == data )
	    return ( 1 ) ;

	++index ;
    }

    return ( 0 ) ;
}

#endif