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/test/minimal.hpp>
8 #include <boost/cstdlib.hpp>
9
10 template <typename DisjointSet>
11 struct test_disjoint_set {
do_testtest_disjoint_set12 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_CHECK(ds.find_set(0) != ds.find_set(1));
34 BOOST_CHECK(ds.find_set(0) != ds.find_set(2));
35 BOOST_CHECK(ds.find_set(0) != ds.find_set(3));
36 BOOST_CHECK(ds.find_set(1) != ds.find_set(2));
37 BOOST_CHECK(ds.find_set(1) != ds.find_set(3));
38 BOOST_CHECK(ds.find_set(2) != ds.find_set(3));
39
40
41 ds.union_set(0, 1);
42 ds.union_set(2, 3);
43 BOOST_CHECK(ds.find_set(0) != ds.find_set(3));
44 int a = ds.find_set(0);
45 BOOST_CHECK(a == ds.find_set(1));
46 int b = ds.find_set(2);
47 BOOST_CHECK(b == ds.find_set(3));
48
49 ds.link(a, b);
50 BOOST_CHECK(ds.find_set(a) == ds.find_set(b));
51 BOOST_CHECK(1 == ds.count_sets(elts, elts + N));
52
53 ds.normalize_sets(elts, elts + N);
54 ds.compress_sets(elts, elts + N);
55 BOOST_CHECK(1 == ds.count_sets(elts, elts + N));
56 }
57 };
58
59 int
test_main(int,char * [])60 test_main(int, char*[])
61 {
62 using namespace boost;
63 {
64 typedef
65 disjoint_sets_with_storage<identity_property_map, identity_property_map,
66 find_with_path_halving> ds_type;
67 test_disjoint_set<ds_type>::do_test();
68 }
69 {
70 typedef
71 disjoint_sets_with_storage<identity_property_map, identity_property_map,
72 find_with_full_path_compression> ds_type;
73 test_disjoint_set<ds_type>::do_test();
74 }
75 return boost::exit_success;
76 }
77