COIN-OR::LEMON - Graph Library

source: lemon/lemon/bucket_heap.h @ 1337:4add05447ca0

Last change on this file since 1337:4add05447ca0 was 956:141f9c0db4a3, checked in by Alpar Juttner <alpar@…>, 14 years ago

Unify the sources (#339)

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