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