[SDP/P] Initial solution to first exercise in project

2 files changed, 340 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/Project/exa/SkipList.hpp b/Year 2/Structures and data algorithms/Project/exa/SkipList.hpp
new file mode 100644
index 0000000..f124516
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Project/exa/SkipList.hpp
@@ -0,0 +1,302 @@
+#ifndef SKIPLIST
+#define SKIPLIST
+
+#include <istream>
+#include <ostream>
+#include <stack>
+
+template <class T>
+class SkipList {
+	struct Node {
+		Node* next;
+		Node* skip;
+		T value;
+
+		Node(const T& value, Node* next = nullptr, Node* skip = nullptr) : next(next), skip(skip), value(value) {}
+	};
+
+	Node* head;
+	Node* tail;
+	unsigned listSize;
+
+	void copyFrom(const SkipList&);
+	void free();
+
+	Node* findNode(const T&);
+	bool recShortSublist(Node*, SkipList<T>&, std::stack<T>&);
+
+public:
+	std::stack<T> shortestSublistIncluding(SkipList<T>&);
+
+	void push(const T& elem);
+	bool addSkip(const T&, const T&);
+	T pop();
+	T& front();
+
+	unsigned size();
+	bool empty();
+
+	std::istream& operator>>(std::istream& istr);
+	std::ostream& print(std::ostream& ostr);
+
+	class Iterator {
+		Node* current;
+		Iterator(Node* start) : current(start) {}
+
+	public:
+		Iterator& operator++() {
+			if (current != nullptr)
+				current = current->next;
+			return *this;
+		}
+
+		Iterator& operator++(int) {
+			Iterator toRet = *this;
+			++(*this);
+			return toRet;
+		}
+
+		T& operator*() {
+			return current->value;
+		}
+
+		bool operator==(const Iterator& other) const {
+			return current == other.current;
+		}
+
+		bool operator!=(const Iterator& other) const {
+			return !(*this == other);
+		}
+
+		friend class SkipList;
+	};
+	Iterator begin();
+	Iterator end();
+
+	SkipList();
+	SkipList(const SkipList&);
+	SkipList& operator=(const SkipList&);
+	~SkipList();
+
+	SkipList(SkipList&&);
+	SkipList& operator=(SkipList&&);
+};
+
+/*
+ * Exercise functionality
+ */
+
+#include <iostream>
+
+template <class T>
+bool SkipList<T>::recShortSublist(Node* current, SkipList<T>& search, std::stack<T>& out) {
+	if (current == nullptr) return false;
+
+	out.push(current->value);
+
+	if (current->value == search.front()) {
+		search.pop();
+		if (search.empty()) return true;
+	}
+
+	if (!recShortSublist(current->skip, search, out) && !recShortSublist(current->next, search, out)) {
+		out.pop();
+		return false;
+	}
+	return true;
+}
+
+template <class T>
+std::stack<T> SkipList<T>::shortestSublistIncluding(SkipList<T>& locs) {
+	std::stack<T> out;
+	recShortSublist(head, locs, out);
+	return out;
+}
+
+/*
+ * SkipList functionality
+ */
+
+/* Private functions */
+
+template <class T>
+typename SkipList<T>::Node* SkipList<T>::findNode(const T& value) {
+	Node* start = head;
+	while (start != nullptr) {
+		if (start->value == value) return start;
+		start = start->next;
+	}
+	return nullptr;
+}
+
+/* Public functions */
+
+template <class T>
+void SkipList<T>::push(const T& elem) {
+	if (empty()) {
+		head = tail = new Node(elem);
+	}
+	else {
+		tail->next = new Node(elem);
+		tail = tail->next;
+	}
+	listSize++;
+}
+
+template <class T>
+bool SkipList<T>::addSkip(const T& start, const T& end) {
+	Node* from = findNode(start);
+	if (from == nullptr) return false;
+	Node* to = findNode(end);
+	if (to == nullptr) return false;
+
+	from->skip = to;
+	return true;
+}
+
+template <class T>
+T SkipList<T>::pop() {
+	if (empty())
+		throw "Pop called on empty SkipList!";
+
+	T val = head->value;
+	Node* oldHead = head;
+	head = head->next;
+	delete oldHead;
+	listSize--;
+	return val;
+}
+
+template <class T>
+T& SkipList<T>::front() {
+	if (empty())
+		throw "Front called on empty SkipList!";
+
+	return head->value;
+}
+
+template <class T>
+unsigned SkipList<T>::size() {
+	return listSize;
+}
+
+template <class T>
+bool SkipList<T>::empty() {
+	return listSize == 0;
+}
+
+template <class T>
+std::istream& SkipList<T>::operator>>(std::istream& istr) {
+	return istr; // TODO
+}
+
+template <class T>
+std::ostream& SkipList<T>::print(std::ostream& ostr) {
+	for (Node* i = head; i != nullptr; i = i->next) {
+		ostr << i->value << ", ";
+		if (i->skip != nullptr)
+			ostr << i->skip->value;
+		ostr << "; ";
+	}
+	return ostr;
+}
+
+/*
+ * Iterators
+ */
+
+template <class T>
+typename SkipList<T>::Iterator SkipList<T>::begin() {
+	return Iterator(head);
+}
+
+template <class T>
+typename SkipList<T>::Iterator SkipList<T>::end() {
+	return Iterator(nullptr);
+}
+
+/* 
+ * Rule of 6
+ */
+
+template <class T>
+void SkipList<T>::copyFrom(const SkipList& other) {
+	Node* newHead = new Node(other.head->value);
+	Node*& newTail = newHead->next;
+
+	T** skips = new T*[other.size()];
+	skips[0] = newHead->skip;
+
+	for (Node* i = other.head->next, si = 1; i != nullptr; i = i->next, si++) {
+		newTail = new Node(i->value);
+		skips[si] = i->skip->value;
+		if (i->next != nullptr)
+			newTail = newTail->next;
+	}
+
+	head = newHead;
+	tail = newTail;
+	listSize = other.listSize();
+
+	for (unsigned i = 0; i < other.size(); i++) {
+		newHead->skip = findNode(*skips[i]);
+	}
+	delete[] skips;
+}
+
+template <class T>
+void SkipList<T>::free() {
+	Node* n;
+	while (head != nullptr) {
+		n = head->next;
+		delete head;
+		head = n;
+	}
+}
+
+template <class T>
+SkipList<T>::SkipList() : head(nullptr), tail(nullptr), listSize(0) {}
+
+template <class T>
+SkipList<T>::SkipList(const SkipList& other) {
+	copyFrom(other);
+}
+
+template <class T>
+SkipList<T>& SkipList<T>::operator=(const SkipList& other) {
+	if (this != &other) {
+		free();
+		copyFrom(other);
+	}
+	return *this;
+}
+
+template <class T>
+SkipList<T>::~SkipList() {
+	free();
+}
+
+template <class T>
+SkipList<T>::SkipList(SkipList&& other) {
+	head = other.head;
+	tail = other.tail;
+	listSize = other.listSize;
+
+	other.head = other.tail = nullptr;
+}
+
+template <class T>
+SkipList<T>& SkipList<T>::operator=(SkipList&& other) {
+	if (this != &other) {
+		free();
+
+		head = other.head;
+		tail = other.tail;
+		listSize = other.listSize;
+
+		other.head = other.tail = nullptr;
+	}
+	return *this;
+}
+
+#endif
diff --git a/Year 2/Structures and data algorithms/Project/exa/main.cpp b/Year 2/Structures and data algorithms/Project/exa/main.cpp
new file mode 100644
index 0000000..1698a2c
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Project/exa/main.cpp
@@ -0,0 +1,38 @@
+#include "SkipList.hpp"
+#include <string>
+#include <iostream>
+
+int main() {
+	SkipList<std::string> cities;
+	cities.push("Sofia");
+	cities.push("Pazardzhik");
+	cities.push("Plovdiv");
+	cities.push("Dimitrovgrad");
+	cities.push("StaraZagora");
+	cities.push("NovaZagora");
+	cities.push("Yambol");
+	cities.push("Karnobat");
+	cities.push("Burgas");
+
+	cities.addSkip("Sofia", "Plovdiv");
+	cities.addSkip("Plovdiv", "NovaZagora");
+	cities.addSkip("Dimitrovgrad", "NovaZagora");
+	cities.addSkip("StaraZagora", "Yambol");
+	cities.addSkip("NovaZagora", "Burgas");
+
+	cities.print(std::cout) << std::endl;
+
+	SkipList<std::string> visit;
+	visit.push("Plovdiv");
+	visit.push("StaraZagora");
+	visit.push("Yambol");
+	visit.push("Burgas");
+	std::stack<std::string> path = cities.shortestSublistIncluding(visit);
+
+	while (!path.empty()) {
+		std::cout << path.top() << ", ";
+		path.pop();
+	}
+	std::cout << std::endl;
+	// path.print(std::cout) << std::endl;
+}