Solved dimitriev hw (sem 10, ex2)

3 files changed, 319 insertions, 0 deletions

diff --git a/Year 1/Object-oriented Programming/Solutions Sem. 10/ex2/Queue.hpp b/Year 1/Object-oriented Programming/Solutions Sem. 10/ex2/Queue.hpp
new file mode 100644
index 0000000..ff3fc11
--- /dev/null
+++ b/Year 1/Object-oriented Programming/Solutions Sem. 10/ex2/Queue.hpp
@@ -0,0 +1,150 @@
+#include <iostream>
+#include <exception>
+template <typename T>
+class MyQueue // Копие от GitHub, качвам го за твое удобство
+{
+	T* data;
+	size_t capacity;
+	size_t size;
+
+	size_t get;
+	size_t put;
+
+	void resize();
+
+	void copyFrom(const MyQueue<T>& other);
+	void free();
+public:
+	MyQueue();
+	
+	MyQueue(const MyQueue<T>& other);
+	MyQueue<T>& operator=(const MyQueue<T>& other);
+
+	void push(const T& obj);
+	void push(T&& obj); //позволява и местене
+	void pop();
+
+	const T& peek() const;
+	bool isEmpty() const;
+
+	~MyQueue();
+
+};
+
+template <typename T>
+MyQueue<T>::MyQueue()
+{
+	capacity = 4;
+	data = new T[capacity];
+	size = 0;
+	get = put = 0;
+}
+
+template <typename T>
+void MyQueue<T>::push(const T& obj)
+{
+	if (size == capacity)
+		resize();
+
+	data[put] = obj; //operator=
+	(++put) %= capacity;
+	size++;
+}
+
+template <typename T>
+void MyQueue<T>::push(T&& obj)
+{
+	if (size == capacity)
+		resize();
+
+	data[put] = obj; //move operator =
+	(++put) %= capacity;
+	size++;
+}
+
+template <typename T>
+bool MyQueue<T>::isEmpty() const
+{
+	return size == 0;
+}
+
+
+template <typename T>
+const T& MyQueue<T>::peek() const
+{
+	if (isEmpty())
+		throw std::logic_error("Empty queue!");
+
+	return data[get];
+}
+
+template <typename T>
+void MyQueue<T>::pop()
+{
+	if (isEmpty())
+		throw std::logic_error("Empty queue!");
+	(++get) %= capacity;
+	size--;
+}
+
+template <typename T>
+void MyQueue<T>::resize()
+{
+	T* resizedData = new T[capacity * 2];
+	for (size_t i = 0; i < size; i++)
+	{
+		resizedData[i] = data[get];
+		(++get) %= capacity;
+	}
+	capacity *= 2;
+	delete[] data;
+	data = resizedData;
+	get = 0;
+	put = size;
+}
+
+
+template <typename T>
+void MyQueue<T>::copyFrom(const MyQueue<T>& other)
+{
+	data = new T[other.capacity];
+	for (int i = 0; i < other.capacity; i++)
+		data[i] = other.data[i];
+
+	get = other.get;
+	put = other.put;
+
+	size = other.size;
+	capacity = other.capacity;
+
+}
+
+template <typename T>
+void MyQueue<T>::free()
+{
+	delete[] data;
+}
+
+template <typename T>
+MyQueue<T>::MyQueue(const MyQueue<T>& other)
+{
+	copyFrom(other);
+
+}
+
+template <typename T>
+MyQueue<T>& MyQueue<T>::operator=(const MyQueue<T>& other)
+{
+	if (this != &other)
+	{
+		free();
+		copyFrom(other);
+	}
+	return *this;
+}
+
+template <typename T>
+MyQueue<T>::~MyQueue()
+{
+	free();
+}
diff --git a/Year 1/Object-oriented Programming/Solutions Sem. 10/ex2/kPriorityQueue.hpp b/Year 1/Object-oriented Programming/Solutions Sem. 10/ex2/kPriorityQueue.hpp
new file mode 100644
index 0000000..14cdcc4
--- /dev/null
+++ b/Year 1/Object-oriented Programming/Solutions Sem. 10/ex2/kPriorityQueue.hpp
@@ -0,0 +1,140 @@
+#include "Queue.hpp"
+#include <stdexcept>
+
+template <typename T>
+class kPriorityQueue
+{
+	MyQueue<T>* priorities;
+	size_t size;
+	size_t largestPriority; // за да може peek да се изпълни за константно време
+
+	void free();
+	void copyFrom(const kPriorityQueue<T>& other);
+public:
+	kPriorityQueue(size_t k);
+
+	void push(const T& obj, size_t kth);
+	void push(T&& obj, size_t kth);
+	void pop();
+
+	const T& peek() const;
+	bool isEmpty() const;
+
+	kPriorityQueue();
+	kPriorityQueue(const kPriorityQueue<T>& other);
+	kPriorityQueue<T>& operator=(const kPriorityQueue<T>& other);
+	~kPriorityQueue();
+};
+
+template <typename T>
+kPriorityQueue<T>::kPriorityQueue(size_t k)
+{
+	size = k;
+	priorities = new MyQueue<T>[size];
+	largestPriority = size - 1;
+}
+
+
+template <typename T>
+void kPriorityQueue<T>::push(const T& obj, size_t kth)
+{
+	if (kth >= size)
+		throw std::invalid_argument("Error! No such priority!");
+
+	priorities[kth].push(obj);
+	if (kth > largestPriority)
+		largestPriority = kth;
+}
+
+template <typename T>
+void kPriorityQueue<T>::push(T&& obj, size_t kth)
+{
+	if (kth >= size)
+		throw std::invalid_argument("Error! No such priority!");
+
+	priorities[kth].push(obj);
+	if (kth > largestPriority)
+		largestPriority = kth;
+}
+
+template <typename T>
+void kPriorityQueue<T>::pop()
+{
+	if (isEmpty())
+		throw std::logic_error("Empty priority queue!");
+
+	bool success = false;
+	while (!success)
+	{
+		try
+		{
+			priorities[largestPriority].pop();
+			success = true;
+			
+			if (priorities[largestPriority].isEmpty())
+				largestPriority--;
+		}
+		catch (std::logic_error e)
+		{
+			largestPriority--;
+		}
+	}
+}
+
+
+template <typename T>
+const T& kPriorityQueue<T>::peek() const
+{
+	return priorities[largestPriority].peek();
+}
+
+template <typename T>
+bool kPriorityQueue<T>::isEmpty() const
+{
+	return size == 0;
+}
+
+
+template <typename T>
+kPriorityQueue<T>::kPriorityQueue() : kPriorityQueue(1)
+{}
+
+template <typename T>
+kPriorityQueue<T>::kPriorityQueue(const kPriorityQueue<T>& other)
+{
+	copyFrom(other);
+}
+
+template <typename T>
+kPriorityQueue<T>& kPriorityQueue<T>::operator=(const kPriorityQueue<T>& other)
+{
+	if (this != &other)
+	{
+		free();
+		copyFrom(other);
+	}
+	return *this;
+}
+
+template <typename T>
+kPriorityQueue<T>::~kPriorityQueue<T>()
+{
+	free();
+}
+
+
+template <typename T>
+void kPriorityQueue<T>::free()
+{
+	delete[] priorities;
+}
+
+template <typename T>
+void kPriorityQueue<T>::copyFrom(const kPriorityQueue<T>& other)
+{
+	priorities = new MyQueue<T>[other.size];
+	for (size_t i = 0; i < other.size; i++)
+		priorities[i] = other.priorities[i];
+	size = other.size;
+	largestPriority = other.largestPriority;
+}
diff --git a/Year 1/Object-oriented Programming/Solutions Sem. 10/ex2/main.cpp b/Year 1/Object-oriented Programming/Solutions Sem. 10/ex2/main.cpp
new file mode 100644
index 0000000..1dbdc8e
--- /dev/null
+++ b/Year 1/Object-oriented Programming/Solutions Sem. 10/ex2/main.cpp
@@ -0,0 +1,29 @@
+#include "kPriorityQueue.hpp"
+#include <iostream>
+
+int main()
+{
+	kPriorityQueue<char> q(5); // 5 priorities - 0, 1, 2, 3 and 4
+  
+	q.push('A',0); //adds A with lowest priority: 0
+	q.push('B',3);
+	q.push('C',2);
+	q.pop();
+	q.push('E',1);
+	q.push('D',2);
+	q.push('F',0);
+	q.push('G',3);
+	q.push('H',4);
+	q.pop();
+	q.push('I',1);
+	q.push('J',2);
+  
+	//q.push('F', 5); //error! No such priority!
+
+	// GCDJEIAF
+	for (int i = 0; i < 8; i++)
+	{
+		std::cout << q.peek();
+		q.pop();
+	}
+}