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
|
/* ScummVM - Graphic Adventure Engine
*
* ScummVM is the legal property of its developers, whose names
* are too numerous to list here. Please refer to the COPYRIGHT
* file distributed with this source distribution.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
*
* Based on the original sources
* Faery Tale II -- The Halls of the Dead
* (c) 1993-1996 The Wyrmkeep Entertainment Co.
*/
#ifndef SAGA2_PRIQUEUE_H
#define SAGA2_PRIQUEUE_H
namespace Saga2 {
template <class ITEM, int size>
class PriorityQueue {
int16 _tail; // end index of queue
ITEM _queue[size + 1];
static int16 parentIndex(int16 index) {
return index >> 1;
}
static int16 child1Index(int16 index) {
return index << 1;
}
static int16 child2Index(int16 index) {
return (index >> 1) + 1;
}
public:
PriorityQueue() { // constructor
_tail = 1;
}
bool insert(ITEM &newItem); // insert an item
bool remove(ITEM &result); // remove an item
void clear() {
_tail = 1; // clear the queue
}
int16 getCount() {
return _tail - 1;
}
};
// Function to insert an element into the queue
template <class ITEM, int size>
bool PriorityQueue<ITEM, size>::insert(ITEM &newItem) {
int16 index,
parentIndex,
newVal = (int)newItem;
ITEM *qi,
*parentItem;
if (_tail >= size + 1) return false;
for (index = _tail, qi = &_queue[index];
index > 1;
index = parentIndex, qi = parentItem) {
parentIndex = PriorityQueue::parentIndex(index);
parentItem = &_queue[parentIndex];
if ((int)*parentItem <= newVal) break;
*qi = *parentItem;
}
*qi = newItem;
_tail++;
return true;
}
// Function to remove the lowest element from the queue
template <class ITEM, int size>
bool PriorityQueue<ITEM, size>::remove(ITEM &result) {
ITEM *item = &_queue[1],
*child;
int16 itemNum = 1,
childNum,
tailVal;
if (_tail <= 1) return false;
result = *item;
_tail--;
tailVal = (int)_queue[_tail];
for (;;) {
childNum = child1Index(itemNum);
if (childNum >= _tail) break;
child = &_queue[childNum];
// Select the lowest of the two children
if (childNum + 1 < _tail
&& (int)child[0] > (int)child[1]) {
childNum++;
child++;
}
if ((int)*child >= tailVal) break;
*item = *child;
item = child;
itemNum = childNum;
}
if (itemNum != _tail) {
*item = _queue[_tail];
}
return true;
}
} // end of namepsace Saga2
#endif
|
