#include <iostream>
#include <iomanip>
#include <algorithm>
#include <windows.h>
#include <ctime>

using namespace std;

LONGLONG getExecutionTime() {
	FILETIME creationTime, exitTime, kernelTime, userTime;
	if (GetProcessTimes(GetCurrentProcess(), &creationTime, &exitTime, &kernelTime, &userTime)==0) {
		LPTSTR lpMsgBuf(0);
		FormatMessage(
			FORMAT_MESSAGE_ALLOCATE_BUFFER | FORMAT_MESSAGE_FROM_SYSTEM,
			NULL,
			GetLastError(),
			MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),
			lpMsgBuf,
			0,
			NULL
		);
		//MessageBox(NULL, lpMsgBuf, (LPCWSTR)"GetLastError", MB_OK|MB_ICONINFORMATION);
		cerr<<lpMsgBuf<<endl;
		LocalFree(lpMsgBuf);
	}
	LARGE_INTEGER utime;
	utime.LowPart=userTime.dwLowDateTime;
	utime.HighPart=userTime.dwHighDateTime;
	return utime.QuadPart;
}

class StopWatch {
public:
	StopWatch();
	void start();
	void stop();
	void reset();
private:
	bool running;
	LONGLONG start_time;
	LONGLONG total_time;
friend ostream& operator<<(ostream& o, const StopWatch& sw);
};

StopWatch::StopWatch(): running(false), total_time(0) {
}

void StopWatch::start() {
	if (!running) {
		running=true;
		start_time=getExecutionTime();
	}
}

void StopWatch::stop() {
	if (running) {
		running=false;
		total_time+=getExecutionTime()-start_time;
	}
}

void StopWatch::reset() {
	total_time=0;
	if (running) {
		start_time=getExecutionTime();
	}
}

ostream& operator<<(ostream& o, const StopWatch& sw) {
	LONGLONG res(sw.running?getExecutionTime()-sw.start_time:sw.total_time);
	return o<<fixed<<setprecision(2)<<res/10000000.0<<" sec";
}

void vulMetMeerderheidsElement(int* begin, int* end) {
	ptrdiff_t N(end-begin);
	for (int* p(begin); p!=begin+N/2-1; ++p) {
		*p=rand();
	}
	int meerderheidsElement(rand());
	for (int* p(begin+N/2-1); p!=end; ++p) {
		*p=meerderheidsElement;
	}
}

bool zoekMeerderheidsElement(int& resultaat, int* begin, int* end) {
//  Vul hier jouw code in!
	return false;
}

bool testMeerderheidsElement() {
	int t1[]={3,4,3,2,4,4,4,5}; // geen meerderheidselement
	int r(0);
	if (zoekMeerderheidsElement(r, t1, t1+sizeof t1/sizeof t1[0])) {
		cout<<"Test 1 failed!"<<endl;
		return false;
	}
	int t2[]={3,4,3,2,4,4,4,4,5}; // meerderheidselement = 4
	if (!zoekMeerderheidsElement(r, t2, t2+sizeof t2/sizeof t2[0]) || r!=4) {
		cout<<"Test 2 failed!"<<endl;
		return false;
	}
	int t3[]={1,1,1,1,3,2,2,3,3,3,2,3,3}; // geen meerderheidselement
	if (zoekMeerderheidsElement(r, t3, t3+sizeof t3/sizeof t3[0])) {
		cout<<"Test 3 failed!"<<endl;
		return false;
	}
	int t4[]={1,1,1,3,3,2,2,3,3,3,2,3,3}; // meerderheidselement = 3
	if (!zoekMeerderheidsElement(r, t4, t4+sizeof t4/sizeof t4[0]) || r!=3) {
		cout<<"Test 4 failed!"<<endl;
		return false;
	}
	return true;
}

int main() {
	if (!testMeerderheidsElement()) {
		cout<<"Druk op een toets om het programma te sluiten."<<endl;
		cin.get();
	}
	else {
		srand((unsigned int)time(0));
		int n(1);
		while (n>0) {
			cout<<"Geef N ( <=0 om te stoppen ): ";
			cin>>n;
			if (n>0) {
				int* array=new int[n];
				vulMetMeerderheidsElement(array, array+n);
				if (n<=100) {
					for (int* p(array); p!=array+n; ++p) {
						cout<<*p<<" ";
					}
					cout<<endl;
				}
				StopWatch sw;
				sw.start();
				int res;
				bool gevonden(zoekMeerderheidsElement(res, array, array+n));
				sw.stop();
				if (gevonden) {
					cout<<"Meerderheids element gevonden: "<<res<<endl;
				}
				else {
					cout<<"Geen meerderheids element gevonden."<<endl;
				}
				delete[] array;
				cout<<"Tijdsduur: "<<sw<<endl;
			}
		}
	}
}