OpenWalnut  1.4.0
WUnionFind_test.h
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