// File name:  List.cpp

#include <iostream.h>
#include <stdlib.h>

template <class Object>
class ListItr;               // Incomplete declaration.

// Implementation from Weiss text, Chapter 3, pages 75-78.

// Constructor
template <class Object>
List<Object>::List()
{
   header = new ListNode<Object>;
}

template <class Object>
bool List<Object> :: isEmpty( ) const    
{
   return ( NULL == header->next );
}

template <class Object>
ListItr<Object> List<Object>::zeroth( ) const
{
   return ListItr<Object> ( header );
}

template <class Object>
ListItr<Object> List<Object>::first( ) const
{
   return ( ListItr<Object> ( header-> next ));
}

template <class Object>
void printList ( const List<Object> & theList )
{
   if ( theList.isEmpty( ) )
      cout << "Empty list" << endl;
   else
   {
      ListItr<Object> itr = theList.first( );
      for ( ; !itr.isPastEnd( ) ; itr.advance( ) )
      {
         cout << itr.retrieve( ) << " ";;
      }
   }
   cout << endl;
}

template<class Object>
ListItr<Object> List<Object>::find ( const Object & x ) const
{
   ListNode<Object> * itr = header->next;

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

   return ListItr<Object> ( itr );
}

template<class Object>
void List<Object>::remove ( const Object & x )
{
   ListItr<Object> p = findPrevious( x );

   if ( p.current->next != NULL )
   {
      ListNode<Object> * oldNode = p.current->next;
      p.current->next = p.current->next->next;  // Bypass deleted node
      delete oldNode;
   }
}

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 = itr->next;

   return ListItr<Object> ( itr );
}  

template<class Object>
void List<Object>::insert( const Object & x, const ListItr<Object> & p )
{
   if ( p.current != NULL )
      p.current->next = new ListNode<Object> (x, p.current->next );
}

template<class Object>
void List<Object>::makeEmpty( )
{
   while ( !isEmpty ( ) )
      remove ( first( ).retrieve( ));
}

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

template<class Object>
const List<Object> & List<Object>:: operator= ( const List<Object> & rhs )
{
   if (this != &rhs)
   {
      makeEmpty ( );  
      if ( rhs.isEmpty( ))
         return *this;

      ListItr<Object> rhsItr = rhs.first();
      ListItr<Object> thisItr = zeroth();
      
      while ( ! rhsItr.isPastEnd( ) )
      {
         insert( rhsItr.retrieve( ), thisItr );
         rhsItr.advance( );
         thisItr.advance( );
      }
   }
   return *this; 
}

// copy constructor, never invoked outside class
template <class Object>
List<Object>::List ( const List<Object> & rhs )
{
   *this = rhs;
}

// += operator appends list           
template <class Object>
void List<Object>::operator+= (const List<Object> &rhs)
{
  ListNode<Object> *listPointer = NULL;
  ListNode<Object> *tempList = NULL;
  ListNode<Object> *newNode = NULL;

  // Copy the first item in the list, if any
  if ((listPointer = (rhs.header)->next)) 
  {
    newNode = new ListNode<Object> (listPointer->element, NULL);
    tempList = newNode;
    listPointer=listPointer->next;
  }
  else
  {
    return;
  }

  // Copy the rest of the list
  for (; 
       listPointer; 
       listPointer=listPointer->next)
  {
      newNode->next = new ListNode<Object> (listPointer->element, NULL);
      newNode = newNode->next;
  }

  // Get to the end of the lhs list
  for (listPointer = header;
       listPointer->next;
       listPointer = listPointer->next);

  // Append the list copy
  listPointer->next = tempList;
}