// Ue6Aufgabe2.cpp : Defines the entry point for the console application.
//
/**
@author Wolfgang Miller 612437
@author Nassim Mouafi 626387
**/

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <fstream>


int *randomArray(int size);
void selectionSort(int *unsortiert, int size);
int getPivot(int *array, int l, int r);
void exchange(int *array, int p, int q);
int binarySearch(int *array, int size, int value, int *compares);
void insert(int value);
int find(int value, int *compares);





/**
Main - Funktion
**/




/**
int *randomArray(int size)

erstellt ein Array mit Zufallszahlen

@param size

**/
int *randomArray(int size){


	int *reihung = new int [size];

	int zufall;

	for (int i=0; i < size; i++){

		zufall = (int)((float)rand() / (float)RAND_MAX * 16383.0f);
		reihung[i] = zufall;
	}

	return reihung;

}

/**
void sort(int *unsortiert, int groesse)

Selection Sort
Sortiert die Werte des Arrays das durch den Zeiger *unsortiert referenziert wird.

@param int *unsortiert
@param int groesse


**/

void selectionSort(int *unsortiert, int groesse){


	bool eintritt;

	while(groesse > 0){

		eintritt = true;
		int vergleich;

		for (int i = 0; i < groesse; i++)
		{


			if(eintritt)
			{
				vergleich = i;
				eintritt = false;
			}

			if (unsortiert[vergleich] < unsortiert[i])
			{
				vergleich = i;
			}			
		}
		exchange(unsortiert, vergleich, groesse-1);

		groesse--;
		eintritt = true;		
	}
	return;

}
/**
void exchange(int *intArray, int p, int q )

Tauscht Indexwerte p und q auf dem int Array auf das der Zeiger *intArray zeigt.

@param int *intArray 
@param int p
@param int q

**/

void exchange(int *intArray, int p, int q ){

	int zwischenspeicher;

	zwischenspeicher = intArray[p];
	intArray[p] = intArray[q];
	intArray[q] = zwischenspeicher;

	return;
}

/**

int binarySearch(int *array, int size, int value, int *compares)

Sucht einen Wert auf dem übergebenen Array.

@param int *array
@param int size
@param int value
@param int *compares

**/

int binarySearch(int *array, int size, int value, int *compares)
{

	int mitte = size/2;
	(*compares)++;

	if (array[mitte] == value)
	{
		return 1;
	}

	if (size == 1)
	{
		return 0;
	}

	(*compares)++;
	if (array[mitte] > value)
	{

		size = mitte;
		return binarySearch(array, size, value, compares);
	}
	else
	{
		return binarySearch(&array[mitte+1], size - mitte, value, compares);
	}
};


/**
Klasse mit Nodes für die Skiplist

@param value 
@param h 
@param head 
**/

class SkiplistNode
{
public:
	
	vector<SkiplistNode*> next;

	
	int value;

	
	SkiplistNode(int value, int h, vector<SkiplistNode*> &head)
	{
		this->value = value;
		for(int i=0; i<h; i++)
		{
			next.push_back(head[i]);
			head[i] = this;
		}
	}
};

class Skiplist
{
public:
	
	vector<SkiplistNode*> head;

	/**
	Ein neues Element wird in die Skipliste eingefügt
	 
	 @param value 
	 @param h_in  
	
	**/
	void insert(int value, int h_in)
	{
		int h = 1;
		
		if (h_in == 0) 
		{
			while (rand() < (RAND_MAX/2))
				h++;
		}
		else 
		{
			while ((rand()<(RAND_MAX/2)) && (h < h_in))
				h++;	    
		}

		
		while (head.size() < h)
			head.push_back(NULL);

		
		new SkiplistNode(value,h,head);
	}


	/**
	 Sucht in der Liste nach dem Element mit dem Wert value

	 @param value 
	 @param *compares 	  
	**/ 
	int find(int value, int *compares)
	{
		
		*compares=0;

		
		vector<SkiplistNode *> *p_akt = &head;	

		int max_size = head.size()-1;	

		while (max_size >= 0)
		{
			
			if ((*p_akt)[max_size] == NULL)
				max_size--;
			
			else
			{
				*compares = *compares + 1;
			
				if ((*p_akt)[max_size]->value < value)
					p_akt = &((*p_akt)[max_size]->next);
				
				else
				{		    
					*compares = *compares + 1;

					
					if ((*p_akt)[max_size]->value == value)
						return 1;

						max_size--;
				}
			}
		}

		return 0;
	}

	~Skiplist()
	{
		SkiplistNode *tmp1 = head[0];

		while (tmp1 != NULL)
		{
			SkiplistNode *tmp2 = tmp1;
			tmp1 = tmp1->next[0];
			delete tmp2;
		}
	}
};

int main(int argc, char* argv[])
{


	int nMin = -1;
	int nMax = -1;
	int mAnzZufallsz = -1;

	if(argc != 4 ||((nMin && nMax && mAnzZufallsz) > 1 || atoi(argv[1]) > atoi(argv[2])))
	{
		std::cout << "Bitte Zahlen >0 übergeben!" << std::endl;
		return 0;

	}
	else{ 

		nMin = atoi(argv[1]);
		nMax = atoi(argv[2]);
		mAnzZufallsz = atoi(argv[3]);
	}

	for (int i = nMin; i <= nMax;i++)
	{	


		int size = i;
		int compares = 0;


		int *reihung = randomArray(size);


		/*	for (int i = 0; i< size; i++)
		{
		std::cout << "Unsortiert: " <<reihung[i]<<std::endl;

		}*/





		selectionSort(reihung, size);


		/*	for (int i = 0; i< size; i++)
		{
		std::cout << "Sortiert: " <<reihung[i]<<std::endl;
		}*/


		for (int i = 0; i < mAnzZufallsz; i++)
		{
			int value =  (int)((float)rand() / (float)RAND_MAX * 16383.0f);

			int peter = binarySearch(reihung, size, value, &compares);

			std::cout << std::endl;

			std::cout << "Gesucht: " << value << std::endl;

			std::cout << "n: " <<size << std::endl; 

			std::cout << "Gefunden: " << peter  << " Vergleiche: " << compares << std::endl;

			compares = 0;

		}

		std::cout << std::endl;

	}
	std::cout << std::endl;


	//system("Pause");
	return 0;

}