/////////////////////////////////////////////////////////////////////
//  LinkedList.H                                                   //
//  CMSC 341 - Fall 2001 Project 2                                 //
//  Kyu Bae xxx-xx-5868, Section 201                               //
//  kyu_bae@yahoo.com / kbae1@umbc.edu                             //
//  Created: 20 September 2001                                     //
//  Current: 30 September 2001                                     //
/////////////////////////////////////////////////////////////////////

#ifndef _LinkedList_H
#define _LinkedList_H

#include "dsexceptions.h"
#include <iostream.h>    // For NULL

////////////////////////////////////////////////////////////
// List class:
// List class has ListNode header and it check for 
// empty and make
// list empty and inserting list.  
// CONSTRUCTION: with no initializer
// Access is via ListItr class
//
// ******************PUBLIC OPERATIONS*********************
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// ListItr zeroth( )      --> Return position to prior to first
// ListItr first( )       --> Return first position
// void insert( x, p )    --> Insert x after current iterator
//                            position p
// void remove( x )       --> Remove x
// ListItr find( x )      --> Return position that views x
// ListItr findPrevious( x )
//                        --> Return position prior to x
// ******************ERRORS********************************
// No special errors
/////////////////////////////////////////////////////////////
template <class Object>
class List;     // Incomplete declaration.

template <class Object>
class ListItr;     // Incomplete declaration.

////////////////////////////////////////////////////////////
// ListNode Class:
// This class makes ListNode next and prev and Object element
// It initialize data members to Null.
///////////////////////////////////////////////////////////
template <class Object>
class ListNode
{
    //////////////////////////////////////////////////////////
    //  Default constructor:
    //  initialize data members to NULL or parameter which are 
    //  passed to theElment to element and n to next and p to 
    //  prev. It used list initializer to initialize the data
    //  members.
    //  Param theElement : assign to element
    //  Param n : the object of ListNode to assign to next
    //  Param p : the object of ListNode to assign to prev
    ///////////////////////////////////////////////////////////
    ListNode( const Object & theElement = Object( ),
              ListNode * n = NULL, ListNode * p = NULL )
        : element( theElement ), next( n ), prev( p ) { }
  
    Object   element;  //Data class object
    ListNode *next;    //ptr to ListNode     
    ListNode *prev;
  
    friend class List<Object>;
    friend class ListItr<Object>;
};

/////////////////////////////////////////////////////////
//  List Class:
//  List class has ListNode header and it check for
//  empty and make
//  list empty and inserting list.  
//  CONSTRUCTION: with no initializer
//  Access is via ListItr class/  
////////////////////////////////////////////////////////
template <class Object>
class List
{
public:
    /////////////////////////////////////////////////////////
    //  Default constructor:
    //  Initialize header to NULL
    /////////////////////////////////////////////////////////  
    List( );
    
    ////////////////////////////////////////////////////////
    //  Copy COnstructor:
    //  Copy another List object to this.
    //  Param rhs: anther object to this
    ////////////////////////////////////////////////////////
    List( const List & rhs );

    ////////////////////////////////////////////////////////
    //  Destructor:
    //  calls makeEmpty() and delete header node 
    ///////////////////////////////////////////////////////
    ~List( );
    
    ////////////////////////////////////////////////////////
    //  isEmpty():
    //  checking if list has any node in the list and if not
    //  return true or false
    //  Return : boolean for empty  
    ////////////////////////////////////////////////////////
    bool isEmpty( ) const;

    /////////////////////////////////////////////////////////
    //  makeEmpty():
    //  Make the list logically empty.
    //
    /////////////////////////////////////////////////////////   
    void makeEmpty( );

    /////////////////////////////////////////////////////////
    //  zeroth():
    //  Return an iterator representing the header node.
    /////////////////////////////////////////////////////////
    ListItr<Object> zeroth( ) const;
    
    //////////////////////////////////////////////////////////
    //  first():
    //  Return an iterator representing the first node in
    //  the list.
    //  This operation is valid for empty lists.
    /////////////////////////////////////////////////////////
    ListItr<Object> first( ) const;
    
