1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/include/bin_heap.h Mon Mar 29 11:08:59 2004 +0000
1.3 @@ -0,0 +1,235 @@
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<ItemType, PrioType, ItemIntMap, [PrioCompare]>
1.13 + *
1.14 + * Ez az osztaly item-prioritas parok tarolasara alkalmas binaris kupacot
1.15 + * valosit meg.
1.16 + * A kupacban legfolul mindig az a par talalhato, amiben a prioritas a
1.17 + * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
1.18 + * lett keszitve...)
1.19 + *
1.20 + * Megjegyzes: a kupacos temakorokben a prioritast kulcsnak szoktak nevezni,
1.21 + * de mivel ez zavaro tud lenni a property-map-es kulcs-ertek szohasznalata
1.22 + * miatt, megprobaltunk valami semleges elnevezeseket kitalalni.
1.23 + *
1.24 + * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
1.25 + * az itemekhez 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 + * set(Item, Prio) 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" prioritasu elemet. De csak nagyjabol,
1.42 + * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
1.43 + *
1.44 + * Kozvetlen mod:
1.45 + * push(Item, Prio) metodussal belerakunk a kupacba (ha az illeto kulcs mar
1.46 + * benn volt, akkor gaz).
1.47 + * increase/decrease(Item i, Prio new_prio) metodusokkal lehet
1.48 + * novelni/csokkenteni az illeto elemhez tartozo prioritast. (Ha nem volt
1.49 + * megbenne a kupacban az illeto elem, 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 Item, typename Prio, typename ItemIntMap,
1.72 + typename Compare = std::less<Prio> >
1.73 + class BinHeap {
1.74 +
1.75 + public:
1.76 + typedef Item ItemType;
1.77 + // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
1.78 + typedef Prio PrioType;
1.79 + typedef std::pair<ItemType,PrioType> PairType;
1.80 + typedef ItemIntMap ItemIntMapType;
1.81 + typedef Compare PrioCompare;
1.82 +
1.83 + /**
1.84 + * Each Item 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 ItemIntMap _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 + ItemIntMap &iim;
1.102 +
1.103 + public:
1.104 + BinHeap(ItemIntMap &_iim) : iim(_iim) {}
1.105 + BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
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) const {
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 + iim.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 + iim.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 Item &i, const Prio &p) { push(PairType(i,p)); }
1.144 +
1.145 + Item top() const {
1.146 + // FIXME: test size>0 ?
1.147 + return data[0].first;
1.148 + }
1.149 + Prio topPrio() 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 Item &i) {
1.159 + rmidx(iim[i]);
1.160 + }
1.161 +
1.162 + Prio get(const Item &i) const {
1.163 + int idx = iim[i];
1.164 + return data[idx].second;
1.165 + }
1.166 + Prio operator[](const Item &i) const {
1.167 + return get(i);
1.168 + }
1.169 + void set(const Item &i, const Prio &p) {
1.170 + int idx = iim[i];
1.171 + if( idx < 0 ) {
1.172 + push(i,p);
1.173 + }
1.174 + else if( comp(p, data[idx].second) ) {
1.175 + bubble_up(idx, PairType(i,p));
1.176 + }
1.177 + else {
1.178 + bubble_down(idx, PairType(i,p), data.size());
1.179 + }
1.180 + }
1.181 +
1.182 + void decrease(const Item &i, const Prio &p) {
1.183 + int idx = iim[i];
1.184 + bubble_up(idx, PairType(i,p));
1.185 + }
1.186 + void increase(const Item &i, const Prio &p) {
1.187 + int idx = iim[i];
1.188 + bubble_down(idx, PairType(i,p), data.size());
1.189 + }
1.190 +
1.191 + state_enum state(const Item &i) const {
1.192 + int s = iim[i];
1.193 + if( s>=0 )
1.194 + s=0;
1.195 + return state_enum(s);
1.196 + }
1.197 +
1.198 + }; // class BinHeap
1.199 +
1.200 +
1.201 + template <typename K, typename V, typename M, typename C>
1.202 + int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
1.203 + int par = parent(hole);
1.204 + while( hole>0 && less(p,data[par]) ) {
1.205 + move(data[par],hole);
1.206 + hole = par;
1.207 + par = parent(hole);
1.208 + }
1.209 + move(p, hole);
1.210 + return hole;
1.211 + }
1.212 +
1.213 + template <typename K, typename V, typename M, typename C>
1.214 + int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
1.215 + int child = second_child(hole);
1.216 + while(child < length) {
1.217 + if( less(data[child-1], data[child]) ) {
1.218 + --child;
1.219 + }
1.220 + if( !less(data[child], p) )
1.221 + goto ok;
1.222 + move(data[child], hole);
1.223 + hole = child;
1.224 + child = second_child(hole);
1.225 + }
1.226 + child--;
1.227 + if( child<length && less(data[child], p) ) {
1.228 + move(data[child], hole);
1.229 + hole=child;
1.230 + }
1.231 + ok:
1.232 + move(p, hole);
1.233 + return hole;
1.234 + }
1.235 +
1.236 +} // namespace hugo
1.237 +
1.238 +#endif // BIN_HEAP_HH
2.1 --- a/src/include/bin_heap.hh Mon Mar 29 10:25:23 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,235 +0,0 @@
2.4 -/* FIXME: Copyright ...
2.5 - *
2.6 - * This implementation is heavily based on STL's heap functions and
2.7 - * the similar class by Alpar Juttner in IKTA...
2.8 - */
2.9 -
2.10 -/******
2.11 - *
2.12 - * BinHeap<ItemType, PrioType, ItemIntMap, [PrioCompare]>
2.13 - *
2.14 - * Ez az osztaly item-prioritas parok tarolasara alkalmas binaris kupacot
2.15 - * valosit meg.
2.16 - * A kupacban legfolul mindig az a par talalhato, amiben a prioritas a
2.17 - * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
2.18 - * lett keszitve...)
2.19 - *
2.20 - * Megjegyzes: a kupacos temakorokben a prioritast kulcsnak szoktak nevezni,
2.21 - * de mivel ez zavaro tud lenni a property-map-es kulcs-ertek szohasznalata
2.22 - * miatt, megprobaltunk valami semleges elnevezeseket kitalalni.
2.23 - *
2.24 - * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
2.25 - * az itemekhez egy int-et tud tarolni (ezzel tudom megkeresni az illeto
2.26 - * elemet a kupacban a csokkentes es hasonlo muveletekhez).
2.27 - * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
2.28 - * is elnie kell. (???)
2.29 - *
2.30 - * Ketfele modon hasznalhato:
2.31 - * Lusta mod:
2.32 - * set(Item, Prio) metodussal pakolunk a kupacba,
2.33 - * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
2.34 - * csokkentettunk-e rajta, vagy noveltunk.
2.35 - * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
2.36 - * minden szobajovo kulcs ertekre, -1 -es ertekkel!
2.37 - * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
2.38 - * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
2.39 - * mar kikerult a kupacbol POST_HEAP=-2).
2.40 - * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
2.41 - * meg meg tudja mondani a "legkisebb" prioritasu elemet. De csak nagyjabol,
2.42 - * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
2.43 - *
2.44 - * Kozvetlen mod:
2.45 - * push(Item, Prio) metodussal belerakunk a kupacba (ha az illeto kulcs mar
2.46 - * benn volt, akkor gaz).
2.47 - * increase/decrease(Item i, Prio new_prio) metodusokkal lehet
2.48 - * novelni/csokkenteni az illeto elemhez tartozo prioritast. (Ha nem volt
2.49 - * megbenne a kupacban az illeto elem, vagy nem abba az iranyba valtoztattad
2.50 - * az erteket, amerre mondtad -- gaz).
2.51 - *
2.52 - * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
2.53 - * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
2.54 - * hasznal. :-))
2.55 - *
2.56 - *
2.57 - * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
2.58 - *
2.59 - */
2.60 -
2.61 -
2.62 -#ifndef BIN_HEAP_HH
2.63 -#define BIN_HEAP_HH
2.64 -
2.65 -#include <vector>
2.66 -#include <utility>
2.67 -#include <functional>
2.68 -
2.69 -namespace hugo {
2.70 -
2.71 - template <typename Item, typename Prio, typename ItemIntMap,
2.72 - typename Compare = std::less<Prio> >
2.73 - class BinHeap {
2.74 -
2.75 - public:
2.76 - typedef Item ItemType;
2.77 - // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
2.78 - typedef Prio PrioType;
2.79 - typedef std::pair<ItemType,PrioType> PairType;
2.80 - typedef ItemIntMap ItemIntMapType;
2.81 - typedef Compare PrioCompare;
2.82 -
2.83 - /**
2.84 - * Each Item element have a state associated to it. It may be "in heap",
2.85 - * "pre heap" or "post heap". The later two are indifferent from the
2.86 - * heap's point of view, but may be useful to the user.
2.87 - *
2.88 - * The ItemIntMap _should_ be initialized in such way, that it maps
2.89 - * PRE_HEAP (-1) to any element to be put in the heap...
2.90 - */
2.91 - enum state_enum {
2.92 - IN_HEAP = 0,
2.93 - PRE_HEAP = -1,
2.94 - POST_HEAP = -2
2.95 - };
2.96 -
2.97 - private:
2.98 - std::vector<PairType> data;
2.99 - Compare comp;
2.100 - // FIXME: jo ez igy???
2.101 - ItemIntMap &iim;
2.102 -
2.103 - public:
2.104 - BinHeap(ItemIntMap &_iim) : iim(_iim) {}
2.105 - BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
2.106 -
2.107 -
2.108 - int size() const { return data.size(); }
2.109 - bool empty() const { return data.empty(); }
2.110 -
2.111 - private:
2.112 - static int parent(int i) { return (i-1)/2; }
2.113 - static int second_child(int i) { return 2*i+2; }
2.114 - bool less(const PairType &p1, const PairType &p2) const {
2.115 - return comp(p1.second, p2.second);
2.116 - }
2.117 -
2.118 - int bubble_up(int hole, PairType p);
2.119 - int bubble_down(int hole, PairType p, int length);
2.120 -
2.121 - void move(const PairType &p, int i) {
2.122 - data[i] = p;
2.123 - iim.set(p.first, i);
2.124 - }
2.125 -
2.126 - void rmidx(int h) {
2.127 - int n = data.size()-1;
2.128 - if( h>=0 && h<=n ) {
2.129 - iim.set(data[h].first, POST_HEAP);
2.130 - if ( h<n ) {
2.131 - bubble_down(h, data[n], n);
2.132 - }
2.133 - data.pop_back();
2.134 - }
2.135 - }
2.136 -
2.137 - public:
2.138 - void push(const PairType &p) {
2.139 - int n = data.size();
2.140 - data.resize(n+1);
2.141 - bubble_up(n, p);
2.142 - }
2.143 - void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
2.144 -
2.145 - Item top() const {
2.146 - // FIXME: test size>0 ?
2.147 - return data[0].first;
2.148 - }
2.149 - Prio topPrio() const {
2.150 - // FIXME: test size>0 ?
2.151 - return data[0].second;
2.152 - }
2.153 -
2.154 - void pop() {
2.155 - rmidx(0);
2.156 - }
2.157 -
2.158 - void erase(const Item &i) {
2.159 - rmidx(iim[i]);
2.160 - }
2.161 -
2.162 - Prio get(const Item &i) const {
2.163 - int idx = iim[i];
2.164 - return data[idx].second;
2.165 - }
2.166 - Prio operator[](const Item &i) const {
2.167 - return get(i);
2.168 - }
2.169 - void set(const Item &i, const Prio &p) {
2.170 - int idx = iim[i];
2.171 - if( idx < 0 ) {
2.172 - push(i,p);
2.173 - }
2.174 - else if( comp(p, data[idx].second) ) {
2.175 - bubble_up(idx, PairType(i,p));
2.176 - }
2.177 - else {
2.178 - bubble_down(idx, PairType(i,p), data.size());
2.179 - }
2.180 - }
2.181 -
2.182 - void decrease(const Item &i, const Prio &p) {
2.183 - int idx = iim[i];
2.184 - bubble_up(idx, PairType(i,p));
2.185 - }
2.186 - void increase(const Item &i, const Prio &p) {
2.187 - int idx = iim[i];
2.188 - bubble_down(idx, PairType(i,p), data.size());
2.189 - }
2.190 -
2.191 - state_enum state(const Item &i) const {
2.192 - int s = iim[i];
2.193 - if( s>=0 )
2.194 - s=0;
2.195 - return state_enum(s);
2.196 - }
2.197 -
2.198 - }; // class BinHeap
2.199 -
2.200 -
2.201 - template <typename K, typename V, typename M, typename C>
2.202 - int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
2.203 - int par = parent(hole);
2.204 - while( hole>0 && less(p,data[par]) ) {
2.205 - move(data[par],hole);
2.206 - hole = par;
2.207 - par = parent(hole);
2.208 - }
2.209 - move(p, hole);
2.210 - return hole;
2.211 - }
2.212 -
2.213 - template <typename K, typename V, typename M, typename C>
2.214 - int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
2.215 - int child = second_child(hole);
2.216 - while(child < length) {
2.217 - if( less(data[child-1], data[child]) ) {
2.218 - --child;
2.219 - }
2.220 - if( !less(data[child], p) )
2.221 - goto ok;
2.222 - move(data[child], hole);
2.223 - hole = child;
2.224 - child = second_child(hole);
2.225 - }
2.226 - child--;
2.227 - if( child<length && less(data[child], p) ) {
2.228 - move(data[child], hole);
2.229 - hole=child;
2.230 - }
2.231 - ok:
2.232 - move(p, hole);
2.233 - return hole;
2.234 - }
2.235 -
2.236 -} // namespace hugo
2.237 -
2.238 -#endif // BIN_HEAP_HH
3.1 --- a/src/include/dijkstra.h Mon Mar 29 10:25:23 2004 +0000
3.2 +++ b/src/include/dijkstra.h Mon Mar 29 11:08:59 2004 +0000
3.3 @@ -31,7 +31,7 @@
3.4 ///\brief Dijkstra algorithm.
3.5
3.6 #include <fib_heap.h>
3.7 -#include "bin_heap.hh"
3.8 +#include <bin_heap.h>
3.9 #include <invalid.h>
3.10
3.11 namespace hugo {
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/alpar/dijkstra/bin_heap.h Mon Mar 29 11:08:59 2004 +0000
4.3 @@ -0,0 +1,239 @@
4.4 +/* FIXME: Copyright ...
4.5 + *
4.6 + * This implementation is heavily based on STL's heap functions and
4.7 + * the similar class by Alpar Juttner in IKTA...
4.8 + */
4.9 +
4.10 +/******
4.11 + *
4.12 + * BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]>
4.13 + *
4.14 + * Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot
4.15 + * valosit meg.
4.16 + * A kupacban legfolul mindig az a par talalhato, amiben az _ertek_ a
4.17 + * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
4.18 + * lett keszitve...)
4.19 + *
4.20 + * Megjegyzes: egy kicsit gyanus nekem, hogy a kupacos temakorben nem
4.21 + * azt hivjak kulcsnak, amit most en annak nevezek. :) En olyan
4.22 + * property_map -os ertelemben hasznalom.
4.23 + *
4.24 + * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
4.25 + * a kulcsokhoz egy int-et tud tarolni (ezzel tudom megkeresni az illeto
4.26 + * elemet a kupacban a csokkentes es hasonlo muveletekhez).
4.27 + * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
4.28 + * is elnie kell. (???)
4.29 + *
4.30 + * Ketfele modon hasznalhato:
4.31 + * Lusta mod:
4.32 + * put(Key, Value) metodussal pakolunk a kupacba,
4.33 + * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
4.34 + * csokkentettunk-e rajta, vagy noveltunk.
4.35 + * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
4.36 + * minden szobajovo kulcs ertekre, -1 -es ertekkel!
4.37 + * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
4.38 + * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
4.39 + * mar kikerult a kupacbol POST_HEAP=-2).
4.40 + * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
4.41 + * meg meg tudja mondani a "legkisebb" erteku elemet. De csak nagyjabol,
4.42 + * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
4.43 + *
4.44 + * Kozvetlen mod:
4.45 + * push(Key, Value) metodussal belerakunk a kupacba (ha az illeto kulcs mar
4.46 + * benn volt, akkor gaz).
4.47 + * increase/decrease(Key k, Value new_value) metodusokkal lehet
4.48 + * novelni/csokkenteni az illeto kulcshoz tartozo erteket. (Ha nem volt meg
4.49 + * benne a kupacban az illeto kulcs, vagy nem abba az iranyba valtoztattad
4.50 + * az erteket, amerre mondtad -- gaz).
4.51 + *
4.52 + * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
4.53 + * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
4.54 + * hasznal. :-))
4.55 + *
4.56 + *
4.57 + * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
4.58 + *
4.59 + */
4.60 +
4.61 +
4.62 +#ifndef BIN_HEAP_HH
4.63 +#define BIN_HEAP_HH
4.64 +
4.65 +///\file
4.66 +///\brief Binary Heap implementation.
4.67 +
4.68 +#include <vector>
4.69 +#include <utility>
4.70 +#include <functional>
4.71 +
4.72 +namespace hugo {
4.73 +
4.74 + /// A Binary Heap implementation.
4.75 + template <typename Key, typename Val, typename KeyIntMap,
4.76 + typename Compare = std::less<Val> >
4.77 + class BinHeap {
4.78 +
4.79 + public:
4.80 + typedef Key KeyType;
4.81 + // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
4.82 + typedef Val ValueType;
4.83 + typedef std::pair<KeyType,ValueType> PairType;
4.84 + typedef KeyIntMap KeyIntMapType;
4.85 + typedef Compare ValueCompare;
4.86 +
4.87 + /**
4.88 + * Each Key element have a state associated to it. It may be "in heap",
4.89 + * "pre heap" or "post heap". The later two are indifferent from the
4.90 + * heap's point of view, but may be useful to the user.
4.91 + *
4.92 + * The KeyIntMap _should_ be initialized in such way, that it maps
4.93 + * PRE_HEAP (-1) to any element to be put in the heap...
4.94 + */
4.95 + ///\todo it is used nowhere
4.96 + ///
4.97 + enum state_enum {
4.98 + IN_HEAP = 0,
4.99 + PRE_HEAP = -1,
4.100 + POST_HEAP = -2
4.101 + };
4.102 +
4.103 + private:
4.104 + std::vector<PairType> data;
4.105 + Compare comp;
4.106 + // FIXME: jo ez igy???
4.107 + KeyIntMap &kim;
4.108 +
4.109 + public:
4.110 + BinHeap(KeyIntMap &_kim) : kim(_kim) {}
4.111 + BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
4.112 +
4.113 +
4.114 + int size() const { return data.size(); }
4.115 + bool empty() const { return data.empty(); }
4.116 +
4.117 + private:
4.118 + static int parent(int i) { return (i-1)/2; }
4.119 + static int second_child(int i) { return 2*i+2; }
4.120 + bool less(const PairType &p1, const PairType &p2) {
4.121 + return comp(p1.second, p2.second);
4.122 + }
4.123 +
4.124 + int bubble_up(int hole, PairType p);
4.125 + int bubble_down(int hole, PairType p, int length);
4.126 +
4.127 + void move(const PairType &p, int i) {
4.128 + data[i] = p;
4.129 + kim.set(p.first, i);
4.130 + }
4.131 +
4.132 + void rmidx(int h) {
4.133 + int n = data.size()-1;
4.134 + if( h>=0 && h<=n ) {
4.135 + kim.set(data[h].first, POST_HEAP);
4.136 + if ( h<n ) {
4.137 + bubble_down(h, data[n], n);
4.138 + }
4.139 + data.pop_back();
4.140 + }
4.141 + }
4.142 +
4.143 + public:
4.144 + void push(const PairType &p) {
4.145 + int n = data.size();
4.146 + data.resize(n+1);
4.147 + bubble_up(n, p);
4.148 + }
4.149 + void push(const Key &k, const Val &v) { push(PairType(k,v)); }
4.150 +
4.151 + Key top() const {
4.152 + // FIXME: test size>0 ?
4.153 + return data[0].first;
4.154 + }
4.155 + Val topValue() const {
4.156 + // FIXME: test size>0 ?
4.157 + return data[0].second;
4.158 + }
4.159 +
4.160 + void pop() {
4.161 + rmidx(0);
4.162 + }
4.163 +
4.164 + void erase(const Key &k) {
4.165 + rmidx(kim[k]);
4.166 + }
4.167 +
4.168 + Val operator[](const Key &k) const {
4.169 + int idx = kim[k];
4.170 + return data[idx].second;
4.171 + }
4.172 +
4.173 + void put(const Key &k, const Val &v) {
4.174 + int idx = kim[k];
4.175 + if( idx < 0 ) {
4.176 + push(k,v);
4.177 + }
4.178 + else if( comp(v, data[idx].second) ) {
4.179 + bubble_up(idx, PairType(k,v));
4.180 + }
4.181 + else {
4.182 + bubble_down(idx, PairType(k,v), data.size());
4.183 + }
4.184 + }
4.185 +
4.186 + void decrease(const Key &k, const Val &v) {
4.187 + int idx = kim[k];
4.188 + bubble_up(idx, PairType(k,v));
4.189 + }
4.190 + void increase(const Key &k, const Val &v) {
4.191 + int idx = kim[k];
4.192 + bubble_down(idx, PairType(k,v), data.size());
4.193 + }
4.194 +
4.195 + state_enum state(const Key &k) const {
4.196 + int s = kim[k];
4.197 + if( s>=0 )
4.198 + s=0;
4.199 + return state_enum(s);
4.200 + }
4.201 +
4.202 + }; // class BinHeap
4.203 +
4.204 +
4.205 + template <typename K, typename V, typename M, typename C>
4.206 + int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
4.207 + int par = parent(hole);
4.208 + while( hole>0 && less(p,data[par]) ) {
4.209 + move(data[par],hole);
4.210 + hole = par;
4.211 + par = parent(hole);
4.212 + }
4.213 + move(p, hole);
4.214 + return hole;
4.215 + }
4.216 +
4.217 + template <typename K, typename V, typename M, typename C>
4.218 + int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
4.219 + int child = second_child(hole);
4.220 + while(child < length) {
4.221 + if( less(data[child-1], data[child]) ) {
4.222 + --child;
4.223 + }
4.224 + if( !less(data[child], p) )
4.225 + goto ok;
4.226 + move(data[child], hole);
4.227 + hole = child;
4.228 + child = second_child(hole);
4.229 + }
4.230 + child--;
4.231 + if( child<length && less(data[child], p) ) {
4.232 + move(data[child], hole);
4.233 + hole=child;
4.234 + }
4.235 + ok:
4.236 + move(p, hole);
4.237 + return hole;
4.238 + }
4.239 +
4.240 +} // namespace hugo
4.241 +
4.242 +#endif // BIN_HEAP_HH
5.1 --- a/src/work/alpar/dijkstra/bin_heap.hh Mon Mar 29 10:25:23 2004 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,239 +0,0 @@
5.4 -/* FIXME: Copyright ...
5.5 - *
5.6 - * This implementation is heavily based on STL's heap functions and
5.7 - * the similar class by Alpar Juttner in IKTA...
5.8 - */
5.9 -
5.10 -/******
5.11 - *
5.12 - * BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]>
5.13 - *
5.14 - * Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot
5.15 - * valosit meg.
5.16 - * A kupacban legfolul mindig az a par talalhato, amiben az _ertek_ a
5.17 - * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
5.18 - * lett keszitve...)
5.19 - *
5.20 - * Megjegyzes: egy kicsit gyanus nekem, hogy a kupacos temakorben nem
5.21 - * azt hivjak kulcsnak, amit most en annak nevezek. :) En olyan
5.22 - * property_map -os ertelemben hasznalom.
5.23 - *
5.24 - * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
5.25 - * a kulcsokhoz egy int-et tud tarolni (ezzel tudom megkeresni az illeto
5.26 - * elemet a kupacban a csokkentes es hasonlo muveletekhez).
5.27 - * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
5.28 - * is elnie kell. (???)
5.29 - *
5.30 - * Ketfele modon hasznalhato:
5.31 - * Lusta mod:
5.32 - * put(Key, Value) metodussal pakolunk a kupacba,
5.33 - * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
5.34 - * csokkentettunk-e rajta, vagy noveltunk.
5.35 - * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
5.36 - * minden szobajovo kulcs ertekre, -1 -es ertekkel!
5.37 - * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
5.38 - * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
5.39 - * mar kikerult a kupacbol POST_HEAP=-2).
5.40 - * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
5.41 - * meg meg tudja mondani a "legkisebb" erteku elemet. De csak nagyjabol,
5.42 - * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
5.43 - *
5.44 - * Kozvetlen mod:
5.45 - * push(Key, Value) metodussal belerakunk a kupacba (ha az illeto kulcs mar
5.46 - * benn volt, akkor gaz).
5.47 - * increase/decrease(Key k, Value new_value) metodusokkal lehet
5.48 - * novelni/csokkenteni az illeto kulcshoz tartozo erteket. (Ha nem volt meg
5.49 - * benne a kupacban az illeto kulcs, vagy nem abba az iranyba valtoztattad
5.50 - * az erteket, amerre mondtad -- gaz).
5.51 - *
5.52 - * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
5.53 - * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
5.54 - * hasznal. :-))
5.55 - *
5.56 - *
5.57 - * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
5.58 - *
5.59 - */
5.60 -
5.61 -
5.62 -#ifndef BIN_HEAP_HH
5.63 -#define BIN_HEAP_HH
5.64 -
5.65 -///\file
5.66 -///\brief Binary Heap implementation.
5.67 -
5.68 -#include <vector>
5.69 -#include <utility>
5.70 -#include <functional>
5.71 -
5.72 -namespace hugo {
5.73 -
5.74 - /// A Binary Heap implementation.
5.75 - template <typename Key, typename Val, typename KeyIntMap,
5.76 - typename Compare = std::less<Val> >
5.77 - class BinHeap {
5.78 -
5.79 - public:
5.80 - typedef Key KeyType;
5.81 - // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
5.82 - typedef Val ValueType;
5.83 - typedef std::pair<KeyType,ValueType> PairType;
5.84 - typedef KeyIntMap KeyIntMapType;
5.85 - typedef Compare ValueCompare;
5.86 -
5.87 - /**
5.88 - * Each Key element have a state associated to it. It may be "in heap",
5.89 - * "pre heap" or "post heap". The later two are indifferent from the
5.90 - * heap's point of view, but may be useful to the user.
5.91 - *
5.92 - * The KeyIntMap _should_ be initialized in such way, that it maps
5.93 - * PRE_HEAP (-1) to any element to be put in the heap...
5.94 - */
5.95 - ///\todo it is used nowhere
5.96 - ///
5.97 - enum state_enum {
5.98 - IN_HEAP = 0,
5.99 - PRE_HEAP = -1,
5.100 - POST_HEAP = -2
5.101 - };
5.102 -
5.103 - private:
5.104 - std::vector<PairType> data;
5.105 - Compare comp;
5.106 - // FIXME: jo ez igy???
5.107 - KeyIntMap &kim;
5.108 -
5.109 - public:
5.110 - BinHeap(KeyIntMap &_kim) : kim(_kim) {}
5.111 - BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
5.112 -
5.113 -
5.114 - int size() const { return data.size(); }
5.115 - bool empty() const { return data.empty(); }
5.116 -
5.117 - private:
5.118 - static int parent(int i) { return (i-1)/2; }
5.119 - static int second_child(int i) { return 2*i+2; }
5.120 - bool less(const PairType &p1, const PairType &p2) {
5.121 - return comp(p1.second, p2.second);
5.122 - }
5.123 -
5.124 - int bubble_up(int hole, PairType p);
5.125 - int bubble_down(int hole, PairType p, int length);
5.126 -
5.127 - void move(const PairType &p, int i) {
5.128 - data[i] = p;
5.129 - kim.set(p.first, i);
5.130 - }
5.131 -
5.132 - void rmidx(int h) {
5.133 - int n = data.size()-1;
5.134 - if( h>=0 && h<=n ) {
5.135 - kim.set(data[h].first, POST_HEAP);
5.136 - if ( h<n ) {
5.137 - bubble_down(h, data[n], n);
5.138 - }
5.139 - data.pop_back();
5.140 - }
5.141 - }
5.142 -
5.143 - public:
5.144 - void push(const PairType &p) {
5.145 - int n = data.size();
5.146 - data.resize(n+1);
5.147 - bubble_up(n, p);
5.148 - }
5.149 - void push(const Key &k, const Val &v) { push(PairType(k,v)); }
5.150 -
5.151 - Key top() const {
5.152 - // FIXME: test size>0 ?
5.153 - return data[0].first;
5.154 - }
5.155 - Val topValue() const {
5.156 - // FIXME: test size>0 ?
5.157 - return data[0].second;
5.158 - }
5.159 -
5.160 - void pop() {
5.161 - rmidx(0);
5.162 - }
5.163 -
5.164 - void erase(const Key &k) {
5.165 - rmidx(kim[k]);
5.166 - }
5.167 -
5.168 - Val operator[](const Key &k) const {
5.169 - int idx = kim[k];
5.170 - return data[idx].second;
5.171 - }
5.172 -
5.173 - void put(const Key &k, const Val &v) {
5.174 - int idx = kim[k];
5.175 - if( idx < 0 ) {
5.176 - push(k,v);
5.177 - }
5.178 - else if( comp(v, data[idx].second) ) {
5.179 - bubble_up(idx, PairType(k,v));
5.180 - }
5.181 - else {
5.182 - bubble_down(idx, PairType(k,v), data.size());
5.183 - }
5.184 - }
5.185 -
5.186 - void decrease(const Key &k, const Val &v) {
5.187 - int idx = kim[k];
5.188 - bubble_up(idx, PairType(k,v));
5.189 - }
5.190 - void increase(const Key &k, const Val &v) {
5.191 - int idx = kim[k];
5.192 - bubble_down(idx, PairType(k,v), data.size());
5.193 - }
5.194 -
5.195 - state_enum state(const Key &k) const {
5.196 - int s = kim[k];
5.197 - if( s>=0 )
5.198 - s=0;
5.199 - return state_enum(s);
5.200 - }
5.201 -
5.202 - }; // class BinHeap
5.203 -
5.204 -
5.205 - template <typename K, typename V, typename M, typename C>
5.206 - int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
5.207 - int par = parent(hole);
5.208 - while( hole>0 && less(p,data[par]) ) {
5.209 - move(data[par],hole);
5.210 - hole = par;
5.211 - par = parent(hole);
5.212 - }
5.213 - move(p, hole);
5.214 - return hole;
5.215 - }
5.216 -
5.217 - template <typename K, typename V, typename M, typename C>
5.218 - int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
5.219 - int child = second_child(hole);
5.220 - while(child < length) {
5.221 - if( less(data[child-1], data[child]) ) {
5.222 - --child;
5.223 - }
5.224 - if( !less(data[child], p) )
5.225 - goto ok;
5.226 - move(data[child], hole);
5.227 - hole = child;
5.228 - child = second_child(hole);
5.229 - }
5.230 - child--;
5.231 - if( child<length && less(data[child], p) ) {
5.232 - move(data[child], hole);
5.233 - hole=child;
5.234 - }
5.235 - ok:
5.236 - move(p, hole);
5.237 - return hole;
5.238 - }
5.239 -
5.240 -} // namespace hugo
5.241 -
5.242 -#endif // BIN_HEAP_HH
6.1 --- a/src/work/alpar/dijkstra/dijkstra.cc Mon Mar 29 10:25:23 2004 +0000
6.2 +++ b/src/work/alpar/dijkstra/dijkstra.cc Mon Mar 29 11:08:59 2004 +0000
6.3 @@ -7,7 +7,7 @@
6.4 #include <dijkstra.h>
6.5 #include <time_measure.h>
6.6
6.7 -#include <bin_heap.hh>
6.8 +#include <bin_heap.h>
6.9 #include <fib_heap.h>
6.10
6.11 using namespace hugo;
7.1 --- a/src/work/bin_heap_demo.cc Mon Mar 29 10:25:23 2004 +0000
7.2 +++ b/src/work/bin_heap_demo.cc Mon Mar 29 11:08:59 2004 +0000
7.3 @@ -1,5 +1,5 @@
7.4 #include <iostream>
7.5 -#include <bin_heap.hh>
7.6 +#include <bin_heap.h>
7.7 #include <string>
7.8 #include <map>
7.9
8.1 --- a/src/work/jacint/dijkstra.cc Mon Mar 29 10:25:23 2004 +0000
8.2 +++ b/src/work/jacint/dijkstra.cc Mon Mar 29 11:08:59 2004 +0000
8.3 @@ -7,7 +7,7 @@
8.4 #include <dijkstra.h>
8.5 #include <time_measure.h>
8.6
8.7 -#include <bin_heap.hh>
8.8 +#include <bin_heap.h>
8.9 #include <fib_heap.h>
8.10
8.11 using namespace hugo;
9.1 --- a/src/work/jacint/prim.cc Mon Mar 29 10:25:23 2004 +0000
9.2 +++ b/src/work/jacint/prim.cc Mon Mar 29 11:08:59 2004 +0000
9.3 @@ -7,7 +7,7 @@
9.4 #include <prim.h>
9.5 #include <time_measure.h>
9.6
9.7 -#include <bin_heap.hh>
9.8 +#include <bin_heap.h>
9.9 #include <fib_heap.h>
9.10
9.11 using namespace hugo;