COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/include/bin_heap.hh @ 37:e0e41f9e2be5

Last change on this file since 37:e0e41f9e2be5 was 37:e0e41f9e2be5, checked in by Mihaly Barasz, 17 years ago

Generikus binaris kupac implementacio.
Alap demo file mukodesenek bemutatasahoz.

File size: 3.8 KB
Line 
1#ifndef BIN_HEAP_HH
2#define BIN_HEAP_HH
3
4#include <vector>
5#include <utility>
6#include <functional>
7
8namespace marci {
9
10  template <typename Key, typename Val, typename KeyIntMap,
11            typename Compare = std::less<Val> >
12  class BinHeap {
13
14  public:
15    typedef Key              KeyType;
16    // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
17    typedef Val              ValueType;
18    typedef std::pair<KeyType,ValueType>     PairType;
19    typedef KeyIntMap        KeyIntMapType;
20    typedef Compare          ValueCompare;
21
22    /**
23     * Each Key element have a state associated to it. It may be "in heap",
24     * "pre heap" or "post heap". The later two are indifferent from the
25     * heap's point of view, but may be useful to the user.
26     *
27     * The KeyIntMap _should_ be initialized in such way, that it maps
28     * PRE_HEAP (-1) to any element to be put in the heap...
29     */
30
31    enum state {
32      IN_HEAP = 0,
33      PRE_HEAP = -1,
34      POST_HEAP = -2
35    };
36
37  private:
38    std::vector<PairType> data;
39    Compare comp;
40    // FIXME: jo ez igy???
41    KeyIntMap &kim;
42
43  public:
44    BinHeap(KeyIntMap &_kim) : kim(_kim) {}
45    BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
46
47
48    int size() const { return data.size(); }
49    bool empty() const { return size() == 0; }
50
51  private:
52    static int parent(int i) { return (i-1)/2; }
53    static int second_child(int i) { return 2*i+2; }
54    bool less(const PairType &p1, const PairType &p2) {
55      return comp(p1.second, p2.second);
56    }
57
58    int bubble_up(int hole, PairType p);
59    int bubble_down(int hole, PairType p, int length);
60
61    void move(const PairType &p, int i) {
62      data[i] = p;
63      kim.put(p.first, i);
64    }
65
66  public:
67    void push(const PairType &p) {
68      int n = data.size();
69      data.resize(n+1);
70      bubble_up(n, p);
71    }
72    void push(const Key &k, const Val &v) { push(PairType(k,v)); }
73
74    Key top() const {
75      // FIXME: test size>0 ?
76      return data[0].first;
77    }
78    Val topValue() const {
79      // FIXME: test size>0 ?
80      return data[0].second;
81    }
82
83    void pop() {
84      int n = data.size()-1;
85      if ( n>0 ) {
86        bubble_down(0, data[n], n);
87      }
88      if ( n>=0 ) {
89        data.pop_back();
90      }
91    }
92
93    const Val get(const Key &k) const {
94      int idx = kim.get(k);
95      return data[idx].second;
96    }
97    void put(const Key &k, const Val &v) {
98      int idx = kim.get(k);
99      if( idx < 0 ) {
100        push(k,v);
101      }
102      else if( comp(v, data[idx].second) ) {
103        bubble_up(idx, PairType(k,v));
104      }
105      else {
106        bubble_down(idx, PairType(k,v), data.size());
107      }
108    }
109
110    void decrease(const Key &k, const Val &v) {
111      int idx = kim.get(k);
112      bubble_up(idx, PairType(k,v));
113    }
114    void increase(const Key &k, const Val &v) {
115      int idx = kim.get(k);
116      bubble_down(idx, PairType(k,v), data.size());
117    }
118
119  }; // class BinHeap
120
121 
122  template <typename K, typename V, typename M, typename C>
123  int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
124    int par = parent(hole);
125    while( hole>0 && less(p,data[par]) ) {
126      move(data[par],hole);
127      hole = par;
128      par = parent(hole);
129    }
130    move(p, hole);
131    return hole;
132  }
133
134  template <typename K, typename V, typename M, typename C>
135  int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
136    int child = second_child(hole);
137    while(child < length) {
138      if( less(data[child-1], data[child]) ) {
139        --child;
140      }
141      if( !less(data[child], p) )
142        goto ok;
143      move(data[child], hole);
144      hole = child;
145      child = second_child(hole);
146    }
147    child--;
148    if( child<length && less(data[child], p) ) {
149      move(data[child], hole);
150      hole=child;
151    }
152  ok:
153    move(p, hole);
154    return hole;
155  }
156
157} // namespace marci
158
159#endif // BIN_HEAP_HH
Note: See TracBrowser for help on using the repository browser.