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

using namespace std;

template < class DT >
ListNode<DT>::ListNode ( const DT &initData, ListNode *nextPtr )
{
	dataItem = initData;
	next = nextPtr;
}

template < class DT >
List<DT>::List ( int ignored )
{
	head = NULL;                  
	cursor = NULL;
}

template < class DT >
List<DT>::~List ()
{
	clear();
	delete head;
    delete cursor;
}

template < class DT >  
void List<DT>::insert ( const DT &newData )
{
ListNode<DT>* location;

if ( cursor == NULL )
	{
	location = new ListNode<DT>(newData, cursor);
	head = location;
	}
	else
	{
    location = new ListNode<DT>(newData, cursor->next);
    cursor->next = location;
	}
	cursor = location;
}

template < class DT >
void List<DT>::clear ()                             
{
	head = NULL;                  
	cursor = NULL;
}

template < class DT >
void List<DT>::showStructure () const
{
    ListNode<DT> *p;   // Iterates through the list

    if ( head == 0 )
       cout << "Empty list" << endl;
    else
    {
       for ( p = head ; p != 0 ; p = p->next )
           if ( p == cursor )
              cout << "[" << p->dataItem << "] ";
           else
              cout << p->dataItem << " ";
       cout << endl;
    }
}

template < class DT >
void List<DT>::write () const                       
{
	cout << "List : ";
    writeSub(head);
    cout << endl;
}

template < class DT >
void List<DT>:: writeSub ( ListNode<DT> *p ) const
{
    if ( p != 0 )
    {
       cout << p->element;   
       writeSub(p->next);    
    }
}

template < class DT >
void List<DT>::insertEnd ( const DT &newData )      // Insert at end
{
	insertEndSub(head,newElement);
}

template < class DT >
void List<DT>:: insertEndSub ( ListNode<DT> *&p, const DT &newElement )
{
    if ( p != 0 )
       insertEndSub(p->next,newElement);    // Continue searching for
    else                                    // end of list
    {
       p = new ListNode<DT>(newElement,0);   // Insert new node
       cursor = p;                           // Move cursor
    }
}

template < class DT >
void List<DT>::writeMirror () const                 // Mirror view of list
{
	cout << "Mirror : ";
    writeMirrorSub(head);
    cout << endl;
}

template < class LE >
void List<LE>:: writeMirrorSub ( ListNode<LE> *p ) const
{
    if ( p != 0 )
    {
       cout << p->element;        
       writeMirrorSub(p->next);   
       cout << p->element;        
    }
}

template < class DT >
void List<DT>::reverse ()                           // Reverse list
{
	reverseSub(0,head);
}

template < class DT >
void List<DT>:: reverseSub ( ListNode<DT> *p, ListNode<DT> *nextP )
{
    if ( nextP != 0 )
    {
       reverseSub(nextP,nextP->next);  
       nextP->next = p;                 
    }
    else
       head = p;                        
}

template < class DT >
void List<DT>::deleteEnd ()                         // Delete from end
{
	deleteEndSub(head);
    cursor = head;
}

template < class DT >
void List<DT>:: deleteEndSub ( ListNode<DT> *&p )
{
    if ( p->next != 0 )
       deleteEndSub(p->next);   
    else
    {
       delete p;                
       p = 0;                   
    }
}

template < class DT >
int List<DT>::getLength () const                    // Length of list
{
	return getLengthSub(head);
}

template < class DT >
int List<DT>:: getLengthSub ( ListNode<DT> *p ) const
{
    int result;   // Result returned

    if ( p == 0 )
       result = 0;                            // End of list reached
    else
       result = ( getLengthSub(p->next) + 1 );   // Number of nodes after
                                              // this one + 1
    return result;
}

template < class DT >   
void List<DT>::unknown1 () const                    // Bridge Exercise
{
	unknown1Sub(head);
    cout << endl;
}

template < class DT >
void List<DT>:: unknown1Sub ( ListNode<DT> *p ) const
{
    if ( p != 0 )
    {
       cout << p->element;
       if ( p->next != 0 )
       {
          unknown1Sub(p->next->next);
          cout << p->next->element;
       }
    }
}

template < class DT >
void List<DT>::unknown2 ()                          // Bridge Exercise
{
	unknown2Sub(head);
}

template < class DT >
void List<DT>:: unknown2Sub ( ListNode<DT> *&p )
{
    ListNode<DT> *q;

    if ( p != 0  &&  p->next != 0 )
    {
       q = p;
       p = p->next;
       q->next = p->next;
       p->next = q;
       unknown2Sub(q->next);
    }
}

template < class DT >
void List<DT>::iterReverse ()                      // In-lab Exercise 1
{
	ListNode<DT> *trailP;
	ListNode<DT> *p;
	ListNode<DT> *nextP;
	
	trailP = 0;
	p = head;

	while ( p != 0 )
	{
		nextP = p->next;
		p->next = trailP;
		trailP = p;
		p = nextP;
	}

	head = trailP;
}

template < class DT >
void List<DT>::stackWriteMirror () const            // In-lab Exercise 1
{
}
 
template < class DT >
void List<DT>::cRemove ()                           // In-lab Exercise 2
{
if ( head != 0 )
  {
    cRemoveSub(head);
    cursor = head;
  }

}

template <class DT>
void List<DT>::cRemoveSub( ListNode<DT> *&p)
{
  if ( ! p -> dataItem )
    exit(1);
  if ( p->next != 0 )  
      cRemoveSub(p->next);
  if ( p->dataItem == 'c' )
  { 
        cursor = p;
	p = p->next;
        delete cursor;
  }
} 

template < class DT >
void List<DT>::aBeforeb ()                          // In-lab Exercise 3
{

}