/////////////////////////////////////////////////////////////////
//  LinkedList.C                                               //
//  CMSC 341 - Fall 2001 Project 2                             //
//  Kyu Bae xxx-xx-5868, Section 201                           //
//  kyu_bae@yahoo.com / kbae1@umbc.edu                         //
//  Created : 20 September 2001                                //
//  Current : 20 September 2001                                //
/////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////
//  Default constructor:
//  Construct the list
//  Initialize the Header  to NULL
///////////////////////////////////////////////////////////////
template <class Object>
List<Object>::List( )
{
  header = new ListNode<Object>;
}

//////////////////////////////////////////////////////////////
//  Default constructor:
//  Initialize header to NULL
//////////////////////////////////////////////////////////////
template <class Object>
List<Object>::List( const List<Object> & rhs )
{
  header = new ListNode<Object>;
  *this = rhs;
}

////////////////////////////////////////////////////////
//  Destructor:
//  calls makeEmpty() and delete header node 
///////////////////////////////////////////////////////
template <class Object>
List<Object>::~List( )
{
  makeEmpty( );
  delete header;
}

////////////////////////////////////////////////////////////
//  isEmpty():
//  Test if the list is logically empty.
//  return true if empty, false otherwise.
//  checking if list has any node in the list and if not
//  return true or false
//  Return : boolean for empty  
/////////////////////////////////////////////////////////////
template <class Object>
bool List<Object>::isEmpty( ) const
{
  return header->next == NULL;
}

////////////////////////////////////////////////////////////
//  makeEmpty():
//  Make the list logically empty.
//
////////////////////////////////////////////////////////////
template <class Object>
void List<Object>::makeEmpty( )
{
  while( !isEmpty( ) )
    remove( first( ).retrieve( ) );
}

////////////////////////////////////////////////////////////
//  zeroth():
//  Return an iterator representing the header node.
//
///////////////////////////////////////////////////////////
template <class Object>
ListItr<Object> List<Object>::zeroth( ) const
{
  return ListItr<Object>( header );
}

//////////////////////////////////////////////////////////////
//  first():
//  Return an iterator representing the first node in the list.
//  This operation is valid for empty lists.
//////////////////////////////////////////////////////////////
template <class Object>
ListItr<Object> List<Object>::first( ) const
{
  return ListItr<Object>( header->next );
}

////////////////////////////////////////////////////////
//   Insert item x after p.
//   Param x: Data class object
//   param p: ListItr object current position
 //////////////////////////////////////////////////////
template <class Object>
void List<Object>::insert( const Object & x, const ListItr<Object> & p )
{
    if( p.current->next == NULL ) { // for first element
        p.current->next = new ListNode<Object>( x, NULL, NULL );
        p.current->prev = p.current->next;

        p.current->next->next = p.current->next;
        p.current->next->prev = p.current->next;

        return;
    }

    p.current->prev
        = new ListNode<Object>(x, p.current->next, p.current->next->prev);
    p.current->next->prev->next = p.current->prev;
    p.current->next->prev = p.current->prev;
}

/////////////////////////////////////////////////////////
//  find():
//  Return iterator corresponding to the first node 
//  containing 
//  an item x.
//  Iterator isPastEnd if item is not found.
//  Param x : Data class object 
//  Return : object of ListItr
/////////////////////////////////////////////////////////
template <class Object>
ListItr<Object> List<Object>::find( const Object & x ) const
{
	ListNode<Object> *itr = header->next;

	while(itr!=NULL && itr->element!=x && itr->next!=header->next)
		itr = itr->next;

        if(itr->element != x)
            itr = NULL;
  
	return ListItr<Object>( itr );
}

/////////////////////////////////////////////////////////
//    findPrevious():
//    Return iterator prior to the first node
//    containing an item x.
//    Param x : object of Data class
//    Return : object ListItr current position
////////////////////////////////////////////////////////
template <class Object>
ListItr<Object> List<Object>::findPrevious( const Object & x ) const
{
    ListNode<Object> *itr = header;
  
    while ( itr->next != NULL && itr->next->element !=x
                && itr != header->prev )
	itr = itr->next;

    if(itr->next->element != x) itr = NULL;
  
    return ListItr<Object>( itr );
}

//////////////////////////////////////////////////////////////////
//  remove():
//  Remove the first occurrence of an item x.
//  param x : object of Data class
/////////////////////////////////////////////////////////////////
template <class Object>
void List<Object>::remove( const Object & x )
{
    ListItr<Object> p = find( x );
    ListNode<Object> *oldNode;
  
    if(p.current != NULL)
        oldNode = p.current;
    else
        return;

    if(p.current == p.current->next) {
        delete oldNode;
        header->next = header->prev = NULL;
    }
    else {
        p.current->prev->next = p.current->next;
        p.current->next->prev = p.current->prev;
        if(header->next == p.current)
            header->next = p.current->next;
        if(header->prev == p.current)
            header->prev = p.current->prev;
        delete oldNode;
    }
}

//////////////////////////////////////////////////////////////
//  operator=():
//  Deep copy of linked lists.
//  Param rhs : assign its data members to rhs
//  Return : List object
/////////////////////////////////////////////////////////////
template <class Object>
const List<Object> & List<Object>::operator=( const List<Object> & rhs )
{
    ListItr<Object> ritr = rhs.first( );
    ListItr<Object> itr = zeroth( );

    if( this != &rhs )
    {
        makeEmpty( );
        for( ; !ritr.isPastEnd(); ritr.advance(), itr.advance() ) {
	    insert( ritr.retrieve( ), itr );
            if(ritr.current->next == rhs.header->next)
                break;
        }
    }

    return *this;
}