src/work/bin_heap_demo.cc
author athos
Mon, 11 Apr 2005 14:26:35 +0000
changeset 1338 b261caf79ce7
parent 618 e944d741f472
permissions -rw-r--r--
A little modification: a call for primalStatus().
     1 #include <iostream>
     2 #include <string>
     3 #include <map>
     4 
     5 #include <lemon/bin_heap.h>
     6 
     7 using namespace lemon;
     8 using namespace std;
     9 
    10 class string_int_map;
    11 
    12 // Egy binaris kupac, ami stringekhez rendelt double ertekeket tarol,
    13 // azaz mindig az a string van a tetejen, amihez a legkisebb szam tartozik.
    14 // A kupac egy string_int_map tipusu property_map segitsegevel tarolja
    15 // a stringek aktualis helyet sajatmagan belul.
    16 // Egy olyan stringhez, ami meg nincsen a kupac -1 -et kell rendelnunk.
    17 typedef BinHeap<string, double, string_int_map> StrDoubleHeap;
    18 
    19 class string_int_map : public map<string,int> {
    20   typedef map<string,int> parent;
    21 public:
    22   int get(const string &s) {
    23     // Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy
    24     // hogy is mukodik ez a map :)
    25     if( count(s) == 0 ) {
    26       parent::operator[](s) = StrDoubleHeap::PRE_HEAP;
    27     }
    28     return parent::operator[](s);
    29   }
    30   int operator[](const string &s) {
    31     return get(s);
    32   }
    33   void set(const string &s, int i) {
    34       parent::operator[](s) = i;
    35   }
    36 };
    37 
    38 
    39 int main()
    40 {
    41   string_int_map sim;
    42   
    43   
    44   cout << "testing string_int_map default value:\n";
    45   cout << "  sim.get(\"alma\"): " << sim.get("alma") << endl;
    46   cout << "  sim[\"alma\"]: " << sim["alma"] << endl;
    47 
    48   cout << "creating the heap\n";
    49   StrDoubleHeap heap(sim);
    50 
    51   cout << "heap.push(\"alma\", 15);\n";
    52   heap.push("alma", 15);
    53 
    54   cout << "heap.set(\"korte\", 3.4);\n";
    55   heap.set("korte", 3.4);
    56 
    57   cout << "heap[\"alma\"] = " 
    58        << heap["alma"]
    59        << endl;
    60 
    61   cout << "heap.top() = "
    62        << heap.top() << endl;
    63   cout << "heap.prio() = "
    64        << heap.prio() << endl;
    65 
    66   cout << "heap.decrease(\"alma\", 1.2);\n";
    67   heap.set("alma", 1.2);
    68 
    69   cout << "heap.top() = "
    70        << heap.top() << endl;
    71   cout << "heap.prio() = "
    72        << heap.prio() << endl;
    73 
    74   cout << "heap.set(\"alma\", 22);\n";
    75   heap.set("alma", 22);
    76 
    77   cout << "heap.top() = "
    78        << heap.top() << endl;
    79   cout << "heap.prio() = "
    80        << heap.prio() << endl;
    81 
    82   cout << "heap.size() = "
    83        << heap.size() << endl;
    84   cout << "heap.pop();\n";
    85   heap.pop();
    86 
    87   cout << "heap.top() = "
    88        << heap.top() << endl;
    89   cout << "heap.prio() = "
    90        << heap.prio() << endl;
    91 
    92   cout << "heap.state(\"szilva\") = "
    93        << heap.state("szilva") << endl;
    94   cout << "heap.set(\"szilva\", 0.5);\n";
    95   heap.set("szilva", 0.5);
    96   cout << "heap.state(\"szilva\") = "
    97        << heap.state("szilva") << endl;
    98   cout << "heap.top() = "
    99        << heap.top() << endl;
   100   cout << "heap.pop();\n";
   101   heap.pop();
   102   cout << "heap.state(\"szilva\") = "
   103        << heap.state("szilva") << endl;
   104 
   105   cout << "heap.size() = "
   106        << heap.size() << endl;
   107   cout << "heap.pop();\n";
   108   heap.pop();
   109 
   110   cout << "heap.size() = "
   111        << heap.size() << endl;  
   112   cout << "heap.empty() = "
   113        << (heap.empty()?"true":"false") << endl;  
   114 }