#ifndef LIST_C
#define LIST_C


//*****************************************************************************
//
//			List.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 "ListIterator.h"
#include "List.h"


//
// Constructors and Destructors
//

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


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


template<class TYPE>
List<TYPE> :: List ( const TYPE& t )
: length ( 1 )
{
    first = last = new ListElement<TYPE> ( t ) ;
}


template<class TYPE>
List<TYPE> :: List ( const List<TYPE>& list )
{
    Copy ( list ) ;
}


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


//
// Private Member Functions
//

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

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

    ListElement<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	List<TYPE> :: Delete ( void )
{
    delete first ;

    first = last = NULL ;

    length = 0 ;
}


//
// Protected Member Functions
//

template<class TYPE>
const TYPE&	List<TYPE> :: Find_Element ( 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

    ListElement<TYPE>*	element = first ;

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


    return ( element->Get_Data ( ) ) ;
}


template<class TYPE>
ListElement<TYPE>*	List<TYPE> :: Find_Previous ( int x ) const
{
    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 ) ;


    // find element prior to index element

    ListElement<TYPE>*	element = first ;

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

    return ( element ) ;
}


template<class TYPE>
void	List<TYPE> :: Remove_Element ( ListElement<TYPE>* prev )
{
    assert ( first != NULL ) ;

    ListElement<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 ) ;

    delete curr ;

    --length ;
}


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

    co << "  Length: " << length << "\n" ;
    co << "  Data:\n" ;
    co << "  {\n" ;

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

    co << "  }" << endl ;
}


template<class TYPE>
void	List<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
    {
	ci >> t ;
	
	Append ( t ) ;
    }

    ci >> c ;
}


//
// Public Member Functions
//

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

    Delete ( ) ;

    Copy ( l ) ;

    return ( *this ) ;
}


template<class TYPE>
List<TYPE>&	List<TYPE> :: operator, ( const TYPE& t )
{
    Append ( t ) ;

    return ( *this ) ;
}


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


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


template<class TYPE>
void	List<TYPE> :: Append ( const TYPE& t )
{
    ListElement<TYPE>*	element = new ListElement<TYPE> ( t ) ;

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

    ++length ;
}


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

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

	last = last->Get_Next ( ) ;
    }
}


template<class TYPE>
void	List<TYPE> :: Insert ( const int x , const TYPE& t )
{
    ListElement<TYPE>*	new_element = new ListElement<TYPE> ( t ) ;


    if ( first == NULL )
    {
	first = last = new_element ;
    }
    else
    {
	ListElement<TYPE>*	previous = Find_Previous ( x ) ;

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

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

	    previous->Set_Next ( new_element ) ;

	    new_element->Set_Next ( next ) ;
	}
    }

    ++length ;
}


template<class TYPE>
void	List<TYPE> :: Insert ( const int x , const List<TYPE>& l )
{
    if ( l.Get_Length ( ) == 0 )
	return ;

    if ( length == 0 )
    {
	operator= ( l ) ;
	return ;
    }


    // find correct place to insert list

    ListElement<TYPE>*	previous = Find_Previous ( x ) ;


    // make copy of list

    List<TYPE>		new_list = l ;


    // insert new_list into this list

    ListElement<TYPE>*	next_element ;

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

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

	previous->Set_Next ( l.first ) ;
    }

    new_list.last->Set_Next ( next_element ) ;

    length += new_list.Get_Length ( ) ;


    // make sure new_list is not deleted

    new_list.first = new_list.last = NULL ;
}


template<class TYPE>
void	List<TYPE> :: Replace ( const int x , const TYPE& t )
{
    ListElement<TYPE>*	element = Find_Previous ( x ) ;

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

    element->Set_Data ( t ) ;
}


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


//
// Friend Functions
//

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

    return ( co ) ;
}


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

    return ( ci ) ;
}


//
// Helper Functions
//

template<class TYPE>
int	Compare_Lists ( const List<TYPE>& l1 , const List<TYPE>& l2 )
{
    ListIterator<TYPE>	j = l2 ;

    for ( ListIterator<TYPE> i = l1 ; ! 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 List<TYPE>& list , const TYPE& data , int& index )
{
    index = 0 ;

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

	++index ;
    }

    index = -1 ;

    return ( 0 ) ;
}


#endif