COIN-OR::LEMON - Graph Library

source: lemon/lemon/bucket_heap.h @ 730:9f529abcaebf

Last change on this file since 730:9f529abcaebf was 730:9f529abcaebf, checked in by Balazs Dezso <deba@…>, 10 years ago

Unification of names in heaps (#50)

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