#include <iostream>
#include <vector>
#include <string>
#include <chrono>
#include <random>
#include <climits>
#include <cmath>
#include <algorithm>
using namespace std;

// Globale tellers, voor het gemak
int vergelijkingen;
int verwisselingen;

// Globale dingen voor het genereren van willekeurige getallen, voor het gemak
unsigned seed;
default_random_engine generator;
uniform_int_distribution<int> verdeling;

// Berekent de 2-log van n (afgerond naar beneden).
int log2 (int n) {
	if (n == 0) {
		return -1;
	}

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

	int l = 0;
	while (n > 1) {
		n >>= 1;
		l++;
	}

	return l;
}

// Print de inhoud van array A, voor posities i tot en met n.
void print_array (const vector<int> & A, const int & n, int i = 0) {
	cout << "[ ";
	for (; i < n; i++) {
		cout << A[i] << " ";
	}
	cout << "]" << endl;
}

// Formatteert een getal met een punt tussen elk drietal cijfers
string maak_leesbaar (int n) {
	string s = to_string(n % 1000);

	while (n >= 1000) {
		// plak er eventueel wat nullen tussen als het vorige getal te klein was
		if (n % 1000 < 100) {
			s = "0" + s;
		}
		if (n % 1000 < 10) {
			s = "0" + s;
		}

		n /= 1000;

		s = to_string(n % 1000) + "." + s;
	}

	return s;
}

// Kopieer de inhoud van array A naar array B
void kopieer (const vector<int> & A, vector<int> & B) {
	for (int i = 0; i < (int) A.size(); i++) {
		B[i] = A[i];
	}
}

// Vul array A van lengte n willekeurig met (al dan niet verschillende) getallen in het interval [1, n].
void vul_willekeurig (vector<int> & A, const int & n, const bool & verschillend) {
	if (verschillend) {
		// Willekeurige permutatie
		for (int i = 0; i < n; i++) {
			A[i] = i;
		}
		shuffle(A.begin(), A.end(), generator);
	} else {
		// Gewoon willekeurig
		uniform_int_distribution<int> verdeling(1, n);

		for (int i = 0; i < n; i++) {
			A[i] = verdeling(generator);
		}
	}
}

// Vul array A van lengte n oplopend met getallen 1 t/m n.
void vul_oplopend (vector<int> & A, const int & n) {
	for (int i = 0; i < n; i++) {
		A[i] = i + 1;
	}
}

// Vul array A van lengte n aflopend met getallen 1 t/m n.
void vul_aflopend (vector<int> & A, const int & n) {
	for (int i = 0; i < n; i++) {
		A[i] = n - i;
	}
}

// Gaat na of array A oplopend is gesorteerd.
bool is_gesorteerd (const vector<int> & A) {
	for (int i = 0; i < (int) A.size() - 1; i++) {
		if (A[i] > A[i + 1]) {
			return false;
		}
	}

	return true;
}

// Verwisselt de elementen A[i] en A[j].
void wissel (vector<int> & A, const int & i, const int & j) {
	int smurf = A[i];
	A[i] = A[j];
	A[j] = smurf;
}

// Implementatie van Shellsort (Hoofdstuk 7.5 van het dictaat)
// Sorteert array A met het gegeven (aflopende) rijtje stapgroottes
// Aangepast naar 0-indices
void shellsort (vector<int> & A, const vector<int> & stapgroottes) {
	int j, smurf;

	// Voor elke stapgrootte (in aflopende volgorde)
	for (int h : stapgroottes) {

		// h-sorteer A
		for (int i = h; i < (int) A.size(); i++) {
			smurf = A[i];
			j = i;

			// Schuif A[i] naar links tot de juiste plek
			while (j - h >= 0) {
				// Tel de vergelijking
				vergelijkingen++;
				if (smurf < A[j - h]) {
					// Tel de verwisseling
					verwisselingen++;
					A[j] = A[j - h];
					j -= h;
				} else {
					break;
				}
			}

			A[j] = smurf;
		}
	}
}

