COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/radix_heap.h @ 2118:54350d5c316a

Last change on this file since 2118:54350d5c316a was 2050:d9a221218ea4, checked in by Balazs Dezso, 14 years ago

Changing the mining of the clear in heaps
It does not touch the heap cross ref. It is
sometimes more clean useable and more efficient

File size: 12.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_RADIX_HEAP_H
20#define LEMON_RADIX_HEAP_H
21
22///\ingroup auxdat
23///\file
24///\brief Radix Heap implementation.
25
26#include <vector>
27#include <lemon/error.h>
28
29namespace lemon {
30
31  /// \brief Exception thrown by RadixHeap.
32  /// 
33  /// This Exception is thrown when a smaller priority
34  /// is inserted into the \e RadixHeap then the last time erased.
35  /// \see RadixHeap
36  /// \author Balazs Dezso
37
38  class UnderFlowPriorityError : public RuntimeError {
39  public:
40    virtual const char* exceptionName() const {
41      return "lemon::UnderFlowPriorityError";
42    } 
43  };
44
45  /// \ingroup auxdata
46  ///
47  /// \brief A Radix Heap implementation.
48  ///
49  /// This class implements the \e radix \e heap data structure. A \e heap
50  /// is a data structure for storing items with specified values called \e
51  /// priorities in such a way that finding the item with minimum priority is
52  /// efficient. This heap type can store only items with \e int priority.
53  /// In a heap one can change the priority of an item, add or erase an
54  /// item, but the priority cannot be decreased under the last removed
55  /// item's priority.
56  ///
57  /// \param _Item Type of the items to be stored. 
58  /// \param _ItemIntMap A read and writable Item int map, used internally
59  /// to handle the cross references.
60  ///
61  /// \see BinHeap
62  /// \see Dijkstra
63  /// \author Balazs Dezso
64
65  template <typename _Item, typename _ItemIntMap>
66  class RadixHeap {
67
68  public:
69    typedef _Item Item;
70    typedef int Prio;
71    typedef _ItemIntMap ItemIntMap;
72
73    /// \brief Type to represent the items states.
74    ///
75    /// Each Item element have a state associated to it. It may be "in heap",
76    /// "pre heap" or "post heap". The latter two are indifferent from the
77    /// heap's point of view, but may be useful to the user.
78    ///
79    /// The ItemIntMap \e should be initialized in such way that it maps
80    /// PRE_HEAP (-1) to any element to be put in the heap...
81    enum state_enum {
82      IN_HEAP = 0,
83      PRE_HEAP = -1,
84      POST_HEAP = -2
85    };
86
87  private:
88   
89    struct RadixItem {
90      int prev, next, box;
91      Item item;
92      int prio;
93      RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
94    };
95
96    struct RadixBox {
97      int first;
98      int min, size;
99      RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
100    };
101
102    std::vector<RadixItem> data;
103    std::vector<RadixBox> boxes;
104
105    ItemIntMap &iim;
106
107
108  public:
109    /// \brief The constructor.
110    ///
111    /// The constructor.
112    ///
113    /// \param _iim It should be given to the constructor, since it is used
114    /// internally to handle the cross references. The value of the map
115    /// should be PRE_HEAP (-1) for each element.
116    ///
117    /// \param minimal The initial minimal value of the heap.
118    /// \param capacity It determines the initial capacity of the heap.
119    RadixHeap(ItemIntMap &_iim, int minimal = 0, int capacity = 0)
120      : iim(_iim) {
121      boxes.push_back(RadixBox(minimal, 1));
122      boxes.push_back(RadixBox(minimal + 1, 1));
123      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
124        extend();
125      }
126    }
127
128    /// The number of items stored in the heap.
129    ///
130    /// \brief Returns the number of items stored in the heap.
131    int size() const { return data.size(); }
132    /// \brief Checks if the heap stores no items.
133    ///
134    /// Returns \c true if and only if the heap stores no items.
135    bool empty() const { return data.empty(); }
136
137    /// \brief Make empty this heap.
138    ///
139    /// Make empty this heap. It does not change the cross reference
140    /// map.  If you want to reuse a heap what is not surely empty you
141    /// should first clear the heap and after that you should set the
142    /// cross reference map for each item to \c PRE_HEAP.
143    void clear(int minimal = 0, int capacity = 0) {
144      data.clear(); boxes.clear();
145      boxes.push_back(RadixBox(minimal, 1));
146      boxes.push_back(RadixBox(minimal + 1, 1));
147      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
148        extend();
149      }
150    }
151
152  private:
153
154    bool upper(int box, Prio prio) {
155      return prio < boxes[box].min;
156    }
157
158    bool lower(int box, Prio prio) {
159      return prio >= boxes[box].min + boxes[box].size;
160    }
161
162    /// \brief Remove item from the box list.
163    void remove(int index) {
164      if (data[index].prev >= 0) {
165        data[data[index].prev].next = data[index].next;
166      } else {
167        boxes[data[index].box].first = data[index].next;
168      }
169      if (data[index].next >= 0) {
170        data[data[index].next].prev = data[index].prev;
171      }
172    }
173
174    /// \brief Insert item into the box list.
175    void insert(int box, int index) {
176      if (boxes[box].first == -1) {
177        boxes[box].first = index;
178        data[index].next = data[index].prev = -1;
179      } else {
180        data[index].next = boxes[box].first;
181        data[boxes[box].first].prev = index;
182        data[index].prev = -1;
183        boxes[box].first = index;
184      }
185      data[index].box = box;
186    }
187
188    /// \brief Add a new box to the box list.
189    void extend() {
190      int min = boxes.back().min + boxes.back().size;
191      int size = 2 * boxes.back().size;
192      boxes.push_back(RadixBox(min, size));
193    }
194
195    /// \brief Move an item up into the proper box.
196    void bubble_up(int index) {
197      if (!lower(data[index].box, data[index].prio)) return;
198      remove(index);
199      int box = findUp(data[index].box, data[index].prio);
200      insert(box, index);     
201    }
202
203    /// \brief Find up the proper box for the item with the given prio.
204    int findUp(int start, int prio) {
205      while (lower(start, prio)) {
206        if (++start == (int)boxes.size()) {
207          extend();
208        }
209      }
210      return start;
211    }
212
213    /// \brief Move an item down into the proper box.
214    void bubble_down(int index) {
215      if (!upper(data[index].box, data[index].prio)) return;
216      remove(index);
217      int box = findDown(data[index].box, data[index].prio);
218      insert(box, index);
219    }
220
221    /// \brief Find up the proper box for the item with the given prio.
222    int findDown(int start, int prio) {
223      while (upper(start, prio)) {
224        if (--start < 0) throw UnderFlowPriorityError();
225      }
226      return start;
227    }
228
229    /// \brief Find the first not empty box.
230    int findFirst() {
231      int first = 0;
232      while (boxes[first].first == -1) ++first;
233      return first;
234    }
235
236    /// \brief Gives back the minimal prio of the box.
237    int minValue(int box) {
238      int min = data[boxes[box].first].prio;
239      for (int k = boxes[box].first; k != -1; k = data[k].next) {
240        if (data[k].prio < min) min = data[k].prio;
241      }
242      return min;
243    }
244
245    /// \brief Rearrange the items of the heap and makes the
246    /// first box not empty.
247    void moveDown() {
248      int box = findFirst();
249      if (box == 0) return;
250      int min = minValue(box);
251      for (int i = 0; i <= box; ++i) {
252        boxes[i].min = min;
253        min += boxes[i].size;
254      }
255      int curr = boxes[box].first, next;
256      while (curr != -1) {
257        next = data[curr].next;
258        bubble_down(curr);
259        curr = next;
260      }     
261    }
262
263    void relocate_last(int index) {
264      if (index != (int)data.size() - 1) {
265        data[index] = data.back();
266        if (data[index].prev != -1) {
267          data[data[index].prev].next = index;
268        } else {
269          boxes[data[index].box].first = index;
270        }
271        if (data[index].next != -1) {
272          data[data[index].next].prev = index;
273        }
274        iim[data[index].item] = index;
275      }
276      data.pop_back();
277    }
278
279  public:
280
281    /// \brief Insert an item into the heap with the given priority.
282    ///   
283    /// Adds \c i to the heap with priority \c p.
284    /// \param i The item to insert.
285    /// \param p The priority of the item.
286    void push(const Item &i, const Prio &p) {
287      int n = data.size();
288      iim.set(i, n);
289      data.push_back(RadixItem(i, p));
290      while (lower(boxes.size() - 1, p)) {
291        extend();
292      }
293      int box = findDown(boxes.size() - 1, p);
294      insert(box, n);
295    }
296
297    /// \brief Returns the item with minimum priority.
298    ///
299    /// This method returns the item with minimum priority. 
300    /// \pre The heap must be nonempty. 
301    Item top() const {
302      const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
303      return data[boxes[0].first].item;
304    }
305
306    /// \brief Returns the minimum priority.
307    ///
308    /// It returns the minimum priority.
309    /// \pre The heap must be nonempty.
310    Prio prio() const {
311      const_cast<RadixHeap<Item, ItemIntMap>&>(*this).moveDown();
312      return data[boxes[0].first].prio;
313     }
314
315    /// \brief Deletes the item with minimum priority.
316    ///
317    /// This method deletes the item with minimum priority.
318    /// \pre The heap must be non-empty. 
319    void pop() {
320      moveDown();
321      int index = boxes[0].first;
322      iim[data[index].item] = POST_HEAP;
323      remove(index);
324      relocate_last(index);
325    }
326
327    /// \brief Deletes \c i from the heap.
328    ///
329    /// This method deletes item \c i from the heap, if \c i was
330    /// already stored in the heap.
331    /// \param i The item to erase.
332    void erase(const Item &i) {
333      int index = iim[i];
334      iim[i] = POST_HEAP;
335      remove(index);
336      relocate_last(index);
337   }
338
339    /// \brief Returns the priority of \c i.
340    ///
341    /// This function returns the priority of item \c i. 
342    /// \pre \c i must be in the heap.
343    /// \param i The item.
344    Prio operator[](const Item &i) const {
345      int idx = iim[i];
346      return data[idx].prio;
347    }
348
349    /// \brief \c i gets to the heap with priority \c p independently
350    /// if \c i was already there.
351    ///
352    /// This method calls \ref push(\c i, \c p) if \c i is not stored
353    /// in the heap and sets the priority of \c i to \c p otherwise.
354    /// It may throw an \e UnderFlowPriorityException.
355    /// \param i The item.
356    /// \param p The priority.
357    void set(const Item &i, const Prio &p) {
358      int idx = iim[i];
359      if( idx < 0 ) {
360        push(i, p);
361      }
362      else if( p >= data[idx].prio ) {
363        data[idx].prio = p;
364        bubble_up(idx);
365      } else {
366        data[idx].prio = p;
367        bubble_down(idx);
368      }
369    }
370
371
372    /// \brief Decreases the priority of \c i to \c p.
373    ///
374    /// This method decreases the priority of item \c i to \c p.
375    /// \pre \c i must be stored in the heap with priority at least \c p, and
376    /// \c should be greater or equal to the last removed item's priority.
377    /// \param i The item.
378    /// \param p The priority.
379    void decrease(const Item &i, const Prio &p) {
380      int idx = iim[i];
381      data[idx].prio = p;
382      bubble_down(idx);
383    }
384
385    /// \brief Increases the priority of \c i to \c p.
386    ///
387    /// This method sets the priority of item \c i to \c p.
388    /// \pre \c i must be stored in the heap with priority at most \c p
389    /// \param i The item.
390    /// \param p The priority.
391    void increase(const Item &i, const Prio &p) {
392      int idx = iim[i];
393      data[idx].prio = p;
394      bubble_up(idx);
395    }
396
397    /// \brief Returns if \c item is in, has already been in, or has
398    /// never been in the heap.
399    ///
400    /// This method returns PRE_HEAP if \c item has never been in the
401    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
402    /// otherwise. In the latter case it is possible that \c item will
403    /// get back to the heap again.
404    /// \param i The item.
405    state_enum state(const Item &i) const {
406      int s = iim[i];
407      if( s >= 0 ) s = 0;
408      return state_enum(s);
409    }
410
411    /// \brief Sets the state of the \c item in the heap.
412    ///
413    /// Sets the state of the \c item in the heap. It can be used to
414    /// manually clear the heap when it is important to achive the
415    /// better time complexity.
416    /// \param i The item.
417    /// \param st The state. It should not be \c IN_HEAP.
418    void state(const Item& i, state_enum st) {
419      switch (st) {
420      case POST_HEAP:
421      case PRE_HEAP:
422        if (state(i) == IN_HEAP) {
423          erase(i);
424        }
425        iim[i] = st;
426        break;
427      case IN_HEAP:
428        break;
429      }
430    }
431
432  }; // class RadixHeap
433
434} // namespace lemon
435
436#endif // LEMON_RADIX_HEAP_H
Note: See TracBrowser for help on using the repository browser.