Initial solution L3

1 files changed, 150 insertions, 20 deletions

diff --git a/labb3/tsp/src/Tour.cpp b/labb3/tsp/src/Tour.cpp
index 2dc3fcc..135e10e 100644
--- a/labb3/tsp/src/Tour.cpp
+++ b/labb3/tsp/src/Tour.cpp
@@ -1,50 +1,180 @@
-// This is the .cpp file you will edit and turn in.
-// We have provided a skeleton for you,
-// but you must finish it as described in the spec.
-// Also remove these comments here and add your own.
-// TODO: remove this comment header
+#include "Tour.h"
 
 #include <iostream>
-#include "Tour.h"
 #include "Node.h"
 #include "Point.h"
 
 Tour::Tour()
-{
-    // TODO: write this member
-}
+    : first(nullptr)
+{}
 
 Tour::~Tour()
 {
-    // TODO: write this member
+    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()
+void Tour::show() const
 {
-    // TODO: write this member
+    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)
+void Tour::draw(QGraphicsScene *scene) const
 {
-    // TODO: write this member
+    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()
+int Tour::size() const
 {
-    // TODO: write this member
+    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()
+double Tour::distance() const
 {
-    // TODO: write this member
+    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)
 {
-    // TODO: write this member
+    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)
 {
-    // TODO: write this member
+    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;
 }