# HG changeset patch
# User klao
# Date 1079033068 0
# Node ID c645f4a2a6aeff1ebf282f7cf525cd865157674e
# Parent  ec3d3596e3c94d7bc1c3cb67427ec515e8f1a7d4
Uj kupac nevezektan

diff -r ec3d3596e3c9 -r c645f4a2a6ae src/include/bin_heap.hh
--- a/src/include/bin_heap.hh	Thu Mar 11 19:19:52 2004 +0000
+++ b/src/include/bin_heap.hh	Thu Mar 11 19:24:28 2004 +0000
@@ -6,27 +6,27 @@
 
 /******
  *
- * BinHeap<KeyType, ValueType, KeyIntMap, [ValueCompare]>
+ * BinHeap<ItemType, PrioType, ItemIntMap, [PrioCompare]>
  *
- * Ez az osztaly kulcs-ertek parok tarolasara alkalmas binaris kupacot
+ * 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
  * is elnie kell. (???)
  *
  * 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.
  * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
@@ -35,15 +35,15 @@
  * (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,
+ * 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).
  *
  * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
@@ -65,24 +65,24 @@
 
 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...
      */
     enum state_enum {
@@ -95,11 +95,11 @@
     std::vector<PairType> data;
     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) {}
 
 
     int size() const { return data.size(); }
@@ -117,13 +117,13 @@
 
     void move(const PairType &p, int i) {
       data[i] = p;
-      kim.put(p.first, i);
+      iim.set(p.first, i);
     }
 
     void rmidx(int h) {
       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);
 	}
@@ -137,13 +137,13 @@
       data.resize(n+1);
       bubble_up(n, p);
     }
-    void push(const Key &k, const Val &v) { push(PairType(k,v)); }
+    void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
 
-    Key top() const {
+    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;
     }
@@ -152,38 +152,38 @@
       rmidx(0);
     }
 
-    void erase(const Key &k) {
-      rmidx(kim.get(k));
+    void erase(const Item &i) {
+      rmidx(iim.get(i));
     }
 
-    const Val get(const Key &k) const {
-      int idx = kim.get(k);
+    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);
+	push(i,p);
       }
-      else if( comp(v, data[idx].second) ) {
-	bubble_up(idx, PairType(k,v));
+      else if( comp(p, data[idx].second) ) {
+	bubble_up(idx, PairType(i,p));
       }
       else {
-	bubble_down(idx, PairType(k,v), data.size());
+	bubble_down(idx, PairType(i,p), data.size());
       }
     }
 
-    void decrease(const Key &k, const Val &v) {
-      int idx = kim.get(k);
-      bubble_up(idx, PairType(k,v));
+    void decrease(const Item &i, const Prio &p) {
+      int idx = iim.get(i);
+      bubble_up(idx, PairType(i,p));
     }
-    void increase(const Key &k, const Val &v) {
-      int idx = kim.get(k);
-      bubble_down(idx, PairType(k,v), data.size());
+    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 Key &k) const {
-      int s = kim.get(k);
+    state_enum state(const Item &i) const {
+      int s = iim.get(i);
       if( s>=0 )
 	s=0;
       return state_enum(s);
diff -r ec3d3596e3c9 -r c645f4a2a6ae src/work/bin_heap_demo.cc
--- a/src/work/bin_heap_demo.cc	Thu Mar 11 19:19:52 2004 +0000
+++ b/src/work/bin_heap_demo.cc	Thu Mar 11 19:24:28 2004 +0000
@@ -25,7 +25,7 @@
     }
     return operator[](s);
   }
-  void put(const string &s, int i) {
+  void set(const string &s, int i) {
       operator[](s) = i;
   }
 };
@@ -45,8 +45,8 @@
   cout << "heap.push(\"alma\", 15);\n";
   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\") = " 
        << heap.get("alma")
@@ -54,24 +54,24 @@
 
   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() = "
        << heap.size() << endl;
@@ -80,13 +80,13 @@
 
   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;
   cout << "heap.top() = "