source: lemon-0.x/src/work/bin_heap_demo.cc @ 1087:d496d1d5a5e7

#include <iostream>
#include <string>
#include <map>

#include <lemon/bin_heap.h>

using namespace lemon;
using namespace std;

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;

class string_int_map : public map<string,int> {
  typedef map<string,int> parent;
public:
  int get(const string &s) {
    // Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy
    // hogy is mukodik ez a map :)
    if( count(s) == 0 ) {
      parent::operator[](s) = StrDoubleHeap::PRE_HEAP;
    }
    return parent::operator[](s);
  }
  int operator[](const string &s) {
    return get(s);
  }
  void set(const string &s, int i) {
      parent::operator[](s) = i;
  }
};


int main()
{
  string_int_map sim;
  
  
  cout << "testing string_int_map default value:\n";
  cout << "  sim.get(\"alma\"): " << sim.get("alma") << endl;
  cout << "  sim[\"alma\"]: " << sim["alma"] << endl;

  cout << "creating the heap\n";
  StrDoubleHeap heap(sim);

  cout << "heap.push(\"alma\", 15);\n";
  heap.push("alma", 15);

  cout << "heap.set(\"korte\", 3.4);\n";
  heap.set("korte", 3.4);

  cout << "heap[\"alma\"] = " 
       << heap["alma"]
       << endl;

  cout << "heap.top() = "
       << heap.top() << endl;
  cout << "heap.prio() = "
       << heap.prio() << endl;

  cout << "heap.decrease(\"alma\", 1.2);\n";
  heap.set("alma", 1.2);

  cout << "heap.top() = "
       << heap.top() << endl;
  cout << "heap.prio() = "
       << heap.prio() << endl;

  cout << "heap.set(\"alma\", 22);\n";
  heap.set("alma", 22);

  cout << "heap.top() = "
       << heap.top() << endl;
  cout << "heap.prio() = "
       << heap.prio() << endl;

  cout << "heap.size() = "
       << heap.size() << endl;
  cout << "heap.pop();\n";
  heap.pop();

  cout << "heap.top() = "
       << heap.top() << endl;
  cout << "heap.prio() = "
       << heap.prio() << endl;

  cout << "heap.state(\"szilva\") = "
       << heap.state("szilva") << endl;
  cout << "heap.set(\"szilva\", 0.5);\n";
  heap.set("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;
  cout << "heap.pop();\n";
  heap.pop();

  cout << "heap.size() = "
       << heap.size() << endl;  
  cout << "heap.empty() = "
       << (heap.empty()?"true":"false") << endl;  
}