COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/bin_heap.h @ 1202:da44ee225dad

Last change on this file since 1202:da44ee225dad was 1191:c988f12c6c0c, checked in by Balazs Dezso, 19 years ago

Correcting explicit declaration.

File size: 5.1 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/bin_heap.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, 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_BIN_HEAP_H
18#define LEMON_BIN_HEAP_H
19
20///\ingroup auxdat
21///\file
22///\brief Binary Heap implementation.
23///\todo It should be documented.
24
25#include <vector>
26#include <utility>
27#include <functional>
28
29namespace lemon {
30
31  /// \addtogroup auxdat
32  /// @{
33
34   /// A Binary Heap implementation.
35 
36  ///\todo Please document...
37  ///
38  ///\sa FibHeap
39  ///\sa Dijkstra
40  template <typename Item, typename Prio, typename ItemIntMap,
41            typename Compare = std::less<Prio> >
42  class BinHeap {
43
44  public:
45    typedef Item                             ItemType;
46    // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
47    typedef Prio                             PrioType;
48    typedef std::pair<ItemType,PrioType>     PairType;
49    typedef ItemIntMap                       ItemIntMapType;
50    typedef Compare                          PrioCompare;
51
52    /**
53     * Each Item element have a state associated to it. It may be "in heap",
54     * "pre heap" or "post heap". The later two are indifferent from the
55     * heap's point of view, but may be useful to the user.
56     *
57     * The ItemIntMap _should_ be initialized in such way, that it maps
58     * PRE_HEAP (-1) to any element to be put in the heap...
59     */
60    ///\todo it is used nowhere
61    ///
62    enum state_enum {
63      IN_HEAP = 0,
64      PRE_HEAP = -1,
65      POST_HEAP = -2
66    };
67
68  private:
69    std::vector<PairType> data;
70    Compare comp;
71    // FIXME: jo ez igy???
72    ItemIntMap &iim;
73
74  public:
75    ///\e
76    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
77    ///\e
78    BinHeap(ItemIntMap &_iim, const Compare &_comp)
79      : iim(_iim), comp(_comp) {}
80
81
82    ///\e
83    int size() const { return data.size(); }
84    ///\e
85    bool empty() const { return data.empty(); }
86
87  private:
88    static int parent(int i) { return (i-1)/2; }
89    static int second_child(int i) { return 2*i+2; }
90    bool less(const PairType &p1, const PairType &p2) const {
91      return comp(p1.second, p2.second);
92    }
93
94    int bubble_up(int hole, PairType p);
95    int bubble_down(int hole, PairType p, int length);
96
97    void move(const PairType &p, int i) {
98      data[i] = p;
99      iim.set(p.first, i);
100    }
101
102    void rmidx(int h) {
103      int n = data.size()-1;
104      if( h>=0 && h<=n ) {
105        iim.set(data[h].first, POST_HEAP);
106        if ( h<n ) {
107          bubble_down(h, data[n], n);
108        }
109        data.pop_back();
110      }
111    }
112
113  public:
114    ///\e
115    void push(const PairType &p) {
116      int n = data.size();
117      data.resize(n+1);
118      bubble_up(n, p);
119    }
120    ///\e
121    void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
122
123    ///\e
124    Item top() const {
125      return data[0].first;
126    }
127    /// Returns the prio of the top element of the heap.
128    Prio prio() const {
129      return data[0].second;
130    }
131
132    ///\e
133    void pop() {
134      rmidx(0);
135    }
136
137    ///\e
138    void erase(const Item &i) {
139      rmidx(iim[i]);
140    }
141
142    ///\e
143    Prio operator[](const Item &i) const {
144      int idx = iim[i];
145      return data[idx].second;
146    }
147
148    ///\e
149    void set(const Item &i, const Prio &p) {
150      int idx = iim[i];
151      if( idx < 0 ) {
152        push(i,p);
153      }
154      else if( comp(p, data[idx].second) ) {
155        bubble_up(idx, PairType(i,p));
156      }
157      else {
158        bubble_down(idx, PairType(i,p), data.size());
159      }
160    }
161
162    ///\e
163    void decrease(const Item &i, const Prio &p) {
164      int idx = iim[i];
165      bubble_up(idx, PairType(i,p));
166    }
167    ///\e
168    void increase(const Item &i, const Prio &p) {
169      int idx = iim[i];
170      bubble_down(idx, PairType(i,p), data.size());
171    }
172
173    ///\e
174    state_enum state(const Item &i) const {
175      int s = iim[i];
176      if( s>=0 )
177        s=0;
178      return state_enum(s);
179    }
180
181  }; // class BinHeap
182
183 
184  template <typename K, typename V, typename M, typename C>
185  int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
186    int par = parent(hole);
187    while( hole>0 && less(p,data[par]) ) {
188      move(data[par],hole);
189      hole = par;
190      par = parent(hole);
191    }
192    move(p, hole);
193    return hole;
194  }
195
196  template <typename K, typename V, typename M, typename C>
197  int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
198    int child = second_child(hole);
199    while(child < length) {
200      if( less(data[child-1], data[child]) ) {
201        --child;
202      }
203      if( !less(data[child], p) )
204        goto ok;
205      move(data[child], hole);
206      hole = child;
207      child = second_child(hole);
208    }
209    child--;
210    if( child<length && less(data[child], p) ) {
211      move(data[child], hole);
212      hole=child;
213    }
214  ok:
215    move(p, hole);
216    return hole;
217  }
218
219  ///@}
220
221} // namespace lemon
222
223#endif // LEMON_BIN_HEAP_H
Note: See TracBrowser for help on using the repository browser.