COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/bin_heap.h @ 932:ade3cdb9b45d

Last change on this file since 932:ade3cdb9b45d was 921:818510fa3d99, checked in by Alpar Juttner, 16 years ago

hugo -> lemon

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