|
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 ///\todo it is used nowhere |
|
89 /// |
|
90 enum state_enum { |
|
91 IN_HEAP = 0, |
|
92 PRE_HEAP = -1, |
|
93 POST_HEAP = -2 |
|
94 }; |
|
95 |
|
96 private: |
|
97 std::vector<PairType> data; |
|
98 Compare comp; |
|
99 // FIXME: jo ez igy??? |
|
100 KeyIntMap &kim; |
|
101 |
|
102 public: |
|
103 BinHeap(KeyIntMap &_kim) : kim(_kim) {} |
|
104 BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {} |
|
105 |
|
106 |
|
107 int size() const { return data.size(); } |
|
108 bool empty() const { return data.empty(); } |
|
109 |
|
110 private: |
|
111 static int parent(int i) { return (i-1)/2; } |
|
112 static int second_child(int i) { return 2*i+2; } |
|
113 bool less(const PairType &p1, const PairType &p2) { |
|
114 return comp(p1.second, p2.second); |
|
115 } |
|
116 |
|
117 int bubble_up(int hole, PairType p); |
|
118 int bubble_down(int hole, PairType p, int length); |
|
119 |
|
120 void move(const PairType &p, int i) { |
|
121 data[i] = p; |
|
122 kim.set(p.first, i); |
|
123 } |
|
124 |
|
125 void rmidx(int h) { |
|
126 int n = data.size()-1; |
|
127 if( h>=0 && h<=n ) { |
|
128 kim.set(data[h].first, POST_HEAP); |
|
129 if ( h<n ) { |
|
130 bubble_down(h, data[n], n); |
|
131 } |
|
132 data.pop_back(); |
|
133 } |
|
134 } |
|
135 |
|
136 public: |
|
137 void push(const PairType &p) { |
|
138 int n = data.size(); |
|
139 data.resize(n+1); |
|
140 bubble_up(n, p); |
|
141 } |
|
142 void push(const Key &k, const Val &v) { push(PairType(k,v)); } |
|
143 |
|
144 Key top() const { |
|
145 // FIXME: test size>0 ? |
|
146 return data[0].first; |
|
147 } |
|
148 Val topValue() const { |
|
149 // FIXME: test size>0 ? |
|
150 return data[0].second; |
|
151 } |
|
152 |
|
153 void pop() { |
|
154 rmidx(0); |
|
155 } |
|
156 |
|
157 void erase(const Key &k) { |
|
158 rmidx(kim[k]); |
|
159 } |
|
160 |
|
161 Val operator[](const Key &k) const { |
|
162 int idx = kim[k]; |
|
163 return data[idx].second; |
|
164 } |
|
165 |
|
166 void put(const Key &k, const Val &v) { |
|
167 int idx = kim[k]; |
|
168 if( idx < 0 ) { |
|
169 push(k,v); |
|
170 } |
|
171 else if( comp(v, data[idx].second) ) { |
|
172 bubble_up(idx, PairType(k,v)); |
|
173 } |
|
174 else { |
|
175 bubble_down(idx, PairType(k,v), data.size()); |
|
176 } |
|
177 } |
|
178 |
|
179 void decrease(const Key &k, const Val &v) { |
|
180 int idx = kim[k]; |
|
181 bubble_up(idx, PairType(k,v)); |
|
182 } |
|
183 void increase(const Key &k, const Val &v) { |
|
184 int idx = kim[k]; |
|
185 bubble_down(idx, PairType(k,v), data.size()); |
|
186 } |
|
187 |
|
188 state_enum state(const Key &k) const { |
|
189 int s = kim[k]; |
|
190 if( s>=0 ) |
|
191 s=0; |
|
192 return state_enum(s); |
|
193 } |
|
194 |
|
195 }; // class BinHeap |
|
196 |
|
197 |
|
198 template <typename K, typename V, typename M, typename C> |
|
199 int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) { |
|
200 int par = parent(hole); |
|
201 while( hole>0 && less(p,data[par]) ) { |
|
202 move(data[par],hole); |
|
203 hole = par; |
|
204 par = parent(hole); |
|
205 } |
|
206 move(p, hole); |
|
207 return hole; |
|
208 } |
|
209 |
|
210 template <typename K, typename V, typename M, typename C> |
|
211 int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) { |
|
212 int child = second_child(hole); |
|
213 while(child < length) { |
|
214 if( less(data[child-1], data[child]) ) { |
|
215 --child; |
|
216 } |
|
217 if( !less(data[child], p) ) |
|
218 goto ok; |
|
219 move(data[child], hole); |
|
220 hole = child; |
|
221 child = second_child(hole); |
|
222 } |
|
223 child--; |
|
224 if( child<length && less(data[child], p) ) { |
|
225 move(data[child], hole); |
|
226 hole=child; |
|
227 } |
|
228 ok: |
|
229 move(p, hole); |
|
230 return hole; |
|
231 } |
|
232 |
|
233 } // namespace hugo |
|
234 |
|
235 #endif // BIN_HEAP_HH |