//--------------------------------------------------------------------
//
//  Laboratory 10                                         listrec.cs
//
//  (Shell) Partial linked list implementation of the List ADT with
//  additional recursive linked list functions
//
//--------------------------------------------------------------------

#include <assert.h>
#include "stacklnk.cpp"
#include "listrec.h"

//--------------------------------------------------------------------
//
// Insert your singly linked list implementations (from Laboratory 7)
// of the following functions:
//
//   - The ListNode class constructor
//
//   - The List class constructor, destructor, insert(), clear(), and
//     showstructure() functions.
//
//--------------------------------------------------------------------



//--------------------------------------------------------------------
//
// Recursively implemented linked list functions used in the Prelab
// Exercise
//
//--------------------------------------------------------------------

template < class LE >
void List<LE>:: write () const

// Outputs the elements in a list from beginning to end. Assumes that
// objects of type LE can be output to the cout stream.

{
    cout << "List : ";
    writeSub(head);
    cout << endl;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class LE >
void List<LE>:: writeSub ( ListNode<LE> *p ) const

// Recursive partner of the write() function. Processes the sublist
// that begins with the node pointed to by p.

{
    if ( p != 0 )
    {
       cout << p->element;   // Output element
       writeSub(p->next);    // Continue with next node
    }
}

//--------------------------------------------------------------------

template < class LE >
void List<LE>:: insertEnd ( const LE &newElement )

// Inserts newElement at the end of a list. Moves the cursor to
// newElement.

{
    insertEndSub(head,newElement);
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class LE >
void List<LE>:: insertEndSub ( ListNode<LE> *&p,
                               const LE &newElement )

// Recursive partner of the insertEnd() function. Processes the
// sublist that begins with the node pointed to by p.

{
    if ( p != 0 )
       insertEndSub(p->next,newElement);    // Continue searching for
    else                                    // end of list
    {
       p = new ListNode<LE>(newElement,0);   // Insert new node
       cursor = p;                           // Move cursor
    }
}

//--------------------------------------------------------------------

template < class LE >
void List<LE>:: writeMirror () const

// Outputs the elements in a list from beginning to end and back
// again. Assumes that objects of type LE can be output to the cout
// stream.

{
    cout << "Mirror : ";
    writeMirrorSub(head);
    cout << endl;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class LE >
void List<LE>:: writeMirrorSub ( ListNode<LE> *p ) const

// Recursive partner of the writeMirror() function. Processes the
// sublist that begins with the node pointed to by p.

{
    if ( p != 0 )
    {
       cout << p->element;        // Output element (forward)
       writeMirrorSub(p->next);   // Continue with next node
       cout << p->element;        // Output element (backward)
    }
}

//--------------------------------------------------------------------

template < class LE >
void List<LE>:: reverse ()

// Reverses the order of the elements in a list.

{
    reverseSub(0,head);
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class LE >
void List<LE>:: reverseSub ( ListNode<LE> *p, ListNode<LE> *nextP )

// Recursive partner of the reverse() function. Processes the sublist
// that begins with the node pointed to by nextP.

{
    if ( nextP != 0 )
    {
       reverseSub(nextP,nextP->next);   // Continue with next node
       nextP->next = p;                 // Reverse link
    }
    else
       head = p;                        // Move head to end of list
}

//--------------------------------------------------------------------

template < class LE >
void List<LE>:: deleteEnd ()

// Deletes the element at the end of a list. Moves the cursor to the
// beginning of the list.

{
    deleteEndSub(head);
    cursor = head;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class LE >
void List<LE>:: deleteEndSub ( ListNode<LE> *&p )

// Recursive partner of the deleteEnd() function. Processes the
// sublist that begins with the node pointed to by p.

{
    if ( p->next != 0 )
       deleteEndSub(p->next);   // Continue looking for the last node
    else
    {
       delete p;                // Delete node
       p = 0;                   // Set p (link or head) to null
    }
}

//--------------------------------------------------------------------

template < class LE >
int List<LE>:: length () const

// Returns the number of elements in a list.

{
    return lengthSub(head);
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class LE >
int List<LE>:: lengthSub ( ListNode<LE> *p ) const

// Recursive partner of the length() function. Processes the sublist
// that begins with the node pointed to by p.

{
    int result;   // Result returned

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

//--------------------------------------------------------------------
//
// "Unknown" operations used in the Bridge Exercise
//
//--------------------------------------------------------------------

template < class LE >
void List<LE>:: unknown1 () const

// Unknown function 1.

{
    unknown1Sub(head);
    cout << endl;
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class LE >
void List<LE>:: unknown1Sub ( ListNode<LE> *p ) const

// Recursive partner of the unknown1() function.

{
    if ( p != 0 )
    {
       cout << p->element;
       if ( p->next != 0 )
       {
          unknown1Sub(p->next->next);
          cout << p->next->element;
       }
    }
}

//--------------------------------------------------------------------

template < class LE >
void List<LE>:: unknown2 ()

// Unknown function 2.

{
    unknown2Sub(head);
}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < class LE >
void List<LE>:: unknown2Sub ( ListNode<LE> *&p )

// Recursive partner of the unknown2() function.

{
    ListNode<LE> *q;

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