// Simple application of List ADT and Ordered List for Integers
// following an imperative style of programming
// File:    list-app0.cc
// Author:  Henry M. Walker
// Date:    May 29, 1998

#define NIL 0
#include <iostream.h>

// list node
struct ListNode {
     int data;
     ListNode *next;
     };
    
// list operation prototypes
void insert (ListNode **front, int item);  
    /* pre:  the list has been initialized
      post:  the specified item is placed at the front of the list  */

void insert_ordered (ListNode **front, int item);
    /* pre:  the list has been initialized and is ordered
      post:  the specified item is inserted on the list to retain ordering */

bool isin (ListNode *front, int item);
    /* pre:  the list has been initialized
      post:  function returns TRUE if item is in list and FALSE otherwise */

void print (ListNode *front);
    /* pre:  the list has been initialized
      post:  a title is printed, followed by the items from front to back */

void print_reverse (ListNode *front);
    /* pre:  the list has been initialized
      post:  a title is printed, followed by the items from back to front */

void count (ListNode *front);
    /* pre:  the list has been initialized
      post:  the items in the list are counted and printed */

// helper operation prototypes
void printData (ListNode *front);
    /* helper function for printing data */
void printReverse (ListNode *front);
    /* helper function for printing data in reverse data*/
int countNode (ListNode *front);
    /* helper function for counting nodes on a list */

// main, menu-drive program
int main () {
    char ch, choice;
    int i;
    ListNode * listin = NIL; // pointer to first node (inialized to NIL)
    ListNode * olistin= NIL; // pointer to first node (list will be ordered)
 

    cout << "program to test List ADT" << endl;
    
    do {
        cout << endl << "options" << endl;
        cout << "   a - search for item on integer list"  << endl;
        cout << "   c - search for item on ordered integer list" << endl;

        cout << "   e - count items on integer list"  << endl;
        cout << "   g - count items on ordered integer list"  << endl;

        cout << "   i - insert integer into integer list"  << endl;
        cout << "   k - insert integer into ordered integer list"  << endl;

        cout << "   n - print integer list in order" << endl;
        cout << "   p - print ordered integer list in order" << endl;
        
        cout << "   r - print integer list from back to front" << endl;
        cout << "   t - print ordered integer list from back to front" << endl;

        cout << "   x - exit" << endl;

        cout << "   enter choice: ";
        cin >> choice;
        switch (choice) {
 	   case 'a': cout << "enter integer for search: ";
                     cin >> i;
                     if (isin(listin, i))
                        {cout << "integer found in list" << endl;}
                        else {cout << "integer not found in list" << endl;}
                     break;          

 	   case 'c': cout << "enter integer for search: ";
                     cin >> i;
                     if (isin(olistin, i))
                        {cout << "integer found in list" << endl;}
                        else {cout << "integer not found in list" << endl;}
                     break;          
          
           case 'e': count(listin); break;

           case 'g': count(olistin); break;

	   case 'i': cout << "enter integer to be inserted: ";
                     cin >> i;
                     insert(&listin, i);
                     break;

	   case 'k': cout << "enter integer to be inserted: ";
                     cin >> i;
                     insert_ordered(&olistin, i);
                     break;

           case 'n': print(listin); break;

           case 'p': print(olistin); break;


	   case 'r': print_reverse(listin); break;

	   case 't': print_reverse(olistin); break;

           case 'x':  cout << "program terminated" << endl; break;
           default:  cout << "invalid option" << endl;
           }
    }
    while (choice != 'x');
    

} /* main */


// operation implementation section
void insert (ListNode **front, int item)
    /* pre:  the list has been initialized
      post:  the specified item is placed at the front of the list  */
{  ListNode *temp = new ListNode;
   temp->data=item;
   temp->next=*front;
   *front = temp;
}

void insert_ordered (ListNode **front, int item)
    /* pre:  the list has been initialized
      post:  the specified item is placed at the front of the list  */
{ if ((*front == NIL) || (item < (*front)->data))
     { ListNode *temp = new ListNode;
       temp->data=item;
       temp->next=*front;
       *front = temp;
     } else {insert_ordered (&((*front)->next), item);}
}

bool isin (ListNode *front, int item)
    /* pre:  the list has been initialized
      post:  function returns TRUE if item is in list and FALSE otherwise */
{   ListNode *temp = front;
    while (temp) {
       if (temp->data == item)
          {return (true);}
          else {temp = temp->next;}
    }
    return (false);
}

void print (ListNode *front)
    /* pre:  the list has been initialized
      post:  a title is printed, followed by the items from front to back */
{   cout << "The items on the list, from front to back, are:" << endl;
    printData(front);
    cout << "End of list" << endl;
}

void printData (ListNode *front)
/* helping function to recursively print the nodes in the list */
{   if (front != NIL) {
        cout << front->data << endl;
        printData (front->next);}
}

void print_reverse (ListNode *front)
    /* pre:  the list has been initialized
      post:  a title is printed, followed by the items from back to front */
{   cout << "The items on the list, from back to front, are:" << endl;
    printReverse(front);
    cout << "End of list" << endl;
}

void printReverse (ListNode *front)
/* helping function to recursively print the nodes in the list backwards */
{   if (front != NIL) {
        printReverse (front->next);
        cout << front->data << endl;}
}

void count (ListNode *front)
    /* pre:  the list has been initialized
      post:  the items in the list are counted and printed */
{   cout << "The number of nodes in the list is " << countNode (front) << endl;
}


int countNode (ListNode *front)
/* helping function to recursively count the nodes in the list */
{   if (front == NIL)
        return (0);
        else return (1 + countNode(front->next));
}