COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/bin_heap.h @ 1021:fd1d073b6557

Last change on this file since 1021:fd1d073b6557 was 967:6563019430ba, checked in by Alpar Juttner, 16 years ago

Several changes in doc.

File size: 5.1 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.
[967]35 
36  ///\todo Please document...
37  ///
38  ///\sa FibHeap
39  ///\sa Dijkstra
[172]40  template <typename Item, typename Prio, typename ItemIntMap,
41            typename Compare = std::less<Prio> >
[37]42  class BinHeap {
43
44  public:
[172]45    typedef Item                             ItemType;
[37]46    // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
[172]47    typedef Prio                             PrioType;
48    typedef std::pair<ItemType,PrioType>     PairType;
49    typedef ItemIntMap                       ItemIntMapType;
50    typedef Compare                          PrioCompare;
[37]51
52    /**
[172]53     * Each Item element have a state associated to it. It may be "in heap",
[37]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     *
[172]57     * The ItemIntMap _should_ be initialized in such way, that it maps
[37]58     * PRE_HEAP (-1) to any element to be put in the heap...
59     */
[274]60    ///\todo it is used nowhere
61    ///
[39]62    enum state_enum {
[37]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???
[172]72    ItemIntMap &iim;
[37]73
74  public:
[967]75    ///\e
[172]76    BinHeap(ItemIntMap &_iim) : iim(_iim) {}
[967]77    ///\e
[172]78    BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
[37]79
80
[967]81    ///\e
[37]82    int size() const { return data.size(); }
[967]83    ///\e
[41]84    bool empty() const { return data.empty(); }
[37]85
86  private:
87    static int parent(int i) { return (i-1)/2; }
88    static int second_child(int i) { return 2*i+2; }
[214]89    bool less(const PairType &p1, const PairType &p2) const {
[37]90      return comp(p1.second, p2.second);
91    }
92
93    int bubble_up(int hole, PairType p);
94    int bubble_down(int hole, PairType p, int length);
95
96    void move(const PairType &p, int i) {
97      data[i] = p;
[172]98      iim.set(p.first, i);
[37]99    }
100
[41]101    void rmidx(int h) {
102      int n = data.size()-1;
103      if( h>=0 && h<=n ) {
[172]104        iim.set(data[h].first, POST_HEAP);
[41]105        if ( h<n ) {
106          bubble_down(h, data[n], n);
107        }
108        data.pop_back();
109      }
110    }
111
[37]112  public:
[967]113    ///\e
[37]114    void push(const PairType &p) {
115      int n = data.size();
116      data.resize(n+1);
117      bubble_up(n, p);
118    }
[967]119    ///\e
[172]120    void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
[37]121
[967]122    ///\e
[172]123    Item top() const {
[37]124      return data[0].first;
125    }
[274]126    /// Returns the prio of the top element of the heap.
127    Prio prio() const {
[37]128      return data[0].second;
129    }
130
[967]131    ///\e
[37]132    void pop() {
[41]133      rmidx(0);
134    }
135
[967]136    ///\e
[172]137    void erase(const Item &i) {
[221]138      rmidx(iim[i]);
[37]139    }
140
[967]141    ///\e
[274]142    Prio operator[](const Item &i) const {
[221]143      int idx = iim[i];
[37]144      return data[idx].second;
145    }
[274]146
[967]147    ///\e
[172]148    void set(const Item &i, const Prio &p) {
[221]149      int idx = iim[i];
[37]150      if( idx < 0 ) {
[172]151        push(i,p);
[37]152      }
[172]153      else if( comp(p, data[idx].second) ) {
154        bubble_up(idx, PairType(i,p));
[37]155      }
156      else {
[172]157        bubble_down(idx, PairType(i,p), data.size());
[37]158      }
159    }
160
[967]161    ///\e
[172]162    void decrease(const Item &i, const Prio &p) {
[221]163      int idx = iim[i];
[172]164      bubble_up(idx, PairType(i,p));
[37]165    }
[967]166    ///\e
[172]167    void increase(const Item &i, const Prio &p) {
[221]168      int idx = iim[i];
[172]169      bubble_down(idx, PairType(i,p), data.size());
[37]170    }
171
[967]172    ///\e
[172]173    state_enum state(const Item &i) const {
[221]174      int s = iim[i];
[39]175      if( s>=0 )
176        s=0;
177      return state_enum(s);
178    }
179
[37]180  }; // class BinHeap
181
182 
183  template <typename K, typename V, typename M, typename C>
184  int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
185    int par = parent(hole);
186    while( hole>0 && less(p,data[par]) ) {
187      move(data[par],hole);
188      hole = par;
189      par = parent(hole);
190    }
191    move(p, hole);
192    return hole;
193  }
194
195  template <typename K, typename V, typename M, typename C>
196  int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
197    int child = second_child(hole);
198    while(child < length) {
199      if( less(data[child-1], data[child]) ) {
200        --child;
201      }
202      if( !less(data[child], p) )
203        goto ok;
204      move(data[child], hole);
205      hole = child;
206      child = second_child(hole);
207    }
208    child--;
209    if( child<length && less(data[child], p) ) {
210      move(data[child], hole);
211      hole=child;
212    }
213  ok:
214    move(p, hole);
215    return hole;
216  }
217
[430]218  ///@}
219
[921]220} // namespace lemon
[37]221
[921]222#endif // LEMON_BIN_HEAP_H
Note: See TracBrowser for help on using the repository browser.