/************************************************************************/
/* Programmer   : Greg Ippolto                                          */
/* Assignment   : Doubly Linked List Implementation                     */
/* Filed As     : hw2.C                                             	*/
/* Files Used   : NONE                                                  */
/* Language     : C++                                                   */
/*                                                                      */
/* Description  : Homework assignment                                   */
/*                                                                      */
/************************************************************************/

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <sys/stat.h>
#include <stdlib.h>
using namespace std;

#ifndef NILL
#define NILL 0
#endif

typedef struct node {
   int key;
   struct node *next;
   struct node *prev;
} Node;

//  Doubly Linked List Routines

void DLLInsert(Node *, Node *);
void DLLDelete(Node *,int);
Node *DLLSearch(Node *,int);
Node *DLLMax(Node *);
Node *DLLMin(Node *);
Node *DLLSuccessor(Node *,int);
Node *DLLPredecessor(Node *,int);
void DLLPrintNode(Node *,Node *);
void DLLPrintList(Node *);

void DLLPrintNode(Node *start, Node *x)
{ 

// Given a pointer to a node print it

   // Check if node or sentinel node
   if(x == start) cout << "NILL" << endl; 
   else cout << x->key << endl;
}

void DLLPrintList(Node *start)
{
   Node *x;

   if(start->next == start)  // sentinel - no list
	cout << "( )" << endl;
   else
   {
	cout << "(";
   	x = start->next;
   	while(x != start)
   	{
   		cout << x->key << " ";
		x=x->next;
   	}
	cout << ")\n";
   }
}

Node *DLLSearch(Node *start, int key_val)
{
   Node *x;
   int position = 0;

   if(start->next == start)  // sentinel - no list
   {
        cout << "ERROR: NILL list - List is empty\n";
        cout << "There is no " << key_val << " in the List!\n";
   	return start;
   }
   else
   {
   	x = start->next;
   	while(x != start)
   	{
	   position++;

	   if(x->key == key_val)
	   {
		cout << key_val << " is in position " << position << endl;
   		return x;
	   }
	   x=x->next;
   	}
	cout << "There is no " << key_val << " in the List!\n";
        return NILL;
   }
}

Node *DLLMax(Node *start)
{
   Node *x, *p_max;
   int max, i, position;

   position = i = 0;

   if(start->next == start)  // sentinel - no list
   {
	cout << " NILL List" << endl;
   	return start;
   }
   else
   {
   	x = start->next;
	max = x->key;
   	while(x != start)
   	{
 		i++;
		if(x->key >= max) 
		{
		   max = x->key;
		   p_max = x;
		   position = i;
		}
		x=x->next;
   	}
	cout << max << " in position " << position << endl;
   	return p_max;
   }
}

Node *DLLMin(Node *start)
{
   Node *x, *p_min;
   int min, i, position;

   position = i = 0;

   if(start->next == start)  // sentinel - no list
   {
	cout << " NILL List " << endl;
   	return start;
   }
   else
   {
   	x = start->next;
	min = x->key;
	position = 1;
   	while(x != start)
   	{
 		i++;
		if(x->key <= min) 
		{
		   min = x->key;
		   p_min = x;
		   position = i;
		}
		x=x->next;
   	}
	cout << min << " in position " << position << endl;
   	return p_min;
   }
}

void DLLInsert(Node *start, Node *x)
{
   Node *p1,  // pointer to predecessor of x
        *p2;  // pointer to successor of x

   if(start->next == start)  // sentinel - no list
   {
   	start->next = x;
	start->prev = x;
	x->next = start;
	x->prev = start;
	return;
   }
   else
   {
   	p2 = start->next;	// start

   	// p2 is successor to x. Past insertion point

   	while(p2 != start && x->key > p2->key)  // search
   	{
		p2 = p2->next;
   	}			// found
	
   	x->prev = p2->prev;	// insert
   	p1 = p2->prev;
   	x->next = p1->next;
   	p2->prev = x; 
	p1->next = x;
   }
}

void DLLDelete(Node *start, int key_val)
{
   Node *p1,  // pointer to predecessor of x
        *p2,  // pointer to successor of x
        *p;   // pointer to node to be deleted

   if(start->next == start)  // sentinel - no list
   {			     // nothing to delete.
    	cout << "List is empty\n";
	cout << "There is no " << key_val << " in the List!\n";
	return;
   }
   else
   {
   	p = start->next;	// start

   	while(p != start)  // search
   	{
   	   if(p->key == key_val) 
	   {
   		p1 = p->prev;	// found - delete
   		p2 = p->next;
   		p1->next = p2;
   		p2->prev = p1; 

 		delete p;
		return;
	   }
	   p = p->next;
   	}			
	
   	if(p == start) 	// not found
	{
		cout << "There is no " << key_val << " in the List!\n";
		return;
	}

   }
}

