#include "Tour.h"

#include <iostream>
#include "Node.h"
#include "Point.h"

Tour::Tour()
    : first(nullptr)
{}

Tour::~Tour()
{
    if (!first) {
        cout << "Empty tour" << endl;
        return;
    }

    // since node is freed, we need to keep track of next as well
    Node *node = first;
    Node *next = first->next;
    do {
        delete node;
        node = next;
        next = node->next;
    } while (node != first); // do-while since `node == first` for the first node

    first = nullptr;
}

void Tour::show() const
{
    if (!first) {
        cout << "Empty tour" << endl;
        return;
    }

    Node *node = first;
    do {
        cout << node << " " << node->next << endl;
        node = node->next;
    } while (node != first); // do-while since `node == first` for the first node
}

void Tour::draw(QGraphicsScene *scene) const
{
    if (!first) {
        cout << "Empty tour" << endl;
        return;
    }

    Node *node = first;
    do {
        node->point.drawTo(node->next->point, scene);
        node = node->next;
    } while (node != first); // do-while since `node == first` for the first node
}

int Tour::size() const
{
    if (!first) {
        cout << "Empty tour" << endl;
        return 0;
    }

    int amount = 0;
    Node *node = first;
    do {
        amount++;
        node = node->next;
    } while (node != first); // do-while since `node == first` for the first node
    return amount;
}

double Tour::distance() const
{
    if (!first) {
        cout << "Empty tour" << endl;
        return 0.0;
    }

    double sum = 0.0;
    Node *node = first;
    do {
        sum += node->point.distanceTo(node->next->point);
        node = node->next;
    } while (node != first); // do-while since `node == first` for the first node
    return sum;
}

void Tour::insertNearest(Point p)
{
    if (!first) {
        // no current nodes
        Node *node = new Node(p);
        first = node;
        node->next = node;
        return;
    }
    if (first == first->next) {
        // only one current node
        Node *node = new Node(p, first);
        first->next = node;
        return;
    }

    /*
     * For each node, inserting a new node at p makes a triangle like below.
     * We insert p in order to minimize d1.
     *
     *          p ----*
     *         /       \----*
     *   d1   /              \----*        d2
     *       /                     \----*
     *      /                            \----*
     *     /                                   \----*
     *   node ------------------------------------ next
     *                        d0
     */
    double smallestDistance = first->point.distanceTo(p); // d1
    Node *node = first->next;
    Node *smallestDistanceNode = first; // the node to insert this node after
    while (node != first) {
        double distance = node->point.distanceTo(p);
        if (distance < smallestDistance) {
            smallestDistance = distance;
            smallestDistanceNode = node;
        }
        node = node->next;
    }
    Node *newNode = new Node(p, smallestDistanceNode->next);
    smallestDistanceNode->next = newNode;
}

void Tour::insertSmallest(Point p)
{
    if (!first) {
        // no current nodes
        Node *node = new Node(p);
        first = node;
        node->next = node;
        return;
    }
    if (first == first->next) {
        // only one current node
        Node *node = new Node(p, first);
        first->next = node;
        return;
    }

    /*
     * For each node, inserting a new node at p makes a triangle like below.
     * We insert p in order to minimize d1 + d2 - d0.
     *
     *          p ----*
     *         /       \----*
     *   d1   /              \----*        d2
     *       /                     \----*
     *      /                            \----*
     *     /                                   \----*
     *   node ------------------------------------ next
     *                        d0
     */
    double smallestDiff = first->point.distanceTo(p)                     // d1
                          + p.distanceTo(first->next->point)             // d2
                          - first->point.distanceTo(first->next->point); // d0
    Node *node = first->next;
    Node *smallestDiffNode = first; // the node to insert this node after
    do {
        double diff = node->point.distanceTo(p)
                      + p.distanceTo(node->next->point)
                      - node->point.distanceTo(node->next->point);
        if (diff < smallestDiff) {
            smallestDiff = diff;
            smallestDiffNode = node;
        }
        node = node->next;
    } while (node != first); // do-while since `node == first` for the first node
    Node *newNode = new Node(p, smallestDiffNode->next);
    smallestDiffNode->next = newNode;
}