//--------------------------------------------------------------------
//
//  Laboratory 7                                         listlnk.cpp
//
//  SOLUTION: Linked list implementation of the List ADT
//
//--------------------------------------------------------------------

#include <assert.h>
#include <alloc.h>
#include "listlnk.h"

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

template < class LE >
ListNode<LE>:: ListNode ( const LE &elem, ListNode<LE> *nextPtr )

// Creates a list node containing element elem and next pointer
// nextPtr.

  : element(elem),
    next(nextPtr)
{}

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

template < class LE >
List<LE>:: List ( int ignored = 0 )

// Creates an empty list. The argument is included for compatibility
// with the array implementation and is ignored.

  : head(0),
    cursor(0)
{}

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

template < class LE >
List<LE>:: ~List ()

// Frees the memory used by a list.

{
    clear ();
}

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

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

// Inserts newElement after the cursor. If the list is empty, then
// newElement is inserted as the first (and only) element in the list.
// In either case, moves the cursor to newElement.

{
    if ( head == 0 )             // Empty list
    {
       head = new ListNode<LE>(newElement,0);
       assert ( head != 0 );
       cursor = head;
    }
    else                         // After cursor
    {
       cursor->next = new ListNode<LE>(newElement,cursor->next);
       assert ( cursor->next != 0 );
       cursor = cursor->next;
    }
}

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

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

// Removes the element marked by the cursor from a list. Moves the
// cursor to the next element in the list. Assumes that the first list
// element "follows" the last list element.

{
    ListNode<LE> *p,   // Pointer to removed node
                 *q;   // Pointer to prior node

    assert ( head != 0 );       // Requires that the list is not empty

    if ( cursor == head )             // Remove first element
    {
       p = head;
       head = head->next;
       cursor = head;
    }
    else if ( cursor->next != 0 )     // Remove middle element
    {
       p = cursor->next;
       cursor->element = p->element;
       cursor->next = p->next;
    }
    else                              // Remove last element
    {
       p = cursor;
       for ( q = head ; q->next != cursor ; q = q->next );
       q->next = 0;
       cursor = head;
    }

    delete p;
}

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

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

// Replaces the element marked by the cursor with newElement and
// leaves the cursor at newElement.

{
    assert ( head != 0 );      //  Requires that the list is not empty
    cursor->element = newElement;
}

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

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

// Removes all the elements from a list.

{
    ListNode<LE> *p,      // Points to successive nodes
                 *nextP;  // Points to next node
    p = head;
    while ( p != 0 )
    {
        nextP = p->next;
        delete p;
        p = nextP;
    }

    head = 0;
    cursor = 0;
}

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

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

// Returns 1 if a list is empty. Otherwise, returns 0.

{
    return ( head == 0 );
}

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

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

// Returns 1 if a list is full. Otherwise, returns 0. Cannot be
// done cleanly in generic C++ because there is sometimes overhead
// associated with a memory allocation.

{
    return ( coreleft() < sizeof(LE) );
}

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

template < class LE >
int List<LE>:: gotoBeginning ()

// If a list is not empty, then moves the cursor to the beginning of
// the list and returns 1. Otherwise, returns 0.

{
   int result;   // Result returned

   if ( head != 0 )
   {
      cursor = head;
      result = 1;
   }
   else
      result = 0;

   return result;
}

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

template < class LE >
int List<LE>:: gotoEnd ()

// If a list is not empty, then moves the cursor to the end of the
// list and returns 1. Otherwise, returns 0.

{
   int result;   // Result returned

   if ( head != 0 )
   {
      for (   ; cursor->next != 0 ; cursor = cursor->next );
      result = 1;
   }
   else
      result = 0;

   return result;
}

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

template < class LE >
int List<LE>:: gotoNext ()

// If the cursor is not at the end of a list, then moves the
// cursor to the next element in the list and returns 1. Otherwise,
// returns 0.

{
   int result;   // Result returned

   if ( cursor->next != 0 )
   {
      cursor = cursor->next;
      result = 1;
   }
   else
      result = 0;

   return result;
}

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

template < class LE >
int List<LE>:: gotoPrior ()

// If the cursor is not at the beginning of a list, then moves the
// cursor to the preceeding element in the list and returns 1.
// Otherwise, returns 0.

{
   ListNode<LE> *p;   // Pointer to prior node
   int result;        // Result returned

   if ( cursor != head )
   {
      for ( p = head ; p->next != cursor ; p = p->next );
      cursor = p;
      result = 1;
   }
   else
      result = 0;

   return result;
}

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

template < class LE >
LE List<LE>:: getCursor () const

// Returns the element marked by the cursor.

{
    assert ( head != 0 );      //  Requires that the list is not empty
    return cursor->element;
}

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

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

// Outputs the elements in a list. If the list is empty, outputs
// "Empty list". This operation is intended for testing and
// debugging purposes only.

{
    ListNode<LE> *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->element << "] ";
           else
              cout << p->element << " ";
       cout << endl;
    }
}