// FILE: 92ab2.cpp 
// PURPOSE: 1992 AB Exam: Question 2 (doubly linked lists)
//---------------------------------------------------------------------
// COMPILATION INSTRUCTIONS: g++ and gxx 
// 1. FILES: All the files must be in directory in which you compile
// 2. COMMAND LINE: g++ (or gxx) 92ab2.cpp 
//--------------------------------------------------------------------
#include <iomanip.h>
#include <string>

struct ListNode {
     int info; 
     ListNode * prev; 
     ListNode * next; 
     ListNode(int val, ListNode *prevPtr, ListNode *nextPtr) // constructor
         : info(val), prev(prevPtr), next(nextPtr) { } 
}; 


ListNode *Location(ListNode *List, int Key) {
//precond: List points to a doubly linked list that contains no duplicate values
  ListNode *left = List->prev;

  return NULL;
}


void MoveToFront(ListNode *&List, int Key) {
// precondition: List represents the list of integers i1 i2 . . . in   
//               and List contains no duplicate values. 
//postcondition: If there exists an ik, 1 <= k <= n, such that ik = Key, then 
//     List represents the list of integers  iki1 . . . ik - 1ik + 1 . . . in.  
//     Otherwise,  List remains i1 i2 . . . in 


}


void testLocation(void);
void testMoveToFront(void);
void initList(ListNode *&); 
void Print(ListNode *, const string &);
void pause(void);
void cls(void);

int main() {
    string title("1992 AB Exam: Question 2");
    cls(); 
    cout << setw(39 + title.length()/2) << title.c_str() << "\n\n";
    testLocation();
    testMoveToFront();
    return 0;
}
/////////////////////////////////////////////
void testLocation(void) {
    ListNode *List, *L;
    initList(List); 
    cout << "Testing Location:\n\n";
    Print(List, "List");
    L = Location(List, 5);    
    cout << "\nAfter statement: L = Location(List, 5), L->info = ";
    if ( L == NULL )  {
       cerr << "\nL->info can't be accessed because Location returned NULL.\n"; 
       pause();
       return;
     }  
    cout << L->info << endl;
    L = Location(List, -2);    
    cout << "After statement: L = Location(List, -2), L->info = "
         << L->info << endl;    
    L = Location(List, 8);    
    cout << "After statement: L = Location(List, 8), L->info = "
         << L->info << endl;
    L = Location(List, -77);    
    cout << "After statement: L = Location(List, -77), L "
         << ( L == NULL ? "= NULL" : "!= NULL" ) << endl;    
    pause();               
}

void testMoveToFront(void) {
    ListNode *List, *List2;
    initList(List); 
    cls();
    cout << "Testing MoveToFront:\n\n";

    Print(List, "List"); MoveToFront(List, -88);
    cout << "After MoveToFront(List, -88):\n"; 
    Print(List, "List"); cout << endl << endl;

    Print(List, "List"); MoveToFront(List, 5);
    cout << "After MoveToFront(List, 5):\n"; 
    Print(List, "List"); cout << endl << endl;
    
    initList(List2);  
    Print(List2, "List2"); MoveToFront(List2, 8);
    cout << "After MoveToFront(List2, 8):\n"; 
    Print(List2, "List2"); cout << endl << endl;
    
    Print(List2, "List2"); MoveToFront(List2, -2);
    cout << "After MoveToFront(List2, -2):\n"; 
    Print(List2, "List2"); cout << endl << endl;                   
    pause();
}

void initList(ListNode *&L) {
   L = new ListNode(8, NULL, 
          new ListNode(-1, NULL, 
              new ListNode(5, NULL,
                 new ListNode(-2, NULL, NULL))));
   for (ListNode *p = L; p->next != NULL; p = p->next)
      p->next->prev = p;     
}

void Print(ListNode * list, const string &Lst) {
   cout << Lst << "--> ";
    while (list != NULL) {
       cout << " " << list->info 
            << (list->next != NULL ? " <--> " : "--> ");
       list = list->next; 
    }
    cout << "NULL" << endl;
}

void pause(void) {
  cout << "\nPress <ENTER>...";
  cin.ignore(10, '\n');
}

void cls(void) {
  for (int k = 1; k <= 55; k++)
    cout << '\n';
}