// FILE: dLinkedShell.cpp 
// PURPOSE: implement doubly linked list operations
//------------------------------------------------------------------
// COMPILATION INSTRUCTIONS: g++ and gxx 
// COMMAND LINE: g++ (or gxx) dLinkedShell.cpp
//------------------------------------------------------------------
// PROGRAMMING INSTRUCTIONS:
// Implement the functions as specified below
//------------------------------------------------------------------
#include <iomanip.h>
#include <stdlib.h>
#include <string>

class Node {
public:
  Node(void) : city(""), prev(NULL), next(NULL) {}
  Node(string city2, Node *prev2, Node *next2);
  string city;
  Node *prev, *next;
};

Node::Node(string city2, Node *prev2, Node *next2) 
  : city(city2), prev(prev2), next(next2)
{}

bool insertFront(Node *&List, string city) {
  //-------------------------------------------------------------------------
  //pre: List points to 1st element in list, city is value to be inserted
  //post: if new operation succeeeds:
  //         1. List points to new Node
  //         2. new Node points to previous 1st Node
  //         3. true is returned
  //      else false is returned 
  //-------------------------------------------------------------------------
   return false;
} //*** insert


bool removeUnordered(Node *&List, string city) {
  //----------------------------------------------------------------------
  //pre: 1. List points to 1st element in unordered list
  //     2  city is value to be removed
  //post: if Node with data member == city is found:
  //         it is removed, its memory is returned to free store, 
  //         true is returned
  //      else false is returned 
  //-----------------------------------------------------------------------
 
  return false;
}//*** removeUnOrdered


bool insertInOrder(Node *&List, string city) {

   return false;
} //*** insertInOrder


bool removeInOrder(Node *&List, string city) {

  return false;
}//** removeInOrder


int countList(Node *List) {
  //------------------------------------------------------------
  //pre:  List points to 1st element in list
  //post: returns number of elements in list:  recursive version
  //-----------------------------------------------------------


    return -77;
}//*** countList



void destroyList(Node* &List) {

}//*** destroyList


void destroyList2(Node* &List) {

}//*** destroyList2



void menu(char &);
void insertProc(Node *&, char);
void removeProc(Node *&, char);
void destroyProc(Node *&);
void countProc(Node *);
void makeList(Node *&);
void printList(Node *);
void cls(void);

int main() {
  Node *List = NULL;
  char ch;
  do {
    cls();
    printList(List);    
    menu(ch);
    switch( ch ) {
    case '1': insertProc(List, ch); break;
    case '2': removeProc(List, ch); break;
    case '3': printList(List); break;
    case '4': insertProc(List, ch); break;
    case '5': removeProc(List, ch); break;
    case '6': countProc(List); break;
    case '7': destroyProc(List);  break;
    case '8': makeList(List);  break;
    case '0': return 0;
    default: break;
    } // switch
    cout << "\nPress <ENTER> to continue..."; cin.ignore(10, '\n');
  } while (ch != '0');
  return 0;
}

void printList(Node *List) {
   Node *np = List;
   int n = 0;
   cout << endl;
   if ( List == NULL ) {
      cout << "List is empty\n";
      return;
   }
   while ( np != NULL ) {
      n += 1;
      cout << setw(3) << n << ".  " << np->city;
      np = np->next;
   }
   cout << endl;
} //*** printList


void menu(char &choice) {
  const string title("DOUBLY LINKED LIST OPERATIONS DRIVER");
  const string PAD("\t\t\t");
  cout << "\n\n" << setw(41 + title.length()/2) 
       << title.c_str() << endl;
  cout << PAD  << "----------------------------------\n";
  cout << PAD << "Insert city in front             1\n";
  cout << PAD << "Delete city (unordered list)     2\n";
  cout << PAD << "Print list                       3\n";
  cout << PAD << "Insert city (ordered list)       4\n";
  cout << PAD << "Delete city (ordered list)       5\n";
  cout << PAD << "Item count                       6\n";
  cout << PAD << "Destroy list                     7\n";
  cout << PAD << "Create ordered list              8\n";
  cout << PAD << "Quit program                     0\n";
  cout << PAD << "----------------------------------\n";
  cout << PAD << "       SELECTION==> ";
  cin.get(choice);
  cin.ignore(10, '\n');
  while ( choice < '0' || choice > '8' ) {
    cout << PAD << "*** Invalid choice. Try again: ";
    cin.get(choice);
    cin.ignore(10, '\n');
  }// while
} //*** menu


void insertProc(Node *&List, char choice) {
  string city;
  cout << "\nEnter city to insert: ";
  getline(cin, city);
  if ( choice == '1' ) {
    cout << "Inserting " << city << " in the front.\n";
    bool success = insertFront(List, city);
    if ( !success )
      cout << "Insertion in front failed: " + city + " not inserted\n";
  }
  else {
    cout << "Inserting " << city << " in order.\n";
    bool success = insertInOrder(List, city);
    if ( !success )
      cout << "Insertion in order failed: " + city + " not inserted\n";
  }
}//*** insertProc


void removeProc(Node *&List, char choice) {
  string city;
  cout << "\nEnter city to delete: ";
  getline(cin, city);
  if ( choice == '2' ) {
    bool deleted = removeUnordered(List, city);
    if ( !deleted )
      cout << "Deletion (unordered) failed: " << city << " not found.\n";
  }
  else { //*** delete in order
    bool deleted = removeInOrder(List, city);
    if ( !deleted )
      cout << "Deletion (ordered) failed: " + city + " not found.\n";
  }
}//*** removeProc


void destroyProc(Node *&List) {
   destroyList(List);
}//*** destroyProc


void countProc(Node *List) {
  cout << "\nNumber of items in list: " << countList(List) << endl;
}//*** countProc


void makeList(Node *&lst) {
  Node *p = new Node("Chicago", NULL, NULL); lst = p;
  p->next = new Node("London", p, NULL); p = p->next;
  p->next = new Node("Paris", p, NULL); p = p->next;
  p->next = new Node("Rome", p, NULL);
}

void cls(void) {
  for (int k = 0; k < 55; k++)
    cout << endl;
}