#include <cstdlib>
#include <iostream>

using namespace std;

struct LinkNode
{
       long TempNum;
       LinkNode *next;
       LinkNode *previous;
       
       LinkNode(void)
       {
                     TempNum=0;
                     next=previous=NULL;
       }
};

struct DoublyLink
       
       {
                 LinkNode *head;
                 LinkNode *tail;
                 LinkNode *current;
                 unsigned int countList;

DoublyLink(void)//constructor
                 {
                  head=new LinkNode;
                  tail=current=head;
                  countList=1;
                  }
                  
~DoublyLink(void)//distructor
  {
                  LinkNode *temp=head;
                  current=head;
                  while(current!=NULL)
                  {
                       current=current->next;
                       delete temp;
                       temp = current;
                  }
  }
int operator[](int index)//index of list list
{
                      if(index >=countList)
                      index%=countList;
                      LinkNode *temp = head;
                      for(int j=0; j<index;j++)
                      temp=temp->next;
                      current=temp;
                      return temp->TempNum;
}
void forward(void)
                  {
                      if(current->next!=NULL)
                      current=current->next;
                  }
                  
void Backward(void)
{
       if(current->previous !=NULL)
        current=current->previous;
}
void insertNode(int TempNum)
{
     tail->next=new LinkNode;
     tail->next->previous=tail;
     tail=tail->next;
     tail->TempNum = TempNum;
     countList++;
}
void display(void)
{
     LinkNode *temp=head;
     current=head;
     while(current!=NULL)
     {
     current=current->next;
                         cout<<temp->TempNum<<"\n";
                         temp=current;
     }
}
                  

};
//----function prototypes
void selection_sort(double s_array[], int Array_length, int Sort_Order=0);
int binary_search(double bsSortedArray[], int bsArrayLength, int bsKey);


