// DOUBLY LINKED ORDERED LIST
// Insertions and deletions done at the appropriate position.

#include "stdstuff.h"

class DNode {
public:
  DNode () { data = 0; prior = next = NULL; }
  DNode (int data, DNode *next, DNode *prior) {
    this -> data = data; this -> next = next; this -> prior = prior;
  }
  int data;
  DNode *next, *prior;
};


int main () {


  DNode *head = NULL, *tail = NULL,
        *n /* new */, *p /* previous */, *c /*current */;
  int option, value;

  for (;;) {

    cout << "\nEnter option\n"
         << "  1 = insert\n"
         << "  2 = delete\n"
         << "  3 = list contents\n"
         << "  4 = list contents backwards\n"
         << "  5 = quit\n"
         << "Option: ";
    cin >> option;

    switch (option) {

    case 1:

      cout << "\nEnter a value: ";
      cin >> value;
      p = NULL; c = head;
      while (c != NULL && c -> data < value) { // expression order important!
        p = c; c = c -> next;
      }
      n = new DNode (value, c, p);
      if (p == NULL) { // no previous node
        head = n; // so update head instead
      } else {
        p -> next = n;
      }
      if (c == NULL) { // no next node
        tail = n; // so update tail instead
      } else {
        c -> prior = n;
      }
      break;

    case 2:

      cout << "\nEnter a value: ";
      cin >> value;
      p = NULL; c = head;
      for (;;) {

        if (c == NULL || c -> data > value) { // rxpression order important
          // the value is not on the list
          cout << "That value is not on the list.\n";
          break;
        }

        if (c -> data == value) { // value found
          // update previous node
          if (p == NULL) { // no previous node
            head = c -> next; // so update head instead
          } else {
            p -> next = c -> next;
          }
          // update following node
          if (c -> next == NULL) { // no following node
            tail = p; // so update taill instead
          } else {
            (c -> next) -> prior = p;
          }
          delete c;
          cout << "Value successfully deleted.\n";
          break;
        }

        p = c; c = c -> next;

      }
      break;

    case 3:

      if (head == NULL) {
        cout << "\nThe list is empty.\n";
      } else {
        cout << "\nThe list contains:";
        for (c = head; c != NULL; c = c -> next) {
          cout << " " << c -> data;
        }
        cout << endl;
      }
      break;

    case 4:

      if (tail == NULL) {
        cout << "\nThe list is empty.\n";
      } else {
        cout << "\nThe list contains:";
        for (c = tail; c != NULL; c = c -> prior) {
          cout << " " << c -> data;
        }
        cout << endl;
      }
      break;

    case 5:

      // no need to clean up the list as the programming is about to terminate
      pause();
      return 0;

    }

  }


}