equal
deleted
inserted
replaced
|
1 // -*- C++ -*- // |
|
2 |
1 /* FIXME: Copyright ... |
3 /* FIXME: Copyright ... |
2 * |
4 * |
3 * This implementation is heavily based on STL's heap functions and |
5 * This implementation is heavily based on STL's heap functions and |
4 * the similar class by Alpar Juttner in IKTA... |
6 * the similar class by Alpar Juttner in IKTA... |
5 */ |
7 */ |
57 |
59 |
58 |
60 |
59 #ifndef BIN_HEAP_HH |
61 #ifndef BIN_HEAP_HH |
60 #define BIN_HEAP_HH |
62 #define BIN_HEAP_HH |
61 |
63 |
|
64 ///\file |
|
65 ///\brief Binary Heap implementation. |
|
66 |
62 #include <vector> |
67 #include <vector> |
63 #include <utility> |
68 #include <utility> |
64 #include <functional> |
69 #include <functional> |
65 |
70 |
66 namespace hugo { |
71 namespace hugo { |
67 |
72 |
|
73 /// A Binary Heap implementation. |
68 template <typename Item, typename Prio, typename ItemIntMap, |
74 template <typename Item, typename Prio, typename ItemIntMap, |
69 typename Compare = std::less<Prio> > |
75 typename Compare = std::less<Prio> > |
70 class BinHeap { |
76 class BinHeap { |
71 |
77 |
72 public: |
78 public: |
83 * heap's point of view, but may be useful to the user. |
89 * heap's point of view, but may be useful to the user. |
84 * |
90 * |
85 * The ItemIntMap _should_ be initialized in such way, that it maps |
91 * The ItemIntMap _should_ be initialized in such way, that it maps |
86 * PRE_HEAP (-1) to any element to be put in the heap... |
92 * PRE_HEAP (-1) to any element to be put in the heap... |
87 */ |
93 */ |
|
94 ///\todo it is used nowhere |
|
95 /// |
88 enum state_enum { |
96 enum state_enum { |
89 IN_HEAP = 0, |
97 IN_HEAP = 0, |
90 PRE_HEAP = -1, |
98 PRE_HEAP = -1, |
91 POST_HEAP = -2 |
99 POST_HEAP = -2 |
92 }; |
100 }; |
138 bubble_up(n, p); |
146 bubble_up(n, p); |
139 } |
147 } |
140 void push(const Item &i, const Prio &p) { push(PairType(i,p)); } |
148 void push(const Item &i, const Prio &p) { push(PairType(i,p)); } |
141 |
149 |
142 Item top() const { |
150 Item top() const { |
143 // FIXME: test size>0 ? |
|
144 return data[0].first; |
151 return data[0].first; |
145 } |
152 } |
146 Prio topPrio() const { |
153 /// Returns the prio of the top element of the heap. |
147 // FIXME: test size>0 ? |
154 Prio prio() const { |
148 return data[0].second; |
155 return data[0].second; |
149 } |
156 } |
150 |
157 |
151 void pop() { |
158 void pop() { |
152 rmidx(0); |
159 rmidx(0); |
154 |
161 |
155 void erase(const Item &i) { |
162 void erase(const Item &i) { |
156 rmidx(iim[i]); |
163 rmidx(iim[i]); |
157 } |
164 } |
158 |
165 |
159 Prio get(const Item &i) const { |
166 Prio operator[](const Item &i) const { |
160 int idx = iim[i]; |
167 int idx = iim[i]; |
161 return data[idx].second; |
168 return data[idx].second; |
162 } |
169 } |
163 Prio operator[](const Item &i) const { |
170 |
164 return get(i); |
|
165 } |
|
166 void set(const Item &i, const Prio &p) { |
171 void set(const Item &i, const Prio &p) { |
167 int idx = iim[i]; |
172 int idx = iim[i]; |
168 if( idx < 0 ) { |
173 if( idx < 0 ) { |
169 push(i,p); |
174 push(i,p); |
170 } |
175 } |