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
|
#ifndef TIBIA_PRIORITY_QUEUE_HH_
#define TIBIA_PRIORITY_QUEUE_HH_ 1
#include "main.hh"
#include "vector.hh"
template<typename K, typename T>
struct priority_queue_entry{
K Key;
T Data;
};
template<typename K, typename T>
struct priority_queue{
// REGULAR FUNCTIONS
// =========================================================================
priority_queue(int capacity, int increment){
Entry = new vector<priority_queue_entry<K, T>>(1, capacity, increment);
Entries = 0;
}
// TODO(fusion): Probably missing some inlined destructor?
void insert(K Key, T *Data){
this->Entries += 1;
int CurrentIndex = this->Entries;
*this->Entry->at(CurrentIndex) = {Key, *Data};
while(CurrentIndex > 1){
int ParentIndex = CurrentIndex / 2;
priority_queue_entry<K, T> *Current = this->Entry->at(CurrentIndex);
priority_queue_entry<K, T> *Parent = this->Entry->at(ParentIndex);
if(Parent->Key <= Current->Key)
break;
std::swap(*Current, *Parent);
CurrentIndex = ParentIndex;
}
}
void deleteMin(void){
if(this->Entries < 1){
error("priority_queue::deleteMin: Warteschlange ist leer.\n");
return;
}
if(this->Entries > 1){
int CurrentIndex = 1;
int LastIndex = this->Entries;
std::swap(*this->Entry->at(CurrentIndex),
*this->Entry->at(LastIndex));
// TODO(fusion): This may be an oversight but the decompiled version
// checks in the loop below would INCLUDE `LastIndex`, which I assume
// is a bug? The first and last elements were just swapped and what
// was the first element in the queue is now at the end and should be
// considered "removed".
while(1){
int SmallestIndex = CurrentIndex * 2;
if(SmallestIndex >= LastIndex){
break;
}
priority_queue_entry<K, T> *Smallest = this->Entry->at(SmallestIndex);
if((SmallestIndex + 1) < LastIndex){
priority_queue_entry<K, T> *Other = this->Entry->at(SmallestIndex + 1);
if(Other->Key < Smallest->Key){
Smallest = Other;
SmallestIndex += 1;
}
}
priority_queue_entry<K, T> *Current = this->Entry->at(CurrentIndex);
if(Current->Key <= Smallest->Key){
break;
}
std::swap(*Current, *Smallest);
CurrentIndex = SmallestIndex;
}
}
this->Entries -= 1;
}
// DATA
// =========================================================================
vector<priority_queue_entry<K, T>> *Entry;
int Entries;
};
// TODO(fusion): We only use this structure two global queues:
// priority_queue<uint32, uint32> ToDoQueue(5000, 1000);
// priority_queue<uint32, TAttackWave*> AttackWaveQueue(100, 100);
#endif //TIBIA_PRIORITY_QUEUE_HH_
|
