summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--algo1w3/IntDoubleLink.cpp19
-rw-r--r--algo1w3/IntDoubleLink.h22
-rw-r--r--algo1w3/IntDoubleLinkedList.cpp167
-rw-r--r--algo1w3/IntDoubleLinkedList.h47
-rw-r--r--algo1w3/main.cpp90
-rw-r--r--algo1w3/makefile1
6 files changed, 288 insertions, 58 deletions
diff --git a/algo1w3/IntDoubleLink.cpp b/algo1w3/IntDoubleLink.cpp
new file mode 100644
index 0000000..fb7d7a3
--- /dev/null
+++ b/algo1w3/IntDoubleLink.cpp
@@ -0,0 +1,19 @@
+#include "IntDoubleLink.h"
+
+IntDoubleLink::IntDoubleLink() { }
+IntDoubleLink::~IntDoubleLink() { }
+
+IntDoubleLink::IntDoubleLink(int value, IntDoubleLink* prev, IntDoubleLink* next) {
+ this->value = value;
+ this->prev = prev;
+ this->next = next;
+}
+
+IntDoubleLink* IntDoubleLink::getPrev() {
+ return this->prev;
+}
+
+IntDoubleLink* IntDoubleLink::getNext() {
+ return this->next;
+}
+
diff --git a/algo1w3/IntDoubleLink.h b/algo1w3/IntDoubleLink.h
new file mode 100644
index 0000000..e3cb385
--- /dev/null
+++ b/algo1w3/IntDoubleLink.h
@@ -0,0 +1,22 @@
+#pragma once
+class IntDoubleLink {
+private:
+ IntDoubleLink();
+ IntDoubleLink(int, IntDoubleLink*, IntDoubleLink*);
+
+public:
+ virtual ~IntDoubleLink();
+
+public:
+ virtual IntDoubleLink *getPrev();
+ virtual IntDoubleLink *getNext();
+
+private:
+ int value = 0;
+ IntDoubleLink* next = nullptr;
+ IntDoubleLink* prev = nullptr;
+
+private:
+ friend class IntDoubleLinkedList;
+};
+
diff --git a/algo1w3/IntDoubleLinkedList.cpp b/algo1w3/IntDoubleLinkedList.cpp
new file mode 100644
index 0000000..4f993a6
--- /dev/null
+++ b/algo1w3/IntDoubleLinkedList.cpp
@@ -0,0 +1,167 @@
+#include <iostream>
+#include "IntDoubleLinkedList.h"
+#include "IntDoubleLink.h"
+
+IntDoubleLinkedList::IntDoubleLinkedList() { }
+IntDoubleLinkedList::~IntDoubleLinkedList() { }
+
+void IntDoubleLinkedList::initFirstElement(int value) {
+ this->head = new IntDoubleLink(value, nullptr, nullptr);
+ this->tail = this->head;
+}
+
+void IntDoubleLinkedList::insertAtStart(int value) {
+ this->size++;
+ if (this->size == 1) return initFirstElement(value);
+
+ // this->tail->prev is used as the new instance holder
+ this->tail->prev = new IntDoubleLink(value, nullptr, this->tail);
+ this->tail->prev->next = this->tail; // yes
+ this->tail = this->tail->prev;
+}
+
+void IntDoubleLinkedList::insertAtEnd(int value) {
+ this->size++;
+ if (this->size == 1) return initFirstElement(value);
+
+ this->head->next = new IntDoubleLink(value, this->head, nullptr);
+ this->head->next->prev = this->head;
+ this->head = this->head->next;
+}
+
+bool IntDoubleLinkedList::removeAtStart() {
+ // can't remove anything from an empty list
+ if (this->tail == nullptr) return false;
+
+ // clear list if last element remaining is deleted
+ if (this->tail->next == nullptr) {
+ head = tail = nullptr;
+ size = 0;
+ return true;
+ }
+
+ // delete and shift
+ IntDoubleLink* node = this->tail;
+ this->tail = this->tail->next;
+ delete node;
+ size--;
+
+ return true;
+}
+
+bool IntDoubleLinkedList::removeAtEnd() {
+ // can't remove anything from an empty list
+ if (this->head == nullptr) return false;
+
+ // clear list if last element remaining is deleted
+ if (this->head->prev == nullptr) {
+ head = tail = nullptr;
+ size = 0;
+ return true;
+ }
+
+ // delete and shift
+ IntDoubleLink* node = this->head;
+ this->head = this->head->prev;
+ delete node;
+ size--;
+
+ return true;
+}
+
+IntDoubleLink* IntDoubleLinkedList::getHead() { return this->head; }
+IntDoubleLink* IntDoubleLinkedList::getTail() { return this->tail; }
+
+int IntDoubleLinkedList::_indexOf(IntDoubleLink* s) {
+ int i = 0;
+ IntDoubleLink* c = tail;
+ while (c != nullptr) {
+ if (c == s) return i;
+ i++;
+ c = c->next;
+ }
+
+ return -1;
+}
+
+void IntDoubleLinkedList::rapidBubbleSort() {
+ // waarom moet hier v ook een pointer sterretje staan!?
+ IntDoubleLink *outer, *inner;
+ bool sorted;
+ for (outer = tail; outer != head; outer = outer->next) {
+ sorted = true; // check if array was modified during inner loop
+ for (inner = head->prev; inner != outer->prev; inner = inner->prev) {
+ // printf("inner [%d, %d]\n", _indexOf(inner), _indexOf(inner->next));
+ if (inner->value >= inner->next->value) {
+ std::swap(inner->value, inner->next->value);
+ sorted = false;
+ }
+ }
+ // printf("outer %d: ", _indexOf(outer)); // indexOf printing for loop debugging
+ // showAll();
+ if (sorted) break; // break if nothing changed (already sorted)
+ }
+}
+
+/*
+ * metingen van de duur van het sorteren...
+ *
+ * aantal waarden: duur in us:
+ * 1000 4718
+ * 2000 19976
+ * 5000 131068
+ * 10000 547875
+ * ...
+ */
+
+/*
+ * gemeten snelheid van dit algoritme: O(n^2)
+ * onderbouwing:
+ *
+ * aan de structuur van de zoekfunctie is niets veranderd, er zijn nog steeds
+ * twee for-lussen waar het aantal iteraties recht evenredig is met de
+ * arraygrotte. mijn zoekfunctie gebruikt geen getAt of setAt, dus er worden
+ * geen extra 'factoren' van n toegevoegd
+ */
+
+/*
+ * Vergelijking met bubblesort van week 3 deel 1
+ *
+ * hij draait wel een ordergrootte sneller dan in deel 1 :^)
+ */
+
+void IntDoubleLinkedList::insertAction(int code) {
+ while (head != actionCursor)
+ if (!removeAtEnd()) break;
+ insertAtEnd(code);
+ actionCursor = head;
+}
+
+int IntDoubleLinkedList::undo() {
+ if (actionCursor->prev != nullptr)
+ actionCursor = actionCursor->prev;
+ return actionCursor->value;
+}
+
+int IntDoubleLinkedList::redo() {
+ if (actionCursor->next != nullptr)
+ actionCursor = actionCursor->next;
+ return actionCursor->value;
+}
+
+int IntDoubleLinkedList::getCurrentAction() {
+ return actionCursor->value;
+}
+
+void IntDoubleLinkedList::showAll() {
+ std::cout << "[";
+ IntDoubleLink* node = this->tail;
+ while (node != nullptr) {
+ if (node == actionCursor) std::cout << "{"; // curly braces for highlighting actionCursor
+ std::cout << node->value;
+ if (node == actionCursor) std::cout << "}";
+ node = node->next;
+ if (node != nullptr) std::cout << ", ";
+ }
+ std::cout << "]" << std::endl;
+}
diff --git a/algo1w3/IntDoubleLinkedList.h b/algo1w3/IntDoubleLinkedList.h
new file mode 100644
index 0000000..e48f254
--- /dev/null
+++ b/algo1w3/IntDoubleLinkedList.h
@@ -0,0 +1,47 @@
+#pragma once
+
+#include <stdio.h>
+
+class IntDoubleLink;
+
+class IntDoubleLinkedList {
+public:
+ IntDoubleLinkedList();
+ virtual ~IntDoubleLinkedList();
+
+public:
+ virtual void insertAtStart(int);
+ virtual void insertAtEnd(int);
+
+ virtual bool removeAtStart();
+ virtual bool removeAtEnd();
+
+ virtual void initFirstElement(int);
+
+public:
+ virtual IntDoubleLink *getHead();
+ virtual IntDoubleLink *getTail();
+
+public: // voor vraag 1
+ virtual void rapidBubbleSort();
+
+public: // voor vraag 2
+ virtual void insertAction(int code);
+ virtual int undo();
+ virtual int redo();
+ virtual int getCurrentAction();
+private:
+ IntDoubleLink* actionCursor = nullptr;
+
+public: // alleen voor het gemak
+ virtual void showAll();
+
+private:
+ size_t size = 0;
+ IntDoubleLink* head = nullptr;
+ IntDoubleLink* tail = nullptr;
+
+private:
+ virtual int _indexOf(IntDoubleLink*);
+};
+
diff --git a/algo1w3/main.cpp b/algo1w3/main.cpp
index 38a88b1..8f89afa 100644
--- a/algo1w3/main.cpp
+++ b/algo1w3/main.cpp
@@ -1,83 +1,57 @@
-// Week3Deel1.cpp : Defines the entry point for the console application.
-//
-
-#include "NAWLinkedList.h"
-#include "IntLinkedList.h"
-
-#include "NAW.h"
-#include "NAWLink.h"
+#include "IntDoubleLinkedList.h"
+#include <cstdlib>
+#include <ctime>
#include <chrono>
#include <iostream>
-#include <sstream>
-void testNAWLinkedList();
-void testintLinkedList();
+void testVraag1();
+void testVraag2();
int main() {
- testNAWLinkedList();
- testintLinkedList();
+ testVraag1();
+ testVraag2();
return 0;
}
-void testNAWLinkedList() {
- NAWLinkedList linkedList;
- NAWLink *link1, *link2;
-
- for (int n = 0; n < 20; n++) {
- std::stringstream naam, adres, plaats;
+void testVraag1() {
+ const int SIZE = 20;
+ IntDoubleLinkedList linkedList;
+ std::chrono::steady_clock::time_point start, end;
- naam << "avans " << n + 1;
- adres << "onderwijsboulevard " << n + 1;
- plaats << "den bosch " << n + 1;
+ std::srand(unsigned(time(nullptr)));
- linkedList.addToStart({ naam.str(), adres.str(), plaats.str() });
+ for (int n = 0; n < SIZE; n++) {
+ if ((n&1) == 0)
+ linkedList.insertAtStart(std::rand());
+ else
+ linkedList.insertAtEnd(std::rand());
}
- linkedList.showAll();
-
- std::stringstream naam, adres, plaats;
-
- naam << "avans " << 7;
- adres << "onderwijsboulevard " << 7;
- plaats << "den bosch " << 7;
+ start = std::chrono::steady_clock::now();
+ linkedList.rapidBubbleSort();// for (int n=0; n<(1<<25); n++);
+ end = std::chrono::steady_clock::now();
- link1 = linkedList.search({ naam.str(), adres.str(), plaats.str() });
- link2 = linkedList.removeFirst({ naam.str(), adres.str(), plaats.str() });
+ std::cout << "duration = " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " us" << std::endl;
- std::cout << link1 << " =?= " << link2 << std::endl;
+ linkedList.showAll();
}
-void testintLinkedList() {
- IntLinkedList linkedList;
- std::chrono::steady_clock::time_point start, end;
-
- for (int n = 20; n > 0; n--) {
- if ((n & 1) == 0)
- linkedList.addToStart(n+10);
- else
- linkedList.addToStart(n);
- }
-
- std::cout << "link at position 7: " << linkedList.getAt(7) << std::endl;
- std::cout << "link at position 37: " << linkedList.getAt(37) << std::endl;
+void testVraag2() {
+ IntDoubleLinkedList linkedList;
- linkedList.setAt( 7, 8);
- linkedList.setAt(37, 38);
+ for (int n = 0; n < 20; n++)
+ linkedList.insertAction(n);
- std::cout << "link at position 7: " << linkedList.getAt(7) << std::endl;
- std::cout << "link at position 37: " << linkedList.getAt(37) << std::endl;
+ for (int n = 0; n < 10; n++)
+ std::cout << linkedList.undo() << std::endl;
- std::cout << linkedList.length1() << " =?= " << linkedList.length2() << std::endl;
+ for (int n = 0; n < 5; n++)
+ std::cout << linkedList.redo() << std::endl;
- linkedList.showAll();
-
- start = std::chrono::steady_clock::now();
- linkedList.bubbleSort(); for (int n=0; n<(1<<25); n++);
- end = std::chrono::steady_clock::now();
-
- std::cout << "duration = " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " us" << std::endl;
+ linkedList.insertAction(100);
+ std::cout << " ----- " << std::endl;
linkedList.showAll();
}
diff --git a/algo1w3/makefile b/algo1w3/makefile
index c414a31..a1f8d29 100644
--- a/algo1w3/makefile
+++ b/algo1w3/makefile
@@ -5,6 +5,7 @@ RM = rm -f
TARGET = main
OUTPUT_ZIP = Huiswerk_2180996.zip
+CFLAGS += -g
LFLAGS += -lstdc++
SRCS += $(wildcard *.cpp)