OpenWalnut
1.4.0
|
00001 //--------------------------------------------------------------------------- 00002 // 00003 // Project: OpenWalnut ( http://www.openwalnut.org ) 00004 // 00005 // Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS 00006 // For more information see http://www.openwalnut.org/copying 00007 // 00008 // This file is part of OpenWalnut. 00009 // 00010 // OpenWalnut is free software: you can redistribute it and/or modify 00011 // it under the terms of the GNU Lesser General Public License as published by 00012 // the Free Software Foundation, either version 3 of the License, or 00013 // (at your option) any later version. 00014 // 00015 // OpenWalnut is distributed in the hope that it will be useful, 00016 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00018 // GNU Lesser General Public License for more details. 00019 // 00020 // You should have received a copy of the GNU Lesser General Public License 00021 // along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>. 00022 // 00023 //--------------------------------------------------------------------------- 00024 00025 #ifndef WUNIONFIND_TEST_H 00026 #define WUNIONFIND_TEST_H 00027 00028 #include <set> 00029 #include <vector> 00030 00031 #include <cxxtest/TestSuite.h> 00032 00033 #include "../WUnionFind.h" 00034 00035 /** 00036 * Unit tests the WUnionFind datastructure. 00037 */ 00038 class WUnionFindTest : public CxxTest::TestSuite 00039 { 00040 public: 00041 /** 00042 * The union always ensure that the new canonical element is the biggest 00043 * index. 00044 */ 00045 void testUnionMergesToBiggerIndex( void ) 00046 { 00047 WUnionFind uf( 5 ); 00048 uf.merge( 4, 0 ); 00049 size_t data[] = { 0, 1, 2, 3, 0 }; // NOLINT 00050 std::vector< size_t > expected( data, data + 5 ); 00051 TS_ASSERT_EQUALS( uf.m_component, expected ); 00052 uf.merge( 1, 3 ); 00053 expected[1] = 3; 00054 TS_ASSERT_EQUALS( uf.m_component, expected ); 00055 } 00056 00057 /** 00058 * Ensure that only the maximal set is returned, and nothing else. 00059 */ 00060 void testMaxSet( void ) 00061 { 00062 WUnionFind uf( 10 ); 00063 uf.merge( 0, 1 ); 00064 for( int i = 2; i < 6; ++i ) 00065 { 00066 uf.merge( i, i + 1 ); 00067 } 00068 size_t data[] = { 2, 3, 4, 5, 6 }; 00069 std::set< size_t > expected( data, data + 5 ); 00070 TS_ASSERT_EQUALS( *uf.getMaxSet(), expected ); 00071 } 00072 }; 00073 00074 #endif // WUNIONFIND_TEST_H