[SDP/HEP] Added preparation for "homework" during class

8 files changed, 533 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/HomeworkExamPrep/LinkedList.hpp b/Year 2/Structures and data algorithms/HomeworkExamPrep/LinkedList.hpp
new file mode 100644
index 0000000..fbab914
--- /dev/null
+++ b/Year 2/Structures and data algorithms/HomeworkExamPrep/LinkedList.hpp
@@ -0,0 +1,230 @@
+#ifndef LINKEDLIST
+#define LINKEDLIST
+
+#include <stdexcept>
+
+template <class T>
+class LinkedList {
+	struct Node {
+		T data;
+		Node* next;
+		Node(const T& data, Node* next = nullptr) : data(data), next(next) {}
+	};
+
+	Node* head;
+	Node* tail;
+	unsigned listSize;
+
+	Node* nodeAt(unsigned index);
+
+public:
+	class Iterator {
+		Node* current;
+		Iterator(Node* current) : current(current) {}
+	public:
+		Iterator& operator++() {
+			if (current == nullptr) return *this;
+
+			current = current->next;
+			return *this;
+		}
+		Iterator operator++(int) {
+			Iterator old = *this;
+			++(*this);
+			return old;
+		}
+		bool operator==(Iterator& other) {
+			return this->current == other.current;
+		}
+		bool operator!=(Iterator& other) {
+			return !(*this == other);
+		}
+		T& operator*() {
+			return current->data;
+		}
+		friend class LinkedList;
+	};
+	Iterator begin();
+	Iterator end();
+
+	class ConstIterator {
+		const Node* current;
+		ConstIterator(Node* current) : current(current) {}
+	public:
+		ConstIterator& operator++() {
+			if (current == nullptr) return *this;
+
+			current = current->next;
+			return *this;
+		}
+		ConstIterator operator++(int) {
+			ConstIterator old = *this;
+			++(*this);
+			return old;
+		}
+		bool operator==(const ConstIterator* other) const {
+			return this->current == other->current;
+		}
+		bool operator!=(const ConstIterator* other) const {
+			return !(*this == *other);
+		}
+		const T& operator*() const {
+			return current->data;
+		}
+		friend class LinkedList;
+	};
+	ConstIterator cbegin() const;
+	ConstIterator cend() const;
+
+	void push_front(const T& elem);
+	void push_back(const T& elem);
+	void push_at(unsigned ind, const T& elem);
+	void pop_front();
+	void pop_back();
+	void pop_at(unsigned ind);
+	T& front();
+	unsigned size();
+	bool empty();
+	
+
+	LinkedList() : head(nullptr) {}
+	~LinkedList();
+	LinkedList(LinkedList& other) = delete;
+	LinkedList& operator=(LinkedList& other) = delete;
+};
+
+template <class T>
+typename LinkedList<T>::Iterator LinkedList<T>::begin() {
+	return Iterator(head);
+}
+
+template <class T>
+typename LinkedList<T>::Iterator LinkedList<T>::end() {
+	return Iterator(nullptr);
+}
+
+template <class T>
+typename LinkedList<T>::ConstIterator LinkedList<T>::cbegin() const {
+	return ConstIterator(head);
+}
+
+template <class T>
+typename LinkedList<T>::ConstIterator LinkedList<T>::cend() const {
+	return ConstIterator(nullptr);
+}
+
+template <class T>
+typename LinkedList<T>::Node* LinkedList<T>::nodeAt(unsigned index) {
+	if (index > listSize)
+		throw std::runtime_error("Index too large!");
+
+	Node* nat;
+	for (nat = head; index > 0; index--) {
+		nat = nat->next;
+	}
+	return nat;
+}
+
+template <class T>
+void LinkedList<T>::push_front(const T& elem) {
+	if (empty()) {
+		head = tail = new Node(elem);
+	}
+	else {
+		head = new Node(elem, head);
+	}
+	listSize++;
+}
+
+template <class T>
+void LinkedList<T>::push_back(const T& elem) {
+	if (empty()) {
+		head = tail = new Node(elem);
+	}
+	else {
+		tail = (tail->next = new Node(elem));
+	}
+	listSize++;
+}
+
+template <class T>
+void LinkedList<T>::push_at(unsigned ind, const T& elem) {
+	if (ind >= listSize) {
+		push_back(elem);
+	}
+	else if (ind == 0) {
+		push_front(elem);
+	}
+	else {
+		Node* prev = nodeAt(ind - 1);
+		prev->next = new Node(elem, prev->next);
+		listSize++;
+	}
+}
+
+template <class T>
+void LinkedList<T>::pop_front() {
+	if (empty())
+		throw std::runtime_error("Pop empty list!");
+
+	Node* old = head;
+	head = head->next;
+	delete old;
+	listSize--;
+
+	if (empty()) tail = nullptr;
+}
+
+template <class T>
+void LinkedList<T>::pop_back() {
+	if (empty())
+		throw std::runtime_error("Pop empty list!");
+
+	Node* old = tail;
+	tail = nodeAt(listSize - 2);
+	tail->next = nullptr;
+	delete old;
+	listSize--;
+
+	if (empty()) head = nullptr;
+}
+
+template <class T>
+void LinkedList<T>::pop_at(unsigned ind) {
+	if (ind >= listSize - 1) {
+		pop_back();
+	}
+	else if (ind == 0) {
+		pop_front();
+	}
+	else {
+		Node* prev = nodeAt(ind - 1);
+		Node* curr = prev->next;
+		prev->next = curr->next;
+		delete curr;
+		listSize--;
+	}
+}
+
+template <class T>
+T& LinkedList<T>::front() {
+	return head->data;
+}
+
+template <class T>
+unsigned LinkedList<T>::size() {
+	return listSize;
+}
+
+template <class T>
+bool LinkedList<T>::empty() {
+	return listSize == 0;
+}
+
+template <class T>
+LinkedList<T>::~LinkedList() {
+	while (!empty())
+		pop_front();
+}
+
+#endif
diff --git a/Year 2/Structures and data algorithms/HomeworkExamPrep/LinkedList.hpp.gch b/Year 2/Structures and data algorithms/HomeworkExamPrep/LinkedList.hpp.gch
new file mode 100644
index 0000000..14b5df7
--- /dev/null
+++ b/Year 2/Structures and data algorithms/HomeworkExamPrep/LinkedList.hpp.gch
diff --git a/Year 2/Structures and data algorithms/HomeworkExamPrep/Queue/Queue_Dynamic.hpp b/Year 2/Structures and data algorithms/HomeworkExamPrep/Queue/Queue_Dynamic.hpp
new file mode 100644
index 0000000..02c8888
--- /dev/null
+++ b/Year 2/Structures and data algorithms/HomeworkExamPrep/Queue/Queue_Dynamic.hpp
@@ -0,0 +1,60 @@
+#ifndef QUEUE_DYNAMIC
+#define QUEUE_DYNAMIC
+
+template <class T>
+class Queue {
+	struct Node {
+		T val;
+		Node* next;
+
+		Node(const T& v) : val(v), next(nullptr) {}
+	};
+
+	Node* head;
+	Node* tail;
+
+public:
+	Queue();
+	~Queue();
+	Queue(Queue& other) = delete;
+	Queue& operator=(Queue& other) = delete;
+
+	void push(const T& v);
+	void pop();
+	T& front();
+};
+
+template <class T>
+Queue<T>::Queue() : head(nullptr), tail(nullptr) {}
+
+template <class T>
+Queue<T>::~Queue() {
+	while (head != nullptr)
+		pop();
+}
+
+template <class T>
+void Queue<T>::push(const T& v) {
+	if (head == nullptr) {
+		head = tail = new Node(v);
+	}
+	else {
+		tail->next = new Node(v);
+		tail = tail->next;
+	}
+}
+
+template <class T>
+void Queue<T>::pop() {
+	Node* toDel = head;
+	head = head->next;
+	delete toDel;
+	if (head == nullptr) tail = nullptr;
+}
+
+template <class T>
+T& Queue<T>::front() {
+	return head->val;
+}
+
+#endif
diff --git a/Year 2/Structures and data algorithms/HomeworkExamPrep/Queue/Queue_Static.hpp b/Year 2/Structures and data algorithms/HomeworkExamPrep/Queue/Queue_Static.hpp
new file mode 100644
index 0000000..2b9dc8d
--- /dev/null
+++ b/Year 2/Structures and data algorithms/HomeworkExamPrep/Queue/Queue_Static.hpp
@@ -0,0 +1,37 @@
+#ifndef QUEUE_STATIC
+#define QUEUE_STATIC
+
+#include <stdexcept>
+#define QUEUE_SIZE 1024
+
+template <class T>
+class Queue {
+	T vals[QUEUE_SIZE];
+	unsigned frontInd;
+	unsigned backInd;
+
+public:
+	void push(const T& v);
+	void pop();
+	T& front();
+};
+
+template <class T>
+void Queue<T>::push(const T& v) {
+	vals[backInd++ % QUEUE_SIZE] = v;
+
+	if (backInd == frontInd)
+		throw std::logic_error("Queue overfill!");
+}
+
+template <class T>
+void Queue<T>::pop() {
+	frontInd++;
+}
+
+template <class T>
+T& Queue<T>::front() {
+	return vals[frontInd];
+}
+
+#endif
diff --git a/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_Dynamic.hpp b/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_Dynamic.hpp
new file mode 100644
index 0000000..db87f96
--- /dev/null
+++ b/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_Dynamic.hpp
@@ -0,0 +1,53 @@
+#ifndef STACK_DYNAMICSEQ
+#define STACK_DYNAMICSEQ
+
+template <class T>
+class Stack {
+	struct Node {
+		T value;
+		Node* next;
+
+		Node(const T& v, Node* n) : value(v), next(n) {}
+	};
+
+	Node* topNode;
+
+public:
+	Stack();
+	~Stack();
+	Stack(Stack& other) = delete;
+	Stack& operator=(const Stack& other) = delete;
+
+	void push(const T& v);
+	void pop();
+	T& top();
+};
+
+template <class T>
+Stack<T>::Stack() : topNode() {}
+
+template <class T>
+Stack<T>::~Stack() {
+	while (topNode != nullptr)
+		pop();
+}
+
+template <class T>
+void Stack<T>::push(const T& v) {
+	topNode = new Node(v, topNode);
+}
+
+template <class T>
+void Stack<T>::pop() {
+	Node* old = topNode;
+	topNode = topNode->next;
+	delete old;
+}
+
+template <class T>
+T& Stack<T>::top() {
+	return topNode->value;
+}
+
+
+#endif
diff --git a/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_DynamicSeq.hpp b/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_DynamicSeq.hpp
new file mode 100644
index 0000000..7f794e7
--- /dev/null
+++ b/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_DynamicSeq.hpp
@@ -0,0 +1,62 @@
+#ifndef STACK_DYNAMIC
+#define STACK_DYNAMIC
+
+template <class T>
+class Stack {
+	T* vals;
+	unsigned topInd;
+	unsigned size;
+
+	void resize();
+
+public:
+	Stack();
+	~Stack();
+	Stack(Stack& other) = delete;
+	Stack& operator=(const Stack& other) = delete;
+
+	void push(const T& v);
+	void pop();
+	T& top();
+};
+
+template <class T>
+void Stack<T>::resize() {
+	unsigned newSize = size << 1;
+	T* newVals = new T[newSize];
+	for (unsigned i = 0; i < size; i++)
+		newVals[i] = vals[i];
+	delete vals;
+	vals = newVals;
+	size = newSize;
+}
+
+template <class T>
+Stack<T>::Stack() {
+	vals = new T[1]; // for testing purposes its 1
+}
+
+template <class T>
+Stack<T>::~Stack() {
+	delete[] vals;
+}
+
+template <class T>
+void Stack<T>::push(const T& v) {
+	if (topInd == size)
+		resize();
+
+	vals[topInd++] = v;
+}
+
+template <class T>
+void Stack<T>::pop() {
+	topInd--;
+}
+
+template <class T>
+T& Stack<T>::top() {
+	return vals[topInd - 1];
+}
+
+#endif
diff --git a/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_Static.hpp b/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_Static.hpp
new file mode 100644
index 0000000..91fdb65
--- /dev/null
+++ b/Year 2/Structures and data algorithms/HomeworkExamPrep/Stack/Stack_Static.hpp
@@ -0,0 +1,32 @@
+#ifndef STACK_STATIC
+#define STACK_STATIC
+
+#define STACK_SIZE 1024
+
+template <class T>
+class Stack {
+	T vals[STACK_SIZE];
+	unsigned topPos = 0;
+
+public:
+	void push(const T& v);
+	void pop();
+	T& top();
+};
+
+template <class T>
+void Stack<T>::push(const T& v) {
+	vals[topPos++] = v;
+}
+
+template <class T>
+void Stack<T>::pop() {
+	topPos--;
+}
+
+template <class T>
+T& Stack<T>::top() {
+	return vals[topPos - 1];
+}
+
+#endif
diff --git a/Year 2/Structures and data algorithms/HomeworkExamPrep/main.cpp b/Year 2/Structures and data algorithms/HomeworkExamPrep/main.cpp
new file mode 100644
index 0000000..060e94c
--- /dev/null
+++ b/Year 2/Structures and data algorithms/HomeworkExamPrep/main.cpp
@@ -0,0 +1,59 @@
+#include <iostream>
+
+// #include "Stack/Stack_Static.hpp"
+// #include "Stack/Stack_DynamicSeq.hpp"
+#include "Stack/Stack_Dynamic.hpp"
+
+// #include "Queue/Queue_Static.hpp"
+#include "Queue/Queue_Dynamic.hpp"
+
+#include "LinkedList.hpp"
+
+int main() {
+	// Stack
+	Stack<int> nums1;
+	nums1.push(1);
+	nums1.push(2);
+	nums1.push(3);
+	for (unsigned i = 0; i < 3; i++) {
+		std::cout << nums1.top() << ", ";
+		nums1.pop();
+	}
+	nums1.push(4);
+	std::cout << nums1.top() << std::endl;
+
+	// Queue
+	Queue<int> nums2;
+	nums2.push(1);
+	nums2.push(2);
+	nums2.push(3);
+	for (unsigned i = 0; i < 3; i++) {
+		std::cout << nums2.front() << ", ";
+		nums2.pop();
+	}
+	nums2.push(4);
+	std::cout << nums2.front() << std::endl;
+
+	// Linked List
+	LinkedList<int> nums3;
+	nums3.push_front(1);
+	nums3.push_back(3);
+	nums3.push_at(1, 2);
+	for (int& i : nums3)
+		std::cout << i << ", ";
+	std::cout << std::endl;
+
+	LinkedList<int> nums4;
+	nums4.push_back(1);
+	nums4.push_back(2);
+	nums4.push_back(3);
+	nums4.push_front(5);
+	nums4.push_back(5);
+	nums4.push_at(2, 5);
+	nums4.pop_at(2);
+	nums4.pop_front();
+	nums4.pop_back();
+	for (const int& i : nums4)
+		std::cout << i << ", ";
+	std::cout << std::endl;
+}