// Wrapper om experimenten te runnen.
// Sorteert een willekeurig gegenereerd rijtje van lengte N met de gegeven rijtjes stapgroottes (die de gegeven namen hebben), en herhaalt dit 'runs' keer.
// Spuwt aan het einde wat data uit.
void run (const int & N, const int & runs, const vector<vector<int>> & stapgroottes, const vector<string> & namen) {

	// Bepaal het aantal rijtjes stapgroottes voor initialisatie van de data-arrays.
	int aantal_rijtjes = (int) stapgroottes.size();
	// Controleer even dat dit overeenkomt met het aantal namen.
	if (aantal_rijtjes != (int) namen.size()) {
		cout << "Aantal rijtjes stapgroottes komt niet overeen met aantal namen." << endl;
		return;
	}

	// Declareer arrays A en B ter grootte N
	vector<int> A, B;
	A.resize(N);
	B.resize(N);

	// Declareer en initialiseer arrays voor het bijhouden van statistieken
	vector<int> min_vgl (aantal_rijtjes, INT_MAX);
	vector<int> max_vgl (aantal_rijtjes, 0);
	vector<long> tot_vgl (aantal_rijtjes, 0);
	vector<int> gem_vgl (aantal_rijtjes, 0);
	vector<int> min_vwsl (aantal_rijtjes, INT_MAX);
	vector<int> max_vwsl (aantal_rijtjes, 0);
	vector<long> tot_vwsl (aantal_rijtjes, 0);
	vector<int> gem_vwsl (aantal_rijtjes, 0);

	// 'runs' keer
	for (int i = 0; i < runs; i++) {

		// vul array A (nu willekeurig)
		// de laatste parameter geeft aan of alle elementen verschillend moeten zijn of niet
		vul_willekeurig(A, N, true);
		// alternatieve manieren om A te vullen
		// vul_oplopend(A, N);
		// vul_aflopend(A, N);

		// voor elk rijtje stapgroottes
		for (int j = 0; j < aantal_rijtjes; j++) {

			// maak een kopie van A (in B)
			kopieer(A, B);
			// zet de tellers (weer) op 0
			vergelijkingen = verwisselingen = 0;
			// en sorteer de kopie (zodat hetzelfde array ook kan worden gesorteerd met de andere rijtjes stapgroottes)
			shellsort(B, stapgroottes[j]);

			// schreeuw iets als het array niet is gesorteerd, dan is er namelijk iets fout
			if (!is_gesorteerd(B)) {
				cout << "Niet gesorteerd!" << endl;
			}

			// werk wat statistieken bij (minimaal, maximaal en totaal aantal vergelijkingen)
			if (vergelijkingen < min_vgl[j]) {
				min_vgl[j] = vergelijkingen;
			}
			if (vergelijkingen > max_vgl[j]) {
				max_vgl[j] = vergelijkingen;
			}
			tot_vgl[j] += vergelijkingen;

			// idem voor verwisselingen
			if (verwisselingen < min_vwsl[j]) {
				min_vwsl[j] = verwisselingen;
			}
			if (verwisselingen > max_vwsl[j]) {
				max_vwsl[j] = verwisselingen;
			}
			tot_vwsl[j] += verwisselingen;
		}
	}

	// voor alle rijtjes stapgroottes
	for (int j = 0; j < aantal_rijtjes; j++) {
		// bereken het gemiddeld aantal vergelijkingen en verwisselingen
		gem_vgl[j] = tot_vgl[j] / runs;
		gem_vwsl[j] = tot_vwsl[j] / runs;

		// en spuw wat geformatteerde data uit
		// je kan deze uitvoer uiteraard veranderen voor andere data en/of andere formattering, om het een en ander te automatiseren
		cout << "===== " << namen[j] << " =====" << endl;
		cout << "Vergelijkingen: gemiddeld " << maak_leesbaar(gem_vgl[j]) << " min " << maak_leesbaar(min_vgl[j]) << " max " << maak_leesbaar(max_vgl[j]) << endl;
		// cout << "Verwisselingen: gemiddeld " << gem_vwsl[j] << " min " << min_vwsl[j] << " max " << max_vwsl[j] << endl;
		cout << endl;
	}
}

// Rijtje stapgroottes voor een array van lengte N, zoals oorspronkelijk gedefinieerd door Shell
vector<int> stapgroottes_shell (const int & N) {
	vector<int> stapgroottes;

	int h = N / 2;

	while (h > 0) {
		stapgroottes.push_back(h);
		 h /= 2;
	}

	return stapgroottes;
}

// Rijtje stapgroottes van Hibbard
vector<int> stapgroottes_hibbard (const int & N) {
	vector<int> stapgroottes;

	int h = 2;

	// bouw het rijtje van laag naar hoog
	while (h < N) {
		stapgroottes.push_back(h - 1);
		h <<= 1; // shift naar links om te verdubbelen
	}

	// draai het rijtje om
	reverse(stapgroottes.begin(), stapgroottes.end());

	return stapgroottes;
}

// Insertion sort
vector<int> stapgroottes_enkel () {
	vector<int> stapgroottes;

	stapgroottes.push_back(1);

	return stapgroottes;
}

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

	// Als niet goed aangeroepen, spuw de juiste aanroep uit.
	if (argc != 3) {
		cout << "Gebruik: " << argv[0] << " <array_grootte> <aantal_runs>" << endl;
		return 0;
	}

	// Initialiseer de random generator
	seed = chrono::system_clock::now().time_since_epoch().count();
	generator.seed(seed);

	// Parse de command-line argumenten voor het aantal runs en de grootte
	// Je kan dit er ook uit slopen en constantes gebruiken
	int N = atoi(argv[1]);
	int runs = atoi(argv[2]);

	// Declareer de rijtjes stapgroottes en hun namen
	vector<vector<int>> stapgroottes;
	vector<string> namen;

	// Voeg rijtjes toe
	stapgroottes.push_back(stapgroottes_shell(N)); // .push_back(x) voegt x toe aan het einde
	namen.push_back("Shell");
	// Print voor de lol even de naam en het gegeneerde rijtje stapgroottes
	cout << namen.back() << ": ";
	print_array(stapgroottes.back(), stapgroottes.back().size()); // .back() pakt het laatste element

	stapgroottes.push_back(stapgroottes_hibbard(N));
	namen.push_back("Hibbard");
	cout << namen.back() << ": ";
	print_array(stapgroottes.back(), stapgroottes.back().size());

	stapgroottes.push_back(stapgroottes_enkel());
	namen.push_back("Insertion sort");
	cout << namen.back() << ": ";
	print_array(stapgroottes.back(), stapgroottes.back().size());

	cout << endl;

	// En roep het experiment aan
	run(N, runs, stapgroottes, namen);
	
	return 0;
}