This repository has been archived by the owner on Aug 5, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpqueue2.h
220 lines (203 loc) · 6.72 KB
/
pqueue2.h
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <string>
#include <iostream>
#define ERSTESELEMENT 1
#define LETZTESELEMENT 2
#define UNBEKANNTESELEMENT 3
using namespace std;
class MyException {
private:
string _error;
public:
MyException(string error);
string msg();
};
template <typename T>
struct PriorityQueueEntry{
float priority;
T value;
PriorityQueueEntry(float getPriority, T getValue);
};
template <typename T>
class PriorityQueue {
private:
int _size;
int _last;
PriorityQueueEntry<T> **_entrys; // Array aus PriorityQueueEntry<T> Pointern
bool isFull(void);
bool isAlmostFull(void);
void changeArray(int Richtung);
void privateRemove( int toggle, T value); // Wird von extractMin und remove aufgerufen um sachen zu löschen
public:
PriorityQueue(int size = 100);
~PriorityQueue(void);
void insert(T value, float priority);
T extractMin(void);
void decreaseKey(T value, float priority);
void remove(T value); // Entscheid nur wo gelöscht werden muss
bool isEmpty(void);
void print();
};
MyException::MyException(string error) {
_error = error;
}
string MyException::msg() {
return _error;
}
template <typename T>
PriorityQueueEntry<T>::PriorityQueueEntry(float getPriority, T getValue) {
priority = getPriority;
value = getValue;
}
template <typename T>
PriorityQueue<T>::PriorityQueue(int size) {
_size = size;
_last = -1;
_entrys = new PriorityQueueEntry<T>*[size];
}
template <typename T>
PriorityQueue<T>::~PriorityQueue() {
for (int i = 0; i < _last ; i++) {
delete _entrys[i]; //Erst die Elemente im Array löschen
}
delete[] _entrys; // Array löschen
}
template <typename T>
void PriorityQueue<T>::changeArray(int richtung) { //Prüft und verändert die Größe des Arrays(1 => Vergrößerung, -1 => Verkleinerung)
if (richtung == 1) {
if (isAlmostFull()) {
PriorityQueueEntry<T> **newArray = new PriorityQueueEntry<T>*[_size * 2];
for (int arraysize = 0; arraysize <= _last ; arraysize++) {
newArray[arraysize] = _entrys[arraysize];
}
delete[](_entrys);
_size *= 2;
_entrys = newArray;
}
} else if (richtung == -1) {
if ((_last+1) * 4 < _size) {
PriorityQueueEntry<T> **newArray = new PriorityQueueEntry<T>*[_size / 2];
for (int arraysize = 0; arraysize <= _last ; arraysize++) {
newArray[arraysize] = _entrys[arraysize];
}
delete[](_entrys);
_size /= 2;
_entrys = newArray;
}
} else {
return;
}
}
template <typename T>
bool PriorityQueue<T>::isFull() {
return _last == (_size - 1);
}
template <typename T>
bool PriorityQueue<T>::isAlmostFull() {
return _last > (_size - 2);
}
template <typename T>
bool PriorityQueue<T>::isEmpty() {
return _last == -1;
}
template <typename T>
void PriorityQueue<T>::insert(T value, float priority) {
changeArray(1);
if (_last == -1) { // ARRAY ist leer. Element kann vorne eingefügt werden
_last += 1;
_entrys[_last] = new PriorityQueueEntry<T>(priority,value);
} else {
int i = 1;
if (priority < _entrys[0]->priority) {// An Erste Position einfügen. Restliches Array 1 nach hinten schieben
for (int arraysize = _last; arraysize >= 0; arraysize--) {
_entrys[arraysize + 1] = _entrys[arraysize];
}
_entrys[0] = new PriorityQueueEntry<T>(priority, value);
_last += 1;
} else if (priority > _entrys[_last]->priority) { // An letzte Position einfügen.
_last += 1;
_entrys[_last] = new PriorityQueueEntry<T>(priority, value);
} else { // Irgendwo einfügen. Position + restlichen 1 nach hinten schieben.
while (_entrys[i]->priority < priority) {
i++;
}
if (priority > _entrys[_last]->priority) {
throw MyException("Element konnte nicht eingefügt werden");
}
for (int arraysize = _last; arraysize >= i; arraysize--) {
_entrys[arraysize + 1] = _entrys[arraysize];
}
_entrys[i] = new PriorityQueueEntry<T>(priority, value);
_last += 1;
}
}
}
template <typename T>
T PriorityQueue<T>::extractMin() {
T ret;
if(_last == -1) { // ARRAY ist lerr
throw MyException("Bitte erst das Array mit Inhalt befüllen");
}
ret = _entrys[0]->value; //Value zwischen speichern
privateRemove(ERSTESELEMENT, ""); // Remove aufrufen um 1. Element zu löschen.
return ret;
}
template <typename T>
void PriorityQueue<T>::privateRemove(int toggle, T value) {
if (_last == -1) {
throw MyException("Das Array ist leer.");
}
int i = 0;
switch(toggle) { // Aufgabe von remove und extractMin übernehmen
case ERSTESELEMENT:
delete _entrys[0]; // Array nach vorne schieben
for (int arraysize = 0; arraysize < _last; arraysize++ ) {
_entrys[arraysize] = _entrys[arraysize + 1];
}
break;
case LETZTESELEMENT:
delete _entrys[_last];
break;
case UNBEKANNTESELEMENT: //Element suchen und löschen + Array nach vorne verschieben
i = 0;
while(_entrys[i]->value != value && i < _last) {
i++;
}
if (_entrys[i]->value != value) {
throw MyException("Das Element wurde nicht gefunden.");
}
delete _entrys[i];
for (int arraysize = i; arraysize < _last; arraysize++) {
_entrys[arraysize] = _entrys[arraysize+1];
}
break;
default:
break;
}
_last -= 1;
changeArray(-1); // Prüfen ob Speicher gespart werden kann
}
template <typename T>
void PriorityQueue<T>::remove(T value) {
if (_entrys[0]->value == value) {
privateRemove(ERSTESELEMENT, ""); // Erstes Element löschen lassen
} else if(_entrys[_last]->value == value) {
privateRemove(LETZTESELEMENT, ""); // Letztes Element löschen lassen
} else {
privateRemove(UNBEKANNTESELEMENT, value); //Unbekanntes Element in privateRemove löschen lassen
}
}
template <typename T>
void PriorityQueue<T>::decreaseKey(T value, float priority) {
remove(value); // Altes Element löschen
insert(value,priority); // Element mit neuer Priorität wieder einfügen
}
template <typename T>
void PriorityQueue<T>::print() { // Array ausgabe.
for(int i = 0; i < _size;i++) {
if (i <= _last) {
cout << _entrys[i]->value << " " << _entrys[i]->priority << " " <<_entrys[i] << endl;
} else {
cout << _entrys[i] << endl;
}
}
}