week 3 deel 1

12 files changed, 485 insertions, 0 deletions

diff --git a/algo1w3/IntLink.cpp b/algo1w3/IntLink.cpp
new file mode 100644
index 0000000..a54d449
--- /dev/null
+++ b/algo1w3/IntLink.cpp
@@ -0,0 +1,11 @@
+
+#include "IntLink.h"
+
+IntLink::IntLink() { }
+
+IntLink::IntLink(int value, IntLink* next) {
+	this->value = value;
+	this->next = next;
+}
+
+IntLink::~IntLink() { }
diff --git a/algo1w3/IntLink.h b/algo1w3/IntLink.h
new file mode 100644
index 0000000..ce8c916
--- /dev/null
+++ b/algo1w3/IntLink.h
@@ -0,0 +1,16 @@
+#pragma once
+
+class IntLink {
+public:
+	IntLink();
+	IntLink(int, IntLink*);
+	virtual ~IntLink();
+
+private:
+	IntLink* next = nullptr;
+	int value = 0;
+
+private:
+	friend class IntLinkedList;
+};
+
diff --git a/algo1w3/IntLinkedList.cpp b/algo1w3/IntLinkedList.cpp
new file mode 100644
index 0000000..ce63a6d
--- /dev/null
+++ b/algo1w3/IntLinkedList.cpp
@@ -0,0 +1,111 @@
+#include <iostream>
+
+#include "IntLinkedList.h"
+#include "IntLink.h"
+
+IntLinkedList::IntLinkedList() { }
+
+IntLinkedList::~IntLinkedList() {
+	IntLink* node = this->next;
+	while (node != nullptr) {
+		IntLink* next = node->next;
+		delete node;
+		node = next;
+	}
+}
+
+IntLink* IntLinkedList::getAt(int index) const {
+	if (this->size == 0) return nullptr;
+	IntLink* out = this->next;
+	for (size_t i = 0; i < this->size; i++) {
+		if (out == nullptr) return nullptr;
+		if (i > 0) out = out->next;
+		if (i == index) return out;
+	}
+	return nullptr;
+}
+
+bool IntLinkedList::setAt(int index, int value) {
+	IntLink* node = getAt(index);
+	if (node == nullptr) return false;
+	node->value = value;
+	return true;
+}
+
+int IntLinkedList::length1() const {
+	size_t accu = 0;
+	IntLink* node = this->next;
+	while (node != nullptr) {
+		accu++;
+		node = node->next;
+	}
+	return accu;
+}
+
+int IntLinkedList::length2() const {
+	return this->size;
+}
+
+void IntLinkedList::bubbleSort() {
+	int outer, inner;
+	bool sorted;
+	for (outer = 0; outer < this->size - 2; outer++) {
+		sorted = true; // check if array was modified during inner loop
+		for (inner = this->size - 2; inner >= outer; inner--) {
+			IntLink* inner_node = getAt(inner);
+			if (inner_node->value >= inner_node->next->value) {
+				std::swap(inner_node->value, inner_node->next->value);
+				sorted = false;
+			}
+		}
+		printf("outer %d:  ", outer);
+		showAll();
+		if (sorted) break; // break if nothing changed (already sorted)
+	}
+}
+
+/*
+ * geschatte snelheid van dit algoritme: O(n^3)
+ *
+ * onderbouwing:
+ *
+ * bubble sort is O(n^2), de getAt functie is O(n). getAt wordt afhankelijk van
+ * de grootte van de array een aantal keer uitgevoerd, n^2 * n == n^3 -> O(n^3)
+ */
+
+ /*
+ * metingen van de duur van het sorteren...
+ *
+ * aantal waarden: duur in us:
+ * 1000   114410
+ * 2000   275901
+ * 5000   1443233
+ * 10000  5585394
+ * ...
+ */ 
+
+/*
+ * gemeten snelheid van dit algoritme: O(n^3)
+ * onderbouwing:
+ *
+ * ik heb google spreadsheets gebruikt om de metingen om te zetten naar een
+ * grafiek, en vervolgens een automatische trendlijn te laten maken. bij een
+ * exponentiele lijn is er nog wat afwijking van de metingen, terwijl er bij de
+ * kwadratische lijn geen afwijking is.
+ */
+
+void IntLinkedList::addToStart(int value) {
+	this->next = new IntLink(value, this->next);
+	this->size++;
+}
+
+void IntLinkedList::showAll() const {
+	std::cout << "[";
+	IntLink* node = this->next;
+	while (node != nullptr) {
+		std::cout << node->value;
+		node = node->next;
+		if (node != nullptr) std::cout << ", ";
+	}
+	std::cout << "]" << std::endl;
+}
diff --git a/algo1w3/IntLinkedList.h b/algo1w3/IntLinkedList.h
new file mode 100644
index 0000000..996b5d9
--- /dev/null
+++ b/algo1w3/IntLinkedList.h
@@ -0,0 +1,30 @@
+#pragma once
+
+#include <stdlib.h>
+
+class IntLink;
+
+class IntLinkedList {
+public:
+	IntLinkedList();
+	virtual ~IntLinkedList();
+
+public: // vraag 3
+	virtual IntLink* getAt(int) const;
+	virtual bool setAt(int, int);
+
+	virtual int length1() const;
+	virtual int length2() const;
+
+public: // vraag 4
+	virtual void bubbleSort();
+
+public: // niet gevraagd wel handig... (zie vraag 1)
+	virtual void addToStart(int);
+	virtual void showAll() const;
+
+private:
+	size_t size = 0;
+	IntLink* next = nullptr;
+};
+
diff --git a/algo1w3/NAW.cpp b/algo1w3/NAW.cpp
new file mode 100644
index 0000000..907ad21
--- /dev/null
+++ b/algo1w3/NAW.cpp
@@ -0,0 +1,42 @@
+#include "NAW.h"
+#include <iostream>
+
+NAW::NAW() { }
+
+NAW::NAW(const std::string& naam, const std::string& adres, const std::string& woonplaats) {
+	setNaam(naam);
+	setAdres(adres);
+	setPlaats(woonplaats);
+}
+
+NAW::~NAW() { }
+
+int NAW::compareTo(const NAW& other) const {
+	int c;
+	c = getPlaats().compare(other.getPlaats());
+	if (c != 0) return c;
+	c = getNaam().compare(other.getNaam());
+	if (c != 0) return c;
+	c = getAdres().compare(other.getAdres());
+	return c;
+}
+
+const std::string& NAW::getNaam() const { return _naam; }
+const std::string& NAW::getAdres() const { return _adres; }
+const std::string& NAW::getPlaats() const { return _woonplaats; }
+
+void NAW::setNaam(const std::string& naam) { _naam = naam; }
+void NAW::setAdres(const std::string& adres) { _adres = adres; }
+void NAW::setPlaats(const std::string& woonplaats) { _woonplaats = woonplaats; }
+
+bool NAW::heeftNaam(const std::string& naam) const { return getNaam().compare(naam) == 0; }
+bool NAW::heeftAdres(const std::string& adres) const { return getAdres().compare(adres) == 0; }
+bool NAW::heeftPlaats(const std::string& woonplaats) const { return getPlaats().compare(woonplaats) == 0; }
+
+std::ostream& operator << (std::ostream& output, const NAW& naw) {
+	output <<
+		"naam: " << naw.getNaam() << std::endl <<
+		"adres: " << naw.getAdres() << std::endl <<
+		"plaats: " << naw.getPlaats() << std::endl;
+	return output;
+}
diff --git a/algo1w3/NAW.h b/algo1w3/NAW.h
new file mode 100644
index 0000000..75fd2c6
--- /dev/null
+++ b/algo1w3/NAW.h
@@ -0,0 +1,36 @@
+#pragma once
+
+#include <string>
+#include <stdbool.h>
+
+class NAW {
+public:
+	NAW();
+	NAW(const std::string&, const std::string&, const std::string&);
+	virtual ~NAW();
+
+public:
+	int compareTo(const NAW&) const;
+
+public:
+	virtual const std::string& getNaam() const;
+	virtual const std::string& getAdres() const;
+	virtual const std::string& getPlaats() const;
+
+public:
+	virtual void setNaam(const std::string&);
+	virtual void setAdres(const std::string&);
+	virtual void setPlaats(const std::string&);
+
+public:
+	virtual bool heeftNaam(const std::string&) const;
+	virtual bool heeftAdres(const std::string&) const;
+	virtual bool heeftPlaats(const std::string&) const;
+
+public:
+	friend std::ostream& operator << (std::ostream& output, const NAW& naw);
+
+private:
+	std::string _naam, _adres, _woonplaats;
+};
+
diff --git a/algo1w3/NAWLink.cpp b/algo1w3/NAWLink.cpp
new file mode 100644
index 0000000..776d649
--- /dev/null
+++ b/algo1w3/NAWLink.cpp
@@ -0,0 +1,13 @@
+#include "NAWLink.h"
+#include "NAW.h"
+
+NAWLink::NAWLink() { }
+
+NAWLink::NAWLink(const NAW& value, NAWLink* next) {
+	this->value = new NAW(value);
+	this->next = next;
+}
+
+NAWLink::~NAWLink() {
+	delete this->value;
+}
diff --git a/algo1w3/NAWLink.h b/algo1w3/NAWLink.h
new file mode 100644
index 0000000..e29cfc5
--- /dev/null
+++ b/algo1w3/NAWLink.h
@@ -0,0 +1,19 @@
+#pragma once
+
+#include "NAW.h"
+
+class NAWLink {
+private:
+	NAWLink();
+	NAWLink(const NAW&, NAWLink*);
+public:
+	virtual ~NAWLink();
+
+private:
+	NAWLink* next = nullptr;
+	NAW* value = nullptr;
+
+private:
+	friend class NAWLinkedList;
+};
+
diff --git a/algo1w3/NAWLinkedList.cpp b/algo1w3/NAWLinkedList.cpp
new file mode 100644
index 0000000..06e46d8
--- /dev/null
+++ b/algo1w3/NAWLinkedList.cpp
@@ -0,0 +1,61 @@
+#include <iostream>
+
+#include "NAWLinkedList.h"
+#include "NAW.h"
+#include "NAWLink.h"
+
+NAWLinkedList::NAWLinkedList() { }
+
+NAWLinkedList::~NAWLinkedList() {
+	NAWLink* node = this->next;
+	while (node != nullptr) {
+		NAWLink* next = node->next;
+		delete node; // also deletes NAW instance -> see NAWLink::~NAWLink
+		node = next;
+	}
+}
+
+void NAWLinkedList::addToStart(const NAW& value) {
+	this->next = new NAWLink(value, this->next);
+	this->size++;
+}
+
+NAWLink* NAWLinkedList::search(const NAW& value) const {
+	NAWLink* node = this->next;
+	while (node != nullptr) {
+		if (node->value->compareTo(value) == 0) return node;
+		node = node->next;
+	}
+	return nullptr;
+}
+
+NAWLink* NAWLinkedList::searchParent(const NAW& value) const {
+	NAWLink* node = this->next;
+	while (node != nullptr) {
+		if (node->next == nullptr) return nullptr;
+		if (node->next->value->compareTo(value) == 0) return node;
+		node = node->next;
+	}
+	return nullptr;
+}
+
+void NAWLinkedList::showAll() const {
+	std::cout << "/------------------------------\\" << std::endl;
+	NAWLink* node = this->next;
+	while (node != nullptr) {
+		std::cout << *node->value; // prints values -> see operator << (std::ostream&, const NAW&)
+		node = node->next;
+		if (node != nullptr) std::cout << "              ----              " << std::endl;
+	}
+	std::cout << "\\------------------------------/" << std::endl;
+}
+
+NAWLink* NAWLinkedList::removeFirst(const NAW& value) {
+	NAWLink* parent = searchParent(value);
+	if (parent == nullptr) return nullptr;
+
+	NAWLink* node = parent->next;
+	parent->next = parent->next->next;
+
+	return node;
+}
diff --git a/algo1w3/NAWLinkedList.h b/algo1w3/NAWLinkedList.h
new file mode 100644
index 0000000..411da61
--- /dev/null
+++ b/algo1w3/NAWLinkedList.h
@@ -0,0 +1,26 @@
+#pragma once
+
+#include <stdlib.h>
+
+class NAW;
+class NAWLink;
+
+class NAWLinkedList {
+public:
+	NAWLinkedList();
+	virtual ~NAWLinkedList();
+
+public:
+	virtual void addToStart(const NAW&);
+	virtual NAWLink* search(const NAW&) const;
+	/** @brief return parent node of node found, if found */
+	virtual NAWLink* searchParent(const NAW&) const;
+	virtual void showAll() const;
+	/** @brief remove first *FOUND* */
+	virtual NAWLink* removeFirst(const NAW&);
+
+private:
+	size_t size = 0;
+	NAWLink* next = nullptr;
+};
+
diff --git a/algo1w3/main.cpp b/algo1w3/main.cpp
new file mode 100644
index 0000000..38a88b1
--- /dev/null
+++ b/algo1w3/main.cpp
@@ -0,0 +1,83 @@
+// Week3Deel1.cpp : Defines the entry point for the console application.
+//
+
+#include "NAWLinkedList.h"
+#include "IntLinkedList.h"
+
+#include "NAW.h"
+#include "NAWLink.h"
+
+#include <chrono>
+#include <iostream>
+#include <sstream>
+
+void testNAWLinkedList();
+void testintLinkedList();
+
+int main() {
+	testNAWLinkedList();
+	testintLinkedList();
+
+	return 0;
+}
+
+void testNAWLinkedList() {
+	NAWLinkedList linkedList;
+	NAWLink *link1, *link2;
+
+	for (int n = 0; n < 20; n++) {
+		std::stringstream naam, adres, plaats;
+
+		naam << "avans " << n + 1;
+		adres << "onderwijsboulevard " << n + 1;
+		plaats << "den bosch " << n + 1;
+
+		linkedList.addToStart({ naam.str(), adres.str(), plaats.str() });
+	}
+
+	linkedList.showAll();
+
+	std::stringstream naam, adres, plaats;
+
+	naam << "avans " << 7;
+	adres << "onderwijsboulevard " << 7;
+	plaats << "den bosch " << 7;
+
+	link1 = linkedList.search({ naam.str(), adres.str(), plaats.str() });
+	link2 = linkedList.removeFirst({ naam.str(), adres.str(), plaats.str() });
+
+	std::cout << link1 << " =?= " << link2 << std::endl;
+}
+
+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;
+
+	linkedList.setAt( 7, 8);
+	linkedList.setAt(37, 38);
+
+	std::cout << "link at position 7: " << linkedList.getAt(7) << std::endl;
+	std::cout << "link at position 37: " << linkedList.getAt(37) << std::endl;
+
+	std::cout << linkedList.length1() << " =?= " << linkedList.length2() << 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.showAll();
+}
diff --git a/algo1w3/makefile b/algo1w3/makefile
new file mode 100644
index 0000000..c414a31
--- /dev/null
+++ b/algo1w3/makefile
@@ -0,0 +1,37 @@
+CPP = g++
+LD = g++
+CC = gcc
+RM = rm -f
+TARGET = main
+OUTPUT_ZIP = Huiswerk_2180996.zip
+
+LFLAGS += -lstdc++
+
+SRCS += $(wildcard *.cpp)
+SRCS += $(wildcard *.c)
+OBJS := $(SRCS)
+OBJS := $(patsubst %.cpp,%.o, $(OBJS))
+OBJS := $(patsubst %.c,%.o, $(OBJS))
+
+.PHONY: clean compile_commands zip
+
+all: $(TARGET)
+
+%.o: %.c
+	$(CC) -c $(CFLAGS) $< -o $@
+
+%.o: %.cpp
+	$(CPP) -c $(CFLAGS) $< -o $@
+
+$(TARGET): $(OBJS)
+	$(LD) $^ $(LFLAGS) -o $@
+
+clean:
+	$(RM) $(TARGET) $(OBJS) $(OUTPUT_ZIP)
+
+compile_commands: clean
+	compiledb make -Bn
+
+zip: all
+	zip -q $(OUTPUT_ZIP) makefile $(wildcard *.cpp) $(wildcard *.h) $(wildcard *.hpp) $(wildcard *.c) $(wildcard *.svg)
+