/* feedback bij week 1
 * PROBLEEM :        josephus
 * INHOUD FEEDBACK : 2 stukken code van studenten,
 *                   van commentaar voorzien na "//+/"-tekens
 * TE DOEN :         nagaan of je de commentaar verstaat
 *                   en bruikbaar vindt
 */
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

//+/ CODE 1
//+/ versie met aanwezigheidstabel;
//+/ maar implementatie is niet vlot leesbaar

int josephus2(int n, int k) {
    //Tabel aanmaken & initialiseren op 0
    vector<bool> killed(n, 0); //+/ gebruik 'false' ipv '0'

    //Tabel vullen
    int i = k - 1;
    int teller = 1;
    int ronde = 0;
    int x, t;

    //+/ Wat hier onder staat kan veel leesbaarder.
    //+/
    //+/ 1. 0m te beginnen zie je dat de test 'while(teller<=n)'
    //+/    niet alleen in de buitenste while voorkomt,
    //+/    maar ook nog eens in de binnenste. Dat is overload.
    //+/
    //+/ 2. Als je op voorhand weet hoeveel bewegingen je moet doen,
    //+/    ben je duidelijker af met een for-lus.
    //+/
    //+/ 3. Bijkomend voordeel van een for-lus:
    //+/    de 'logische' volgorde wordt niet dooreengegooid zoals
    //+/    bij een while (waar je eerst wegstreept, en dan
    //+/    positie van de volgende moet klaarzetten)
    //+/
    //+/ 4. Je hebt twee 'constanten' (n en k),
    //+/    en daarbovenop nog 3 tellers (teller, x, t)
    //+/    --- dat is vrij veel om de draad niet kwijt te raken
    //+/    (toch in while-lussen).

    while (teller <= n) {
        if (killed[i % n] == 0) { //+/ deze test komt ook twee maal voor.
            //+/ kan dat niet vermeden worden?
            killed[i % n] = 1;
            teller++;
            x = (i + 1) % n;
            t = 0;
            while (t < k && teller <= n) {
                (i++);
                if (killed[i % n] == 0) { //+/ een bool-variabele NOOIT
                                          //+/ expliciet vergelijken!
                    t++;
                }
            }//volgende i bepaald
        }
    }

    return x;
}

//+/ een alternatief met for-lussen wordt:

int josephus3(int n, int k) {
    vector<bool> killed(n, false);

    int teller = -1;                    //+/ start eentje vroeger!
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < k; j++) {   //+/ doe k keer:
            teller = (teller + 1) % n;  //+/ ga 1 plaats verder
            while (killed[teller]) {    //+/ maar zorg via test-op-actie
                                        //+/ ervoor dat je 'n GOEDE
                teller = (teller + 1) % n; //+/ plaats verder loopt
            }
        }
        killed[teller] = true;
    }

    //+/ TWEE MOGELIJKHEDEN om de overblijver te bepalen:
    //+/ 1. laat bovenstaande for(i)-lus EEN keertje meer lopen,
    //+/    dan zal 'teller(+1)' je de overblijver geven.
    //+/ 2. loop het rijtje af op zoek naar de overblijver (mag vanaf 0,
    //+/    zo moet je geen %n meer doen). uitgewerkt hieronder:
    teller = 0;
    while (teller < n && killed[teller]) { //+/ eerste test mag weg
                                      //+/(na testfase); je weet zeker
                                      //+/ dat er een persoon overschiet.
        teller++;
    }

    return teller + 1; //+/ teller staat voor index; soldatennrs vanaf 1
}
//+/ BELANGRIJK :
//+/ snelheidswinst tov studentenversie met while-lussen:
//+/ 10 % (n=50000, k=200)

/////////////////////////////////////////////////////////////////////

//+/ CODE 2
//+/ circulaire lijst

//+/ voordeel: elimineren gaat vlot
//+/ voordeel: geen modulo-rekenen of ingreep nodig indien 'laatste'
//+/           van de rij gepasseerd wordt

//+/ nog kleine efficientie-ingrepen nodig (zie commentaar na //+/),
//+/ hoofdmoot van de code is OK!

//+/ wat er mankeerde in het hoofdprogramma:
//+/ controle of probleem juist opgelost werd
//+/ (ga uit van een zelf-opgesteld voorbeeld,
//+/ en laat "OK" of "NIET OK" uitschrijven)

struct knoop {
    int waarde;
    knoop *vorige;
    knoop *volgende;
};

void josephus(int n, int k) {
    //klok starten
    clock_t start = clock();

    knoop *huidige = new knoop();
    huidige->waarde = 1;

    knoop *temp = huidige;

    //lijst opvullen
    for (int i = 2; i <= n; i++) {
        huidige->volgende = new knoop();
        huidige->volgende->vorige = huidige;
        huidige = huidige->volgende;
        huidige->waarde = i;
    }

    //circulair maken
    huidige->volgende = temp;
    huidige->volgende->vorige = huidige; //+/ of temp->vorige = huidige;

    huidige = huidige->volgende; //+/ laat huidige op de laatste staan;
    //+/ als je de derde uit de groep moet weghalen,
    //+/ is je startpositie '0', zodat je na 3 stappen
    //+/ (->1 ->2 ->3) bij 3 uitkomt.

    //lijst is aangemaakt, beginnen met elimineren
    int teller = 1;
    //zolang huidige knoop niet naar zichzelf wijst (=1 knoop over)
    while (huidige->volgende != huidige) {
        //+/ alternatief voor deze while: een for-lus

        if (teller == k) {
            //cout << "Geëlimineerd: " << huidige->waarde << endl;

            huidige->vorige->volgende = huidige->volgende;
            huidige->volgende->vorige = huidige->vorige;

            //huidige temp bewaren
            knoop *volgende = huidige->vorige->volgende;
                       //+/ = huidige->volgende  (is korter)
            delete huidige;

            //+/ onderstaande stap kan je vermijden door
            //+/ de rollen om te keren: de nieuwe pointer 'volgende'
            //+/ vervang je door een pointer 'magweg' die naar
            //+/ 'huidige' wijst; je schuift 'huidige' een knoop op;
            //+/ en je delete 'magweg'.
            huidige = volgende;
            teller = 1;
        } else {
            teller++;
            huidige = huidige->volgende;
        }
        //+/ Alternatief voor bovenstaande code:
        //+/ in plaats van
        //+/      if(teller==k){
        //+/          elimineer
        //+/          teller=1
        //+/      }
        //+/      else{
        //+/          loop verder
        //+/      }
        //+/ kan je ook schrijven
        //+/      for(k){
        //+/          loop verder
        //+/      }
        //+/      elimineer
        //+/
        //+/ Ga zelf na wat je het meest leesbaar vindt
        //+/ (de structuur die je zelf het meest hanteert,
        //+/ zul je uiteraard ook meest leesbaar vinden)
    }

    //klok stoppen
    clock_t stop = clock();
    double tijd = double(stop - start) / CLOCKS_PER_SEC;

    cout << "Overlever: " << huidige->waarde << endl;
    cout << "Tijd: " << tijd << endl;

    delete huidige;
}