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

using namespace std;

class StopWatch {
public:
    StopWatch();
    void start();
    void stop();
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;
    }
}

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 - N%2); ++p) {
        *p = rand();
    }
    int meerderheidsElement(rand());
    for (int* p = begin + N/2 - (1 - N%2); p != end; ++p) {
        *p = meerderheidsElement;
    }
}

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

bool testMeerderheidsElement() {
    int r = 0;
    int t0[] = { 3 }; // meerderheidselement = 3
    if (!zoekMeerderheidsElement(r, t0, t0 + sizeof t0 / sizeof t0[0]) || r != 3) {
        cout << "Test 0 failed!" << endl;
        return false;
    }
    int t1[] = {3, 4, 3, 2, 4, 4, 4, 5}; // geen meerderheidselement
    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(static_cast<unsigned int>(time(0)));
        size_t 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;
                int res;
                sw.start();
                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;
            }
        }
    }
}