COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/radix_heap.h @ 1311:b810a07248a0

Last change on this file since 1311:b810a07248a0 was 1205:a9a3354b01d4, checked in by Balazs Dezso, 15 years ago

Bug fix in radix heap.

File size: 8.6 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/bin_heap.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
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.
10 *
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
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_RADIX_HEAP_H
18#define LEMON_RADIX_HEAP_H
19
20///\ingroup auxdat
21///\file
22///\brief Radix Heap implementation.
23///\todo It should be documented.
24
25#include <vector>
26#include <lemon/error.h>
27
28namespace lemon {
29
30  /// \addtogroup auxdat
31  /// @{
32
33  /// A Radix Heap implementation.
34 
35  ///\todo Please document...
36  ///
37  ///\sa BinHeap
38  ///\sa Dijkstra
39
40  class UnderFlowPriorityException : public RuntimeError {
41  public:
42    virtual const char* exceptionName() const {
43      return "lemon::UnderFlowPriorityException";
44    } 
45  };
46
47  template <typename _Item, typename _ItemIntMap>
48  class RadixHeap {
49
50  public:
51    typedef _Item Item;
52    // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
53    typedef int Prio;
54    typedef _ItemIntMap ItemIntMap;
55
56    /**
57     * Each Item element have a state associated to it. It may be "in heap",
58     * "pre heap" or "post heap". The later two are indifferent from the
59     * heap's point of view, but may be useful to the user.
60     *
61     * The ItemIntMap _should_ be initialized in such way, that it maps
62     * PRE_HEAP (-1) to any element to be put in the heap...
63     */
64    ///\todo it is used nowhere
65    ///
66    enum state_enum {
67      IN_HEAP = 0,
68      PRE_HEAP = -1,
69      POST_HEAP = -2
70    };
71
72  private:
73   
74    struct RadixItem {
75      int prev, next, box;
76      Item item;
77      int prio;
78      RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
79    };
80
81    struct RadixBox {
82      int first;
83      int min, size;
84      RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
85    };
86
87    std::vector<RadixItem> data;
88    std::vector<RadixBox> boxes;
89
90    ItemIntMap &iim;
91
92
93  public:
94    ///\e
95    explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {
96      boxes.push_back(RadixBox(0, 1));
97      boxes.push_back(RadixBox(1, 1));
98    }
99
100    ///\e
101    RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {
102      boxes.push_back(RadixBox(0, 1));
103      boxes.push_back(RadixBox(1, 1));
104      while (upper(boxes.back(), capacity)) {
105        extend();
106      }
107    }
108
109    ///\e
110    int size() const { return data.size(); }
111    ///\e
112    bool empty() const { return data.empty(); }
113
114  private:
115
116    bool upper(int box, Prio prio) {
117      return prio < boxes[box].min;
118    }
119
120    bool lower(int box, Prio prio) {
121      return prio >= boxes[box].min + boxes[box].size;
122    }
123
124    /// \brief Remove item from the box list.
125    void remove(int index) {
126      if (data[index].prev >= 0) {
127        data[data[index].prev].next = data[index].next;
128      } else {
129        boxes[data[index].box].first = data[index].next;
130      }
131      if (data[index].next >= 0) {
132        data[data[index].next].prev = data[index].prev;
133      }
134    }
135
136    /// \brief Insert item into the box list.
137    void insert(int box, int index) {
138      if (boxes[box].first == -1) {
139        boxes[box].first = index;
140        data[index].next = data[index].prev = -1;
141      } else {
142        data[index].next = boxes[box].first;
143        data[boxes[box].first].prev = index;
144        data[index].prev = -1;
145        boxes[box].first = index;
146      }
147      data[index].box = box;
148    }
149
150    /// \brief Add a new box to the box list.
151    void extend() {
152      int min = boxes.back().min + boxes.back().size;
153      int size = 2 * boxes.back().size;
154      boxes.push_back(RadixBox(min, size));
155    }
156
157    /// \brief Move an item up into the proper box.
158    void bubble_up(int index) {
159      if (!lower(data[index].box, data[index].prio)) return;
160      remove(index);
161      int box = findUp(data[index].box, data[index].prio);
162      insert(box, index);     
163    }
164
165    /// \brief Find up the proper box for the item with the given prio.
166    int findUp(int start, int prio) {
167      while (lower(start, prio)) {
168        if (++start == (int)boxes.size()) {
169          extend();
170        }
171      }
172      return start;
173    }
174
175    /// \brief Move an item down into the proper box.
176    void bubble_down(int index) {
177      if (!upper(data[index].box, data[index].prio)) return;
178      remove(index);
179      int box = findDown(data[index].box, data[index].prio);
180      insert(box, index);
181    }
182
183    /// \brief Find up the proper box for the item with the given prio.
184    int findDown(int start, int prio) {
185      while (upper(start, prio)) {
186        if (--start < 0) throw UnderFlowPriorityException();
187      }
188      return start;
189    }
190
191    /// \brief Find the first not empty box.
192    int findFirst() {
193      int first = 0;
194      while (boxes[first].first == -1) ++first;
195      return first;
196    }
197
198    /// \brief Gives back the minimal prio of the box.
199    int minValue(int box) {
200      int min = data[boxes[box].first].prio;
201      for (int k = boxes[box].first; k != -1; k = data[k].next) {
202        if (data[k].prio < min) min = data[k].prio;
203      }
204      return min;
205    }
206
207    /// \brief Rearrange the items of the heap and makes the
208    /// first box not empty.
209    void moveDown() {
210      //      print(); printf("moveDown\n"); fflush(stdout);       
211      int box = findFirst();
212      if (box == 0) return;
213      int min = minValue(box);
214      for (int i = 0; i <= box; ++i) {
215        boxes[i].min = min;
216        min += boxes[i].size;
217      }
218      int curr = boxes[box].first, next;
219      while (curr != -1) {
220        next = data[curr].next;
221        bubble_down(curr);
222        curr = next;
223      }     
224    }
225
226    void relocate_last(int index) {
227      if (index != (int)data.size() - 1) {
228        data[index] = data.back();
229        if (data[index].prev != -1) {
230          data[data[index].prev].next = index;
231        } else {
232          boxes[data[index].box].first = index;
233        }
234        if (data[index].next != -1) {
235          data[data[index].next].prev = index;
236        }
237        iim[data[index].item] = index;
238      }
239      data.pop_back();
240    }
241
242  public:
243
244    ///\e
245    void push(const Item &i, const Prio &p) {
246      fflush(stdout);
247      int n = data.size();
248      iim.set(i, n);
249      data.push_back(RadixItem(i, p));
250      while (lower(boxes.size() - 1, p)) {
251        extend();
252      }
253      int box = findDown(boxes.size() - 1, p);
254      insert(box, n);
255      //      printf("Push %d\n", p);
256      //print();
257    }
258
259    ///\e
260    Item top() const {
261      //      print(); printf("top\n");  fflush(stdout);
262      const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
263      return data[boxes[0].first].item;
264      //      print(); printf("top_end\n");  fflush(stdout);
265    }
266
267    /// Returns the prio of the top element of the heap.
268    Prio prio() const {
269      //      print(); printf("prio\n"); fflush(stdout);
270      const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
271      return data[boxes[0].first].prio;
272     }
273
274    ///\e
275    void pop() {
276      //      print(); printf("pop\n"); fflush(stdout);
277      moveDown();
278      int index = boxes[0].first;
279      iim[data[index].item] = POST_HEAP;
280      remove(index);
281      relocate_last(index);
282      //      printf("Pop \n");
283      //print();
284    }
285
286    ///\e
287    void erase(const Item &i) {
288      int index = iim[i];
289      iim[i] = POST_HEAP;
290      remove(index);
291      relocate_last(index);
292   }
293
294    ///\e
295    Prio operator[](const Item &i) const {
296      int idx = iim[i];
297      return data[idx].prio;
298    }
299
300    ///\e
301    void set(const Item &i, const Prio &p) {
302      int idx = iim[i];
303      if( idx < 0 ) {
304        push(i, p);
305      }
306      else if( p >= data[idx].prio ) {
307        data[idx].prio = p;
308        bubble_up(idx);
309      } else {
310        data[idx].prio = p;
311        bubble_down(idx);
312      }
313    }
314
315    ///\e
316    void decrease(const Item &i, const Prio &p) {
317      //      print(); printf("decrease\n"); fflush(stdout);
318      int idx = iim[i];
319      data[idx].prio = p;
320      bubble_down(idx);
321    }
322
323    ///\e
324    void increase(const Item &i, const Prio &p) {
325      int idx = iim[i];
326      data[idx].prio = p;
327      bubble_up(idx);
328    }
329
330    ///\e
331    state_enum state(const Item &i) const {
332      int s = iim[i];
333      if( s >= 0 ) s = 0;
334      return state_enum(s);
335    }
336
337//     void print() const {
338//       for (int i = 0; i < boxes.size(); ++i) {
339//      printf("(%d, %d) ", boxes[i].min, boxes[i].size);
340//      for (int k = boxes[i].first; k != -1; k = data[k].next) {
341//        printf("%d ", data[k].prio);
342//      }
343//      printf("\n");
344//       }
345//       fflush(stdout);
346//     }
347
348  }; // class RadixHeap
349
350
351  ///@}
352
353} // namespace lemon
354
355#endif // LEMON_RADIX_HEAP_H
Note: See TracBrowser for help on using the repository browser.