#include <iostream>
#include <array>
#include <vector>
#include <random>
using namespace std;

// Deklariert ein Template für den Typparameter des Arrays mit den Koordinaten
template<typename coordinateType, int dimensions>

// Deklariert eine Klasse für einen Punkt in einem mehrdimensionalen euklidischen Raum. Der Typparameter coordinateType muss ein numerischer Datentyp sein.
class Point
{
public:
    // Konstruktor
    Point(initializer_list<coordinateType> list)
    {
        int length = min(dimensions, (int)list.size());
        copy_n(list.begin(), length, coordinates.begin()); // Initialisiert das Array mit den Koordinaten
    }

    // Diese Funktion gibt die Koordinate der mit dem gegebenen Index zurück
    coordinateType get(int index) const
    {
        return coordinates[index];
    }

    // Diese Funktion gibt den quadrierten Abstand des Punkts zum gegebenen Punkt zurück
    double getSquaredDistance(const Point& point) const
    {
        double squaredDistance = 0;
        for (int i = 0; i < dimensions; i++)
        {
            double difference = (double)get(i) - (double)point.get(i);
            squaredDistance += difference * difference;
        }
        return squaredDistance;
    }
private:
    // Deklariert ein Array der Länge dimensions mit dem Typparameter coordinateType für die Koordinaten des Punkts
    array<coordinateType, dimensions> coordinates;
};

template<typename coordinateType, int dimensions>

// Deklariert den Operator <<, der die Koordinaten des gegebenen Punkts auf der Konsole ausgibt
ostream& operator<<(ostream& output, const Point<coordinateType, dimensions>& point)
{
    output << '(';
    for (int i = 0; i < dimensions; i++)
    {
        if (i > 0)
        {
            output << ", ";
        }
        output << point.get(i);
    }
    output << ')';
    return output;
}

template<typename coordinateType, int dimensions>

// Deklariert eine Klasse für den k-d-Baum
class KDTree
{
public:
    typedef Point<coordinateType, dimensions> pointType;
private:
    // Datentyp für die Knoten des Baums
    struct node
    {
        // Diese Funktion initialisiert den Knoten
        node(const pointType& _point) : point(_point), left(nullptr), right(nullptr) {}
        // Diese Funktion gibt die Koordinate mit dem gegebenen Index zurück
        coordinateType get(int index) const
        {
            return point.get(index); // Ruft die Funktions der Klasse Point auf
        }
        // Diese Funktion gibt den quadrierten Abstand zum gegebenen Punkt zurück
        double getSquaredDistance(const pointType& _point) const
        {
            return point.getSquaredDistance(_point); // Ruft die Funktion der Klasse Point auf
        }
        pointType point; // Punkt, der dem Knoten zugeordnet ist
        node* left; // Linker Nachfolger des Knoten
        node* right; // Rechter Nachfolger des Knoten
    };

    node* root = nullptr; // Zeiger auf den Wurzelknoten des Baums
    node* nearestNode = nullptr; // Zeiger auf den bisher gefundenen Knoten mit dem kleinsten Abstand zum Wurzelknoten
    double smallestDistance = 0; // Abstand zum Wurzelknoten
    int numberOfVisited = 0; // Zähler für die bisher besuchten Knoten
    vector<node> nodes; // Vektor, der die Knoten des Baums enthält

    struct nodeCompare
    {
        // Vergleichsfunktion
        nodeCompare(int _index) : index(_index) {}
        // Deklariert den Operator (), der die Koordinaten mit dem gegebenen Index vergleicht. Gibt true zurück, wenn die Koordinate des ersten Knotens kleiner als die des zweiten Knotens ist, sonst false. 
        bool operator()(const node& node1, const node& node2) const
        {
            return node1.point.get(index) < node2.point.get(index);
        }
        int index;
    };

    // Diese rekursive Funktion erzeugt den Baum mit den Knoten im angegebenen Indexbereich und gibt einen Zeiger auf den Knoten mit dem Median der Punkte zurück
    node* createTree(int startIndex, int endIndex, int index)
    {
        // Abbruchbedingung für die Rekursion, gibt einen Nullzeiger zurück und verlässt die Funktion
        if (startIndex >= endIndex)
        {
            return nullptr;
        }
        int meanIndex = startIndex + (endIndex - startIndex) / 2; // Berechnet den mittleren Index
        auto i = nodes.begin(); // Iterator, der auf den ersten Knoten des Vektors zeigt
        // Setzt den richtigen Knoten auf den mittleren Index und teilt den Vektor nodes nach der Koordinaten mit dem Index in zwei Wertebereiche auf. Dafür wird die Vergleichsfunktion nodeCompare verwendet.
        nth_element(i + startIndex, i + meanIndex, i + endIndex, nodeCompare(index));
        index = (index + 1) % dimensions; // Index für die Koordinate um 1 erhöhen, bei Überlauf auf 0 setzen

        nodes[meanIndex].left = createTree(startIndex, meanIndex, index); // Rekursiver Aufruf für den linken Teilbaum, weist den linken Nachfolgerknoten zu
        nodes[meanIndex].right = createTree(meanIndex + 1, endIndex, index); // Rekursiver Aufruf für den rechten Teilbaum, weist den rechten Nachfolgerknoten zu

        return &nodes[meanIndex]; // Gibt den Knoten mit dem mittleren Index zurück
    }

