1 : /* _________________________________________________________________________
2 : *
3 : * UTILIB: A utility library for developing portable C++ codes.
4 : * Copyright (c) 2008 Sandia Corporation.
5 : * This software is distributed under the BSD License.
6 : * Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
7 : * the U.S. Government retains certain rights in this software.
8 : * For more information, see the README file in the top UTILIB directory.
9 : * _________________________________________________________________________
10 : */
11 :
12 : //
13 : // heap.cpp
14 : //
15 : #include <utilib/std_headers.h>
16 : #include <utilib/_math.h>
17 : #include <utilib/CharString.h>
18 : #include <utilib/SimpleHeap.h>
19 : #include <utilib/GenericHeap.h>
20 : #include <utilib/OptionParser.h>
21 :
22 : #ifdef UTILIB_HAVE_NAMESPACES
23 : using namespace std;
24 : #endif
25 :
26 : using namespace utilib;
27 : #define LIMIT 9
28 :
29 : namespace {
30 :
31 : bool debug=false;
32 :
33 : template <class T>
34 2 : class A {
35 :
36 : public:
37 :
38 46 : A() {}
39 :
40 : int compare(const A<T>& tmp) const;
41 :
42 : T val;
43 :
44 : int write(ostream& os) const
45 : {os << val; return OK;}
46 :
47 : int read(istream& is)
48 : {is >> val; return OK;}
49 :
50 40 : A<T>& operator=(A<T>& tmp)
51 40 : {val = tmp.val; return *this;}
52 : };
53 :
54 :
55 : template <class T>
56 238 : int A<T>::compare(const A<T>& tmp) const
57 : {
58 238 : int foo = utilib::compare(val,tmp.val);
59 238 : return foo;
60 : }
61 :
62 :
63 : template <class T>
64 144 : double test_fn(BasicArray<T>& x)
65 : {
66 144 : double ans=0.0;
67 864 : for (size_type i=0; i<x.size(); i++)
68 720 : ans += x[i]*x[i];
69 144 : return ans;
70 : }
71 :
72 :
73 : template <class T, class Compare>
74 8 : void fill_table(SimpleHeap<BasicArray<T>,Compare>& table)
75 : {
76 8 : BasicArray<T> tmp(5);
77 8 : tmp << (T) (sqrt(2.0)*100);
78 8 : T delta= (T) 1.0;
79 8 : table.add(tmp);
80 :
81 8 : int j=0;
82 88 : while (j < LIMIT) {
83 72 : if (debug) {
84 0 : cerr << j << "\t" << tmp << "\t" << delta << endl;
85 0 : cerr << table << endl;
86 : }
87 72 : bool flag=false;
88 72 : int i=0;
89 72 : double curr = test_fn(tmp);
90 144 : while ((i<5) && !flag) {
91 72 : T foo=tmp[i];
92 72 : tmp[i] = foo-delta;
93 72 : if (test_fn(tmp) < curr) {
94 72 : table.add(tmp);
95 72 : flag=true;
96 72 : j++;
97 72 : break;
98 : }
99 0 : tmp[i] = foo+delta;
100 0 : if (test_fn(tmp) < curr) {
101 0 : table.add(tmp);
102 0 : flag=true;
103 0 : j++;
104 0 : break;
105 : }
106 0 : tmp[i] = foo;
107 0 : i++;
108 : }
109 72 : if (!flag)
110 0 : delta = (T) (delta*0.9);
111 72 : if (delta < 1e-16)
112 8 : break;
113 : }
114 : }
115 :
116 :
117 :
118 : #define FN(x) (fabs(x)*fabs(x))
119 :
120 : template <class Compare>
121 4 : void fill_table(SimpleHeap<double,Compare>& table)
122 : {
123 4 : double tmp = sqrt(2.0);
124 4 : double delta=1.0;
125 4 : table.add(tmp);
126 :
127 4 : int j=0;
128 88 : while (j < LIMIT) {
129 80 : double curr = FN(tmp);
130 80 : if (FN(tmp-delta) < curr) {
131 20 : tmp = tmp-delta;
132 20 : table.add(tmp);
133 20 : j++;
134 : }
135 60 : else if (FN(tmp+delta) < curr) {
136 16 : tmp = tmp+delta;
137 16 : table.add(tmp);
138 16 : j++;
139 : }
140 : else {
141 48 : delta *= 0.9;
142 : }
143 : }
144 : }
145 :
146 :
147 : template <class Compare>
148 4 : void fill_table(SimpleHeap<int,Compare>& table)
149 : {
150 : int tmp;
151 40 : for (int i=0; i<LIMIT; i++) {
152 36 : tmp = i*i*i;
153 40 : table.add(tmp);
154 : }
155 : }
156 :
157 : template <class T, class Compare>
158 8 : void do_stest(const CharString& msg, SimpleHeap<T,Compare>& tree, ostream& os)
159 : {
160 8 : os << "\\" << endl;
161 8 : os << "\\" << endl;
162 8 : os << "\\" << endl;
163 8 : os << msg << endl;
164 8 : os << "\\" << endl;
165 8 : os << "\\" << endl;
166 8 : os << "\\" << endl;
167 8 : fill_table(tree);
168 8 : fill_table(tree);
169 :
170 8 : os << "Extracting items from heap" << endl;
171 4 : T tmp;
172 172 : while (tree) {
173 : bool status;
174 156 : typename SimpleHeap<T,Compare>::item_t* top = tree.top();
175 156 : tree.remove(top,tmp,status);
176 164 : os << tmp << "\t" << tree.size() << "\t" << status << endl;
177 : }
178 : }
179 :
180 :
181 :
182 : template <class Compare>
183 : void fill_table(GenericHeap<A<int>,Compare>& table)
184 : {
185 : A<int>* tmp;
186 : for (int i=0; i<LIMIT; i++) {
187 : tmp = new A<int>;
188 : tmp->val = i*i*i;
189 : table.add(*tmp);
190 :
191 : tmp = new A<int>;
192 : tmp->val = i*i*i;
193 : table.add(*tmp);
194 : }
195 : }
196 :
197 :
198 : template <class Compare>
199 4 : void fill_table(GenericHeap<A<CharString>,Compare>& table)
200 : {
201 4 : ifstream hash_data("hash.data");
202 : A<CharString>* tmp;
203 4 : tmp = new A<CharString>;
204 4 : hash_data >> tmp->val;
205 4 : int j=0;
206 44 : while (hash_data) {
207 40 : table.add(*tmp);
208 40 : tmp = new A<CharString>;
209 40 : hash_data >> tmp->val;
210 44 : if (++j > LIMIT) break;
211 : }
212 : }
213 :
214 :
215 : template <class T, class Compare>
216 2 : void do_test(const CharString& msg, GenericHeap<A<T>,Compare>& tree, ostream& os)
217 : {
218 2 : os << "\\" << endl;
219 2 : os << "\\" << endl;
220 2 : os << "\\" << endl;
221 2 : os << msg << endl;
222 2 : os << "\\" << endl;
223 2 : os << "\\" << endl;
224 2 : os << "\\" << endl;
225 2 : fill_table(tree);
226 2 : fill_table(tree);
227 :
228 2 : os << "Extracting items from heap" << endl;
229 2 : A<T> tmp;
230 44 : while (tree) {
231 : bool status;
232 40 : typename GenericHeap<A<T>,Compare>::item_t* top = tree.top();
233 40 : tree.remove(top,tmp,status);
234 42 : os << tmp.val << "\t" << tree.size() << "\t" << status << endl;
235 : }
236 : }
237 :
238 :
239 1 : void exec_test()
240 : {
241 : ////
242 : //// SimpleCompare
243 : ////
244 :
245 : //
246 : // HEAP BasicArray<double>
247 : //
248 : {
249 : //ofstream ofstr("heap-array-double");
250 1 : SimpleHeap<BasicArray<double> > test_double;
251 1 : do_stest("Testing BasicArray<double> simpleST",test_double,cout);
252 : }
253 :
254 :
255 : //
256 : // HEAP BasicArray<int>
257 : //
258 : {
259 : //ofstream ofstr("heap-array-int");
260 1 : SimpleHeap<BasicArray<int> > test_int;
261 2 : do_stest("Testing BasicArray<int> simpleST",test_int,cout);
262 : }
263 :
264 :
265 : //
266 : // HEAP double
267 : //
268 : {
269 : //ofstream ofstr("heap-double");
270 1 : SimpleHeap<double> test_double;
271 2 : do_stest("Testing double simpleST",test_double,cout);
272 : }
273 :
274 :
275 : //
276 : // HEAP int
277 : //
278 : {
279 : //ofstream ofstr("heap-int");
280 1 : SimpleHeap<int> test_int;
281 2 : do_stest("Testing int simpleST",test_int,cout);
282 : }
283 :
284 :
285 : //
286 : // HASHING STRINGS
287 : //
288 : {
289 : //ofstream ofstr("heap-str");
290 1 : GenericHeap<A<CharString> > foo;
291 2 : do_test("Testing char* HT with default function",foo,cout);
292 : }
293 :
294 : ////
295 : //// Reverse(SimpleCompare)
296 : ////
297 :
298 : //
299 : // HEAP BasicArray<double>
300 : //
301 : {
302 : //ofstream ofstr("heap-r-array-double");
303 : SimpleHeap<BasicArray<double>,
304 1 : Reverse<SimpleCompare<BasicArray<double> > > > test_double;
305 2 : do_stest("Testing BasicArray<double> simpleST",test_double,cout);
306 : }
307 :
308 :
309 : //
310 : // HEAP BasicArray<int>
311 : //
312 : {
313 : //ofstream ofstr("heap-r-array-int");
314 : SimpleHeap<BasicArray<int>,
315 1 : Reverse<SimpleCompare<BasicArray<int> > > > test_int;
316 2 : do_stest("Testing BasicArray<int> simpleST",test_int,cout);
317 : }
318 :
319 :
320 : //
321 : // HEAP double
322 : //
323 : {
324 : //ofstream ofstr("heap-r-double");
325 : SimpleHeap<double,
326 1 : Reverse<SimpleCompare<double> > > test_double;
327 2 : do_stest("Testing double simpleST",test_double,cout);
328 : }
329 :
330 :
331 : //
332 : // HEAP int
333 : //
334 : {
335 : //ofstream ofstr("heap-r-int");
336 : SimpleHeap<int,
337 1 : Reverse<SimpleCompare<int> > > test_int;
338 2 : do_stest("Testing int simpleST",test_int,cout);
339 : }
340 :
341 :
342 : //
343 : // HASHING STRINGS
344 : //
345 : {
346 : //ofstream ofstr("heap-r-str");
347 : GenericHeap<A<CharString>,
348 1 : Reverse<GenericHeapCompare<A<CharString> > > > foo;
349 2 : do_test("Testing char* HT with default function",foo,cout);
350 : }
351 :
352 1 : }
353 :
354 : }
355 :
356 1 : int test_heap(int argc, char** argv)
357 : {
358 1 : OptionParser params;
359 1 : params.add("debug",debug);
360 1 : params.parse_args(argc,argv);
361 1 : if (params.help_option())
362 : {
363 0 : params.write(std::cout);
364 0 : return -11;
365 : }
366 :
367 1 : exec_test();
368 1 : return OK;
369 68 : }
|
