NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/bin_heap.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_BIN_HEAP_H
18 #define LEMON_BIN_HEAP_H
22 ///\brief Binary Heap implementation.
30 /// \addtogroup auxdat
33 /// A Binary Heap implementation.
35 ///This class implements the \e binary \e heap data structure. A \e heap
36 ///is a data structure for storing items with specified values called \e
37 ///priorities in such a way that finding the item with minimum priority is
38 ///efficient. \c Compare specifies the ordering of the priorities. In a heap
39 ///one can change the priority of an item, add or erase an item, etc.
41 ///\param Item Type of the items to be stored.
42 ///\param Prio Type of the priority of the items.
43 ///\param ItemIntMap A read and writable Item int map, used internally
44 ///to handle the cross references.
45 ///\param Compare A class for the ordering of the priorities. The
46 ///default is \c std::less<Prio>.
50 template <typename Item, typename Prio, typename ItemIntMap,
51 typename Compare = std::less<Prio> >
55 typedef Item ItemType;
56 // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
57 typedef Prio PrioType;
58 typedef std::pair<ItemType,PrioType> PairType;
59 typedef ItemIntMap ItemIntMapType;
60 typedef Compare PrioCompare;
62 /// \brief Type to represent the items states.
64 /// Each Item element have a state associated to it. It may be "in heap",
65 /// "pre heap" or "post heap". The latter two are indifferent from the
66 /// heap's point of view, but may be useful to the user.
68 /// The ItemIntMap \e should be initialized in such way that it maps
69 /// PRE_HEAP (-1) to any element to be put in the heap...
77 std::vector<PairType> data;
82 /// \brief The constructor.
85 /// \param _iim should be given to the constructor, since it is used
86 /// internally to handle the cross references. The value of the map
87 /// should be PRE_HEAP (-1) for each element.
88 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
90 /// \brief The constructor.
93 /// \param _iim should be given to the constructor, since it is used
94 /// internally to handle the cross references. The value of the map
95 /// should be PRE_HEAP (-1) for each element.
97 /// \param _comp The comparator function object.
98 BinHeap(ItemIntMap &_iim, const Compare &_comp)
99 : iim(_iim), comp(_comp) {}
102 /// The number of items stored in the heap.
104 /// \brief Returns the number of items stored in the heap.
105 int size() const { return data.size(); }
107 /// \brief Checks if the heap stores no items.
109 /// Returns \c true if and only if the heap stores no items.
110 bool empty() const { return data.empty(); }
112 /// \brief Make empty this heap.
114 /// Make empty this heap.
116 for (int i = 0; i < (int)data.size(); ++i) {
117 iim.set(data[i].first, POST_HEAP);
123 static int parent(int i) { return (i-1)/2; }
124 static int second_child(int i) { return 2*i+2; }
125 bool less(const PairType &p1, const PairType &p2) const {
126 return comp(p1.second, p2.second);
129 int bubble_up(int hole, PairType p);
130 int bubble_down(int hole, PairType p, int length);
132 void move(const PairType &p, int i) {
138 int n = data.size()-1;
140 iim.set(data[h].first, POST_HEAP);
142 bubble_down(h, data[n], n);
149 /// \brief Insert a pair of item and priority into the heap.
151 /// Adds \c p.first to the heap with priority \c p.second.
152 /// \param p The pair to insert.
153 void push(const PairType &p) {
159 /// \brief Insert an item into the heap with the given heap.
161 /// Adds \c i to the heap with priority \c p.
162 /// \param i The item to insert.
163 /// \param p The priority of the item.
164 void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
166 /// \brief Returns the item with minimum priority relative to \c Compare.
168 /// This method returns the item with minimum priority relative to \c
170 /// \pre The heap must be nonempty.
172 return data[0].first;
175 /// \brief Returns the minimum priority relative to \c Compare.
177 /// It returns the minimum priority relative to \c Compare.
178 /// \pre The heap must be nonempty.
180 return data[0].second;
183 /// \brief Deletes the item with minimum priority relative to \c Compare.
185 /// This method deletes the item with minimum priority relative to \c
186 /// Compare from the heap.
187 /// \pre The heap must be non-empty.
192 /// \brief Deletes \c i from the heap.
194 /// This method deletes item \c i from the heap, if \c i was
195 /// already stored in the heap.
196 /// \param i The item to erase.
197 void erase(const Item &i) {
202 /// \brief Returns the priority of \c i.
204 /// This function returns the priority of item \c i.
205 /// \pre \c i must be in the heap.
206 /// \param i The item.
207 Prio operator[](const Item &i) const {
209 return data[idx].second;
212 /// \brief \c i gets to the heap with priority \c p independently
213 /// if \c i was already there.
215 /// This method calls \ref push(\c i, \c p) if \c i is not stored
216 /// in the heap and sets the priority of \c i to \c p otherwise.
217 /// \param i The item.
218 /// \param p The priority.
219 void set(const Item &i, const Prio &p) {
224 else if( comp(p, data[idx].second) ) {
225 bubble_up(idx, PairType(i,p));
228 bubble_down(idx, PairType(i,p), data.size());
232 /// \brief Decreases the priority of \c i to \c p.
234 /// This method decreases the priority of item \c i to \c p.
235 /// \pre \c i must be stored in the heap with priority at least \c
236 /// p relative to \c Compare.
237 /// \param i The item.
238 /// \param p The priority.
239 void decrease(const Item &i, const Prio &p) {
241 bubble_up(idx, PairType(i,p));
244 /// \brief Increases the priority of \c i to \c p.
246 /// This method sets the priority of item \c i to \c p.
247 /// \pre \c i must be stored in the heap with priority at most \c
248 /// p relative to \c Compare.
249 /// \param i The item.
250 /// \param p The priority.
251 void increase(const Item &i, const Prio &p) {
253 bubble_down(idx, PairType(i,p), data.size());
256 /// \brief Returns if \c item is in, has already been in, or has
257 /// never been in the heap.
259 /// This method returns PRE_HEAP if \c item has never been in the
260 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
261 /// otherwise. In the latter case it is possible that \c item will
262 /// get back to the heap again.
263 /// \param i The item.
264 state_enum state(const Item &i) const {
268 return state_enum(s);
274 template <typename K, typename V, typename M, typename C>
275 int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
276 int par = parent(hole);
277 while( hole>0 && less(p,data[par]) ) {
278 move(data[par],hole);
286 template <typename K, typename V, typename M, typename C>
287 int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
288 int child = second_child(hole);
289 while(child < length) {
290 if( less(data[child-1], data[child]) ) {
293 if( !less(data[child], p) )
295 move(data[child], hole);
297 child = second_child(hole);
300 if( child<length && less(data[child], p) ) {
301 move(data[child], hole);
313 #endif // LEMON_BIN_HEAP_H