    // Diese rekursive Funktion bestimmt den Knoten des Baums, dessen Punkt den kleinsten Abstand vom gegebenen Punkt hat. Das Ergebnis wird Attributen von KDTree zugewiesen.
    void nearest(node* currentNode, const pointType& point, int index)
    {
        // Wenn der Zeiger für den aktuellen Knoten ein Nullzeiger ist, Funktion verlassen
        if (currentNode == nullptr)
        {
            return;
        }
        numberOfVisited++; // Zähler für die bisher besuchten Knoten um 1 erhöhen
        double squaredDistance = currentNode->getSquaredDistance(point); // Funktionsaufruf, bestimmt den quadrierten Abstand des Punkts
        if (nearestNode == nullptr || squaredDistance < smallestDistance) // Wenn das Attribut für den Knoten noch nicht zugewiesen oder der quadrierte Abstand des gefundenen Punkts kleiner als der bisherige Abstand ist
        {
            smallestDistance = squaredDistance; // Weist den quadrierten Abstand dem Attribut zu
            nearestNode = currentNode; // Weist den aktuellen Knoten dem Attribut zu
        }
        // Wenn der gefundene Punkt den Abstand 0 vom gegebenen Punkt hat, Funktion verlassen
        if (smallestDistance == 0)
        {
            return;
        }
        double difference = (double)currentNode->get(index) - (double)point.get(index); // Berechnet die Differenz zwischen der Koordinate des aktuellen und des gegebenen Knotens
        index = (index + 1) % dimensions; // Index für die Koordinate um 1 erhöhen, bei Überlauf auf 0 setzen

        nearest(difference > 0 ? currentNode->left : currentNode->right, point, index); // Rekursiver Aufruf für den Nachfolgerknoten mit Fallunterscheidung, Differenz positiv: linker Knoten, Differenz negativ: rechter Knoten
        // Wenn die Differenz der Koordinatenwerte größer ist als der bisher gefundene kleinste Abstand, Funktion verlassen
        if (difference * difference >= smallestDistance)
        {
            return;
        }
        nearest(difference > 0 ? currentNode->right : currentNode->left, point, index); // Rekursiver Aufruf für den Nachfolgerknoten mit Fallunterscheidung, Differenz positiv: rechter Knoten, Differenz negativ: linker Knoten
    }
public:
    template<typename iterator>

    // Konstruktor, der die Punkte im gegebenen Bereich in den Baum einfügt
    KDTree(iterator iterator1, iterator iterator2) : nodes(iterator1, iterator2)
    {
        root = createTree(0, nodes.size(), 0); // Funktionsaufruf, weist den Zeiger auf den Wurzelknoten zu
    }

    // Gibt true zurück, wenn der Baum leer ist, sonst false
    bool empty() const { return nodes.empty(); }
    // Gibt die Anzahl der besuchten Knoten nach dem letzten Aufruf der Funktion nearest zurück
    int visited() const { return numberOfVisited; }
    // Gibt den Abstand zwischen dem gegebenen Punkt und dem zuletzt von der Funktion nearest zurückgegebenen Punkt zurück
    double distance() const { return sqrt(smallestDistance); }

    // Diese Funktion gibt den Punkt mit dem kleinsten Abstand zum gegebenen Punkt zurück. Wenn der Baum leer ist, wird eine Ausnahme ausgelöst.
    pointType& nearest(const pointType& point)
    {
        // Wenn der Zeiger für den Wurzelknoten auf keinen Knoten verweist
        if (root == nullptr)
        {
            throw logic_error("Der Baum ist leer"); // Wirft eine Ausnahme
        }
        // Setzt die Startwerte der Variablen
        nearestNode = nullptr;
        numberOfVisited = 0;
        smallestDistance = 0;
        nearest(root, point, 0); // Funktionsaufruf
        return nearestNode->point;
    }
};

// Hauptfunktion die das Programm ausführt
int main()
{
    // Typdefinitionen
    typedef Point<int, 2> point2d;
    typedef KDTree<int, 2> kdTree2d;

    // Deklariert und initialisiert ein Array mit 6 Punkten
    point2d points[] = { { 2, 3 }, { 5, 4 }, { 9, 6 }, { 4, 7 }, { 8, 1 }, { 7, 2 } };
    // Deklariert und initialisiert die Variable für den k-d-Baum
    kdTree2d tree(begin(points), end(points));
    point2d nearestPoint = tree.nearest({ 9, 2 }); // Funktionsaufruf, weist den Punkt mit dem kleinsten Abstand der Variablen zu

    cout << "Punkt mit dem kleinsten Abstand: " << nearestPoint << endl; // Ausgabe auf der Konsole
    cout << "Abstand: " << tree.distance() << endl; // Ausgabe auf der Konsole
    cout << "Anzahl der besuchten Knoten: " << tree.visited() << endl; // Ausgabe auf der Konsole
}