Initial solution L3

3 files changed, 181 insertions, 43 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;
 }
diff --git a/labb3/tsp/src/Tour.h b/labb3/tsp/src/Tour.h
index 5262792..bb5166b 100644
--- a/labb3/tsp/src/Tour.h
+++ b/labb3/tsp/src/Tour.h
@@ -1,9 +1,9 @@
-// This is the .h 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, as well as on the members.
-// TODO: remove this comment header
-
+/*
+ * TDDD86 Lab 3b - gusso230 (group 11)
+ * This file contains the tour structure.
+ * You can insert points using two algorithms (nearest neighbour and smallest
+ * increase), get the total length of the tour and draw the tour.
+ */
 #ifndef TOUR_H
 #define TOUR_H
 
@@ -12,18 +12,17 @@
 
 class Tour {
 public:
-
-    Tour();
-    ~Tour();
-    void show();
-    void draw(QGraphicsScene* scene);
-    int size();
-    double distance();
-    void insertNearest(Point p);
-    void insertSmallest(Point p);
+    Tour();                                 // create an empty tour
+    ~Tour();                                // free all nodes
+    void show() const;                      // print the tour to stdout
+    void draw(QGraphicsScene *scene) const; // draw the tour on `scene`
+    int size() const;                       // return number of points on tour
+    double distance() const;                // return total distance of tour
+    void insertNearest(Point p);            // insert `p` using nearestNeighbour
+    void insertSmallest(Point p);           // insert `p` using insertSmallest
 
 private:
-
+    Node *first; // first node
 };
 
 #endif // TOUR_H
diff --git a/labb3/tsp/src/tsp.cpp b/labb3/tsp/src/tsp.cpp
index 566bf7c..57de067 100644
--- a/labb3/tsp/src/tsp.cpp
+++ b/labb3/tsp/src/tsp.cpp
@@ -18,7 +18,16 @@
 int main(int argc, char *argv[]) {
     QApplication a(argc, argv);
 
-    string filename = "tsp10.txt";
+    // MY ADDITION
+    cout << "file: ";
+    string filename;
+    getline(cin, filename);
+    if (filename == "") {
+        filename = "tsp10.txt";
+    }
+    // END OF ADDITION
+
+    //string filename = "tsp100.txt";
     ifstream input;
     input.open(filename);
 
@@ -42,12 +51,12 @@ int main(int argc, char *argv[]) {
     double y;
     while (input >> x >> y) {
         Point p(x, y);
-        tour.insertNearest(p);
-        //uncomment the 4 lines below to animate
-        //tour.draw(scene);
-        //std::chrono::milliseconds dura(50);
-        //std::this_thread::sleep_for(dura);
-        //a.processEvents();
+        tour.insertSmallest(p);
+        // uncomment the 4 lines below to animate
+        // tour.draw(scene);
+        // std::chrono::milliseconds dura(50);
+        // std::this_thread::sleep_for(dura);
+        // a.processEvents();
     }
     input.close();