]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. | |
3 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek | |
4 | // | |
5 | // Distributed under the Boost Software License, Version 1.0. (See | |
6 | // accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | //======================================================================= | |
9 | #include <boost/config.hpp> | |
10 | #include <iostream> | |
11 | #include <vector> | |
12 | #include <boost/graph/random.hpp> | |
92f5a8d4 TL |
13 | #ifndef BOOST_NO_CXX11_HDR_RANDOM |
14 | #include <random> | |
15 | namespace random_ns = std; | |
16 | #else | |
7c673cae | 17 | #include <boost/random/mersenne_twister.hpp> |
92f5a8d4 TL |
18 | namespace random_ns = boost; |
19 | #endif | |
7c673cae FG |
20 | #include <algorithm> |
21 | #include <boost/pending/fibonacci_heap.hpp> | |
22 | #include <boost/graph/graph_utility.hpp> | |
23 | #include <boost/pending/indirect_cmp.hpp> | |
24 | ||
25 | using namespace boost; | |
26 | ||
f67539c2 | 27 | int main() |
7c673cae | 28 | { |
f67539c2 TL |
29 | typedef indirect_cmp< float*, std::less< float > > ICmp; |
30 | int i; | |
31 | random_ns::mt19937 gen; | |
32 | for (int N = 2; N < 200; ++N) | |
33 | { | |
34 | uniform_int<> distrib(0, N - 1); | |
35 | boost::variate_generator< random_ns::mt19937&, uniform_int<> > rand_gen( | |
36 | gen, distrib); | |
37 | for (int t = 0; t < 10; ++t) | |
38 | { | |
39 | std::vector< float > v, w(N); | |
7c673cae | 40 | |
f67539c2 TL |
41 | ICmp cmp(&w[0], std::less< float >()); |
42 | fibonacci_heap< int, ICmp > Q(N, cmp); | |
7c673cae | 43 | |
f67539c2 TL |
44 | for (int c = 0; c < w.size(); ++c) |
45 | w[c] = c; | |
92f5a8d4 | 46 | #ifndef BOOST_NO_CXX98_RANDOM_SHUFFLE |
f67539c2 | 47 | std::random_shuffle(w.begin(), w.end()); |
92f5a8d4 | 48 | #else |
f67539c2 | 49 | std::shuffle(w.begin(), w.end(), gen); |
92f5a8d4 | 50 | #endif |
7c673cae | 51 | |
f67539c2 TL |
52 | for (i = 0; i < N; ++i) |
53 | Q.push(i); | |
7c673cae | 54 | |
f67539c2 TL |
55 | for (i = 0; i < N; ++i) |
56 | { | |
57 | int u = rand_gen(); | |
58 | float r = rand_gen(); | |
59 | r /= 2.0; | |
60 | w[u] = w[u] - r; | |
61 | Q.update(u); | |
62 | } | |
7c673cae | 63 | |
f67539c2 TL |
64 | for (i = 0; i < N; ++i) |
65 | { | |
66 | v.push_back(w[Q.top()]); | |
67 | Q.pop(); | |
68 | } | |
69 | std::sort(w.begin(), w.end()); | |
7c673cae | 70 | |
f67539c2 TL |
71 | if (!std::equal(v.begin(), v.end(), w.begin())) |
72 | { | |
73 | std::cout << std::endl << "heap sorted: "; | |
74 | std::copy(v.begin(), v.end(), | |
75 | std::ostream_iterator< float >(std::cout, " ")); | |
76 | std::cout << std::endl << "correct: "; | |
77 | std::copy(w.begin(), w.end(), | |
78 | std::ostream_iterator< float >(std::cout, " ")); | |
79 | std::cout << std::endl; | |
80 | return -1; | |
81 | } | |
82 | } | |
7c673cae | 83 | } |
f67539c2 TL |
84 | std::cout << "fibonacci heap passed test" << std::endl; |
85 | return 0; | |
7c673cae | 86 | } |