[SDP/E2] Added work from exam

1 files changed, 81 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/Exam 2/ex2.cpp b/Year 2/Structures and data algorithms/Exam 2/ex2.cpp
new file mode 100644
index 0000000..cbe6a02
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Exam 2/ex2.cpp
@@ -0,0 +1,81 @@
+#include <iostream>
+
+template <typename T>
+struct DLListElem {
+	T data;
+	DLListElem<T> *next, *prev;
+	DLListElem(const T& data, DLListElem<T>* next = nullptr, DLListElem<T>* prev = nullptr) : data(data), next(next), prev(prev) {}
+};
+
+template <typename T>
+void freeList(DLListElem<T>* l) {
+	DLListElem<T>* temp;
+	while (l != nullptr) {
+		temp = l;
+		l = l->next;
+		delete temp;
+	}
+}
+
+// A <-> i <-> j <-> D
+
+template <typename T>
+void swap(DLListElem<T>* i, DLListElem<T>* j) {
+	if (i == j) return;
+	if (i->prev != nullptr) i->prev->next = j;
+	if (j->next != nullptr) j->next->prev = i;
+	DLListElem<T>* iPrev = i->prev;
+	i->next = j->next;
+	i->prev = j;
+	j->next = i;
+	j->prev = iPrev;
+}
+template <typename T>
+void swapNext(DLListElem<T>* i, DLListElem<T>* j) {
+	if (i == j) return;
+	if (i->prev != nullptr) i->prev->next = j;
+	i->next = j->next;
+	j->next = i;
+}
+
+// O(n^2) time complexity
+template <typename T>
+void sortDescending(DLListElem<T>* start, DLListElem<T>* end) {
+	for (DLListElem<T>* i = end; i != start && i != nullptr; i = i->prev) {
+		DLListElem<T>* toSwap = i;
+		for (DLListElem<T>* j = i->prev; j != start && j != nullptr; j = j->prev) {
+			if (j->data < toSwap->data) toSwap = j;
+		}
+		//swap(i, toSwap);
+		swapNext(i, toSwap);
+	}
+	// TODO: update prevs
+}
+
+int main() {
+	DLListElem<int>* l1 = new DLListElem<int>(1);
+	DLListElem<int>* l2 = new DLListElem<int>(2);
+	DLListElem<int>* l3 = new DLListElem<int>(3);
+	DLListElem<int>* l4 = new DLListElem<int>(4);
+	DLListElem<int>* l5 = new DLListElem<int>(5);
+	DLListElem<int>* l6 = new DLListElem<int>(6);
+	DLListElem<int>* l7 = new DLListElem<int>(7);
+	DLListElem<int>* l8 = new DLListElem<int>(8);
+	
+	// 8 7 2 5 6 1 4 3
+	               l8->next = l7;
+	l7->prev = l8; l7->next = l2;
+	l2->prev = l7; l2->next = l5;
+	l5->prev = l2; l5->next = l6;
+	l6->prev = l5; l6->next = l1;
+	l1->prev = l6; l1->next = l4;
+	l4->prev = l1; l4->next = l3;
+	l3->prev = l4;
+
+	sortDescending(l8, l3);
+	for (DLListElem<int>* i = l8; i != nullptr; i = i->next)
+		std::cout << i->data << ", ";
+	std::cout << std::endl;
+
+	freeList(l1);
+}