int main()
{
	//----Declare variables
	double DataList[50]; //--array that can hold a maximum of 50 data
	int array_max=50; //--Maximum Elements 'DataArray[]' can store
	int DataListTotal=0; //--Current Total of elemets entered by user in the 'DataArray[]'
	int DataSorted=0; //DataSorted=0:Data is not sorted, DataSorted=1:Data sorted Assending, DataSorted=2:Data sorted Decending

    //--Temporary Variables
	char MenuOptionA; //--stores the options choosen in the menu
	char MenuOptionB;
	int TempNum=0;
	int TempIndex=0; //--to store search results
	int TempCounterA;

    while(true)            
	{
                           
      		//--display main menu
		//_________________________
		cout<<"\n\n";
		cout<<"    Main Menu\n";
		cout<<"    ---------\n";
		cout<<" 1: Insert new element to the list\n";
		cout<<" 2: Display Data\n";
		cout<<" 3: Sort Data\n";
		cout<<" 4: Search Data\n";
		cout<<" 5: Delete an element from the list\n";
		cout<<" 6: Add new element\n";
		cout<<" 7: Modify an element\n";
		cout<<" 8: Exit\n\n";
		cout<<"      Choose an option [1-8] = ";
		cin>>MenuOptionA;
	    
	  	  	//ENTER DATA  
	  	//_________________________
		
        switch(MenuOptionA)
		{
	
		case '1':
			//--display data entry menu
			cout<<"\n\n";
			cout<<"    Data Entry Menu\n";
			cout<<"    ---------------\n";
			cout<<" How many numbers would you like to enter? ";
			cin>>TempNum;
			
			if (TempNum<=0) //--dont accept zero and negative numbers
			{
				cout<<"\n   Invalid Number!\n";
				break;
			}
			else if(TempNum+DataListTotal>array_max) //--check if there is room in array for storage
			{
				cout<<"\n   Cannot store more then "<<array_max<<" elements in array!\n";
				break;
			}

			//--enter data
			
			cout<<"\n";
			cout<<" 1: Insert at the back of the list\n";
			cout<<" 2: Insert at the end of the list\n\n";
			cout<<"     Choose an option [1-2] = ";
			cin>>MenuOptionB;

			if (MenuOptionB=='1')
			{
				selection_sort(DataList,DataListTotal,0); //--send for sorting in Ascending order
				DataSorted=1;//--data is now sorted in Ascending order
			}
			else if (MenuOptionB=='2')
			{
				selection_sort(DataList,DataListTotal,1); //--send for sorting in Descending order
				DataSorted=2;//--data is now sorted in Descending order
			}
			else
				cout<<"\n   Invalid Selection!\n";
				
			for(TempCounterA=0;TempCounterA<TempNum;TempCounterA++)
			{
				DataListTotal++;
				cout<<"ArrayIndex["<<DataListTotal-1<<"], Enter a number: ";
				cin>>DataList[DataListTotal-1];
			}
			cout<<"\n\nNumber of Data entered = "<<TempCounterA<<",\n";
			cout<<"Total Data in the list = "<<DataListTotal<<",\n";

			//--exit
			DataSorted=0;//--data is no longer sorted
			break;
			
			
        
		//VIEW DATA
		
		case '2':
			//--check if there is data to view
			if (DataListTotal<=0)
			{
				cout<<"\n   No Data in the list to view!\n";
				break; //--exit
			}

			//--display data view menu
			cout<<"\n\n";
			cout<<"    Data Display Menu\n";
			cout<<"    ---------------\n";
			cout<<"\n\n";
			
			
			cout<<"    ---------------\n";
			cout<<" 1: Display data from LAST-FIRST\n";
			cout<<" 2: Display data from FIRST-LAST\n\n";
			cout<<"      Choose an option [1-2] ";
			cin>>MenuOptionB;
			
				cout<<"\n";
				for(TempCounterA=0;TempCounterA<DataListTotal;TempCounterA++)
				{
					cout<<"ListIndex["<<TempCounterA<<"] = "<<DataList[TempCounterA]<<"\n";
				}
				cout<<"\nTotal "<<DataListTotal<<" elements displayed\n";

				//--exit
				break;
			
   
		//----SORT DATA
		
		
		case '3':
			//--check if there is enough data for sorting
			if (DataListTotal<=1)
			{
				cout<<"\n   Not enough Data in the list sorting!\n";
				break; //--exit
			}

			//--display data sort menu
			cout<<"\n\n";
			cout<<"    Data Sort Menu\n";
			cout<<"    ---------------\n";
			cout<<" 1: Sort Ascending\n";
			cout<<" 2: Sort Descending\n\n";
			cout<<"      Choose an option [1-2] ";
			cin>>MenuOptionB;

			if (MenuOptionB=='1')
			{
				selection_sort(DataList,DataListTotal,0); //--send for sorting in Ascending order
				DataSorted=1;//--data is now sorted in Ascending order
			}
			else if (MenuOptionB=='2')
			{
				selection_sort(DataList,DataListTotal,1); //--send for sorting in Descending order
				DataSorted=2;//--data is now sorted in Descending order
			}
			else
				cout<<"\n   Invalid Selection!\n";

			//--view the data after being sorted
			cout<<"\n\n";
			cout<<"    Viewing Sorted Data\n";
			cout<<"\n";
			for(TempCounterA=0;TempCounterA<DataListTotal;TempCounterA++)
			{
				cout<<"DoublyLinkListIndex["<<TempCounterA<<"] = "<<DataList[TempCounterA]<<"\n";
			}
			cout<<"\nTotal "<<DataListTotal<<" elements displayed\n";

			
			//--exit
			break;


		//----SEARCH DATA
		
		
		case '4':
			//--check if there is data for searching
			if (DataListTotal<=0)
			{
				cout<<"\n   No Data in the list to search!\n";
				break; //--exit
			}

			//----SORTING
			if(DataSorted!=1)
			{
				cout<<"\n   Data not sorted, Sorting Data now!\n";
				selection_sort(DataList,DataListTotal,0); //--send for sorting in Ascending order
				DataSorted=1;//--data is now sorted in Ascending order
			}

			//--display data search menu
			cout<<"\n\n";
			cout<<"    Data Search Menu\n";
			cout<<"    ---------------\n";
			cout<<" Enter number to search? ";
			cin>>TempNum;

			//--call function for searching
			TempIndex=binary_search(DataList,DataListTotal,TempNum);

			if(TempIndex==-1)
			{
				cout<<"\n   Search Failed!, the number entered is not in the list.\n";
				break; //--exit
			}

			//--Data found
			cout<<"\n   Search Completed Successfully!\n";
			cout<<"\n    DoublyLinkListIndex="<<TempIndex<<", TempNum="<<DataList[TempIndex]<<",\n";
			break; //--exit


		//    REMOVE DATA
		
			
        case '5':
			//--check if there is data to remove
			if (DataListTotal<=0)
			{
				cout<<"\n   No Data in the list to remove!\n";
				break; //--exit
			}

			//--display data view menu
			cout<<"\n\n";
			cout<<"    Data Remove Menu\n";
			cout<<"    ---------------\n";
			cout<<" 1: Remove by TempNum\n";
			cout<<" 2: Remove by Index\n";
			cout<<" 3: Remove All\n";
			cout<<" 4: Back\n\n";
			cout<<"      Choose an option [1-4] ";
			cin>>MenuOptionB;


			//--REMOVE DATA BY TempNum
			
			
			
			if (MenuOptionB=='1')
			{


				// SORTING
				if(DataSorted!=1)
				{
					cout<<"\n   Data not sorted, Sorting Data now!\n";
					selection_sort(DataList,DataListTotal,0); //--send for sorting in Ascending order
					DataSorted=1;//--data is now sorted in Ascending order
				}

				cout<<"\n Enter number to search and remove? ";
				cin>>TempNum;
				
				//--call function for searching
				TempIndex=binary_search(DataList,DataListTotal,TempNum);

				if(TempIndex==-1)
				{
					cout<<"\n   TempNum not found in the list!\n";
					break; //--exit
				}

				//--remove that TempNum
				DataList[TempIndex]=0;
				cout<<"\n   Data Removed!! (TempNum=0)\n";			
				break;//--exit
			}

			//--REMOVE DATA BY REFERENCING ARRAY INDEX
		
            
            if (MenuOptionB=='2')
			{
				cout<<"\n Enter List Index TempNum to remove [0-"<<DataListTotal-1<<"] : ";
				cin>>TempNum;

				if(TempNum<0 || TempNum>DataListTotal-1)
				{
					cout<<"\n   Invalid List Index!\n";
					break; //--exit
				}

				//--remove that TempNum
				DataList[TempNum]=0;
				cout<<"\n   Data Removed!! (TempNum=0)\n";			
				break;//--exit

			}

             
			//--REMOVE ALL THE DATA
			
			
			if (MenuOptionB=='3')
			{

				//--remove all data
				for(TempCounterA=0;TempCounterA<DataListTotal;TempCounterA++)
				{
					DataList[TempCounterA]=0;
				}

				//--output
				cout<<"\n   All Data Removed!! (All TempNums=0)\n";			
				break;//--exit

			}

			
			//--back to main manu
			if (MenuOptionB=='4')
				break; //--exit


			//--invalid selection exit
			cout<<"\n   Invalid Selection!\n";
			break;
			
			
		
        case '6':
       	    cout<<"\n\n";
			cout<<"    Add new element to the list\n";
			cout<<"    ---------------\n";
			cout<<" 1: Add new element after the list\n";
			cout<<" 2: Add new element before the list\n";
			cout<<"      Choose an option [1-2] ";
			cin>>MenuOptionB;
            //
            //
            break;
   case '7':
        cout<<"\n\n";
        cout<<" Modify and element in the list\n";
        cout<<" ------------------------------\n";
        cout<<" Enter the element to be modified\n";
        cin>>TemNum;
        
        //
        break;
        
        
   case '8':
			//--end the program
			return 0;
			break;
		}


	}

	
	return 0;
	

}