Node *DLLSuccessor(Node *start, int key_val)
{
   Node *p;  // pointer to successor of x
   int position = 0;
   int found = 0;

   if(start->next == start)  // sentinel - no list
   {
    	cout << "List is empty\n";
	return NILL;
   }
   else
   {
   	p = start->next;

   	while(p != start) // if p == start then sentinel
   	{
	   position++;

   	   if(p->key == key_val)
	   {
	      found = 1;
	   }
   	   if(found && p->key > key_val)
	   {
 	      if(p->next == start)
	      {
	         cout << "Successor of " << key_val << " is NILL"; 
	         cout << " in position 0!\n";
   	         return p;
	      }
	      else
	      {
	         cout << "Successor of " << key_val << " is " << p->key; 
	         cout << " in position " << position << "!\n";
   	         return p;
	      }
	   }
       	   p = p->next;
   	}

	if(found)
	{
	   cout << "Successor of " << key_val << " is NILL"; 
	   cout << " in position 0!\n";
   	   return NILL;
	}
    	else
	{
	   cout << "There is no " << key_val << " in the list\n";
   	   return NILL;
	}
   }

}

Node *DLLPredecessor(Node *start, int key_val)
{
   Node *p;  // pointer to predecessor of x
   int position = 0;

   if(start->next == start)  // sentinel - no list
   {
    	cout << "List is empty\n";
	return NILL;
   }
   else
   {
   	p = start->next;

   	while(p != start) // if p == start then sentinel
   	{

   	   if(p->key == key_val)
	   {
 	      if(position)
	      {
       	         p = p->prev;
	         cout << "Predecessor of " << key_val << " is " << p->key; 
	         cout << " in position " << position << "!\n";
   	         return p;
	      }
	      else
	      {
       	         p = p->prev;
	         cout << "Predecessor of " << key_val << " is NILL"; 
	         cout << " in position " << position << "!\n";
   	         return p;
	      }
	   }
	   position++;
       	   p = p->next;
   	}

	cout << "There is no " << key_val << " in the list\n";
   	return NILL;
   }

}

main()
{
   Node *start, sentinel, *x, *dummy;
   char choice;
   int lnum;

   start = &sentinel;

   start->next = &sentinel;
   start->prev = &sentinel;

ASK: ;
   cout << "\nDoubly Linked List Testing Program MENU\n";

   cout << "1-Insert, 2-Delete, 3-Search, 4-Max, 5-Min, 6-Successor,";
   cout << " 7-Predecessor, 8-Print List, 9-Quit\n";

   cout << "Enter your choice:";

   cin >> choice;

   switch(choice) {
	case '1':
	   cout << " ==>Insert:";
	   cin >> lnum;
	   x = new Node;
	   if(!x){ cout << "Allocation error\n"; exit(1); }
	   x->key = lnum;
	   DLLInsert(start, x);
	   break;
	case '2':
	   cout << " ==>Delete:";
	   cin >> lnum;
	   DLLDelete(start, lnum);
	   break;
	case '3':
	   cout << " ==>Search:";
	   cin >> lnum;
	   dummy = DLLSearch(start, lnum);
	   break;
	case '4':
	   cout << " ==>Maximum ";
	   dummy = DLLMax(start);
	   break;
	case '5':
	   cout << " ==>Minimum ";
	   dummy = DLLMin(start);
	   break;
	case '6':
	   cout << " ==>Successor of:";
	   cin >> lnum;
	   dummy = DLLSuccessor(start, lnum);
	   break;
	case '7':
	   cout << " ==>Predecessor of:";
	   cin >> lnum;
	   dummy = DLLPredecessor(start, lnum);
	   break;
	case '8':
	   cout << " ==> ";
	   DLLPrintList(start);
	   break;
	case '9':
	   cout << " Quit \n";
   	   return 0;
	default:
   	   if(choice < '1' || choice > '9')
   	   {
	      cout << "Incorrect entry made. Enter a value between 1 and 9\n";
   	   }
	   break;
   }
   goto ASK;

}