|
alpar@222
|
1 |
/* FIXME: Copyright ...
|
|
alpar@222
|
2 |
*
|
|
alpar@222
|
3 |
* This implementation is heavily based on STL's heap functions and
|
|
alpar@222
|
4 |
* the similar class by Alpar Juttner in IKTA...
|
|
alpar@222
|
5 |
*/
|
|
alpar@222
|
6 |
|
|
alpar@222
|
7 |
/******
|
|
alpar@222
|
8 |
*
|
|
alpar@222
|
9 |
* BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]>
|
|
alpar@222
|
10 |
*
|
|
alpar@222
|
11 |
* Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot
|
|
alpar@222
|
12 |
* valosit meg.
|
|
alpar@222
|
13 |
* A kupacban legfolul mindig az a par talalhato, amiben az _ertek_ a
|
|
alpar@222
|
14 |
* legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
|
|
alpar@222
|
15 |
* lett keszitve...)
|
|
alpar@222
|
16 |
*
|
|
alpar@222
|
17 |
* Megjegyzes: egy kicsit gyanus nekem, hogy a kupacos temakorben nem
|
|
alpar@222
|
18 |
* azt hivjak kulcsnak, amit most en annak nevezek. :) En olyan
|
|
alpar@222
|
19 |
* property_map -os ertelemben hasznalom.
|
|
alpar@222
|
20 |
*
|
|
alpar@222
|
21 |
* A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
|
|
alpar@222
|
22 |
* a kulcsokhoz egy int-et tud tarolni (ezzel tudom megkeresni az illeto
|
|
alpar@222
|
23 |
* elemet a kupacban a csokkentes es hasonlo muveletekhez).
|
|
alpar@222
|
24 |
* A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
|
|
alpar@222
|
25 |
* is elnie kell. (???)
|
|
alpar@222
|
26 |
*
|
|
alpar@222
|
27 |
* Ketfele modon hasznalhato:
|
|
alpar@222
|
28 |
* Lusta mod:
|
|
alpar@222
|
29 |
* put(Key, Value) metodussal pakolunk a kupacba,
|
|
alpar@222
|
30 |
* aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
|
|
alpar@222
|
31 |
* csokkentettunk-e rajta, vagy noveltunk.
|
|
alpar@222
|
32 |
* Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
|
|
alpar@222
|
33 |
* minden szobajovo kulcs ertekre, -1 -es ertekkel!
|
|
alpar@222
|
34 |
* Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
|
|
alpar@222
|
35 |
* (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
|
|
alpar@222
|
36 |
* mar kikerult a kupacbol POST_HEAP=-2).
|
|
alpar@222
|
37 |
* Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
|
|
alpar@222
|
38 |
* meg meg tudja mondani a "legkisebb" erteku elemet. De csak nagyjabol,
|
|
alpar@222
|
39 |
* hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
|
|
alpar@222
|
40 |
*
|
|
alpar@222
|
41 |
* Kozvetlen mod:
|
|
alpar@222
|
42 |
* push(Key, Value) metodussal belerakunk a kupacba (ha az illeto kulcs mar
|
|
alpar@222
|
43 |
* benn volt, akkor gaz).
|
|
alpar@222
|
44 |
* increase/decrease(Key k, Value new_value) metodusokkal lehet
|
|
alpar@222
|
45 |
* novelni/csokkenteni az illeto kulcshoz tartozo erteket. (Ha nem volt meg
|
|
alpar@222
|
46 |
* benne a kupacban az illeto kulcs, vagy nem abba az iranyba valtoztattad
|
|
alpar@222
|
47 |
* az erteket, amerre mondtad -- gaz).
|
|
alpar@222
|
48 |
*
|
|
alpar@222
|
49 |
* Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
|
|
alpar@222
|
50 |
* Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
|
|
alpar@222
|
51 |
* hasznal. :-))
|
|
alpar@222
|
52 |
*
|
|
alpar@222
|
53 |
*
|
|
alpar@222
|
54 |
* Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
|
|
alpar@222
|
55 |
*
|
|
alpar@222
|
56 |
*/
|
|
alpar@222
|
57 |
|
|
alpar@222
|
58 |
|
|
alpar@222
|
59 |
#ifndef BIN_HEAP_HH
|
|
alpar@222
|
60 |
#define BIN_HEAP_HH
|
|
alpar@222
|
61 |
|
|
alpar@242
|
62 |
///\file
|
|
alpar@242
|
63 |
///\brief Binary Heap implementation.
|
|
alpar@242
|
64 |
|
|
alpar@222
|
65 |
#include <vector>
|
|
alpar@222
|
66 |
#include <utility>
|
|
alpar@222
|
67 |
#include <functional>
|
|
alpar@222
|
68 |
|
|
alpar@222
|
69 |
namespace hugo {
|
|
alpar@222
|
70 |
|
|
alpar@224
|
71 |
/// A Binary Heap implementation.
|
|
alpar@222
|
72 |
template <typename Key, typename Val, typename KeyIntMap,
|
|
alpar@222
|
73 |
typename Compare = std::less<Val> >
|
|
alpar@222
|
74 |
class BinHeap {
|
|
alpar@222
|
75 |
|
|
alpar@222
|
76 |
public:
|
|
alpar@222
|
77 |
typedef Key KeyType;
|
|
alpar@222
|
78 |
// FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
|
|
alpar@222
|
79 |
typedef Val ValueType;
|
|
alpar@222
|
80 |
typedef std::pair<KeyType,ValueType> PairType;
|
|
alpar@222
|
81 |
typedef KeyIntMap KeyIntMapType;
|
|
alpar@222
|
82 |
typedef Compare ValueCompare;
|
|
alpar@222
|
83 |
|
|
alpar@222
|
84 |
/**
|
|
alpar@222
|
85 |
* Each Key element have a state associated to it. It may be "in heap",
|
|
alpar@222
|
86 |
* "pre heap" or "post heap". The later two are indifferent from the
|
|
alpar@222
|
87 |
* heap's point of view, but may be useful to the user.
|
|
alpar@222
|
88 |
*
|
|
alpar@222
|
89 |
* The KeyIntMap _should_ be initialized in such way, that it maps
|
|
alpar@222
|
90 |
* PRE_HEAP (-1) to any element to be put in the heap...
|
|
alpar@222
|
91 |
*/
|
|
alpar@222
|
92 |
///\todo it is used nowhere
|
|
alpar@222
|
93 |
///
|
|
alpar@222
|
94 |
enum state_enum {
|
|
alpar@222
|
95 |
IN_HEAP = 0,
|
|
alpar@222
|
96 |
PRE_HEAP = -1,
|
|
alpar@222
|
97 |
POST_HEAP = -2
|
|
alpar@222
|
98 |
};
|
|
alpar@222
|
99 |
|
|
alpar@222
|
100 |
private:
|
|
alpar@222
|
101 |
std::vector<PairType> data;
|
|
alpar@222
|
102 |
Compare comp;
|
|
alpar@222
|
103 |
// FIXME: jo ez igy???
|
|
alpar@222
|
104 |
KeyIntMap &kim;
|
|
alpar@222
|
105 |
|
|
alpar@222
|
106 |
public:
|
|
alpar@222
|
107 |
BinHeap(KeyIntMap &_kim) : kim(_kim) {}
|
|
alpar@222
|
108 |
BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
|
|
alpar@222
|
109 |
|
|
alpar@222
|
110 |
|
|
alpar@222
|
111 |
int size() const { return data.size(); }
|
|
alpar@222
|
112 |
bool empty() const { return data.empty(); }
|
|
alpar@222
|
113 |
|
|
alpar@222
|
114 |
private:
|
|
alpar@222
|
115 |
static int parent(int i) { return (i-1)/2; }
|
|
alpar@222
|
116 |
static int second_child(int i) { return 2*i+2; }
|
|
alpar@222
|
117 |
bool less(const PairType &p1, const PairType &p2) {
|
|
alpar@222
|
118 |
return comp(p1.second, p2.second);
|
|
alpar@222
|
119 |
}
|
|
alpar@222
|
120 |
|
|
alpar@222
|
121 |
int bubble_up(int hole, PairType p);
|
|
alpar@222
|
122 |
int bubble_down(int hole, PairType p, int length);
|
|
alpar@222
|
123 |
|
|
alpar@222
|
124 |
void move(const PairType &p, int i) {
|
|
alpar@222
|
125 |
data[i] = p;
|
|
alpar@222
|
126 |
kim.set(p.first, i);
|
|
alpar@222
|
127 |
}
|
|
alpar@222
|
128 |
|
|
alpar@222
|
129 |
void rmidx(int h) {
|
|
alpar@222
|
130 |
int n = data.size()-1;
|
|
alpar@222
|
131 |
if( h>=0 && h<=n ) {
|
|
alpar@222
|
132 |
kim.set(data[h].first, POST_HEAP);
|
|
alpar@222
|
133 |
if ( h<n ) {
|
|
alpar@222
|
134 |
bubble_down(h, data[n], n);
|
|
alpar@222
|
135 |
}
|
|
alpar@222
|
136 |
data.pop_back();
|
|
alpar@222
|
137 |
}
|
|
alpar@222
|
138 |
}
|
|
alpar@222
|
139 |
|
|
alpar@222
|
140 |
public:
|
|
alpar@222
|
141 |
void push(const PairType &p) {
|
|
alpar@222
|
142 |
int n = data.size();
|
|
alpar@222
|
143 |
data.resize(n+1);
|
|
alpar@222
|
144 |
bubble_up(n, p);
|
|
alpar@222
|
145 |
}
|
|
alpar@222
|
146 |
void push(const Key &k, const Val &v) { push(PairType(k,v)); }
|
|
alpar@222
|
147 |
|
|
alpar@222
|
148 |
Key top() const {
|
|
alpar@222
|
149 |
// FIXME: test size>0 ?
|
|
alpar@222
|
150 |
return data[0].first;
|
|
alpar@222
|
151 |
}
|
|
alpar@222
|
152 |
Val topValue() const {
|
|
alpar@222
|
153 |
// FIXME: test size>0 ?
|
|
alpar@222
|
154 |
return data[0].second;
|
|
alpar@222
|
155 |
}
|
|
alpar@222
|
156 |
|
|
alpar@222
|
157 |
void pop() {
|
|
alpar@222
|
158 |
rmidx(0);
|
|
alpar@222
|
159 |
}
|
|
alpar@222
|
160 |
|
|
alpar@222
|
161 |
void erase(const Key &k) {
|
|
alpar@222
|
162 |
rmidx(kim[k]);
|
|
alpar@222
|
163 |
}
|
|
alpar@222
|
164 |
|
|
alpar@222
|
165 |
Val operator[](const Key &k) const {
|
|
alpar@222
|
166 |
int idx = kim[k];
|
|
alpar@222
|
167 |
return data[idx].second;
|
|
alpar@222
|
168 |
}
|
|
alpar@222
|
169 |
|
|
alpar@222
|
170 |
void put(const Key &k, const Val &v) {
|
|
alpar@222
|
171 |
int idx = kim[k];
|
|
alpar@222
|
172 |
if( idx < 0 ) {
|
|
alpar@222
|
173 |
push(k,v);
|
|
alpar@222
|
174 |
}
|
|
alpar@222
|
175 |
else if( comp(v, data[idx].second) ) {
|
|
alpar@222
|
176 |
bubble_up(idx, PairType(k,v));
|
|
alpar@222
|
177 |
}
|
|
alpar@222
|
178 |
else {
|
|
alpar@222
|
179 |
bubble_down(idx, PairType(k,v), data.size());
|
|
alpar@222
|
180 |
}
|
|
alpar@222
|
181 |
}
|
|
alpar@222
|
182 |
|
|
alpar@222
|
183 |
void decrease(const Key &k, const Val &v) {
|
|
alpar@222
|
184 |
int idx = kim[k];
|
|
alpar@222
|
185 |
bubble_up(idx, PairType(k,v));
|
|
alpar@222
|
186 |
}
|
|
alpar@222
|
187 |
void increase(const Key &k, const Val &v) {
|
|
alpar@222
|
188 |
int idx = kim[k];
|
|
alpar@222
|
189 |
bubble_down(idx, PairType(k,v), data.size());
|
|
alpar@222
|
190 |
}
|
|
alpar@222
|
191 |
|
|
alpar@222
|
192 |
state_enum state(const Key &k) const {
|
|
alpar@222
|
193 |
int s = kim[k];
|
|
alpar@222
|
194 |
if( s>=0 )
|
|
alpar@222
|
195 |
s=0;
|
|
alpar@222
|
196 |
return state_enum(s);
|
|
alpar@222
|
197 |
}
|
|
alpar@222
|
198 |
|
|
alpar@222
|
199 |
}; // class BinHeap
|
|
alpar@222
|
200 |
|
|
alpar@222
|
201 |
|
|
alpar@222
|
202 |
template <typename K, typename V, typename M, typename C>
|
|
alpar@222
|
203 |
int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
|
|
alpar@222
|
204 |
int par = parent(hole);
|
|
alpar@222
|
205 |
while( hole>0 && less(p,data[par]) ) {
|
|
alpar@222
|
206 |
move(data[par],hole);
|
|
alpar@222
|
207 |
hole = par;
|
|
alpar@222
|
208 |
par = parent(hole);
|
|
alpar@222
|
209 |
}
|
|
alpar@222
|
210 |
move(p, hole);
|
|
alpar@222
|
211 |
return hole;
|
|
alpar@222
|
212 |
}
|
|
alpar@222
|
213 |
|
|
alpar@222
|
214 |
template <typename K, typename V, typename M, typename C>
|
|
alpar@222
|
215 |
int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
|
|
alpar@222
|
216 |
int child = second_child(hole);
|
|
alpar@222
|
217 |
while(child < length) {
|
|
alpar@222
|
218 |
if( less(data[child-1], data[child]) ) {
|
|
alpar@222
|
219 |
--child;
|
|
alpar@222
|
220 |
}
|
|
alpar@222
|
221 |
if( !less(data[child], p) )
|
|
alpar@222
|
222 |
goto ok;
|
|
alpar@222
|
223 |
move(data[child], hole);
|
|
alpar@222
|
224 |
hole = child;
|
|
alpar@222
|
225 |
child = second_child(hole);
|
|
alpar@222
|
226 |
}
|
|
alpar@222
|
227 |
child--;
|
|
alpar@222
|
228 |
if( child<length && less(data[child], p) ) {
|
|
alpar@222
|
229 |
move(data[child], hole);
|
|
alpar@222
|
230 |
hole=child;
|
|
alpar@222
|
231 |
}
|
|
alpar@222
|
232 |
ok:
|
|
alpar@222
|
233 |
move(p, hole);
|
|
alpar@222
|
234 |
return hole;
|
|
alpar@222
|
235 |
}
|
|
alpar@222
|
236 |
|
|
alpar@222
|
237 |
} // namespace hugo
|
|
alpar@222
|
238 |
|
|
alpar@222
|
239 |
#endif // BIN_HEAP_HH
|