1.1 --- a/doc/Doxyfile Thu Apr 01 15:32:31 2004 +0000
1.2 +++ b/doc/Doxyfile Thu Apr 01 21:06:53 2004 +0000
1.3 @@ -396,7 +396,7 @@
1.4 ../src/include/smart_graph.h \
1.5 ../src/include/skeletons/maps.h \
1.6 ../src/include/dijkstra.h \
1.7 - ../src/demo/alpar/dijkstra/bin_heap.h \
1.8 + ../src/include/bin_heap.h \
1.9 ../src/include/fib_heap.h \
1.10 ../src/demo/athos/xy/xy.h \
1.11 maps.dox
2.1 --- a/src/include/bin_heap.h Thu Apr 01 15:32:31 2004 +0000
2.2 +++ b/src/include/bin_heap.h Thu Apr 01 21:06:53 2004 +0000
2.3 @@ -1,3 +1,5 @@
2.4 +// -*- C++ -*- //
2.5 +
2.6 /* FIXME: Copyright ...
2.7 *
2.8 * This implementation is heavily based on STL's heap functions and
2.9 @@ -59,12 +61,16 @@
2.10 #ifndef BIN_HEAP_HH
2.11 #define BIN_HEAP_HH
2.12
2.13 +///\file
2.14 +///\brief Binary Heap implementation.
2.15 +
2.16 #include <vector>
2.17 #include <utility>
2.18 #include <functional>
2.19
2.20 namespace hugo {
2.21
2.22 + /// A Binary Heap implementation.
2.23 template <typename Item, typename Prio, typename ItemIntMap,
2.24 typename Compare = std::less<Prio> >
2.25 class BinHeap {
2.26 @@ -85,6 +91,8 @@
2.27 * The ItemIntMap _should_ be initialized in such way, that it maps
2.28 * PRE_HEAP (-1) to any element to be put in the heap...
2.29 */
2.30 + ///\todo it is used nowhere
2.31 + ///
2.32 enum state_enum {
2.33 IN_HEAP = 0,
2.34 PRE_HEAP = -1,
2.35 @@ -140,11 +148,10 @@
2.36 void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
2.37
2.38 Item top() const {
2.39 - // FIXME: test size>0 ?
2.40 return data[0].first;
2.41 }
2.42 - Prio topPrio() const {
2.43 - // FIXME: test size>0 ?
2.44 + /// Returns the prio of the top element of the heap.
2.45 + Prio prio() const {
2.46 return data[0].second;
2.47 }
2.48
2.49 @@ -156,13 +163,11 @@
2.50 rmidx(iim[i]);
2.51 }
2.52
2.53 - Prio get(const Item &i) const {
2.54 + Prio operator[](const Item &i) const {
2.55 int idx = iim[i];
2.56 return data[idx].second;
2.57 }
2.58 - Prio operator[](const Item &i) const {
2.59 - return get(i);
2.60 - }
2.61 +
2.62 void set(const Item &i, const Prio &p) {
2.63 int idx = iim[i];
2.64 if( idx < 0 ) {
3.1 --- a/src/work/alpar/dijkstra/bin_heap.h Thu Apr 01 15:32:31 2004 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,239 +0,0 @@
3.4 -/* FIXME: Copyright ...
3.5 - *
3.6 - * This implementation is heavily based on STL's heap functions and
3.7 - * the similar class by Alpar Juttner in IKTA...
3.8 - */
3.9 -
3.10 -/******
3.11 - *
3.12 - * BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]>
3.13 - *
3.14 - * Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot
3.15 - * valosit meg.
3.16 - * A kupacban legfolul mindig az a par talalhato, amiben az _ertek_ a
3.17 - * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
3.18 - * lett keszitve...)
3.19 - *
3.20 - * Megjegyzes: egy kicsit gyanus nekem, hogy a kupacos temakorben nem
3.21 - * azt hivjak kulcsnak, amit most en annak nevezek. :) En olyan
3.22 - * property_map -os ertelemben hasznalom.
3.23 - *
3.24 - * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
3.25 - * a kulcsokhoz egy int-et tud tarolni (ezzel tudom megkeresni az illeto
3.26 - * elemet a kupacban a csokkentes es hasonlo muveletekhez).
3.27 - * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
3.28 - * is elnie kell. (???)
3.29 - *
3.30 - * Ketfele modon hasznalhato:
3.31 - * Lusta mod:
3.32 - * put(Key, Value) metodussal pakolunk a kupacba,
3.33 - * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
3.34 - * csokkentettunk-e rajta, vagy noveltunk.
3.35 - * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
3.36 - * minden szobajovo kulcs ertekre, -1 -es ertekkel!
3.37 - * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
3.38 - * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
3.39 - * mar kikerult a kupacbol POST_HEAP=-2).
3.40 - * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
3.41 - * meg meg tudja mondani a "legkisebb" erteku elemet. De csak nagyjabol,
3.42 - * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
3.43 - *
3.44 - * Kozvetlen mod:
3.45 - * push(Key, Value) metodussal belerakunk a kupacba (ha az illeto kulcs mar
3.46 - * benn volt, akkor gaz).
3.47 - * increase/decrease(Key k, Value new_value) metodusokkal lehet
3.48 - * novelni/csokkenteni az illeto kulcshoz tartozo erteket. (Ha nem volt meg
3.49 - * benne a kupacban az illeto kulcs, vagy nem abba az iranyba valtoztattad
3.50 - * az erteket, amerre mondtad -- gaz).
3.51 - *
3.52 - * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
3.53 - * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
3.54 - * hasznal. :-))
3.55 - *
3.56 - *
3.57 - * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
3.58 - *
3.59 - */
3.60 -
3.61 -
3.62 -#ifndef BIN_HEAP_HH
3.63 -#define BIN_HEAP_HH
3.64 -
3.65 -///\file
3.66 -///\brief Binary Heap implementation.
3.67 -
3.68 -#include <vector>
3.69 -#include <utility>
3.70 -#include <functional>
3.71 -
3.72 -namespace hugo {
3.73 -
3.74 - /// A Binary Heap implementation.
3.75 - template <typename Key, typename Val, typename KeyIntMap,
3.76 - typename Compare = std::less<Val> >
3.77 - class BinHeap {
3.78 -
3.79 - public:
3.80 - typedef Key KeyType;
3.81 - // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
3.82 - typedef Val ValueType;
3.83 - typedef std::pair<KeyType,ValueType> PairType;
3.84 - typedef KeyIntMap KeyIntMapType;
3.85 - typedef Compare ValueCompare;
3.86 -
3.87 - /**
3.88 - * Each Key element have a state associated to it. It may be "in heap",
3.89 - * "pre heap" or "post heap". The later two are indifferent from the
3.90 - * heap's point of view, but may be useful to the user.
3.91 - *
3.92 - * The KeyIntMap _should_ be initialized in such way, that it maps
3.93 - * PRE_HEAP (-1) to any element to be put in the heap...
3.94 - */
3.95 - ///\todo it is used nowhere
3.96 - ///
3.97 - enum state_enum {
3.98 - IN_HEAP = 0,
3.99 - PRE_HEAP = -1,
3.100 - POST_HEAP = -2
3.101 - };
3.102 -
3.103 - private:
3.104 - std::vector<PairType> data;
3.105 - Compare comp;
3.106 - // FIXME: jo ez igy???
3.107 - KeyIntMap &kim;
3.108 -
3.109 - public:
3.110 - BinHeap(KeyIntMap &_kim) : kim(_kim) {}
3.111 - BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
3.112 -
3.113 -
3.114 - int size() const { return data.size(); }
3.115 - bool empty() const { return data.empty(); }
3.116 -
3.117 - private:
3.118 - static int parent(int i) { return (i-1)/2; }
3.119 - static int second_child(int i) { return 2*i+2; }
3.120 - bool less(const PairType &p1, const PairType &p2) {
3.121 - return comp(p1.second, p2.second);
3.122 - }
3.123 -
3.124 - int bubble_up(int hole, PairType p);
3.125 - int bubble_down(int hole, PairType p, int length);
3.126 -
3.127 - void move(const PairType &p, int i) {
3.128 - data[i] = p;
3.129 - kim.set(p.first, i);
3.130 - }
3.131 -
3.132 - void rmidx(int h) {
3.133 - int n = data.size()-1;
3.134 - if( h>=0 && h<=n ) {
3.135 - kim.set(data[h].first, POST_HEAP);
3.136 - if ( h<n ) {
3.137 - bubble_down(h, data[n], n);
3.138 - }
3.139 - data.pop_back();
3.140 - }
3.141 - }
3.142 -
3.143 - public:
3.144 - void push(const PairType &p) {
3.145 - int n = data.size();
3.146 - data.resize(n+1);
3.147 - bubble_up(n, p);
3.148 - }
3.149 - void push(const Key &k, const Val &v) { push(PairType(k,v)); }
3.150 -
3.151 - Key top() const {
3.152 - // FIXME: test size>0 ?
3.153 - return data[0].first;
3.154 - }
3.155 - Val topValue() const {
3.156 - // FIXME: test size>0 ?
3.157 - return data[0].second;
3.158 - }
3.159 -
3.160 - void pop() {
3.161 - rmidx(0);
3.162 - }
3.163 -
3.164 - void erase(const Key &k) {
3.165 - rmidx(kim[k]);
3.166 - }
3.167 -
3.168 - Val operator[](const Key &k) const {
3.169 - int idx = kim[k];
3.170 - return data[idx].second;
3.171 - }
3.172 -
3.173 - void put(const Key &k, const Val &v) {
3.174 - int idx = kim[k];
3.175 - if( idx < 0 ) {
3.176 - push(k,v);
3.177 - }
3.178 - else if( comp(v, data[idx].second) ) {
3.179 - bubble_up(idx, PairType(k,v));
3.180 - }
3.181 - else {
3.182 - bubble_down(idx, PairType(k,v), data.size());
3.183 - }
3.184 - }
3.185 -
3.186 - void decrease(const Key &k, const Val &v) {
3.187 - int idx = kim[k];
3.188 - bubble_up(idx, PairType(k,v));
3.189 - }
3.190 - void increase(const Key &k, const Val &v) {
3.191 - int idx = kim[k];
3.192 - bubble_down(idx, PairType(k,v), data.size());
3.193 - }
3.194 -
3.195 - state_enum state(const Key &k) const {
3.196 - int s = kim[k];
3.197 - if( s>=0 )
3.198 - s=0;
3.199 - return state_enum(s);
3.200 - }
3.201 -
3.202 - }; // class BinHeap
3.203 -
3.204 -
3.205 - template <typename K, typename V, typename M, typename C>
3.206 - int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
3.207 - int par = parent(hole);
3.208 - while( hole>0 && less(p,data[par]) ) {
3.209 - move(data[par],hole);
3.210 - hole = par;
3.211 - par = parent(hole);
3.212 - }
3.213 - move(p, hole);
3.214 - return hole;
3.215 - }
3.216 -
3.217 - template <typename K, typename V, typename M, typename C>
3.218 - int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
3.219 - int child = second_child(hole);
3.220 - while(child < length) {
3.221 - if( less(data[child-1], data[child]) ) {
3.222 - --child;
3.223 - }
3.224 - if( !less(data[child], p) )
3.225 - goto ok;
3.226 - move(data[child], hole);
3.227 - hole = child;
3.228 - child = second_child(hole);
3.229 - }
3.230 - child--;
3.231 - if( child<length && less(data[child], p) ) {
3.232 - move(data[child], hole);
3.233 - hole=child;
3.234 - }
3.235 - ok:
3.236 - move(p, hole);
3.237 - return hole;
3.238 - }
3.239 -
3.240 -} // namespace hugo
3.241 -
3.242 -#endif // BIN_HEAP_HH
4.1 --- a/src/work/bin_heap_demo.cc Thu Apr 01 15:32:31 2004 +0000
4.2 +++ b/src/work/bin_heap_demo.cc Thu Apr 01 21:06:53 2004 +0000
4.3 @@ -53,33 +53,30 @@
4.4 cout << "heap.set(\"korte\", 3.4);\n";
4.5 heap.set("korte", 3.4);
4.6
4.7 - cout << "heap.get(\"alma\") = "
4.8 - << heap.get("alma")
4.9 - << endl;
4.10 cout << "heap[\"alma\"] = "
4.11 << heap["alma"]
4.12 << endl;
4.13
4.14 cout << "heap.top() = "
4.15 << heap.top() << endl;
4.16 - cout << "heap.topPrio() = "
4.17 - << heap.topPrio() << endl;
4.18 + cout << "heap.prio() = "
4.19 + << heap.prio() << endl;
4.20
4.21 cout << "heap.decrease(\"alma\", 1.2);\n";
4.22 heap.set("alma", 1.2);
4.23
4.24 cout << "heap.top() = "
4.25 << heap.top() << endl;
4.26 - cout << "heap.topPrio() = "
4.27 - << heap.topPrio() << endl;
4.28 + cout << "heap.prio() = "
4.29 + << heap.prio() << endl;
4.30
4.31 cout << "heap.set(\"alma\", 22);\n";
4.32 heap.set("alma", 22);
4.33
4.34 cout << "heap.top() = "
4.35 << heap.top() << endl;
4.36 - cout << "heap.topPrio() = "
4.37 - << heap.topPrio() << endl;
4.38 + cout << "heap.prio() = "
4.39 + << heap.prio() << endl;
4.40
4.41 cout << "heap.size() = "
4.42 << heap.size() << endl;
4.43 @@ -88,8 +85,8 @@
4.44
4.45 cout << "heap.top() = "
4.46 << heap.top() << endl;
4.47 - cout << "heap.topPrio() = "
4.48 - << heap.topPrio() << endl;
4.49 + cout << "heap.prio() = "
4.50 + << heap.prio() << endl;
4.51
4.52 cout << "heap.state(\"szilva\") = "
4.53 << heap.state("szilva") << endl;