#ifndef __QUADTREE
#define __QUADTREE

#include <iostream>
#include <queue>

using namespace std;

//Quadtree voor punten met int-co"ordinaten
//de PRquadtree kan alleen punten bevatten met
//-maxcoordinaat <= x < maxcoordinaat
//-maxcoordinaat <= y < maxcoordinaat

static const int OOST = 0;
static const int WEST = 1;
static const int NOORD = 0;
static const int ZUID = 2;

/*
 *  1  |  0
 * ---------
 *  3  |  2
 */

class Gebied {
public:

    Gebied(int maxc) : xl(-maxc), xr(maxc), yl(-maxc), yr(maxc), xc(0), yc(0) {
    };

    void maakdeelgebied(int x, int y) {
        if (x < xc)
            xr = xc;
        else
            xl = xc;
        if (y < yc)
            yr = yc;
        else
            yl = yc;
        xc = (xl + xr) / 2;
        yc = (yl + yr) / 2;
        cout << "Gebied is door punt (" << x << "," << y << ") gesplitst -> centrum = (" << xc << "," << yc << ")" << endl;
    };

    int geefKwadrant(int x, int y) const {
        return (x < xc ? WEST : OOST) + (y < yc ? ZUID : NOORD);
    }

    int geefXCentrum() const {
        return xc;
    }

    int geefYCentrum() const {
        return yc;
    }
private:
    int xl, xr, yl, yr, xc, yc; //geven grenzen gebied; l,r,c: links, rechts, centraal.
};

class PRquadtree {
public:

    PRquadtree(int _maxcoordinaat) : maxcoordinaat(_maxcoordinaat), k(0) {
    };
    //voegtoe veronderstelt dat het punt in het gebied ligt.
    void voegtoe(int x, int y);

    friend ostream & operator <<(ostream& os, const PRquadtree& boom) {
        os << "PRQuadtree: " << endl;
        for (int i = 0; i < 20; i++) os << "*";
        os << endl;

        queue<Knoop*> wachtrij;
        int knoopTeller = 0;
        int volgendeDiepte = 1;
        int vorigeDiepte = 0;
        int aantalBladeren = 0;
        if (boom.k != 0) {
            wachtrij.push(boom.k);
        } else {
            os << "PRQuadtree is leeg" << endl;
        }
        while (!wachtrij.empty()) {
            knoopTeller++;
            Knoop* huidigeknoop = wachtrij.front();
            wachtrij.pop();
            if (huidigeknoop != 0) {
                if (huidigeknoop->isblad()) {
                    Blad* huidigblad = (Blad*) huidigeknoop;
                    os << *huidigblad << "  | ";
                    aantalBladeren++;
                } else {
                    Nietblad* huidignietblad = (Nietblad*) huidigeknoop;
                    for (int i = 0; i < 4; i++) {
                        wachtrij.push(huidignietblad->geefkind(i));
                    }
                    vorigeDiepte = volgendeDiepte + 4;
                    os << "(NB) | ";
                }
            } else {
                os << "(null) | ";
            }
            if (knoopTeller == volgendeDiepte) {
                os << endl;
                volgendeDiepte = vorigeDiepte;
            }
        }
        os << endl << "Aantal bladeren: " << aantalBladeren << endl;
    }
protected:

    class Knoop {
    public:
        virtual bool isblad() const = 0;
    };

    class Blad : public Knoop {
    public:

        Blad(int _x, int _y) : x(_x), y(_y) {
        };

        virtual bool isblad() const {
            return true;
        }
        int x, y; //co"ordinaten punt

        friend ostream & operator <<(ostream& os, const Blad& blad) {
            os << "(" << blad.x << "," << blad.y << ")";
        }
    };

    class Nietblad : public Knoop {
    public:

        Nietblad() {
            for (int i = 0; i < 4; i++)
                kind[i] = 0;
        }

        virtual bool isblad() const {
            return false;
        }

        Knoop** geefkind(int x, int y, int xc, int yc) {//geen const: kindtabel kan gewijzigd worden
            int xindex = (x < xc ? WEST : OOST);
            int yindex = (y < yc ? ZUID : NOORD);
            cout << "Index van (" << x << "," << y << "): " << (xindex + yindex) << endl;
            return &kind[xindex + yindex];
        }

        Knoop** geefKindInKwadrant(int kwadrant) {
            return &kind[kwadrant];
        }

        Knoop* geefkind(int index) {
            return kind[index];
        }

    private:
        Knoop* kind[4]; //indexeren met windrichting (bv. kind[NOORD+OOST] bevat punten
        //met x en y kleiner dan grenswaarde)
        //leeg gebied: nulpointer
    };
    const int maxcoordinaat; //wordt opgegeven in constructor;
    Knoop* k;
};

