Changeset 39:28b0d751d29f in lemon-0.x for src

Timestamp:

01/27/04 22:23:33 (21 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@53

Message:

Alap leiras a BinHeap? -rol

BinHeap::state() befejezese

Location:

src

Files:

• include/bin_heap.hh (modified) (4 diffs)
• work/bin_heap_demo.cc (modified) (3 diffs)

src/include/bin_heap.hh

@@ +1 @@
+/* FIXME: Copyright ... 
+ *
+ * This implementation is heavily based on STL's heap functions and
+ * the similar class by Alpar Juttner in IKTA...
+ */
+
+/******
+ *
+ * BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]>
+ *
+ * Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot
+ * valosit meg.
+ * A kupacban legfolul mindig az a par talalhato, amiben az _ertek_ a
+ * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
+ * lett keszitve...)
+ *
+ * Megjegyzes: egy kicsit gyanus nekem, hogy a kupacos temakorben nem
+ * azt hivjak kulcsnak, amit most en annak nevezek. :) En olyan 
+ * property_map -os ertelemben hasznalom.
+ *
+ * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
+ * a kulcsokhoz egy int-et tud tarolni (ezzel tudom megkeresni az illeto
+ * elemet a kupacban a csokkentes es hasonlo muveletekhez).
+ * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
+ * is elnie kell. (???)
+ *
+ * Ketfele modon hasznalhato:
+ * Lusta mod:
+ * put(Key, Value) metodussal pakolunk a kupacba,
+ * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
+ * csokkentettunk-e rajta, vagy noveltunk.
+ * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
+ * minden szobajovo kulcs ertekre, -1 -es ertekkel!
+ * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
+ * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
+ *  mar kikerult a kupacbol POST_HEAP=-2).
+ * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
+ * meg meg tudja mondani a "legkisebb" erteku elemet. De csak nagyjabol,
+ * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
+ *
+ * Kozvetlen mod:
+ * push(Key, Value) metodussal belerakunk a kupacba (ha az illeto kulcs mar
+ * benn volt, akkor gaz).
+ * increase/decrease(Key k, Value new_value) metodusokkal lehet
+ * novelni/csokkenteni az illeto kulcshoz tartozo erteket. (Ha nem volt meg
+ * benne a kupacban az illeto kulcs, vagy nem abba az iranyba valtoztattad
+ * az erteket, amerre mondtad -- gaz).
+ *
+ * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
+ * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
+ * hasznal. :-))
+ *
+ *
+ * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
+ *
+ */
+
+
 #ifndef BIN_HEAP_HH
 #define BIN_HEAP_HH
@@ -28 +86 @@
      * PRE_HEAP (-1) to any element to be put in the heap...
      */
-
-    enum state {
+    enum state_enum {
       IN_HEAP = 0,
       PRE_HEAP = -1,
@@ -83 +140 @@
     void pop() {
       int n = data.size()-1;
-      if ( n>0 ) {
-        bubble_down(0, data[n], n);
-      }
-      if ( n>=0 ) {
+      if( n>=0 ) {
+        kim.put(data[0].first, POST_HEAP);
+        if ( n>0 ) {
+          bubble_down(0, data[n], n);
+        }
         data.pop_back();
       }
@@ -115 +173 @@
       int idx = kim.get(k);
       bubble_down(idx, PairType(k,v), data.size());
+    }
+
+    state_enum state(const Key &k) const {
+      int s = kim.get(k);
+      if( s>=0 )
+        s=0;
+      return state_enum(s);
     }
 

src/work/bin_heap_demo.cc

@@ -9 +9 @@
 class string_int_map;
 
+// Egy binaris kupac, ami stringekhez rendelt double ertekeket tarol,
+// azaz mindig az a string van a tetejen, amihez a legkisebb szam tartozik.
+// A kupac egy string_int_map tipusu property_map segitsegevel tarolja
+// a stringek aktualis helyet sajatmagan belul.
+// Egy olyan stringhez, ami meg nincsen a kupac -1 -et kell rendelnunk.
 typedef BinHeap<string, double, string_int_map> StrDoubleHeap;
 
@@ -79 +84 @@
        << heap.topValue() << endl;
 
+  cout << "heap.state(\"szilva\") = "
+       << heap.state("szilva") << endl;
+  cout << "heap.put(\"szilva\", 0.5);\n";
+  heap.put("szilva", 0.5);
+  cout << "heap.state(\"szilva\") = "
+       << heap.state("szilva") << endl;
+  cout << "heap.top() = "
+       << heap.top() << endl;
+  cout << "heap.pop();\n";
+  heap.pop();
+  cout << "heap.state(\"szilva\") = "
+       << heap.state("szilva") << endl;
+
   cout << "heap.size() = "
        << heap.size() << endl;
@@ -89 +107 @@
        << (heap.empty()?"true":"false") << endl;  
 }
-