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 } |
|