1 | // (C) Copyright Jeremy Siek 2002. |
2 | // Distributed under the Boost Software License, Version 1.0. (See |
3 | // accompanying file LICENSE_1_0.txt or copy at |
4 | // http://www.boost.org/LICENSE_1_0.txt) |
5 | |
6 | #include <boost/pending/disjoint_sets.hpp> |
7 | #include <boost/core/lightweight_test.hpp> |
8 | #include <boost/cstdlib.hpp> |
9 | |
10 | template < typename DisjointSet > struct test_disjoint_set |
11 | { |
12 | static void do_test() |
13 | { |
14 | // The following tests are pretty lame, just a basic sanity check. |
15 | // Industrial strength tests still need to be written. |
16 | |
17 | #if !defined(__MWERKS__) || __MWERKS__ > 0x3003 |
18 | std::size_t elts[] |
19 | #else |
20 | std::size_t elts[4] |
21 | #endif |
22 | = { 0, 1, 2, 3 }; |
23 | |
24 | const int N = sizeof(elts) / sizeof(*elts); |
25 | |
26 | DisjointSet ds(N); |
27 | |
28 | ds.make_set(elts[0]); |
29 | ds.make_set(elts[1]); |
30 | ds.make_set(elts[2]); |
31 | ds.make_set(elts[3]); |
32 | |
33 | BOOST_TEST(ds.find_set(0) != ds.find_set(1)); |
34 | BOOST_TEST(ds.find_set(0) != ds.find_set(2)); |
35 | BOOST_TEST(ds.find_set(0) != ds.find_set(3)); |
36 | BOOST_TEST(ds.find_set(1) != ds.find_set(2)); |
37 | BOOST_TEST(ds.find_set(1) != ds.find_set(3)); |
38 | BOOST_TEST(ds.find_set(2) != ds.find_set(3)); |
39 | |
40 | ds.union_set(0, 1); |
41 | ds.union_set(2, 3); |
42 | BOOST_TEST(ds.find_set(0) != ds.find_set(3)); |
43 | int a = ds.find_set(0); |
44 | BOOST_TEST(a == ds.find_set(1)); |
45 | int b = ds.find_set(2); |
46 | BOOST_TEST(b == ds.find_set(3)); |
47 | |
48 | ds.link(a, b); |
49 | BOOST_TEST(ds.find_set(a) == ds.find_set(b)); |
50 | BOOST_TEST(1 == ds.count_sets(elts, elts + N)); |
51 | |
52 | ds.normalize_sets(elts, elts + N); |
53 | ds.compress_sets(elts, elts + N); |
54 | BOOST_TEST(1 == ds.count_sets(elts, elts + N)); |
55 | } |
56 | }; |
57 | |
58 | int main(int, char*[]) |
59 | { |
60 | using namespace boost; |
61 | { |
62 | typedef disjoint_sets_with_storage< identity_property_map, |
63 | identity_property_map, find_with_path_halving > |
64 | ds_type; |
65 | test_disjoint_set< ds_type >::do_test(); |
66 | } |
67 | { |
68 | typedef disjoint_sets_with_storage< identity_property_map, |
69 | identity_property_map, find_with_full_path_compression > |
70 | ds_type; |
71 | test_disjoint_set< ds_type >::do_test(); |
72 | } |
73 | return boost::report_errors(); |
74 | } |
75 | |