|
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 |
|
59 #ifndef BIN_HEAP_HH |
|
60 #define BIN_HEAP_HH |
|
61 |
|
62 #include <vector> |
|
63 #include <utility> |
|
64 #include <functional> |
|
65 |
|
66 namespace hugo { |
|
67 |
|
68 template <typename Key, typename Val, typename KeyIntMap, |
|
69 typename Compare = std::less<Val> > |
|
70 class BinHeap { |
|
71 |
|
72 public: |
|
73 typedef Key KeyType; |
|
74 // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot... |
|
75 typedef Val ValueType; |
|
76 typedef std::pair<KeyType,ValueType> PairType; |
|
77 typedef KeyIntMap KeyIntMapType; |
|
78 typedef Compare ValueCompare; |
|
79 |
|
80 /** |
|
81 * Each Key element have a state associated to it. It may be "in heap", |
|
82 * "pre heap" or "post heap". The later two are indifferent from the |
|
83 * heap's point of view, but may be useful to the user. |
|
84 * |
|
85 * The KeyIntMap _should_ be initialized in such way, that it maps |
|
86 * PRE_HEAP (-1) to any element to be put in the heap... |
|
87 */ |
|
88 enum state_enum { |
|
89 IN_HEAP = 0, |
|
90 PRE_HEAP = -1, |
|
91 POST_HEAP = -2 |
|
92 }; |
|
93 |
|
94 private: |
|
95 std::vector<PairType> data; |
|
96 Compare comp; |
|
97 // FIXME: jo ez igy??? |
|
98 KeyIntMap &kim; |
|
99 |
|
100 public: |
|
101 BinHeap(KeyIntMap &_kim) : kim(_kim) {} |
|
102 BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {} |
|
103 |
|
104 |
|
105 int size() const { return data.size(); } |
|
106 bool empty() const { return data.empty(); } |
|
107 |
|
108 private: |
|
109 static int parent(int i) { return (i-1)/2; } |
|
110 static int second_child(int i) { return 2*i+2; } |
|
111 bool less(const PairType &p1, const PairType &p2) { |
|
112 return comp(p1.second, p2.second); |
|
113 } |
|
114 |
|
115 int bubble_up(int hole, PairType p); |
|
116 int bubble_down(int hole, PairType p, int length); |
|
117 |
|
118 void move(const PairType &p, int i) { |
|
119 data[i] = p; |
|
120 kim.set(p.first, i); |
|
121 } |
|
122 |
|
123 void rmidx(int h) { |
|
124 int n = data.size()-1; |
|
125 if( h>=0 && h<=n ) { |
|
126 kim.set(data[h].first, POST_HEAP); |
|
127 if ( h<n ) { |
|
128 bubble_down(h, data[n], n); |
|
129 } |
|
130 data.pop_back(); |
|
131 } |
|
132 } |
|
133 |
|
134 public: |
|
135 void push(const PairType &p) { |
|
136 int n = data.size(); |
|
137 data.resize(n+1); |
|
138 bubble_up(n, p); |
|
139 } |
|
140 void push(const Key &k, const Val &v) { push(PairType(k,v)); } |
|
141 |
|
142 Key top() const { |
|
143 // FIXME: test size>0 ? |
|
144 return data[0].first; |
|
145 } |
|
146 Val topValue() const { |
|
147 // FIXME: test size>0 ? |
|
148 return data[0].second; |
|
149 } |
|
150 |
|
151 void pop() { |
|
152 rmidx(0); |
|
153 } |
|
154 |
|
155 void erase(const Key &k) { |
|
156 rmidx(kim.get(k)); |
|
157 } |
|
158 |
|
159 const Val get(const Key &k) const { |
|
160 int idx = kim.get(k); |
|
161 return data[idx].second; |
|
162 } |
|
163 void put(const Key &k, const Val &v) { |
|
164 int idx = kim.get(k); |
|
165 if( idx < 0 ) { |
|
166 push(k,v); |
|
167 } |
|
168 else if( comp(v, data[idx].second) ) { |
|
169 bubble_up(idx, PairType(k,v)); |
|
170 } |
|
171 else { |
|
172 bubble_down(idx, PairType(k,v), data.size()); |
|
173 } |
|
174 } |
|
175 |
|
176 void decrease(const Key &k, const Val &v) { |
|
177 int idx = kim.get(k); |
|
178 bubble_up(idx, PairType(k,v)); |
|
179 } |
|
180 void increase(const Key &k, const Val &v) { |
|
181 int idx = kim.get(k); |
|
182 bubble_down(idx, PairType(k,v), data.size()); |
|
183 } |
|
184 |
|
185 state_enum state(const Key &k) const { |
|
186 int s = kim.get(k); |
|
187 if( s>=0 ) |
|
188 s=0; |
|
189 return state_enum(s); |
|
190 } |
|
191 |
|
192 }; // class BinHeap |
|
193 |
|
194 |
|
195 template <typename K, typename V, typename M, typename C> |
|
196 int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) { |
|
197 int par = parent(hole); |
|
198 while( hole>0 && less(p,data[par]) ) { |
|
199 move(data[par],hole); |
|
200 hole = par; |
|
201 par = parent(hole); |
|
202 } |
|
203 move(p, hole); |
|
204 return hole; |
|
205 } |
|
206 |
|
207 template <typename K, typename V, typename M, typename C> |
|
208 int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) { |
|
209 int child = second_child(hole); |
|
210 while(child < length) { |
|
211 if( less(data[child-1], data[child]) ) { |
|
212 --child; |
|
213 } |
|
214 if( !less(data[child], p) ) |
|
215 goto ok; |
|
216 move(data[child], hole); |
|
217 hole = child; |
|
218 child = second_child(hole); |
|
219 } |
|
220 child--; |
|
221 if( child<length && less(data[child], p) ) { |
|
222 move(data[child], hole); |
|
223 hole=child; |
|
224 } |
|
225 ok: |
|
226 move(p, hole); |
|
227 return hole; |
|
228 } |
|
229 |
|
230 } // namespace hugo |
|
231 |
|
232 #endif // BIN_HEAP_HH |