void PRquadtree::voegtoe(int x, int y) {
    cout << "Nieuw punt (" << x << "," << y << ") toevoegen" << endl;
    // Gebied aanmaken a.d.h.v. de maxcoördinaat
    Gebied gebied(maxcoordinaat);

    // Gebied al in 4 splitsen. Anders wordt enkel kind[0] van de wortel gebruikt
    gebied.maakdeelgebied(x, y);

    // Blad aanmaken met de gegevens coördinaten
    Knoop* nieuwBlad = new Blad(x, y);

    if (k == 0) {
        cout << "Wortel is leeg, vervangen met Nietblad" << endl;
        // PRQuadtree is leeg
        // Wortel wijst nu naar een Nietblad met 1 kind
        k = new Nietblad();
        //gebied.maakdeelgebied(x, y);
        cout << "Laat kind wijzen naar knoop met index van (" << x << "," << y << ")" << endl;
        Knoop** hulp = (static_cast<Nietblad*> (k))->geefkind(x, y, gebied.geefXCentrum(), gebied.geefYCentrum());
        (*hulp) = nieuwBlad;
    } else {
        cout << "Wortel is niet leeg" << endl;
        // Pointer bijhouden naar de het adres van de knoop waaronder het nieuwe
        // blad moet komen
        Knoop** kind = &k;

        // Zolang k bestaat en geen blad is moeten we verder zoeken
        while (*kind != 0 && !(*kind)->isblad()) {
            gebied.maakdeelgebied(x, y);
            cout << "Laat kind wijzen naar knoop met index van (" << x << "," << y << ")" << endl;
            kind = ((static_cast<Nietblad*> (*kind)))->geefKindInKwadrant(gebied.geefKwadrant(x, y));
        }

        // Is kind een adres naar een nullpointer? Dan kunnen we het nieuwe blad
        // gewoon aan de boom hangen
        if (*kind == 0) {
            cout << "Kind is nullpointer, wordt vervangen door het nieuwe blad" << endl;
            (*kind) = nieuwBlad;
        } else {
            cout << "Kind is geen nullpointer, dit blad moet gesplitst worden" << endl;
            // Blad gevonden, dit moet gesplitst worden

            // Nietblad aanmaken
            Knoop* nietblad = new Nietblad();

            // Pointer naar het oude blad bijhouden
            Knoop* oudBlad = *kind;

            // Kind vervangen door het nietblad
            (*kind) = nietblad;

            // Nietblad_hulp declareren
            Knoop* nietblad_hulp = 0;

            // Zolang het gevonden blad in hetzelfde kwadrant ligt als het
            // nieuwe punt, moeten we verder splitsen
            int kwadrantOudBlad = gebied.geefKwadrant((static_cast<Blad*> (oudBlad))->x, (static_cast<Blad*> (oudBlad))->y);
            int kwadrantNieuwBlad = gebied.geefKwadrant(x, y);

            while (kwadrantOudBlad == kwadrantNieuwBlad) {
                // Beide punten liggen in hetzelfde kwadrant
                cout << "Beide punten liggen in hetzelfde kwadrant: " << kwadrantOudBlad << endl;

                // Nieuw nietblad aanmaken
                nietblad_hulp = new Nietblad();

                // Plaats waar het nieuwe Nietblad moet komen bepalen
                cout << "Verplaats kindpointer naar index " << kwadrantOudBlad << " van nietblad" << endl;
                kind = (static_cast<Nietblad*> (nietblad))->geefKindInKwadrant(kwadrantOudBlad);
                (*kind) = nietblad_hulp;
                cout << "Nietblad toegevoegd aan de boom" << endl;

                // Gebied opsplitsen
                gebied.maakdeelgebied((static_cast<Blad*> (oudBlad))->x, ((static_cast<Blad*> (oudBlad))->y));

                //Kwadranten opnieuw berekenen
                kwadrantOudBlad = gebied.geefKwadrant((static_cast<Blad*> (oudBlad))->x, (static_cast<Blad*> (oudBlad))->y);
                kwadrantNieuwBlad = gebied.geefKwadrant(x, y);

                // Nieuw adres waar het oude punt moet terechtkomen bepalen
                cout << "Verplaats kindpointer naar index " << kwadrantOudBlad << " van nietblad_hulp" << endl;
                kind = (static_cast<Nietblad*> (nietblad_hulp))->geefKindInKwadrant(kwadrantOudBlad);
            }
            // We vragen een pointer naar de plaats waar het nieuwe punt moet
            // toegevoegd worden. Deze pointer is sowieso 0, want anders bevinden
            // we ons nog in de while-lus

            // Het oude blad opnieuw aan de boom toevoegen
            cout << "Punt (" << (static_cast<Blad*> (oudBlad))->x << "," << (static_cast<Blad*> (oudBlad))->y << ") opnieuw toevoegen aan de boom" << endl;
            (*kind) = oudBlad;

            // De nieuwe coördinaat kan nu toegevoegd worden aan de boom
            Knoop** hulp;
            cout << "Verplaats hulppointer naar index " << kwadrantNieuwBlad << " van nietblad_hulp" << endl;
            if (nietblad_hulp != 0)
                hulp = (static_cast<Nietblad*> (nietblad_hulp))->geefKindInKwadrant(kwadrantNieuwBlad);
            else
                hulp = (static_cast<Nietblad*> (nietblad))->geefKindInKwadrant(kwadrantNieuwBlad);
            cout << "Punt (" << x << "," << y << ") toevoegen aan de boom" << endl;
            (*hulp) = nieuwBlad;
        }
    }
    cout << "Nieuw punt (" << x << "," << y << ") is toegevoegd" << endl << endl;
    cout << *this;
    for (int i = 0; i < 20; i++) cout << "*";
    cout << endl << endl;
}

#endif