summaryrefslogtreecommitdiffstats
path: root/labb3
diff options
context:
space:
mode:
Diffstat (limited to 'labb3')
-rw-r--r--labb3/tiles/TileList.cpp117
-rw-r--r--labb3/tiles/TileList.h50
-rw-r--r--labb3/tsp/src/Tour.cpp170
-rw-r--r--labb3/tsp/src/Tour.h31
-rw-r--r--labb3/tsp/src/tsp.cpp23
5 files changed, 316 insertions, 75 deletions
diff --git a/labb3/tiles/TileList.cpp b/labb3/tiles/TileList.cpp
index 29a309b..88bdc21 100644
--- a/labb3/tiles/TileList.cpp
+++ b/labb3/tiles/TileList.cpp
@@ -1,52 +1,133 @@
-// 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 "TileList.h"
TileList::TileList()
{
- // TODO: write this member
+ tiles = new Tile[INITIAL_SIZE];
+ cur_size = INITIAL_SIZE;
}
TileList::~TileList()
-{
- // TODO: write this member
+{delete tiles;
}
void TileList::addTile(Tile tile)
{
- // TODO: write this member
+ // O(1) amortized
+ if (amount_tiles == cur_size) {
+ // reached size limit, so allocate new array and move the old tiles
+ Tile *expanded_tiles = new Tile[cur_size + INCREASE_SIZE];
+ for (int i = 0; i < cur_size; i++) {
+ expanded_tiles[i] = tiles[i];
+ }
+ cur_size += INCREASE_SIZE;
+ delete tiles;
+ tiles = expanded_tiles;
+ }
+ tiles[amount_tiles++] = tile;
+}
+
+void TileList::drawAll(QGraphicsScene *scene) const
+{
+ // O(n)
+ for (int i = 0; i < amount_tiles; i++) {
+ (tiles + i)->draw(scene);
+ }
+}
+
+int TileList::indexOfTopTile(int x, int y) const
+{
+ // O(n)
+ for (int i = 0; i < amount_tiles; i++) {
+ if ((tiles + i)->contains(x, y)) {
+ return i;
+ }
+ }
+ return -1;
+}
+
+int TileList::indexOfBottomTile(int x, int y) const
+{
+ // O(n)
+ for (int i = amount_tiles - 1; i >= 0; i--) {
+ if ((tiles + i)->contains(x, y)) {
+ return i;
+ }
+ }
+ return -1;
}
-void TileList::drawAll(QGraphicsScene* scene)
+void TileList::shiftRight(int start, int end)
{
- // TODO: write this member
+ // e.g. length=5, start=1, end=4:
+ // 0 1 2 3 4 5
+ // 0 1 1 2 3 5
+ // O(n)
+ for (int i = end; i > start; i--) {
+ tiles[i] = tiles[i - 1];
+ }
}
-int TileList::indexOfTopTile(int x, int y)
+void TileList::shiftLeft(int start, int end)
{
- // TODO: write this member
+ // e.g. length=5, start=4, end=1:
+ // 0 1 2 3 4 5
+ // 0 2 3 4 4 5
+ // O(n)
+ for (int i = start; i < end; i++) {
+ tiles[i] = tiles[i + 1];
+ }
}
void TileList::raise(int x, int y)
{
- // TODO: write this member
+ // 0 1 2 3 4 5 -
+ // 0 1 2 3 4 5 3
+ // 0 1 2 4 5 5 3
+ // 0 1 2 4 5 3 -
+ // O(n)
+ int index = indexOfTopTile(x, y);
+ if (index == -1 || index == amount_tiles - 1) {
+ // no tile found, or tile is already at top
+ return;
+ }
+ Tile tmpTile = tiles[index];
+ shiftLeft(index, amount_tiles - 1);
+ tiles[amount_tiles - 1] = tmpTile;
}
void TileList::lower(int x, int y)
{
- // TODO: write this member
+ // 0 1 2 3 4 5 -
+ // 0 1 2 3 4 5 3
+ // 0 0 1 2 4 5 3
+ // 3 0 1 2 4 5 -
+ // O(n)
+ int index = indexOfBottomTile(x, y);
+ if (index == -1 || index == 0) {
+ // no tile found, or tile is already at bottom
+ return;
+ }
+ Tile tmpTile = tiles[index];
+ shiftRight(0, index);
+ tiles[0] = tmpTile;
}
void TileList::remove(int x, int y)
{
- // TODO: write this member
+ // O(n)
+ int index;
+ if ((index = indexOfBottomTile(x, y)) != -1) {
+ shiftLeft(index, amount_tiles - 1);
+ amount_tiles--;
+ }
}
void TileList::removeAll(int x, int y)
{
- // TODO: write this member
+ // O(n^2)
+ int index;
+ while ((index = indexOfTopTile(x, y)) != -1) {
+ shiftLeft(index, amount_tiles - 1);
+ amount_tiles--;
+ }
}
diff --git a/labb3/tiles/TileList.h b/labb3/tiles/TileList.h
index a4b6ce6..865823f 100644
--- a/labb3/tiles/TileList.h
+++ b/labb3/tiles/TileList.h
@@ -1,8 +1,8 @@
-// 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 3a - gusso230 (group 11)
+ * This file contains the tile list structure.
+ * You can add, draw, lower, raise and remove tiles.
+ */
#ifndef TILELIST_H
#define TILELIST_H
@@ -12,18 +12,40 @@
class TileList {
public:
- TileList();
- ~TileList();
- void addTile(Tile tile);
- void drawAll(QGraphicsScene* scene);
- int indexOfTopTile(int x, int y);
- void lower(int x, int y);
- void raise(int x, int y);
- void remove(int x, int y);
- void removeAll(int x, int y);
+ TileList(); // allocate an empty tile list
+ ~TileList(); // deallocate the tile list
+ void addTile(Tile tile); // add a tile to the tile list, possibly reallocating
+ void drawAll(QGraphicsScene *scene) const; // draw all tiles to `scene`
+ int indexOfTopTile(int x, int y) const;
+ void lower(int x, int y); // move the top tile at (x, y) to the bottom
+ void raise(int x, int y); // move the bottom tile at (x, y) to the top
+ void remove(int x, int y); // remove the top tile at (x, y)
+ void removeAll(int x, int y); // remove all tiles at (x, y)
private:
+ static const int INITIAL_SIZE = 10; // the initial size
+ static const int INCREASE_SIZE = 10; // how much the size is increased when
+ // it's needed
+ int cur_size = 0; // current size of array
+ int amount_tiles; // number of active tiles in array
+ Tile *tiles; // the array
+ int indexOfBottomTile(int x, int y) const;
+
+ /*
+ * shiftRight and shiftLeft move a group of tiles either right or left
+ * in the internal array.
+ * shiftRight(1, 4):
+ * 0 1 2 3 4 5
+ * 0 1 1 2 3 5
+ * shiftLeft(4, 1):
+ * 0 1 2 3 4 5
+ * 0 2 3 4 4 5
+ * Effectively, `start` is duplicated either to the right for shiftRight
+ * or to the left for shiftLeft, and `end` is lost.
+ */
+ void shiftRight(int start, int end);
+ void shiftLeft(int start, int end);
};
#endif // TILELIST_H
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();
generated by cgit v1.2.1 (git 2.18.0) at 2025-12-14 00:47:15 +0100