//=============================================================================
// dllist.h
// A doubly linked list class.
// Stores non-negative integers. (Making it easy to pass "-1" back from a 
//    function to indicate an error.  Lazy, but effective.)
// contains head and tail pointers, and implements various operations.
//
// Written by Chuck Cusack, Feb 2001.
// Revised April 2002.
//=============================================================================
#ifndef DLLIST
#define DLLIST

#include<cstdlib>
#include<iostream>

using namespace std;

//=============================================================================
// Each item in the linked list is a node, which contains a key (the value we
// care about), and previous and next pointers.
//
struct node {
    int key;        // The value of interest in the node
    node *next;     // A pointer to the previous node in the list
    node *previous; // A pointer to the next node in the list
};


//=============================================================================
class dllist {
public:
    //---------------------------------------------------------
    // The default constructor: Create an empty linked list
    //
    dllist();

    //---------------------------------------------------------
    // The destructor: Delete the linked list.  Specifically, 
    // delete all of the nodes currently on the list
    //
    ~dllist();

    //---------------------------------------------------------
    // The copy constructor.  Implements a "deep" copy.  That is,
    // copies all of the nodes in originalList to the new list.  
    // 
    dllist(const dllist& originalList);

    //---------------------------------------------------------
    // The overloaded assign operator.  Implements a "deep" copy.  
    // That is, copies all of the nodes in originalList to the 
    // new list.  
    // 
    dllist& operator=(const dllist & originalList);

    //---------------------------------------------------------
    // Insert a new item at the head of the list, containing a 
    // key with value K
    //
    void InsertAtHead(int K);

    //---------------------------------------------------------
    // Insert a new item at the tail of the list, containing a 
    // key with value K
    // 
    void InsertAtTail(int K);

    //---------------------------------------------------------
    // Search for an item on the list with value K.
    // Return true (1) if it is, false (0) if it is not.
    //
    bool Find(int K);

    //---------------------------------------------------------
    // Delete the value K from the linked list.
    // Return true (1) if the key is on the list and was deleted,
    // and false (0) if it is not on the list (and therefore was
    // not deleted).
    // Precondition: The list is not empty
    // 
    bool Delete(int K);

    //---------------------------------------------------------
    // Delete the first item from the list.
    // Return the value of the head if the list is not empty, 
    // and -1 if the list is empty.
    // Precondition: The list is not empty
    // 
    int DeleteFromHead();

    //---------------------------------------------------------
    // Delete the last item from the list.
    // Return the value of the tail if the list is not empty, 
    // and -1 if the list is empty.
    // Precondition: The list is not empty
    // 
    int DeleteFromTail();

    //---------------------------------------------------------
    // Delete all items from the list.
    void Purge();

    //---------------------------------------------------------
    // Return the value of the first item on the list. If the
    // list is empty, return -1.
    int getHead() const;

    //---------------------------------------------------------
    // Return the value of the last item on the list. If the
    // list is empty, return -1.
    // 
    int getTail() const;

    //---------------------------------------------------------
    // Return true (1) if the list is empty, and false (0) if
    // the list is not empty.
    // 
    bool isEmpty() const;
 
    //---------------------------------------------------------
    // The overloaded >> operator.  Used to read in a doubly 
    // linked list from a stream (cin, or a file stream). 
    // Assumes the list is stored by specifying the elements on
    // the list from head to tail.
    // Example: if the linked list is:
    //  head->12->3->123->34->4->null
    // then the file contains:
    // 12 3 123 34 4
    //
    // --Not actually a class method, but a friend--
    //
    friend istream &operator>>(istream &thestream, dllist& theList);

    //---------------------------------------------------------
    // The overloaded << operator.  Used to write a doubly linked
    // list to a stream.  Writes each element from head to tail.
    // See the '>>' operator above for an example.
    //
    // --Not actually a class method, but a friend--
    //
    friend ostream &operator<<(ostream &thestream, const dllist theList);


//-----------------------------------------------------------------------------
private:  // The data
    node *head;  // Points to the first item on the linked list
    node *tail;  // Points to the last item on the linked list
};
#endif
//=============================================================================