//
//   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; }

  virtual ~ DList( );    // destructor

  // 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; }
};


//
//   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 )
{
  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( )
{
}

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;
  }
}

#endif