// Template List class definition

// for illustration purposes only, no robust implementation ( no error-ckecking, etc)



#ifndef LIST_H

#define LIST_H



#include <iostream>

using std::cout;



#include <new>



template< class NODETYPE >

class List {



public:

   List();      // constructor

   ~List();     // destructor

   void insertAtFront( const NODETYPE & );

   void insertAtBack( const NODETYPE & );

   bool removeFromFront( NODETYPE & );

   bool removeFromBack( NODETYPE & );

   bool isEmpty() const;

   void print() const;



private:

   struct ListNode {

      ListNode( const NODETYPE & info ): data( info ), nextPtr( 0 ) { }  // constructor

      NODETYPE data;     // data

      ListNode* nextPtr; // next node in list

   }; // end struct ListNode



   ListNode* firstPtr;  // pointer to first node

   ListNode* lastPtr;   // pointer to last node



public:

   class Iterator { // public access!

   public:

      friend class List< NODETYPE >;



      Iterator( ListNode* initPos = 0 ) : currentPos( initPos ) { }

      Iterator( const List< NODETYPE >& currentList )

      {

         *this = currentList.begin();

      }



      const NODETYPE& operator*() const

      {

         return currentPos->data;

      }

      NODETYPE& operator*()

      {

         return currentPos->data;

      }



      Iterator& operator++()  // prefix

      {

         if( currentPos )

            currentPos = currentPos->nextPtr;

         return *this;

      }

      Iterator operator++( int )  // postfix

      {

         Iterator temp = *this;

         ++*this;

         return temp;

      }



      bool operator==( const Iterator& x ) const

      {

         return currentPos == x.currentPos;

      }

      bool operator!=( const Iterator& x ) const

      {

         return currentPos != x.currentPos;

      }



   private:

      ListNode* currentPos;

   }; // end class Iterator



   Iterator begin() const

   {

      return Iterator( firstPtr );

   }

   Iterator end() const

   {

      return Iterator();

   }

}; // 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 *currentPtr = firstPtr;

      ListNode *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 *newPtr = new ListNode( 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 *newPtr = new ListNode( 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 *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 *tempPtr = lastPtr;



      if ( firstPtr == lastPtr )

         firstPtr = lastPtr = 0;

      else {

         ListNode *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



// 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 *currentPtr = firstPtr;



   cout << "The list is: ";



   while ( currentPtr != 0 ) {

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

      currentPtr = currentPtr->nextPtr;



   } // end while



   cout << "\n\n";



} // end function print



#endif