diff options
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(); + } +} |