1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/include/bin_heap.hh Tue Jan 27 19:16:38 2004 +0000
1.3 @@ -0,0 +1,159 @@
1.4 +#ifndef BIN_HEAP_HH
1.5 +#define BIN_HEAP_HH
1.6 +
1.7 +#include <vector>
1.8 +#include <utility>
1.9 +#include <functional>
1.10 +
1.11 +namespace marci {
1.12 +
1.13 + template <typename Key, typename Val, typename KeyIntMap,
1.14 + typename Compare = std::less<Val> >
1.15 + class BinHeap {
1.16 +
1.17 + public:
1.18 + typedef Key KeyType;
1.19 + // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
1.20 + typedef Val ValueType;
1.21 + typedef std::pair<KeyType,ValueType> PairType;
1.22 + typedef KeyIntMap KeyIntMapType;
1.23 + typedef Compare ValueCompare;
1.24 +
1.25 + /**
1.26 + * Each Key element have a state associated to it. It may be "in heap",
1.27 + * "pre heap" or "post heap". The later two are indifferent from the
1.28 + * heap's point of view, but may be useful to the user.
1.29 + *
1.30 + * The KeyIntMap _should_ be initialized in such way, that it maps
1.31 + * PRE_HEAP (-1) to any element to be put in the heap...
1.32 + */
1.33 +
1.34 + enum state {
1.35 + IN_HEAP = 0,
1.36 + PRE_HEAP = -1,
1.37 + POST_HEAP = -2
1.38 + };
1.39 +
1.40 + private:
1.41 + std::vector<PairType> data;
1.42 + Compare comp;
1.43 + // FIXME: jo ez igy???
1.44 + KeyIntMap &kim;
1.45 +
1.46 + public:
1.47 + BinHeap(KeyIntMap &_kim) : kim(_kim) {}
1.48 + BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
1.49 +
1.50 +
1.51 + int size() const { return data.size(); }
1.52 + bool empty() const { return size() == 0; }
1.53 +
1.54 + private:
1.55 + static int parent(int i) { return (i-1)/2; }
1.56 + static int second_child(int i) { return 2*i+2; }
1.57 + bool less(const PairType &p1, const PairType &p2) {
1.58 + return comp(p1.second, p2.second);
1.59 + }
1.60 +
1.61 + int bubble_up(int hole, PairType p);
1.62 + int bubble_down(int hole, PairType p, int length);
1.63 +
1.64 + void move(const PairType &p, int i) {
1.65 + data[i] = p;
1.66 + kim.put(p.first, i);
1.67 + }
1.68 +
1.69 + public:
1.70 + void push(const PairType &p) {
1.71 + int n = data.size();
1.72 + data.resize(n+1);
1.73 + bubble_up(n, p);
1.74 + }
1.75 + void push(const Key &k, const Val &v) { push(PairType(k,v)); }
1.76 +
1.77 + Key top() const {
1.78 + // FIXME: test size>0 ?
1.79 + return data[0].first;
1.80 + }
1.81 + Val topValue() const {
1.82 + // FIXME: test size>0 ?
1.83 + return data[0].second;
1.84 + }
1.85 +
1.86 + void pop() {
1.87 + int n = data.size()-1;
1.88 + if ( n>0 ) {
1.89 + bubble_down(0, data[n], n);
1.90 + }
1.91 + if ( n>=0 ) {
1.92 + data.pop_back();
1.93 + }
1.94 + }
1.95 +
1.96 + const Val get(const Key &k) const {
1.97 + int idx = kim.get(k);
1.98 + return data[idx].second;
1.99 + }
1.100 + void put(const Key &k, const Val &v) {
1.101 + int idx = kim.get(k);
1.102 + if( idx < 0 ) {
1.103 + push(k,v);
1.104 + }
1.105 + else if( comp(v, data[idx].second) ) {
1.106 + bubble_up(idx, PairType(k,v));
1.107 + }
1.108 + else {
1.109 + bubble_down(idx, PairType(k,v), data.size());
1.110 + }
1.111 + }
1.112 +
1.113 + void decrease(const Key &k, const Val &v) {
1.114 + int idx = kim.get(k);
1.115 + bubble_up(idx, PairType(k,v));
1.116 + }
1.117 + void increase(const Key &k, const Val &v) {
1.118 + int idx = kim.get(k);
1.119 + bubble_down(idx, PairType(k,v), data.size());
1.120 + }
1.121 +
1.122 + }; // class BinHeap
1.123 +
1.124 +
1.125 + template <typename K, typename V, typename M, typename C>
1.126 + int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
1.127 + int par = parent(hole);
1.128 + while( hole>0 && less(p,data[par]) ) {
1.129 + move(data[par],hole);
1.130 + hole = par;
1.131 + par = parent(hole);
1.132 + }
1.133 + move(p, hole);
1.134 + return hole;
1.135 + }
1.136 +
1.137 + template <typename K, typename V, typename M, typename C>
1.138 + int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
1.139 + int child = second_child(hole);
1.140 + while(child < length) {
1.141 + if( less(data[child-1], data[child]) ) {
1.142 + --child;
1.143 + }
1.144 + if( !less(data[child], p) )
1.145 + goto ok;
1.146 + move(data[child], hole);
1.147 + hole = child;
1.148 + child = second_child(hole);
1.149 + }
1.150 + child--;
1.151 + if( child<length && less(data[child], p) ) {
1.152 + move(data[child], hole);
1.153 + hole=child;
1.154 + }
1.155 + ok:
1.156 + move(p, hole);
1.157 + return hole;
1.158 + }
1.159 +
1.160 +} // namespace marci
1.161 +
1.162 +#endif // BIN_HEAP_HH