//
//   Example code for manipulating a circularly linked lists with
//   header nodes.  Note that the List class is actually a template
//   class. 
//
//

#ifndef List_H
#define List_H

#ifdef GNU
#define std 
#include <iostream.h>
#else
#include <iostream>
#endif

#include "listiter.h"

////////////////////////////////////////////////////
// CLASS: LIST
////////////////////////////////////////////////////
template <class EleType>
class Node {
 public:
  EleType element;
  Node<EleType> * next;
  
  // constructor for Node.  Don't initialize the pointers.
  //
  Node( const EleType & e ) : element(e) { }
};


template <class EleType>
class List {
protected:
  Node<EleType> * head;
  Node<EleType> * current;

  // Find the previous node for the node with element value x.
  bool Find_Prev(const EleType & x);

public:
  List( ){
    EleType et;
    head = new Node<EleType>(et);
    head->next = head;  current = head; }

  // Here is the prototype for the new "copy constructor."  Note that
  // the existing list is passed by reference!  Otherwise, the copy
  // constructor would call itself in an infinite recursion.
  //
  List( const List<EleType> & old );

  virtual ~ List( );    // destructor

  //Here's the prototype for the assignment operator. Note that the
  //argument is passed by reference.
  List & operator = (const List<EleType> &old);

  // Here are the pre-increment and -decrement operators.
  // We could insert more here operators here.  See examples in the
  // text for details on singly linked lists.   

  const List & operator ++ ( )   // pre-increment
    { if (current != head)  current = current->next;
      return *this; }

  //  Here are a few of the member functions declarations (along with
  //  a few in-line definitions.

  bool Is_Empty( ) { return head->next == head; }

  // Find the node with element value x.  If it is found, make the
  // current pointer point to the node containing x and return true.  If
  // it is not found, make the current pointer point to the last
  // element. 
  //
  bool Find( const EleType & x );

  //  Make the current pointer point to the beginning / end of the
  //  list. 
  //
  void First( ) { current = head->next; }

  //Make current pointer point to the dummy header.
  void Head ( ) { current = head;}

  //return the dummy header
  const Node<EleType>* Header() const {return head;}

  //  Insert a node with element value x after the current node in the
  //  list.   Update the current node to point to the new element.
  //
  virtual void Insert( const EleType & x );
  
  //  Delete the node pointed to by the current node.  Current will
  //  then point to the next element of the list.
  //
  void Delete( const EleType & x );

  //  Return the current value in the list as long as the current
  //  pointer is pointing to an element of the list.
  //
  const EleType & Current_Value( );

  // return the current value. Unlike the routine above this routine
  // returns a non-const reference pointer to the element, i.e., the
  // returned element can be modified by the caller.
  EleType & Current_LValue() {return current->element;}

  //  Has the current pointer scanned through the entire list?
  //
  bool Exhausted( ) { return current == head; }

  //output routine
  friend std::ostream &
    operator << ( std::ostream & out_str, const List<EleType> & ll );
};

//
//   Code for member functions that are not "in-line"
//

// Here is the new "copy constructor."   It marches down the existing
// list, making copies of each node in the list.  
//
// I have included the "this" pointer to show how it is used.
//
// Finally, this copy constructor is invoked automatically for
// Sorted_List since its copy constructor does not exist.
//
template <class EleType>
List<EleType>::List( const List<EleType> & old )
{
  // std::cout << "In copy constructor.\n";  // uncomment to show calls

  EleType et;
  this->head = new Node<EleType>(et);
  Node<EleType> * prev_new = this->head;  // most recent node added to the new list 
  Node<EleType> * next_new;               // next node added to the new list
  Node<EleType> * old_p = old.head->next; // pointer to a node in the old list

  while ( old_p != old.head ) {
    next_new = new Node<EleType>( old_p->element );
    prev_new->next = next_new;
    prev_new = next_new;
    if ( old.current == old_p ) {
      this->current = next_new;
    }
    old_p = old_p->next;
  }
  prev_new->next = this->head;
}

//Here's the prototype for the assignment operator. Note that the
//argument is passed by reference.
template <class EleType>
List<EleType> & 
List<EleType>::operator = (const List<EleType> &old){
  Node<EleType> * temp;
  current = head->next;
  
  while ( current != head ) {
    temp = current;
    current = current->next;
    delete temp;
  }
  delete head;

  EleType et;
  head = new Node<EleType>(et);
  Node<EleType> * prev_new = head;  // most recent node added to the new list 
	Node<EleType> * next_new;               // next node added to the new list
	Node<EleType> * old_p = old.head->next; // pointer to a node in the old list

	while ( old_p != old.head ) {
		next_new = new Node<EleType>( old_p->element );
		prev_new->next = next_new;
		prev_new = next_new;
		if ( old.current == old_p ) {
			current = next_new;
		}
		old_p = old_p->next;
	}
	prev_new->next = head;
	return *this;
}

template <class EleType>
List<EleType>::~List( )
{
  Node<EleType> * temp;
  current = head->next;
  
  while ( current != head ) {
    temp = current;
    current = current->next;
    delete temp;
  }
  delete head;
}

template <class EleType>
bool
List<EleType>::
Find_Prev(const EleType & x)
{
  if (head->next->element == x){
    current = head;
    return true;
  }
  Node<EleType> * p = head->next;
  while ( p != head ) {
    if ( p->next->element == x ) {
      current = p;
      return true;
    }
    p = p->next;
  }
  current = head;
  return false;
}

template <class EleType>
bool
List<EleType>::
Find( const EleType & x )
{
  Node<EleType> * p = head->next;
  while ( p != head ) {
    if ( p->element == x ) {
      current = p;
      return true;
    }
    p = p->next;
  }
  current = head;
  return false;
}

template <class EleType>
void
List<EleType>::
Insert( const EleType & x )
{
  Node<EleType> * p = new Node<EleType>( x );
  p->next = current->next;
  current->next = p;
  current = p;
}


template <class EleType>
void
List<EleType>::
Delete( const EleType & x )
{
  if (Find_Prev(x)){
    Node<EleType> * temp = current->next;
    current->next = current->next->next;
    delete temp;
  }
}

template <class EleType>
const EleType &
List<EleType>::
Current_Value( )
{
    return current->element;
}


template <class EleType>
std::ostream &
operator << ( std::ostream & out_str, const List<EleType> & ll )
{
  ListIter<EleType> li(ll);
  for (; !li.Exhausted(); ++li) {
    out_str << li.Current_Value( ) << " ";
  }
  return out_str;
}


#endif