Changeset 172:c645f4a2a6ae in lemon-0.x for src

Timestamp:

03/11/04 20:24:28 (21 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

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

Message:

Uj kupac nevezektan

Location:

src

Files:

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

src/include/bin_heap.hh

@@ -7 +7 @@
 /******
  *
- * BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]>
- *
- * Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot
+ * BinHeap<ItemType, PrioType, ItemIntMap, [PrioCompare]>
+ *
+ * Ez az osztaly item-prioritas parok tarolasara alkalmas binaris kupacot
  * valosit meg.
- * A kupacban legfolul mindig az a par talalhato, amiben az _ertek_ a
+ * A kupacban legfolul mindig az a par talalhato, amiben a prioritas 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.
+ * Megjegyzes: a kupacos temakorokben a prioritast kulcsnak szoktak nevezni,
+ * de mivel ez zavaro tud lenni a property-map-es kulcs-ertek szohasznalata
+ * miatt, megprobaltunk valami semleges elnevezeseket kitalalni.
  *
  * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
- * a kulcsokhoz egy int-et tud tarolni (ezzel tudom megkeresni az illeto
+ * az itemekhez 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
@@ -27 +27 @@
  * Ketfele modon hasznalhato:
  * Lusta mod:
- * put(Key, Value) metodussal pakolunk a kupacba,
+ * set(Item, Prio) 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.
@@ -36 +36 @@
  *  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,
+ * meg meg tudja mondani a "legkisebb" prioritasu 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
+ * push(Item, Prio) 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
+ * increase/decrease(Item i, Prio new_prio) metodusokkal lehet
+ * novelni/csokkenteni az illeto elemhez tartozo prioritast. (Ha nem volt
+ * megbenne a kupacban az illeto elem, vagy nem abba az iranyba valtoztattad
  * az erteket, amerre mondtad -- gaz).
  *
@@ -66 +66 @@
 namespace hugo {
 
-  template <typename Key, typename Val, typename KeyIntMap,
-            typename Compare = std::less<Val> >
+  template <typename Item, typename Prio, typename ItemIntMap,
+            typename Compare = std::less<Prio> >
   class BinHeap {
 
   public:
-    typedef Key              KeyType;
+    typedef Item                             ItemType;
     // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
-    typedef Val              ValueType;
-    typedef std::pair<KeyType,ValueType>     PairType;
-    typedef KeyIntMap        KeyIntMapType;
-    typedef Compare          ValueCompare;
+    typedef Prio                             PrioType;
+    typedef std::pair<ItemType,PrioType>     PairType;
+    typedef ItemIntMap                       ItemIntMapType;
+    typedef Compare                          PrioCompare;
 
     /**
-     * Each Key element have a state associated to it. It may be "in heap",
+     * Each Item element have a state associated to it. It may be "in heap",
      * "pre heap" or "post heap". The later two are indifferent from the
      * heap's point of view, but may be useful to the user.
      *
-     * The KeyIntMap _should_ be initialized in such way, that it maps
+     * The ItemIntMap _should_ be initialized in such way, that it maps
      * PRE_HEAP (-1) to any element to be put in the heap...
      */
@@ -96 +96 @@
     Compare comp;
     // FIXME: jo ez igy???
-    KeyIntMap &kim;
+    ItemIntMap &iim;
 
   public:
-    BinHeap(KeyIntMap &_kim) : kim(_kim) {}
-    BinHeap(KeyIntMap &_kim, const Compare &_comp) : comp(_comp), kim(_kim) {}
+    BinHeap(ItemIntMap &_iim) : iim(_iim) {}
+    BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
 
 
@@ -118 +118 @@
     void move(const PairType &p, int i) {
       data[i] = p;
-      kim.put(p.first, i);
+      iim.set(p.first, i);
     }
 
@@ -124 +124 @@
       int n = data.size()-1;
       if( h>=0 && h<=n ) {
-        kim.put(data[h].first, POST_HEAP);
+        iim.set(data[h].first, POST_HEAP);
         if ( h<n ) {
           bubble_down(h, data[n], n);
@@ -138 +138 @@
       bubble_up(n, p);
     }
-    void push(const Key &k, const Val &v) { push(PairType(k,v)); }
-
-    Key top() const {
+    void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
+
+    Item top() const {
       // FIXME: test size>0 ?
       return data[0].first;
     }
-    Val topValue() const {
+    Prio topPrio() const {
       // FIXME: test size>0 ?
       return data[0].second;
@@ -153 +153 @@
     }
 
-    void erase(const Key &k) {
-      rmidx(kim.get(k));
-    }
-
-    const Val get(const Key &k) const {
-      int idx = kim.get(k);
+    void erase(const Item &i) {
+      rmidx(iim.get(i));
+    }
+
+    const Prio get(const Item &i) const {
+      int idx = iim.get(i);
       return data[idx].second;
     }
-    void put(const Key &k, const Val &v) {
-      int idx = kim.get(k);
+    void set(const Item &i, const Prio &p) {
+      int idx = iim.get(i);
       if( idx < 0 ) {
-        push(k,v);
-      }
-      else if( comp(v, data[idx].second) ) {
-        bubble_up(idx, PairType(k,v));
+        push(i,p);
+      }
+      else if( comp(p, data[idx].second) ) {
+        bubble_up(idx, PairType(i,p));
       }
       else {
-        bubble_down(idx, PairType(k,v), data.size());
-      }
-    }
-
-    void decrease(const Key &k, const Val &v) {
-      int idx = kim.get(k);
-      bubble_up(idx, PairType(k,v));
-    }
-    void increase(const Key &k, const Val &v) {
-      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);
+        bubble_down(idx, PairType(i,p), data.size());
+      }
+    }
+
+    void decrease(const Item &i, const Prio &p) {
+      int idx = iim.get(i);
+      bubble_up(idx, PairType(i,p));
+    }
+    void increase(const Item &i, const Prio &p) {
+      int idx = iim.get(i);
+      bubble_down(idx, PairType(i,p), data.size());
+    }
+
+    state_enum state(const Item &i) const {
+      int s = iim.get(i);
       if( s>=0 )
         s=0;

src/work/bin_heap_demo.cc

@@ -26 +26 @@
     return operator[](s);
   }
-  void put(const string &s, int i) {
+  void set(const string &s, int i) {
       operator[](s) = i;
   }
@@ -46 +46 @@
   heap.push("alma", 15);
 
-  cout << "heap.put(\"korte\", 3.4);\n";
-  heap.put("korte", 3.4);
+  cout << "heap.set(\"korte\", 3.4);\n";
+  heap.set("korte", 3.4);
 
   cout << "heap.get(\"alma\") = " 
@@ -55 +55 @@
   cout << "heap.top() = "
        << heap.top() << endl;
-  cout << "heap.topValue() = "
-       << heap.topValue() << endl;
+  cout << "heap.topPrio() = "
+       << heap.topPrio() << endl;
 
   cout << "heap.decrease(\"alma\", 1.2);\n";
-  heap.put("alma", 1.2);
+  heap.set("alma", 1.2);
 
   cout << "heap.top() = "
        << heap.top() << endl;
-  cout << "heap.topValue() = "
-       << heap.topValue() << endl;
+  cout << "heap.topPrio() = "
+       << heap.topPrio() << endl;
 
-  cout << "heap.put(\"alma\", 22);\n";
-  heap.put("alma", 22);
+  cout << "heap.set(\"alma\", 22);\n";
+  heap.set("alma", 22);
 
   cout << "heap.top() = "
        << heap.top() << endl;
-  cout << "heap.topValue() = "
-       << heap.topValue() << endl;
+  cout << "heap.topPrio() = "
+       << heap.topPrio() << endl;
 
   cout << "heap.size() = "
@@ -81 +81 @@
   cout << "heap.top() = "
        << heap.top() << endl;
-  cout << "heap.topValue() = "
-       << heap.topValue() << endl;
+  cout << "heap.topPrio() = "
+       << heap.topPrio() << endl;
 
   cout << "heap.state(\"szilva\") = "
        << heap.state("szilva") << endl;
-  cout << "heap.put(\"szilva\", 0.5);\n";
-  heap.put("szilva", 0.5);
+  cout << "heap.set(\"szilva\", 0.5);\n";
+  heap.set("szilva", 0.5);
   cout << "heap.state(\"szilva\") = "
        << heap.state("szilva") << endl;