1 /*++
2 Copyright (c) 2006 Microsoft Corporation
3
4 Module Name:
5
6 tst_heap.cpp
7
8 Abstract:
9
10 Test heap template.
11
12 Author:
13
14 Leonardo de Moura (leonardo) 2006-09-18.
15
16 Revision History:
17
18 --*/
19 #include<iostream>
20 #include "util/util.h"
21 #include "util/heap.h"
22 #include "util/trace.h"
23 #include "util/uint_set.h"
24 // include "util/hashtable.h"
25
operator ()lt_proc26 struct lt_proc { bool operator()(int v1, int v2) const { return v1 < v2; } };
27 //struct int_hash_proc { unsigned operator()(int v) const { std::cout << "hash " << v << "\n"; VERIFY(v >= 0); return v; }};
28 //typedef int_hashtable<int_hash_proc, default_eq<int> > int_set;
29 typedef heap<lt_proc> int_heap;
30 #define N 10000
31
32 static random_gen heap_rand(1);
33
tst1()34 static void tst1() {
35 int_heap h(N);
36 // int_set t;
37 uint_set t;
38 for (int i = 0; i < N * 3; i++) {
39 int val = heap_rand() % N;
40 if (!h.contains(val)) {
41 ENSURE(!t.contains(val));
42 h.insert(val);
43 t.insert(val);
44 }
45 else {
46 if (!t.contains(val)) {
47 for (int v : t) std::cout << v << "\n";
48 }
49 ENSURE(t.contains(val));
50 }
51 }
52 ENSURE(h.check_invariant());
53 for (int v : t) {
54 ENSURE(h.contains(v));
55 }
56 while (!h.empty()) {
57 int m1 = h.min_value();
58 int m2 = h.erase_min();
59 (void)m1;
60 (void)m2;
61 ENSURE(m1 == m2);
62 ENSURE(-1 < m2);
63 }
64 }
65
66 int g_value[N];
67
operator ()lt_proc268 struct lt_proc2 { bool operator()(int v1, int v2) const { ENSURE(v1 < N && v2 < N); return g_value[v1] < g_value[v2]; } };
69 typedef heap<lt_proc2> int_heap2;
70
init_values()71 static void init_values() {
72 for (unsigned i = 0; i < N; i++)
73 g_value[i] = heap_rand();
74 }
75
76 #ifdef _TRACE
dump_heap(const int_heap2 & h,std::ostream & out)77 static void dump_heap(const int_heap2 & h, std::ostream & out) {
78 // int_heap2::const_iterator it = h.begin();
79 // int_heap2::const_iterator end = h.end();
80 // for (; it != end; ++it) {
81 // out << *it << ":" << g_value[*it] << " ";
82 // }
83 // out << "\n";
84 }
85 #endif
86
tst2()87 static void tst2() {
88 int_heap2 h(N);
89 for (int i = 0; i < N * 10; i++) {
90
91 // if (i % 1 == 0) std::cout << "i: " << i << std::endl;
92 if (i % 1000 == 0) std::cout << "i: " << i << std::endl;
93 int cmd = heap_rand() % 10;
94 if (cmd <= 3) {
95 // insert
96 int val = heap_rand() % N;
97 if (!h.contains(val)) {
98 TRACE("heap", tout << "inserting: " << val << "\n";);
99 h.insert(val);
100 TRACE("heap", dump_heap(h, tout););
101 ENSURE(h.contains(val));
102 }
103 }
104 else if (cmd <= 6) {
105 int val = heap_rand() % N;
106 if (h.contains(val)) {
107 TRACE("heap", tout << "removing: " << val << "\n";);
108 h.erase(val);
109 TRACE("heap", dump_heap(h, tout););
110 ENSURE(!h.contains(val));
111 }
112 }
113 else if (cmd <= 8) {
114 // increased & decreased
115 int val = heap_rand() % N;
116 int old_v = g_value[val];
117 int new_v = heap_rand();
118 if (h.contains(val)) {
119 g_value[val] = new_v;
120 if (old_v < new_v) {
121 TRACE("heap", tout << "value of: " << val << " increased old: " << old_v << " new: " << new_v << "\n";);
122 h.increased(val);
123 }
124 else {
125 TRACE("heap", tout << "value of: " << val << " decreased old: " << old_v << " new: " << new_v << "\n";);
126 h.decreased(val);
127 }
128 }
129 }
130 else {
131 ENSURE(h.check_invariant());
132 }
133 }
134 ENSURE(h.check_invariant());
135 }
136
tst_heap()137 void tst_heap() {
138 // enable_debug("heap");
139 enable_trace("heap");
140 unsigned i = 0;
141 while (i < 3) {
142 IF_VERBOSE(1, verbose_stream() << "test\n";);
143 heap_rand.set_seed(i++);
144 tst1();
145 init_values();
146 tst2();
147 }
148 }
149
150