/*
        Programmer:  Christopher S. Dixon
        Prof:  Dr. Zizhong Wang
        Procedure:  This program allows the user to input, delete, print, sort
		    and find numbers in a list that is created by the user.
        Compile(in linux environment): g++ clemsoncode1.cpp
        Execute(in linux environment): ./a.out
*/

#include <iostream>

using namespace std;

const int MAX=50;

class List
{ 
	int length;
	int data[MAX];
	void BinSearch ( int item, bool& found, int& position) const;

public:
	List ( ) // empty list
	{ 	length = 0; 	}
	int Length ( ) const
	{	 return length;	 }
	bool IsFull ( ) const
	{ 	return ( length == MAX );	 }
	bool IsEmpty ( ) const
	{ 	return ( length == 0 );	 }
	void Print ( ) const     // as an array
	{ 	for ( int k=0; k<length; k++ )
			cout << data[k] << ' ';
			cout << endl;
	}	
	void Insert ( int item )
	{ 	data[ length ] = item;
		length ++;
	}
	void Delete ( int item )
	{
		bool found;
		int position;
		BinSearch( item, found, position );
		if (!found)
			cout << "Error.  No " << item << " in the list.\n";
		else
			{ for (int i=position; i<length; i++)
				data[i] = data[i+1];
				//shift data to the left
				cout << item << " is deleted from the list.\n";
				length --;
			}
	}
	bool IsPresent ( int item ) const
	{
		bool done = false;
		for ( int k=0; k<length && ! done; k++ )
		if ( data[k] == item )
			done = true;
		return done;
	}
	void SelSort ( );
};

// implementation
void List :: SelSort ( )
{	 int temp; // dummy for swapping
	int passCount;
	int minIndex;
	// total (length - 1) passes
	for ( passCount=0; passCount<length-1; passCount ++ )
	{ 	// search the smallest from present location
		minIndex = passCount;
		// compare from next item
		for ( int k=passCount+1; k<length; k++ )
		{ if ( data[minIndex] > data[k] )
			minIndex = k;
		}
		// find the minIndex, then swap it with the starting index
		temp = data[minIndex];
		data[minIndex] = data[passCount];
		data[passCount] = temp;
	}
}

void List :: BinSearch ( int item, bool& found, int& position )const
{ 
	int first = 0;
	int last = length - 1;
	int middle;

	found = false;
	while ( last >=first && !found )
	{	middle = ( first + last ) / 2;
		if ( item < data[middle] ) // located in the first half
			last = middle - 1;
		else if ( item > data[middle] ) // located in the last half
			first = middle + 1;
		else found = true;
	} // found or not find (last < first)
	if ( found ) position = middle;
}

// function prototypes
void menu ();
void process ( char, List& );

int main()
{
	List myList; // empty List
	char ch;

	cout << "******************************"<< endl; //30
	cout << "*   Thank You For Using My   *"<< endl;
	cout << "*     Number Input List      *"<< endl;
	cout << "******************************\n" << endl;

	menu(); // reads the first entry
	cin >> ch;
	while ( tolower(ch) != 'q' )
	{
		process(ch, myList);
		menu(); // read next entry
		cin >> ch;
	}
	getchar();

	cout << "******************************"<< endl; //30
        cout << "*   Thanks Again For Using   *"<< endl;
        cout << "*       My Number Input      *"<< endl;
        cout << "*   List.  Have A Nice Day   *"<< endl;
        cout << "******************************\n" << endl;


	return 0;
}

void menu ()
{
	cout << "i insert an integer\n";
	cout << "f find an integer\n";
	cout << "p print the list\n";
	cout << "d delete an integer\n";
	cout << "s sort the list\n";
	cout << "q quit the operation\n";
	cout << "\nPlease Make a Selection: ";
}

void process ( char ch, List& myList )
{
	int number;
	switch ( tolower(ch) )
	{	 case 'i':
			cout <<"Input a integer: ";
			cin >> number;
			myList.Insert(number);
			// for debug
			cout << "\n\nThe list is: ";
			myList.Print();
			cout << "\n\nType any key to continue ..\n\n\n\n";
			getchar();
			break;
		case 's':
			myList.SelSort();
			// for debug
			cout << "\n\nThe list is: ";
			myList.Print();
			cout << "\n\nType any key to continue ..\n\n\n\n";
			getchar();
			break;
		case 'p':
			cout << "\n\nThe list is: ";
			myList.Print();
			cout << "\n\nType any key to continue ..\n\n\n\n";
			getchar();
			break;
		case 'd':
			cout << "Input an integer to be deleted: ";
			cin >> number;
			myList.Delete(number);
			// for debug
			cout << "\n\nThe list is: ";
			myList.Print();
			cout << "\n\nType any key to continue ..\n\n\n\n";
			getchar();
			break;
		case 'f':
			cout << "Input an item to be found: ";
			cin >> number;
			if ( myList.IsPresent(number) )
				cout << "\n\n" << number << " is in the list.\n";
			else
				cout << "\n\n" << number << " isn't in the list.\n";
			cout << "\n\nType any key to continue ..\n\n\n\n";
			getchar();
			break;
		default:
			cout << "\nInvalid input.\n" ;
			cout << "\n\nType any key to continue ..\n\n\n\n";
			getchar();
	}
	return;
}