|
1 /* FIXME: Copyright ... |
|
2 * |
|
3 * This implementation is heavily based on STL's heap functions and |
|
4 * the similar class by Alpar Juttner in IKTA... |
|
5 */ |
|
6 |
|
7 /****** |
|
8 * |
|
9 * BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]> |
|
10 * |
|
11 * Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot |
|
12 * valosit meg. |
|
13 * A kupacban legfolul mindig az a par talalhato, amiben az _ertek_ a |
|
14 * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz |
|
15 * lett keszitve...) |
|
16 * |
|
17 * Megjegyzes: egy kicsit gyanus nekem, hogy a kupacos temakorben nem |
|
18 * azt hivjak kulcsnak, amit most en annak nevezek. :) En olyan |
|
19 * property_map -os ertelemben hasznalom. |
|
20 * |
|
21 * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami |
|
22 * a kulcsokhoz egy int-et tud tarolni (ezzel tudom megkeresni az illeto |
|
23 * elemet a kupacban a csokkentes es hasonlo muveletekhez). |
|
24 * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek |
|
25 * is elnie kell. (???) |
|
26 * |
|
27 * Ketfele modon hasznalhato: |
|
28 * Lusta mod: |
|
29 * put(Key, Value) metodussal pakolunk a kupacba, |
|
30 * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor |
|
31 * csokkentettunk-e rajta, vagy noveltunk. |
|
32 * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen |
|
33 * minden szobajovo kulcs ertekre, -1 -es ertekkel! |
|
34 * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal: |
|
35 * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0, |
|
36 * mar kikerult a kupacbol POST_HEAP=-2). |
|
37 * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak |
|
38 * meg meg tudja mondani a "legkisebb" erteku elemet. De csak nagyjabol, |
|
39 * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk... |
|
40 * |
|
41 * Kozvetlen mod: |
|
42 * push(Key, Value) metodussal belerakunk a kupacba (ha az illeto kulcs mar |
|
43 * benn volt, akkor gaz). |
|
44 * increase/decrease(Key k, Value new_value) metodusokkal lehet |
|
45 * novelni/csokkenteni az illeto kulcshoz tartozo erteket. (Ha nem volt meg |
|
46 * benne a kupacban az illeto kulcs, vagy nem abba az iranyba valtoztattad |
|
47 * az erteket, amerre mondtad -- gaz). |
|
48 * |
|
49 * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni. |
|
50 * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac |
|
51 * hasznal. :-)) |
|
52 * |
|
53 * |
|
54 * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi) |
|
55 * |
|
56 */ |
|
57 |
|
58 |
1 #ifndef BIN_HEAP_HH |
59 #ifndef BIN_HEAP_HH |
2 #define BIN_HEAP_HH |
60 #define BIN_HEAP_HH |
3 |
61 |
4 #include <vector> |
62 #include <vector> |
5 #include <utility> |
63 #include <utility> |
112 bubble_up(idx, PairType(k,v)); |
170 bubble_up(idx, PairType(k,v)); |
113 } |
171 } |
114 void increase(const Key &k, const Val &v) { |
172 void increase(const Key &k, const Val &v) { |
115 int idx = kim.get(k); |
173 int idx = kim.get(k); |
116 bubble_down(idx, PairType(k,v), data.size()); |
174 bubble_down(idx, PairType(k,v), data.size()); |
|
175 } |
|
176 |
|
177 state_enum state(const Key &k) const { |
|
178 int s = kim.get(k); |
|
179 if( s>=0 ) |
|
180 s=0; |
|
181 return state_enum(s); |
117 } |
182 } |
118 |
183 |
119 }; // class BinHeap |
184 }; // class BinHeap |
120 |
185 |
121 |
186 |