//       Function For Binary search


int binary_search(double bsSortedArray[], int bsArrayLength, int bsKey)
{
	//--bsSortedArray[], array of sorted (ascending) TempNums.
	//--bsArrayLength, length of data in 'bsSortedArray[]'
	//--bsKey, TempNum to search for
	//----This fuction returns '-1' if TempNum was not found or the array Index if found
	int bsFirst, bsLast, bsMid, bsCounter; //--for calculation purpose

	//--check if there is data in array
	if(bsArrayLength<=0)
		return -1;  //--no data in array so exit

	//--initilize variables
	bsFirst=0;
	bsLast=bsArrayLength-1;
	bsCounter=0;

	//--do the searching   
	while (bsFirst <= bsLast) {
		bsCounter++; //--just a counter
		bsMid = (bsFirst + bsLast) / 2;  //--compute bsMid point.
		if (bsKey > bsSortedArray[bsMid]) 
			bsFirst = bsMid + 1;  //--repeat search in top half.
		else if (bsKey < bsSortedArray[bsMid]) 
			bsLast = bsMid - 1; //--repeat search in bottom half.
		else
			return bsMid;     //--found it. return position
	}
		return -1;    //--failed to find bsKey

}

//----Function For Sorting Data using Selection Sort

 
void selection_sort(double s_array[], int Array_length, int Sort_Order)
{
	//--sdArray[] contains reference to the array to sort
	//--sdArrayLength is the number of elements in 'sdArray[]'
	//--sdSortOrder=0 mean Sort Ascending order, sdSortOrder=1 mean Sort Descending order,
	int Temp_pass; //--used as temporary counters
	int Temp_A; //--used as temporary counters
	int small; //--stores the index of the smallest number
	double swap; //--used to store Calue m for swapping (should be same data type as array)
	
	//--check if there is at least 2 data in array
	if(Array_length<=1)
	{
		cout<<"\nThere is not enough Data in the list for sorting\n";
		return; //--exit
	}
	if(Sort_Order!=1) Sort_Order=0; //--can contain only 0 and 1

	//--display order of sorting used
	if(Sort_Order==0)
		cout<<"\nSorting "<<Array_length<<" elements in Ascending order\n";
	if(Sort_Order==1)
		cout<<"\nSorting "<<Array_length<<" elements in Descending order\n";


        	//--Do the sorting
    for (Temp_pass=0; Temp_pass<Array_length-1; Temp_pass++) {
        small = Temp_pass;  // assume this is smallest

        //--- Look over remaining elements to find smallest or largest depeding on sort order
        for (Temp_A=Temp_pass+1; Temp_A<Array_length; Temp_A++) {
            //if (sdArray[Temp_A] < sdArray[small])
            if ((s_array[Temp_A] < s_array[small] && Sort_Order==0) || (s_array[Temp_A] > s_array[small] && Sort_Order==1))
			{
                //--- Remember index for latter swap.
                small = Temp_A;
    }
        }
        
        //--- Swap smallest remaining element
        swap = s_array[Temp_pass];
        s_array[Temp_pass] = s_array[small];
        s_array[small] = swap;
    }
}