1.1 --- a/src/work/jacint/bin_heap.hh Sat Mar 20 17:01:45 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,233 +0,0 @@
1.4 -/* FIXME: Copyright ...
1.5 - *
1.6 - * This implementation is heavily based on STL's heap functions and
1.7 - * the similar class by Alpar Juttner in IKTA...
1.8 - */
1.9 -
1.10 -/******
1.11 - *
1.12 - * BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]>
1.13 - *
1.14 - * Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot
1.15 - * valosit meg.
1.16 - * A kupacban legfolul mindig az a par talalhato, amiben az _ertek_ a
1.17 - * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
1.18 - * lett keszitve...)
1.19 - *
1.20 - * Megjegyzes: egy kicsit gyanus nekem, hogy a kupacos temakorben nem
1.21 - * azt hivjak kulcsnak, amit most en annak nevezek. :) En olyan
1.22 - * property_map -os ertelemben hasznalom.
1.23 - *
1.24 - * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
1.25 - * a kulcsokhoz egy int-et tud tarolni (ezzel tudom megkeresni az illeto
1.26 - * elemet a kupacban a csokkentes es hasonlo muveletekhez).
1.27 - * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
1.28 - * is elnie kell. (???)
1.29 - *
1.30 - * Ketfele modon hasznalhato:
1.31 - * Lusta mod:
1.32 - * put(Key, Value) metodussal pakolunk a kupacba,
1.33 - * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
1.34 - * csokkentettunk-e rajta, vagy noveltunk.
1.35 - * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
1.36 - * minden szobajovo kulcs ertekre, -1 -es ertekkel!
1.37 - * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
1.38 - * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
1.39 - * mar kikerult a kupacbol POST_HEAP=-2).
1.40 - * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
1.41 - * meg meg tudja mondani a "legkisebb" erteku elemet. De csak nagyjabol,
1.42 - * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
1.43 - *
1.44 - * Kozvetlen mod:
1.45 - * push(Key, Value) metodussal belerakunk a kupacba (ha az illeto kulcs mar
1.46 - * benn volt, akkor gaz).
1.47 - * increase/decrease(Key k, Value new_value) metodusokkal lehet
1.48 - * novelni/csokkenteni az illeto kulcshoz tartozo erteket. (Ha nem volt meg
1.49 - * benne a kupacban az illeto kulcs, vagy nem abba az iranyba valtoztattad
1.50 - * az erteket, amerre mondtad -- gaz).
1.51 - *
1.52 - * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
1.53 - * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
1.54 - * hasznal. :-))
1.55 - *
1.56 - *
1.57 - * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
1.58 - *
1.59 - */
1.60 -
1.61 -
1.62 -#ifndef BIN_HEAP_HH
1.63 -#define BIN_HEAP_HH
1.64 -
1.65 -#include <vector>
1.66 -#include <utility>
1.67 -#include <functional>
1.68 -
1.69 -namespace hugo {
1.70 -
1.71 - template <typename Key, typename Val, typename KeyIntMap,
1.72 - typename Compare = std::less<Val> >
1.73 - class BinHeap {
1.74 -
1.75 - public:
1.76 - typedef Key KeyType;
1.77 - // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
1.78 - typedef Val ValueType;
1.79 - typedef std::pair<KeyType,ValueType> PairType;
1.80 - typedef KeyIntMap KeyIntMapType;
1.81 - typedef Compare ValueCompare;
1.82 -
1.83 - /**
1.84 - * Each Key element have a state associated to it. It may be "in heap",
1.85 - * "pre heap" or "post heap". The later two are indifferent from the
1.86 - * heap's point of view, but may be useful to the user.
1.87 - *
1.88 - * The KeyIntMap _should_ be initialized in such way, that it maps
1.89 - * PRE_HEAP (-1) to any element to be put in the heap...
1.90 - */
1.91 - enum state_enum {
1.92 - IN_HEAP = 0,
1.93 - PRE_HEAP = -1,
1.94 - POST_HEAP = -2
1.95 - };
1.96 -
1.97 - private:
1.98 - std::vector<PairType> data;
1.99 - Compare comp;
1.100 - // FIXME: jo ez igy???
1.101 - KeyIntMap &kim;
1.102 -
1.103 - public:
1.104 - BinHeap(KeyIntMap &_kim) : kim(_kim) {}
1.105 - BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
1.106 -
1.107 -
1.108 - int size() const { return data.size(); }
1.109 - bool empty() const { return data.empty(); }
1.110 -
1.111 - private:
1.112 - static int parent(int i) { return (i-1)/2; }
1.113 - static int second_child(int i) { return 2*i+2; }
1.114 - bool less(const PairType &p1, const PairType &p2) {
1.115 - return comp(p1.second, p2.second);
1.116 - }
1.117 -
1.118 - int bubble_up(int hole, PairType p);
1.119 - int bubble_down(int hole, PairType p, int length);
1.120 -
1.121 - void move(const PairType &p, int i) {
1.122 - data[i] = p;
1.123 - kim.set(p.first, i);
1.124 - }
1.125 -
1.126 - void rmidx(int h) {
1.127 - int n = data.size()-1;
1.128 - if( h>=0 && h<=n ) {
1.129 - kim.set(data[h].first, POST_HEAP);
1.130 - if ( h<n ) {
1.131 - bubble_down(h, data[n], n);
1.132 - }
1.133 - data.pop_back();
1.134 - }
1.135 - }
1.136 -
1.137 - public:
1.138 - void push(const PairType &p) {
1.139 - int n = data.size();
1.140 - data.resize(n+1);
1.141 - bubble_up(n, p);
1.142 - }
1.143 - void push(const Key &k, const Val &v) { push(PairType(k,v)); }
1.144 -
1.145 - Key top() const {
1.146 - // FIXME: test size>0 ?
1.147 - return data[0].first;
1.148 - }
1.149 - Val topValue() const {
1.150 - // FIXME: test size>0 ?
1.151 - return data[0].second;
1.152 - }
1.153 -
1.154 - void pop() {
1.155 - rmidx(0);
1.156 - }
1.157 -
1.158 - void erase(const Key &k) {
1.159 - rmidx(kim[k]);
1.160 - }
1.161 -
1.162 - Val operator[](const Key &k) const {
1.163 - int idx = kim[k];
1.164 - return data[idx].second;
1.165 - }
1.166 -
1.167 - void put(const Key &k, const Val &v) {
1.168 - int idx = kim[k];
1.169 - if( idx < 0 ) {
1.170 - push(k,v);
1.171 - }
1.172 - else if( comp(v, data[idx].second) ) {
1.173 - bubble_up(idx, PairType(k,v));
1.174 - }
1.175 - else {
1.176 - bubble_down(idx, PairType(k,v), data.size());
1.177 - }
1.178 - }
1.179 -
1.180 - void decrease(const Key &k, const Val &v) {
1.181 - int idx = kim[k];
1.182 - bubble_up(idx, PairType(k,v));
1.183 - }
1.184 - void increase(const Key &k, const Val &v) {
1.185 - int idx = kim[k];
1.186 - bubble_down(idx, PairType(k,v), data.size());
1.187 - }
1.188 -
1.189 - state_enum state(const Key &k) const {
1.190 - int s = kim[k];
1.191 - if( s>=0 )
1.192 - s=0;
1.193 - return state_enum(s);
1.194 - }
1.195 -
1.196 - }; // class BinHeap
1.197 -
1.198 -
1.199 - template <typename K, typename V, typename M, typename C>
1.200 - int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
1.201 - int par = parent(hole);
1.202 - while( hole>0 && less(p,data[par]) ) {
1.203 - move(data[par],hole);
1.204 - hole = par;
1.205 - par = parent(hole);
1.206 - }
1.207 - move(p, hole);
1.208 - return hole;
1.209 - }
1.210 -
1.211 - template <typename K, typename V, typename M, typename C>
1.212 - int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
1.213 - int child = second_child(hole);
1.214 - while(child < length) {
1.215 - if( less(data[child-1], data[child]) ) {
1.216 - --child;
1.217 - }
1.218 - if( !less(data[child], p) )
1.219 - goto ok;
1.220 - move(data[child], hole);
1.221 - hole = child;
1.222 - child = second_child(hole);
1.223 - }
1.224 - child--;
1.225 - if( child<length && less(data[child], p) ) {
1.226 - move(data[child], hole);
1.227 - hole=child;
1.228 - }
1.229 - ok:
1.230 - move(p, hole);
1.231 - return hole;
1.232 - }
1.233 -
1.234 -} // namespace hugo
1.235 -
1.236 -#endif // BIN_HEAP_HH