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