#ifndef DLL_H_
#define DLL_H_ 1

// Oldham, Jeffrey D.
// 2000Mar24
// CS1321

// Doubly-Linked List Implementation

// This class implements a doubly-linked list.  Each link is allocatd
// from dynamic memory.  The list is represented as a line with ground 
// pointers at either end of the list.

// As a design decision, we decided to hold onto the list using a
// pointers to both the leftmost and rightmost links.  Both pointers
// are 0 if the list has no links.

#include <iostream>
#include <assert.h>		// has assert()

class dll {
public:
  typedef char item_type;

  class link {
  public:
    item_type itm;
    link * prev;		// pointers to other links
    link * next;
  };

  dll(void) { create(); return; }

  // copy constructor
  dll(const dll & d) { copy(d); return; }

  // assignment operator
  dll& operator=(const dll & d) {
    if (this != &d) {
      destroy();
      copy(d);
    }
    return *this;
  }

  // Insert the item before the link.
  link * insert(link * pos, const item_type & i) {
    link * n = new link;
    n->itm = i;

    // Change new link's pointers.
    link * leftGuy = (pos != 0) ? pos->prev : rightmostLink;
    link * rightGuy = pos;
    n->next = rightGuy;
    n->prev = leftGuy;

    // Change the surrounding links' pointers.
    if (leftGuy != 0) leftGuy->next = n; else leftmostLink = n;
    if (rightGuy != 0) rightGuy->prev = n; else rightmostLink = n;

    return n;
  }

  // Delete the specified item.
  link * erase(link * n) {
    assert(n != 0);		// illegal to delete an empty list
    link * rightGal = n->next;
    link * leftGal = n->prev;

    // Change the surrounding links' pointers.
    if (leftGal != 0) leftGal->next = rightGal; else leftmostLink = rightGal;
    if (rightGal != 0) rightGal->prev = leftGal; else rightmostLink = leftGal;
    
    // Change new link's pointers. (not actually necessary)
    n->prev = 0;
    n->next = 0;

    delete n;
    return rightGal;
  }

  ~dll(void) {
    // Delete all the links.
    destroy();
  }

  link * begin(void) const { return leftmostLink; }

  link * end(void) const { return 0; } // useless!

  link * pred(const link * lnk) const {
    if (lnk != 0) return lnk->prev; else return rightmostLink;
  }

  link * succ(const link * lnk) const {
    if (lnk != 0) return lnk->next; else return leftmostLink;
  }

  // Print the list's contents.
  // Should not really be part of the class but useful for debugging.
  friend ostream& operator<<(ostream& out, const dll & d) {
    for (link * here = d.begin(); here != 0; here = here->next)
      out << here->itm << endl;
    return out;
  }

private:
  link * leftmostLink;		// holds onto the list
  link * rightmostLink;		// holds onto the list

  // Create an empty list.
  void create(void) {
    rightmostLink = 0;
    leftmostLink = 0;
    return;
  }

  // Destroy this list;
  void destroy(void) {
    link * destroyLink = leftmostLink;
    while (destroyLink != 0)
      destroyLink = erase(destroyLink);
    return;
  }

  // Copy the given list into this one.
  void copy(const dll & d) {
    create();
    for (link * pos = d.leftmostLink; pos != 0; pos = d.succ(pos))
      insert(0 /* always insert at end */, pos->itm);
    return;
  }
};

#endif // DLL_H_