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

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/work/bin_heap_demo.cc	Tue Jan 27 19:16:38 2004 +0000
     2.3 @@ -0,0 +1,91 @@
     2.4 +#include <iostream>
     2.5 +#include <bin_heap.hh>
     2.6 +#include <string>
     2.7 +#include <map>
     2.8 +
     2.9 +using namespace marci;
    2.10 +using namespace std;
    2.11 +
    2.12 +class string_int_map;
    2.13 +
    2.14 +typedef BinHeap<string, double, string_int_map> StrDoubleHeap;
    2.15 +
    2.16 +class string_int_map : public map<string,int> {
    2.17 +public:
    2.18 +  int get(const string &s) {
    2.19 +    // Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy
    2.20 +    // hogy is mukodik ez a map :)
    2.21 +    if( count(s) == 0 ) {
    2.22 +      operator[](s) = StrDoubleHeap::PRE_HEAP;
    2.23 +    }
    2.24 +    return operator[](s);
    2.25 +  }
    2.26 +  void put(const string &s, int i) {
    2.27 +      operator[](s) = i;
    2.28 +  }
    2.29 +};
    2.30 +
    2.31 +
    2.32 +int main()
    2.33 +{
    2.34 +  string_int_map sim;
    2.35 +  
    2.36 +  
    2.37 +  cout << "testing string_int_map default value:\n";
    2.38 +  cout << "  alma: " << sim.get("alma") << endl;
    2.39 +
    2.40 +  cout << "creating the heap\n";
    2.41 +  StrDoubleHeap heap(sim);
    2.42 +
    2.43 +  cout << "heap.push(\"alma\", 15);\n";
    2.44 +  heap.push("alma", 15);
    2.45 +
    2.46 +  cout << "heap.put(\"korte\", 3.4);\n";
    2.47 +  heap.put("korte", 3.4);
    2.48 +
    2.49 +  cout << "heap.get(\"alma\") = " 
    2.50 +       << heap.get("alma")
    2.51 +       << endl;
    2.52 +
    2.53 +  cout << "heap.top() = "
    2.54 +       << heap.top() << endl;
    2.55 +  cout << "heap.topValue() = "
    2.56 +       << heap.topValue() << endl;
    2.57 +
    2.58 +  cout << "heap.decrease(\"alma\", 1.2);\n";
    2.59 +  heap.put("alma", 1.2);
    2.60 +
    2.61 +  cout << "heap.top() = "
    2.62 +       << heap.top() << endl;
    2.63 +  cout << "heap.topValue() = "
    2.64 +       << heap.topValue() << endl;
    2.65 +
    2.66 +  cout << "heap.put(\"alma\", 22);\n";
    2.67 +  heap.put("alma", 22);
    2.68 +
    2.69 +  cout << "heap.top() = "
    2.70 +       << heap.top() << endl;
    2.71 +  cout << "heap.topValue() = "
    2.72 +       << heap.topValue() << endl;
    2.73 +
    2.74 +  cout << "heap.size() = "
    2.75 +       << heap.size() << endl;
    2.76 +  cout << "heap.pop();\n";
    2.77 +  heap.pop();
    2.78 +
    2.79 +  cout << "heap.top() = "
    2.80 +       << heap.top() << endl;
    2.81 +  cout << "heap.topValue() = "
    2.82 +       << heap.topValue() << endl;
    2.83 +
    2.84 +  cout << "heap.size() = "
    2.85 +       << heap.size() << endl;
    2.86 +  cout << "heap.pop();\n";
    2.87 +  heap.pop();
    2.88 +
    2.89 +  cout << "heap.size() = "
    2.90 +       << heap.size() << endl;  
    2.91 +  cout << "heap.empty() = "
    2.92 +       << (heap.empty()?"true":"false") << endl;  
    2.93 +}
    2.94 +