blob: 99d0372c4ff17db8e30a76694e0e6acee9cbc066 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#include <iostream>
#include "Queue.hpp"
#include <exception>
#ifndef K_PRIORITY_QUEUE
#define K_PRIORITY_QUEUE
template<typename T>
class kPriorityQueue
{
size_t maxPriority;
MyQueue<T>* queues;
void free();
void copyFrom(const kPriorityQueue<T> &other);
size_t elementsCount = 0;
public:
kPriorityQueue(size_t maxPriority);
kPriorityQueue(const kPriorityQueue<T>& other);
kPriorityQueue<T>& operator=(const kPriorityQueue<T>& other);
~kPriorityQueue();
void push(const T& obj, size_t priority);
void push(T&& obj, size_t priority);
void pop();
const T& peek() const;
bool isEmpty() const;
};
template<typename T>
void kPriorityQueue<T>::free()
{
delete[] queues;
}
template<typename T>
void kPriorityQueue<T>::copyFrom(const kPriorityQueue<T> &other)
{
this->maxPriority = maxPriority;
queues = new MyQueue<T>[maxPriority];
for (size_t i = 0; i < maxPriority; i++)
queues[i] = other.queues[i];
}
template<typename T>
kPriorityQueue<T>::kPriorityQueue(size_t maxPriority)
{
if (maxPriority == 0)
throw std::logic_error("Cannot create priority queue with no priorities");
this->maxPriority = maxPriority;
queues = new MyQueue<T>[maxPriority];
}
template<typename T>
kPriorityQueue<T>::kPriorityQueue(const kPriorityQueue<T> &other)
{
copyFrom();
}
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()
{
free();
}
template<typename T>
void kPriorityQueue<T>::push(const T &obj, size_t priority)
{
if (priority >= maxPriority)
throw std::logic_error("No such priority");
elementsCount++;
queues[priority].push(obj);
}
template<typename T>
void kPriorityQueue<T>::push(T &&obj, size_t priority)
{
if (priority >= maxPriority)
throw std::logic_error("No such priority");
elementsCount++;
queues[priority].push(std::move(obj));
}
template<typename T>
void kPriorityQueue<T>::pop()
{
if(isEmpty())
throw std::logic_error("Empty queue!");
for (int i = maxPriority - 1; i >= 0; i--)
{
if (!queues[i].isEmpty())
{
queues[i].pop();
elementsCount--;
return;
}
}
}
template<typename T>
const T& kPriorityQueue<T>::peek() const
{
for (int i = maxPriority - 1; i >= 0; i--)
{
if (!queues[i].isEmpty())
return queues[i].peek();
}
}
template<typename T>
bool kPriorityQueue<T>::isEmpty() const
{
return elementsCount == 0;
}
#endif
|
