COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/radix_heap.h @ 1902:e9af75c90c28

Last change on this file since 1902:e9af75c90c28 was 1902:e9af75c90c28, checked in by Balazs Dezso, 14 years ago

state setting function for heaps

If we know that which elements were in the heap then
we can clear it in better time complexity.

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