add tsp codeL3

1 files changed, 143 insertions, 0 deletions

diff --git a/labb3/tsp/src/Tour.cpp b/labb3/tsp/src/Tour.cpp
new file mode 100644
index 0000000..8f5dd99
--- /dev/null
+++ b/labb3/tsp/src/Tour.cpp
@@ -0,0 +1,143 @@
+#include <iostream>
+#include "Tour.h"
+#include "Node.h"
+#include "Point.h"
+
+Tour::Tour() : first(nullptr)
+{ }
+
+Tour::~Tour()
+{
+    if (!first) {
+        cout << "Empty tour" << endl;
+        return;
+    }
+    Node *node = first;
+    Node *next = first->next;
+    do {
+        delete node;
+        node = next;
+        next = node->next;
+    }
+    while (node != first);
+    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);
+}
+
+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);
+}
+
+int Tour::size() const
+{
+    if (!first) {
+        cout << "Empty tour" << endl;
+        return 0;
+    }
+    Node *node = first;
+    int amount = 0;
+    do {
+        amount++;
+        node = node->next;
+    }
+    while (node != first);
+    return amount;
+}
+
+double Tour::distance() const
+{
+    if (!first) {
+        cout << "Empty tour" << endl;
+        return 0;
+    }
+    Node *node = first;
+    double sum = 0;
+    do {
+        sum += node->point.distanceTo(node->next->point);
+        node = node->next;
+    }
+    while (node != first);
+    return sum;
+}
+
+void Tour::insertNearest(Point p)
+{
+    if (!first) {
+        Node *node = new Node(p);
+        first = node;
+        node->next = node;
+        return;
+    }
+    if (first == first->next) {
+        Node *node = new Node(p, first);
+        first->next = node;
+        return;
+    }
+    double smallestDistance = first->point.distanceTo(p);
+    Node *smallestDistanceNode = first;
+    Node *node = first->next;
+    do {
+        double distance = node->point.distanceTo(p);
+        if (distance < smallestDistance) {
+            smallestDistance = distance;
+            smallestDistanceNode = node;
+        }
+        node = node->next;
+    }
+    while (node != first);
+    Node *newNode = new Node(p, smallestDistanceNode->next);
+    smallestDistanceNode->next = newNode;
+}
+
+void Tour::insertSmallest(Point p)
+{
+    if (!first) {
+        Node *node = new Node(p);
+        first = node;
+        node->next = node;
+        return;
+    }
+    if (first == first->next) {
+        Node *node = new Node(p, first);
+        first->next = node;
+        return;
+    }
+    
+    double smallestDiff = first->point.distanceTo(p) + p.distanceTo(first->next->point) - first->point.distanceTo(first->next->point);
+    Node *smallestDiffNode = first;
+    Node *node = first->next;
+    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);
+    Node *newNode = new Node(p, smallestDiffNode->next);
+    smallestDiffNode->next = newNode;
+}