// Template List class definition



#ifndef LIST_H

#define LIST_H



#include <iostream>

using std::cout;



#include <new>



#include "listnode.h"  // ListNode class definition



template< class NODETYPE >

class List {



public:

   List();

   ~List();

   void insertInOrder( const NODETYPE &value );

   bool removeFromFront( NODETYPE & );

   bool removeFromBack( NODETYPE & );

   bool deleteNode( const NODETYPE &, NODETYPE & );

   bool isEmpty() const;

   void print() const;



private:

   void insertAtFront( const NODETYPE & );

   void insertAtBack( const NODETYPE & );



   ListNode< NODETYPE > *firstPtr;  // pointer to first node

   ListNode< NODETYPE > *lastPtr;   // pointer to last node



}; // end class List



// default constructor

template< class NODETYPE >

List< NODETYPE >::List() 

   : firstPtr( 0 ), 

     lastPtr( 0 ) 

{ 

   // empty body



} // end List constructor



// destructor

template< class NODETYPE >

List< NODETYPE >::~List()

{

   if ( !isEmpty() ) {    // List is not empty

      cout << "Destroying nodes ...\n";



      ListNode< NODETYPE > *currentPtr = firstPtr;

      ListNode< NODETYPE > *tempPtr;



      while ( currentPtr != 0 ) {  // delete remaining nodes

         tempPtr = currentPtr;

         cout << tempPtr->data << '\n';

         currentPtr = currentPtr->nextPtr;

         delete tempPtr;



      } // end while



   } // end if



   cout << "All nodes destroyed\n\n";



} // end List destructor



// insert node at front of list

template< class NODETYPE >

void List< NODETYPE >::insertAtFront( const NODETYPE &value )

{

   ListNode< NODETYPE > *newPtr = new ListNode< NODETYPE >( value );



   if ( isEmpty() )  // List is empty

      firstPtr = lastPtr = newPtr;



   else {  // List is not empty

      newPtr->nextPtr = firstPtr;

      firstPtr = newPtr;



   } // end else



} // end function insertAtFront



// insert node at back of list

template< class NODETYPE >

void List< NODETYPE >::insertAtBack( const NODETYPE &value )

{

   ListNode< NODETYPE > *newPtr = new ListNode< NODETYPE >( value );



   if ( isEmpty() )  // List is empty

      firstPtr = lastPtr = newPtr;



   else {  // List is not empty

      lastPtr->nextPtr = newPtr;

      lastPtr = newPtr;



   } // end else



} // end function insertAtBack



// delete node from front of list

template< class NODETYPE >

bool List< NODETYPE >::removeFromFront( NODETYPE &value )

{

   if ( isEmpty() )  // List is empty

      return false;  // delete unsuccessful



   else {  

      ListNode< NODETYPE > *tempPtr = firstPtr;



      if ( firstPtr == lastPtr )

         firstPtr = lastPtr = 0;

      else

         firstPtr = firstPtr->nextPtr;



      value = tempPtr->data;  // data being removed

      delete tempPtr;



      return true;  // delete successful



   } // end else



} // end function removeFromFront



// delete node from back of list

template< class NODETYPE >

bool List< NODETYPE >::removeFromBack( NODETYPE &value )

{

   if ( isEmpty() )

      return false;  // delete unsuccessful



   else {

      ListNode< NODETYPE > *tempPtr = lastPtr;



      if ( firstPtr == lastPtr )

         firstPtr = lastPtr = 0;

      else {

         ListNode< NODETYPE > *currentPtr = firstPtr;



         // locate second-to-last element

         while ( currentPtr->nextPtr != lastPtr )

            currentPtr = currentPtr->nextPtr;



         lastPtr = currentPtr;

         currentPtr->nextPtr = 0;



      } // end else



      value = tempPtr->data;

      delete tempPtr;



      return true;  // delete successful



   } // end else



} // end function removeFromBack





// insert node in sorted order

template< class NODETYPE >

void List< NODETYPE >::insertInOrder( const NODETYPE &value )

{

   if ( isEmpty() ) {

      ListNode< NODETYPE > *newPtr = new ListNode< NODETYPE >( value );

      firstPtr = lastPtr = newPtr;

   }

   else {

      if( firstPtr->data >= value)

         insertAtFront( value );

      else if( lastPtr->data < value)

         insertAtBack( value );

      else {

         ListNode< NODETYPE > *currentPtr = firstPtr->nextPtr,

                              *previousPtr = firstPtr,

                              *newPtr = new ListNode< NODETYPE >( value );



         // locate element before new node gets inserted

         while ( currentPtr != lastPtr && currentPtr->data < value ) {

            previousPtr = currentPtr;

            currentPtr = currentPtr->nextPtr;

         }



         previousPtr->nextPtr = newPtr;

         newPtr->nextPtr = currentPtr;



      } // end else



   } // end else



} // end function insertInOrder



// delete a node from anywhere in the list

template< class NODETYPE >

bool List< NODETYPE >::deleteNode( const NODETYPE &value, NODETYPE &deletedVal )

{

   if ( isEmpty() )

      return false;   // delete unsuccessful

   else {

      if ( firstPtr->data == value ) {

         removeFromFront( deletedVal );

         return true;  // delete successful

      }

      else if ( lastPtr->data == value ) {

         removeFromBack( deletedVal );

         return true;  // delete successful

      }

      else {

         ListNode< NODETYPE > *currentPtr = firstPtr->nextPtr,

                              *previousPtr = firstPtr;



         while ( currentPtr != lastPtr && currentPtr->data < value ) {

            previousPtr = currentPtr;

            currentPtr = currentPtr->nextPtr;

         }



         if ( currentPtr->data == value ) {

            ListNode< NODETYPE > *tempPtr = currentPtr;

            deletedVal = currentPtr->data;

            previousPtr = currentPtr->nextPtr;

            delete tempPtr;

            return true;  // delete successful

         }

         else

            return false;  // delete unsuccessful



      } // end else



   } // end else



} // end function deleteNode



// is List empty?

template< class NODETYPE > 

bool List< NODETYPE >::isEmpty() const 

{ 

   return firstPtr == 0; 

   

} // end function isEmpty



// display contents of List

template< class NODETYPE >

void List< NODETYPE >::print() const

{

   if ( isEmpty() ) {

      cout << "The list is empty\n\n";

      return;



   } // end if



   ListNode< NODETYPE > *currentPtr = firstPtr;



   cout << "The list is: ";



   while ( currentPtr != 0 ) {

      cout << currentPtr->data << ' ';

      currentPtr = currentPtr->nextPtr;



   } // end while



   cout << "\n\n";



} // end function print



#endif