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