COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bucket_heap.h @ 2059:ebf3b2962554

Last change on this file since 2059:ebf3b2962554 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: 13.0 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_BUCKET_HEAP_H
20#define LEMON_BUCKET_HEAP_H
21
22///\ingroup auxdat
23///\file
24///\brief Bucket Heap implementation.
25
26#include <vector>
27#include <utility>
28#include <functional>
29
30namespace lemon {
31
32  /// \ingroup auxdat
33
34  /// \brief A Bucket Heap implementation.
35  ///
36  /// This class implements the \e bucket \e heap data structure. A \e heap
37  /// is a data structure for storing items with specified values called \e
38  /// priorities in such a way that finding the item with minimum priority is
39  /// efficient. The bucket heap is very simple implementation, it can store
40  /// only integer priorities and it stores for each priority in the
41  /// \f$ [0..C) \f$ range a list of items. So it should be used only when
42  /// the priorities are small. It is not intended to use as dijkstra heap.
43  ///
44  /// \param _Item Type of the items to be stored. 
45  /// \param _ItemIntMap A read and writable Item int map, used internally
46  /// to handle the cross references.
47  /// \param minimize If the given parameter is true then the heap gives back
48  /// the lowest priority.
49  template <typename _Item, typename _ItemIntMap, bool minimize = true >
50  class BucketHeap {
51
52  public:
53    typedef _Item Item;
54    typedef int Prio;
55    typedef std::pair<Item, Prio> Pair;
56    typedef _ItemIntMap ItemIntMap;
57
58    /// \brief Type to represent the items states.
59    ///
60    /// Each Item element have a state associated to it. It may be "in heap",
61    /// "pre heap" or "post heap". The latter two are indifferent from the
62    /// heap's point of view, but may be useful to the user.
63    ///
64    /// The ItemIntMap \e should be initialized in such way that it maps
65    /// PRE_HEAP (-1) to any element to be put in the heap...
66    enum state_enum {
67      IN_HEAP = 0,
68      PRE_HEAP = -1,
69      POST_HEAP = -2
70    };
71
72  public:
73    /// \brief The constructor.
74    ///
75    /// The constructor.
76    /// \param _index should be given to the constructor, since it is used
77    /// internally to handle the cross references. The value of the map
78    /// should be PRE_HEAP (-1) for each element.
79    explicit BucketHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
80   
81    /// The number of items stored in the heap.
82    ///
83    /// \brief Returns the number of items stored in the heap.
84    int size() const { return data.size(); }
85   
86    /// \brief Checks if the heap stores no items.
87    ///
88    /// Returns \c true if and only if the heap stores no items.
89    bool empty() const { return data.empty(); }
90
91    /// \brief Make empty this heap.
92    ///
93    /// Make empty this heap. It does not change the cross reference
94    /// map.  If you want to reuse a heap what is not surely empty you
95    /// should first clear the heap and after that you should set the
96    /// cross reference map for each item to \c PRE_HEAP.
97    void clear() {
98      data.clear(); first.clear(); minimal = 0;
99    }
100
101  private:
102
103    void relocate_last(int idx) {
104      if (idx + 1 < (int)data.size()) {
105        data[idx] = data.back();
106        if (data[idx].prev != -1) {
107          data[data[idx].prev].next = idx;
108        } else {
109          first[data[idx].value] = idx;
110        }
111        if (data[idx].next != -1) {
112          data[data[idx].next].prev = idx;
113        }
114        index[data[idx].item] = idx;
115      }
116      data.pop_back();
117    }
118
119    void unlace(int idx) {
120      if (data[idx].prev != -1) {
121        data[data[idx].prev].next = data[idx].next;
122      } else {
123        first[data[idx].value] = data[idx].next;
124      }
125      if (data[idx].next != -1) {
126        data[data[idx].next].prev = data[idx].prev;
127      }
128    }
129
130    void lace(int idx) {
131      if ((int)first.size() <= data[idx].value) {
132        first.resize(data[idx].value + 1, -1);
133      }
134      data[idx].next = first[data[idx].value];
135      if (data[idx].next != -1) {
136        data[data[idx].next].prev = idx;
137      }
138      first[data[idx].value] = idx;
139      data[idx].prev = -1;
140    }
141
142  public:
143    /// \brief Insert a pair of item and priority into the heap.
144    ///
145    /// Adds \c p.first to the heap with priority \c p.second.
146    /// \param p The pair to insert.
147    void push(const Pair& p) {
148      push(p.first, p.second);
149    }
150
151    /// \brief Insert an item into the heap with the given priority.
152    ///   
153    /// Adds \c i to the heap with priority \c p.
154    /// \param i The item to insert.
155    /// \param p The priority of the item.
156    void push(const Item &i, const Prio &p) {
157      int idx = data.size();
158      index[i] = idx;
159      data.push_back(BucketItem(i, p));
160      lace(idx);
161      if (p < minimal) {
162        minimal = p;
163      }
164    }
165
166    /// \brief Returns the item with minimum priority.
167    ///
168    /// This method returns the item with minimum priority.
169    /// \pre The heap must be nonempty. 
170    Item top() const {
171      while (first[minimal] == -1) {
172        ++minimal;
173      }
174      return data[first[minimal]].item;
175    }
176
177    /// \brief Returns the minimum priority.
178    ///
179    /// It returns the minimum priority.
180    /// \pre The heap must be nonempty.
181    Prio prio() const {
182      while (first[minimal] == -1) {
183        ++minimal;
184      }
185      return minimal;
186    }
187
188    /// \brief Deletes the item with minimum priority.
189    ///
190    /// This method deletes the item with minimum priority from the heap. 
191    /// \pre The heap must be non-empty. 
192    void pop() {
193      while (first[minimal] == -1) {
194        ++minimal;
195      }
196      int idx = first[minimal];
197      index[data[idx].item] = -2;
198      unlace(idx);
199      relocate_last(idx);
200    }
201
202    /// \brief Deletes \c i from the heap.
203    ///
204    /// This method deletes item \c i from the heap, if \c i was
205    /// already stored in the heap.
206    /// \param i The item to erase.
207    void erase(const Item &i) {
208      int idx = index[i];
209      index[data[idx].item] = -2;
210      unlace(idx);
211      relocate_last(idx);
212    }
213
214   
215    /// \brief Returns the priority of \c i.
216    ///
217    /// This function returns the priority of item \c i. 
218    /// \pre \c i must be in the heap.
219    /// \param i The item.
220    Prio operator[](const Item &i) const {
221      int idx = index[i];
222      return data[idx].value;
223    }
224
225    /// \brief \c i gets to the heap with priority \c p independently
226    /// if \c i was already there.
227    ///
228    /// This method calls \ref push(\c i, \c p) if \c i is not stored
229    /// in the heap and sets the priority of \c i to \c p otherwise.
230    /// \param i The item.
231    /// \param p The priority.
232    void set(const Item &i, const Prio &p) {
233      int idx = index[i];
234      if (idx < 0) {
235        push(i,p);
236      } else if (p > data[idx].value) {
237        increase(i, p);
238      } else {
239        decrease(i, p);
240      }
241    }
242
243    /// \brief Decreases the priority of \c i to \c p.
244
245    /// This method decreases the priority of item \c i to \c p.
246    /// \pre \c i must be stored in the heap with priority at least \c
247    /// p relative to \c Compare.
248    /// \param i The item.
249    /// \param p The priority.
250    void decrease(const Item &i, const Prio &p) {
251      int idx = index[i];
252      unlace(idx);
253      data[idx].value = p;
254      if (p < minimal) {
255        minimal = p;
256      }
257      lace(idx);
258    }
259   
260    /// \brief Increases the priority of \c i to \c p.
261    ///
262    /// This method sets the priority of item \c i to \c p.
263    /// \pre \c i must be stored in the heap with priority at most \c
264    /// p relative to \c Compare.
265    /// \param i The item.
266    /// \param p The priority.
267    void increase(const Item &i, const Prio &p) {
268      int idx = index[i];
269      unlace(idx);
270      data[idx].value = p;
271      lace(idx);
272    }
273
274    /// \brief Returns if \c item is in, has already been in, or has
275    /// never been in the heap.
276    ///
277    /// This method returns PRE_HEAP if \c item has never been in the
278    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
279    /// otherwise. In the latter case it is possible that \c item will
280    /// get back to the heap again.
281    /// \param i The item.
282    state_enum state(const Item &i) const {
283      int idx = index[i];
284      if (idx >= 0) idx = 0;
285      return state_enum(idx);
286    }
287
288    /// \brief Sets the state of the \c item in the heap.
289    ///
290    /// Sets the state of the \c item in the heap. It can be used to
291    /// manually clear the heap when it is important to achive the
292    /// better time complexity.
293    /// \param i The item.
294    /// \param st The state. It should not be \c IN_HEAP.
295    void state(const Item& i, state_enum st) {
296      switch (st) {
297      case POST_HEAP:
298      case PRE_HEAP:
299        if (state(i) == IN_HEAP) {
300          erase(i);
301        }
302        index[i] = st;
303        break;
304      case IN_HEAP:
305        break;
306      }
307    }
308
309  private:
310
311    struct BucketItem {
312      BucketItem(const Item& _item, int _value)
313        : item(_item), value(_value) {}
314
315      Item item;
316      int value;
317
318      int prev, next;
319    };
320
321    ItemIntMap& index;
322    std::vector<int> first;
323    std::vector<BucketItem> data;
324    mutable int minimal;
325
326  }; // class BucketHeap
327
328
329  template <typename _Item, typename _ItemIntMap>
330  class BucketHeap<_Item, _ItemIntMap, false> {
331
332  public:
333    typedef _Item Item;
334    typedef int Prio;
335    typedef std::pair<Item, Prio> Pair;
336    typedef _ItemIntMap ItemIntMap;
337
338    enum state_enum {
339      IN_HEAP = 0,
340      PRE_HEAP = -1,
341      POST_HEAP = -2
342    };
343
344  public:
345
346    explicit BucketHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
347
348    int size() const { return data.size(); }
349    bool empty() const { return data.empty(); }
350
351    void clear() {
352      data.clear(); first.clear(); maximal = -1;
353    }
354
355  private:
356
357    void relocate_last(int idx) {
358      if (idx + 1 != (int)data.size()) {
359        data[idx] = data.back();
360        if (data[idx].prev != -1) {
361          data[data[idx].prev].next = idx;
362        } else {
363          first[data[idx].value] = idx;
364        }
365        if (data[idx].next != -1) {
366          data[data[idx].next].prev = idx;
367        }
368        index[data[idx].item] = idx;
369      }
370      data.pop_back();
371    }
372
373    void unlace(int idx) {
374      if (data[idx].prev != -1) {
375        data[data[idx].prev].next = data[idx].next;
376      } else {
377        first[data[idx].value] = data[idx].next;
378      }
379      if (data[idx].next != -1) {
380        data[data[idx].next].prev = data[idx].prev;
381      }
382    }
383
384    void lace(int idx) {
385      if ((int)first.size() <= data[idx].value) {
386        first.resize(data[idx].value + 1, -1);
387      }
388      data[idx].next = first[data[idx].value];
389      if (data[idx].next != -1) {
390        data[data[idx].next].prev = idx;
391      }
392      first[data[idx].value] = idx;
393      data[idx].prev = -1;
394    }
395
396  public:
397
398    void push(const Pair& p) {
399      push(p.first, p.second);
400    }
401
402    void push(const Item &i, const Prio &p) {
403      int idx = data.size();
404      index[i] = idx;
405      data.push_back(BucketItem(i, p));
406      lace(idx);
407      if (data[idx].value > maximal) {
408        maximal = data[idx].value;
409      }
410    }
411
412    Item top() const {
413      while (first[maximal] == -1) {
414        --maximal;
415      }
416      return data[first[maximal]].item;
417    }
418
419    Prio prio() const {
420      while (first[maximal] == -1) {
421        --maximal;
422      }
423      return maximal;
424    }
425
426    void pop() {
427      while (first[maximal] == -1) {
428        --maximal;
429      }
430      int idx = first[maximal];
431      index[data[idx].item] = -2;
432      unlace(idx);
433      relocate_last(idx);
434    }
435
436    void erase(const Item &i) {
437      int idx = index[i];
438      index[data[idx].item] = -2;
439      unlace(idx);
440      relocate_last(idx);
441    }
442
443    Prio operator[](const Item &i) const {
444      int idx = index[i];
445      return data[idx].value;
446    }
447
448    void set(const Item &i, const Prio &p) {
449      int idx = index[i];
450      if (idx < 0) {
451        push(i,p);
452      } else if (p > data[idx].value) {
453        decrease(i, p);
454      } else {
455        increase(i, p);
456      }
457    }
458
459    void decrease(const Item &i, const Prio &p) {
460      int idx = index[i];
461      unlace(idx);
462      data[idx].value = p;
463      if (p > maximal) {
464        maximal = p;
465      }
466      lace(idx);
467    }
468   
469    void increase(const Item &i, const Prio &p) {
470      int idx = index[i];
471      unlace(idx);
472      data[idx].value = p;
473      lace(idx);
474    }
475
476    state_enum state(const Item &i) const {
477      int idx = index[i];
478      if (idx >= 0) idx = 0;
479      return state_enum(idx);
480    }
481
482    void state(const Item& i, state_enum st) {
483      switch (st) {
484      case POST_HEAP:
485      case PRE_HEAP:
486        if (state(i) == IN_HEAP) {
487          erase(i);
488        }
489        index[i] = st;
490        break;
491      case IN_HEAP:
492        break;
493      }
494    }
495
496  private:
497
498    struct BucketItem {
499      BucketItem(const Item& _item, int _value)
500        : item(_item), value(_value) {}
501
502      Item item;
503      int value;
504
505      int prev, next;
506    };
507
508    ItemIntMap& index;
509    std::vector<int> first;
510    std::vector<BucketItem> data;
511    mutable int maximal;
512
513  }; // class BucketHeap
514
515}
516 
517#endif
Note: See TracBrowser for help on using the repository browser.