OpenWalnut  1.3.1
WUnionFind_test.h
1 //---------------------------------------------------------------------------
2 //
3 // Project: OpenWalnut ( http://www.openwalnut.org )
4 //
5 // Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS
6 // For more information see http://www.openwalnut.org/copying
7 //
8 // This file is part of OpenWalnut.
9 //
10 // OpenWalnut is free software: you can redistribute it and/or modify
11 // it under the terms of the GNU Lesser General Public License as published by
12 // the Free Software Foundation, either version 3 of the License, or
13 // (at your option) any later version.
14 //
15 // OpenWalnut is distributed in the hope that it will be useful,
16 // but WITHOUT ANY WARRANTY; without even the implied warranty of
17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 // GNU Lesser General Public License for more details.
19 //
20 // You should have received a copy of the GNU Lesser General Public License
21 // along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>.
22 //
23 //---------------------------------------------------------------------------
24 
25 #ifndef WUNIONFIND_TEST_H
26 #define WUNIONFIND_TEST_H
27 
28 #include <set>
29 #include <vector>
30 
31 #include <cxxtest/TestSuite.h>
32 
33 #include "../WUnionFind.h"
34 
35 /**
36  * Unit tests the WUnionFind datastructure.
37  */
38 class WUnionFindTest : public CxxTest::TestSuite
39 {
40 public:
41  /**
42  * The union always ensure that the new canonical element is the biggest
43  * index.
44  */
46  {
47  WUnionFind uf( 5 );
48  uf.merge( 4, 0 );
49  size_t data[] = { 0, 1, 2, 3, 0 }; // NOLINT
50  std::vector< size_t > expected( data, data + 5 );
51  TS_ASSERT_EQUALS( uf.m_component, expected );
52  uf.merge( 1, 3 );
53  expected[1] = 3;
54  TS_ASSERT_EQUALS( uf.m_component, expected );
55  }
56 
57  /**
58  * Ensure that only the maximal set is returned, and nothing else.
59  */
60  void testMaxSet( void )
61  {
62  WUnionFind uf( 10 );
63  uf.merge( 0, 1 );
64  for( int i = 2; i < 6; ++i )
65  {
66  uf.merge( i, i + 1 );
67  }
68  size_t data[] = { 2, 3, 4, 5, 6 };
69  std::set< size_t > expected( data, data + 5 );
70  TS_ASSERT_EQUALS( *uf.getMaxSet(), expected );
71  }
72 };
73 
74 #endif // WUNIONFIND_TEST_H