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/linear_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_LINEAR_HEAP_H
18 #define LEMON_LINEAR_HEAP_H
22 ///\brief Binary Heap implementation.
30 /// \addtogroup auxdat
33 /// \brief A Linear Heap implementation.
35 /// This class implements the \e linear \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. The linear heap is very simple implementation, it can store
39 /// only integer priorities and it stores for each priority in the [0..C]
40 /// range a list of items. So it should be used only when the priorities
41 /// are small. It is not intended to use as dijkstra heap.
43 /// \param _Item Type of the items to be stored.
44 /// \param _ItemIntMap A read and writable Item int map, used internally
45 /// to handle the cross references.
46 /// \param minimize If the given parameter is true then the heap gives back
47 /// the lowest priority.
48 template <typename _Item, typename _ItemIntMap, bool minimize = true >
54 typedef std::pair<Item, Prio> Pair;
55 typedef _ItemIntMap ItemIntMap;
57 /// \brief Type to represent the items states.
59 /// Each Item element have a state associated to it. It may be "in heap",
60 /// "pre heap" or "post heap". The latter two are indifferent from the
61 /// heap's point of view, but may be useful to the user.
63 /// The ItemIntMap \e should be initialized in such way that it maps
64 /// PRE_HEAP (-1) to any element to be put in the heap...
72 /// \brief The constructor.
75 /// \param _index should be given to the constructor, since it is used
76 /// internally to handle the cross references. The value of the map
77 /// should be PRE_HEAP (-1) for each element.
78 explicit LinearHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
80 /// The number of items stored in the heap.
82 /// \brief Returns the number of items stored in the heap.
83 int size() const { return data.size(); }
85 /// \brief Checks if the heap stores no items.
87 /// Returns \c true if and only if the heap stores no items.
88 bool empty() const { return data.empty(); }
90 /// \brief Make empty this heap.
92 /// Make empty this heap.
94 for (int i = 0; i < (int)data.size(); ++i) {
95 index[data[i].item] = -2;
97 data.clear(); first.clear(); minimal = 0;
102 void relocate_last(int idx) {
103 if (idx + 1 < (int)data.size()) {
104 data[idx] = data.back();
105 if (data[idx].prev != -1) {
106 data[data[idx].prev].next = idx;
108 first[data[idx].value] = idx;
110 if (data[idx].next != -1) {
111 data[data[idx].next].prev = idx;
113 index[data[idx].item] = idx;
118 void unlace(int idx) {
119 if (data[idx].prev != -1) {
120 data[data[idx].prev].next = data[idx].next;
122 first[data[idx].value] = data[idx].next;
124 if (data[idx].next != -1) {
125 data[data[idx].next].prev = data[idx].prev;
130 if ((int)first.size() <= data[idx].value) {
131 first.resize(data[idx].value + 1, -1);
133 data[idx].next = first[data[idx].value];
134 if (data[idx].next != -1) {
135 data[data[idx].next].prev = idx;
137 first[data[idx].value] = idx;
142 /// \brief Insert a pair of item and priority into the heap.
144 /// Adds \c p.first to the heap with priority \c p.second.
145 /// \param p The pair to insert.
146 void push(const Pair& p) {
147 push(p.first, p.second);
150 /// \brief Insert an item into the heap with the given priority.
152 /// Adds \c i to the heap with priority \c p.
153 /// \param i The item to insert.
154 /// \param p The priority of the item.
155 void push(const Item &i, const Prio &p) {
156 int idx = data.size();
158 data.push_back(LinearItem(i, p));
165 /// \brief Returns the item with minimum priority.
167 /// This method returns the item with minimum priority.
168 /// \pre The heap must be nonempty.
170 while (first[minimal] == -1) {
173 return data[first[minimal]].item;
176 /// \brief Returns the minimum priority.
178 /// It returns the minimum priority.
179 /// \pre The heap must be nonempty.
181 while (first[minimal] == -1) {
187 /// \brief Deletes the item with minimum priority.
189 /// This method deletes the item with minimum priority from the heap.
190 /// \pre The heap must be non-empty.
192 while (first[minimal] == -1) {
195 int idx = first[minimal];
196 index[data[idx].item] = -2;
201 /// \brief Deletes \c i from the heap.
203 /// This method deletes item \c i from the heap, if \c i was
204 /// already stored in the heap.
205 /// \param i The item to erase.
206 void erase(const Item &i) {
208 index[data[idx].item] = -2;
214 /// \brief Returns the priority of \c i.
216 /// This function returns the priority of item \c i.
217 /// \pre \c i must be in the heap.
218 /// \param i The item.
219 Prio operator[](const Item &i) const {
221 return data[idx].value;
224 /// \brief \c i gets to the heap with priority \c p independently
225 /// if \c i was already there.
227 /// This method calls \ref push(\c i, \c p) if \c i is not stored
228 /// in the heap and sets the priority of \c i to \c p otherwise.
229 /// \param i The item.
230 /// \param p The priority.
231 void set(const Item &i, const Prio &p) {
235 } else if (p > data[idx].value) {
242 /// \brief Decreases the priority of \c i to \c p.
244 /// This method decreases the priority of item \c i to \c p.
245 /// \pre \c i must be stored in the heap with priority at least \c
246 /// p relative to \c Compare.
247 /// \param i The item.
248 /// \param p The priority.
249 void decrease(const Item &i, const Prio &p) {
259 /// \brief Increases the priority of \c i to \c p.
261 /// This method sets the priority of item \c i to \c p.
262 /// \pre \c i must be stored in the heap with priority at most \c
263 /// p relative to \c Compare.
264 /// \param i The item.
265 /// \param p The priority.
266 void increase(const Item &i, const Prio &p) {
273 /// \brief Returns if \c item is in, has already been in, or has
274 /// never been in the heap.
276 /// This method returns PRE_HEAP if \c item has never been in the
277 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
278 /// otherwise. In the latter case it is possible that \c item will
279 /// get back to the heap again.
280 /// \param i The item.
281 state_enum state(const Item &i) const {
283 if (idx >= 0) idx = 0;
284 return state_enum(idx);
290 LinearItem(const Item& _item, int _value)
291 : item(_item), value(_value) {}
300 std::vector<int> first;
301 std::vector<LinearItem> data;
304 }; // class LinearHeap
307 template <typename _Item, typename _ItemIntMap>
308 class LinearHeap<_Item, _ItemIntMap, false> {
313 typedef std::pair<Item, Prio> Pair;
314 typedef _ItemIntMap ItemIntMap;
324 explicit LinearHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
326 int size() const { return data.size(); }
327 bool empty() const { return data.empty(); }
330 for (int i = 0; i < (int)data.size(); ++i) {
331 index[data[i].item] = -2;
333 data.clear(); first.clear(); maximal = -1;
338 void relocate_last(int idx) {
339 if (idx + 1 != (int)data.size()) {
340 data[idx] = data.back();
341 if (data[idx].prev != -1) {
342 data[data[idx].prev].next = idx;
344 first[data[idx].value] = idx;
346 if (data[idx].next != -1) {
347 data[data[idx].next].prev = idx;
349 index[data[idx].item] = idx;
354 void unlace(int idx) {
355 if (data[idx].prev != -1) {
356 data[data[idx].prev].next = data[idx].next;
358 first[data[idx].value] = data[idx].next;
360 if (data[idx].next != -1) {
361 data[data[idx].next].prev = data[idx].prev;
366 if ((int)first.size() <= data[idx].value) {
367 first.resize(data[idx].value + 1, -1);
369 data[idx].next = first[data[idx].value];
370 if (data[idx].next != -1) {
371 data[data[idx].next].prev = idx;
373 first[data[idx].value] = idx;
379 void push(const Pair& p) {
380 push(p.first, p.second);
383 void push(const Item &i, const Prio &p) {
384 int idx = data.size();
386 data.push_back(LinearItem(i, p));
388 if (data[idx].value > maximal) {
389 maximal = data[idx].value;
394 while (first[maximal] == -1) {
397 return data[first[maximal]].item;
401 while (first[maximal] == -1) {
408 while (first[maximal] == -1) {
411 int idx = first[maximal];
412 index[data[idx].item] = -2;
417 void erase(const Item &i) {
419 index[data[idx].item] = -2;
424 Prio operator[](const Item &i) const {
426 return data[idx].value;
429 void set(const Item &i, const Prio &p) {
433 } else if (p > data[idx].value) {
440 void decrease(const Item &i, const Prio &p) {
450 void increase(const Item &i, const Prio &p) {
457 state_enum state(const Item &i) const {
459 if (idx >= 0) idx = 0;
460 return state_enum(idx);
466 LinearItem(const Item& _item, int _value)
467 : item(_item), value(_value) {}
476 std::vector<int> first;
477 std::vector<LinearItem> data;
480 }; // class LinearHeap