From 8b6a241faee1e0d9aac9281be7be883ba0332ac1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Mon, 21 Sep 2020 15:44:37 +0200 Subject: Initial solution L3 --- labb3/tiles/TileList.cpp | 117 +++++++++++++++++++++++++++----- labb3/tiles/TileList.h | 50 ++++++++++---- labb3/tsp/src/Tour.cpp | 170 +++++++++++++++++++++++++++++++++++++++++------ labb3/tsp/src/Tour.h | 31 +++++---- labb3/tsp/src/tsp.cpp | 23 +++++-- 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 -#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(); -- cgit v1.2.1