//
//   Example code for manipulating circular, doubly-linked lists with
//   header nodes.  Note that the DList class is actually a template
//   class. 
//
//   Source code location:  /dept/cs/cs230/class/ch3/dlist.h
//

#ifndef DLIST_H
#define DLIST_H

#include <iostream>
#include <string>

struct DList_error {
  std::string type;
  DList_error(std::string t = "not specified") : type(t) { }
};

template <class EleType>
class DList {
protected:

  struct Node {
    EleType element;
    Node * next;
    Node * prev;
    
    // constructor for Node.  Don't initialize the pointers.
    //
    Node( const EleType & e ) : element(e) { }
  };

  Node * head;
  Node * current;

public:
  DList( ) : head( new Node(0) )
    { head->next = head->prev = 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.
  //
  DList( const DList<EleType> & old );

  virtual ~ DList( );    // destructor

  //Here's the prototype for the assignment operator. Note that the
  //argument is passed by reference.
  DList & operator = (const DList<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 DList & operator ++ ( )   // pre-increment
    { if (current != head)  current = current->next;
      return *this; }

  const DList & operator -- ( )  // pre-decrement
    { if (current != head)  current = current->prev;
      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; }
  void Last( ) { current = head->prev; }

  //  Insert a node with element value x after the current node in the
  //  list.   Update the current node to point to the new element.
  //
  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( );

  //  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( );

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

// Here is the new "copy constructor."   It marches down the existing
// list, making copies of each node in the list.  It does this by
// keeping track of the previous node that it allocated, and setting
// this node's next pointer only after allocating a new node.  It can
// immediately set this new node's prev pointer to be the previous
// node.  It also figures out which node to make the new current
// pointer point to.  
//
// I have included the "this" pointer to show how it is used.
//
// Finally, this copy constructor is invoked automatically for
// Sorted_DList since its copy constructor does not exist.
//
template <class EleType>
DList<EleType>::DList( const DList<EleType> & old )
{
  // std::cout << "In copy constructor.\n";  // uncomment to show calls

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

  while ( old_p != old.head ) {
    next_new = new Node( old_p->element );
    next_new->prev = prev_new;
    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;
  this->head->prev = prev_new;
}

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

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

	while ( old_p != old.head ) {
		next_new = new Node( old_p->element );
		next_new->prev = prev_new;
		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;
	head->prev = prev_new;
	return *this;
}

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

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

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

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


template <class EleType>
void
DList<EleType>::
Delete( )
{
  if ( current != head ) {
    current->next->prev = current->prev;
    current->prev->next = current->next;
    Node * temp = current;
    current = current->next;
    delete temp;
  }
}

template <class EleType>
const EleType &
DList<EleType>::
Current_Value( )
{
  if ( current == head ) {
    throw DList_error("attempted to access non-existent element of a list");
    return 0;
  }
  else {
    return current->element;
  }
}


//
//  The Sorted_DList is a derived class of DList.  It redefines only
//  the Find and Insert member functions.
//
template <class EleType>
class Sorted_DList : public DList<EleType> {
public:
  //
  //  Find searches for element x in the list.  If it finds the list
  //  it makes the current pointer point to the node holding x and it
  //  returns true.  If it does not find x, it makes the current
  //  pointer point to the node before where a node containing x
  //  should be inserted and it returns false.
  //
  bool Find( const EleType & x );

  //
  //  Insert value x into the list, placing it in the appropriate
  //  position in increasing order.  x is placed in the list in a
  //  separate node regardless of whether it is already in the list.
  //
  void Insert( const EleType & x );
};


template <class EleType>
bool
Sorted_DList<EleType>::
Find( const EleType & x )
{
  Node * p = head->next;
  while ( p != head ) {
    if ( p->element == x ) {
      current = p;
      return true;
    }
    else if ( x < p->element ) { // x can't be in the list
      current = p->prev;
      return false;
    }
    p = p->next;
  }
  current = head->prev;  // current points to the last element
  return false;
}


template <class EleType>
void
Sorted_DList<EleType>::
Insert( const EleType & x )
{
  int result = Find( x );  
  DList<EleType>::Insert( x );
}

#endif