week 3 deel 2

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)