#include <iostream>
#include <iomanip>
#include <algorithm>
#include <ctime>

using namespace std;

class StopWatch {
public:
	StopWatch();
	void start();
	void stop();
	void reset();
private:
	bool running;
	clock_t start_time;
	clock_t 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=clock();
	}
}

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

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

ostream& operator<<(ostream& o, const StopWatch& sw) {
	clock_t res(sw.running?clock()-sw.start_time:sw.total_time);
	return o<<fixed<<setprecision(2)<<static_cast<double>(res)/CLK_TCK<<" 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;
			}
		}
	}
}