#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(time(0));
    	while (true) {
    		cout<<"Geef N (of Ctrl+C om te stoppen): ";
    		int n;
    		cin>>n;
    		if (n<2) {
                n=2;
            }
            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;;
    	}
    }
}