    /////////////////////////////////////////////////////////
    //   insert():
    //   Insert item x after p.
    //   Param x: Data class object
    //   param p: ListItr object current position
    ///////////////////////////////////////////////////////// 
    void insert( const Object & x, const ListItr<Object> & p );
   
    /////////////////////////////////////////////////////////
    //  find():
    //  Return iterator corresponding to the first node 
    //  containing 
    //  an item x.
    //  Iterator isPastEnd if item is not found.
    //  Param x : Data class object 
    //  Return : object of ListItr
    ///////////////////////////////////////////////////////// 
    ListItr<Object> find( const Object & x ) const;

    /////////////////////////////////////////////////////////
    //    findPrevious():
    //    Return iterator prior to the first node
    //    containing an item x.
    //    Param x : object of Data class
    //    Return : object ListItr current position
    /////////////////////////////////////////////////////////
    ListItr<Object> findPrevious( const Object & x ) const;
   
    //////////////////////////////////////////////////////////
    //  remove():
    //  Remove the first occurrence of an item x.
    //  param x : object of Data class
    //////////////////////////////////////////////////////////
    void remove( const Object & x );
  
    ///////////////////////////////////////////////////////////
    //  operator=():
    //  Deep copy of linked lists.
    //  Param rhs : assign its data members to rhs
    //  Return : List object
    ////////////////////////////////////////////////////////// 
    const List & operator=( const List & rhs );
  
private:
    ListNode<Object> *header;
};

///////////////////////////////////////////////////////////
// ListItr class; maintains "current position"
//
// CONSTRUCTION: Package friendly only, with a ListNode
//
// ******************PUBLIC OPERATIONS*********************
// bool isPastEnd( )      --> True if past end position in list
// void advance( )        --> Advance (if not already null)
// Object retrieve        --> Return item in current position
///////////////////////////////////////////////////////////
template <class Object>
class ListItr
{
public:
    ////////////////////////////////////////////////////////
    //  Default constructor:
    //  initialize current to Null
    //  used list initializer to assign current to Null
    //////////////////////////////////////////////////////// 
    ListItr( ) : current( NULL ) { }
    
    //////////////////////////////////////////////////////
    //   isPastEnd();
    //   checking if iterator has passed the list and to
    //   Null.
    //   Return : boolean for past end node
    /////////////////////////////////////////////////////     
    bool isPastEnd( ) const    //No header & 1 element
        { if(current == NULL || current->next == NULL)
              return true;
          return false; }

    /////////////////////////////////////////////////////
    //   advance();
    //   moving forward and check if it has passed  past
    //   end
    /////////////////////////////////////////////////////
    void advance( )
        { if( !isPastEnd( ) ) current = current->next; }

    ///////////////////////////////////////////////////////
    //  retrieve():
    //  get node (Data class element) and if there is no node
    //  it throw exception
    //  Return : Data class object
    //  Pre cond: must not be empty list
    ////////////////////////////////////////////////////////
    void retreat()
        { if( !isPastEnd( ) ) current = current->prev; }
    
    ///////////////////////////////////////////////////////
    //  retrieve():
    //  get node (Data class element) and if there is no node
    //  it throw exception
    //  Return : Data class object
    //  Pre cond: must not be empty list
    ////////////////////////////////////////////////////////
    const Object & retrieve( ) const
        { if( isPastEnd( ) ) throw BadIterator( );
          return current->element; }
  
private:
    ListNode<Object> *current;    // Current position
    
    ///////////////////////////////////////////////////////
    //  Constructor:
    //  calls ListNode constructor to theNode to currentNode
    //  Param theNode: object of ListNode
    //  Uses list initializer to assign current to theNOde
    /////////////////////////////////////////////////////// 
    ListItr( ListNode<Object> *theNode )
        : current( theNode ) { }
  
    friend class List<Object>; // Grant access to constructor
};

#include "LinkedList.C"
#endif