1.1 --- a/src/include/bin_heap.hh	Tue Jan 27 19:17:46 2004 +0000
     1.2 +++ b/src/include/bin_heap.hh	Tue Jan 27 21:23:33 2004 +0000
     1.3 @@ -1,3 +1,61 @@
     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 @@ -27,8 +85,7 @@
    1.66       * The KeyIntMap _should_ be initialized in such way, that it maps
    1.67       * PRE_HEAP (-1) to any element to be put in the heap...
    1.68       */
    1.69 -
    1.70 -    enum state {
    1.71 +    enum state_enum {
    1.72        IN_HEAP = 0,
    1.73        PRE_HEAP = -1,
    1.74        POST_HEAP = -2
    1.75 @@ -82,10 +139,11 @@
    1.76  
    1.77      void pop() {
    1.78        int n = data.size()-1;
    1.79 -      if ( n>0 ) {
    1.80 -	bubble_down(0, data[n], n);
    1.81 -      }
    1.82 -      if ( n>=0 ) {
    1.83 +      if( n>=0 ) {
    1.84 +	kim.put(data[0].first, POST_HEAP);
    1.85 +	if ( n>0 ) {
    1.86 +	  bubble_down(0, data[n], n);
    1.87 +	}
    1.88  	data.pop_back();
    1.89        }
    1.90      }
    1.91 @@ -116,6 +174,13 @@
    1.92        bubble_down(idx, PairType(k,v), data.size());
    1.93      }
    1.94  
    1.95 +    state_enum state(const Key &k) const {
    1.96 +      int s = kim.get(k);
    1.97 +      if( s>=0 )
    1.98 +	s=0;
    1.99 +      return state_enum(s);
   1.100 +    }
   1.101 +
   1.102    }; // class BinHeap
   1.103  
   1.104    

     2.1 --- a/src/work/bin_heap_demo.cc	Tue Jan 27 19:17:46 2004 +0000
     2.2 +++ b/src/work/bin_heap_demo.cc	Tue Jan 27 21:23:33 2004 +0000
     2.3 @@ -8,6 +8,11 @@
     2.4  
     2.5  class string_int_map;
     2.6  
     2.7 +// Egy binaris kupac, ami stringekhez rendelt double ertekeket tarol,
     2.8 +// azaz mindig az a string van a tetejen, amihez a legkisebb szam tartozik.
     2.9 +// A kupac egy string_int_map tipusu property_map segitsegevel tarolja
    2.10 +// a stringek aktualis helyet sajatmagan belul.
    2.11 +// Egy olyan stringhez, ami meg nincsen a kupac -1 -et kell rendelnunk.
    2.12  typedef BinHeap<string, double, string_int_map> StrDoubleHeap;
    2.13  
    2.14  class string_int_map : public map<string,int> {
    2.15 @@ -78,6 +83,19 @@
    2.16    cout << "heap.topValue() = "
    2.17         << heap.topValue() << endl;
    2.18  
    2.19 +  cout << "heap.state(\"szilva\") = "
    2.20 +       << heap.state("szilva") << endl;
    2.21 +  cout << "heap.put(\"szilva\", 0.5);\n";
    2.22 +  heap.put("szilva", 0.5);
    2.23 +  cout << "heap.state(\"szilva\") = "
    2.24 +       << heap.state("szilva") << endl;
    2.25 +  cout << "heap.top() = "
    2.26 +       << heap.top() << endl;
    2.27 +  cout << "heap.pop();\n";
    2.28 +  heap.pop();
    2.29 +  cout << "heap.state(\"szilva\") = "
    2.30 +       << heap.state("szilva") << endl;
    2.31 +
    2.32    cout << "heap.size() = "
    2.33         << heap.size() << endl;
    2.34    cout << "heap.pop();\n";
    2.35 @@ -88,4 +106,3 @@
    2.36    cout << "heap.empty() = "
    2.37         << (heap.empty()?"true":"false") << endl;  
    2.38  }
    2.39 -