TrieTest.cpp

#include "TrieTest.h"

CPPUNIT_TEST_SUITE_NAMED_REGISTRATION ( TrieTest, "bits" );
CPPUNIT_TEST_SUITE_REGISTRATION ( TrieTest );

void TrieTest::setUp ( ) {
}

void TrieTest::tearDown ( ) {
}

void TrieTest::print_tree ( const ext::trie < char, int > & tree, std::string indent ) {
	std::cout << indent << tree.getData ( ) << std::endl;
	for ( const std::pair < const char, ext::trie < char, int > > & child : tree.getChildren ( ) ) {
		std::cout << indent << child.first << ":" << std::endl;
		print_tree ( child.second, indent + " " );
	}
}

void TrieTest::testTrieStdStructure ( ) {
	ext::trie < char, int > t ( 0, std::map < char, ext::trie < char, int > > { std::make_pair ( 'a', ext::trie < char, int > ( 1 ) ), std::make_pair ( 'b', ext::trie < char, int > ( 2 ) ) } );

	// std::cout << "structure t " << std::boolalpha << t.checkStructure() << std::endl;

	ext::trie < char, int > t2 ( 3 );
	CPPUNIT_ASSERT ( t2 == ( ext::trie < char, int > ( 3 ) ) );

	 // std::cout << "structure t2 " << std::boolalpha << t2.checkStructure() << std::endl;
	t2.insert ( t2.root ( ), 'c', ext::trie < char, int > ( 4 ) );

	std::cout << t2 << std::endl;

	CPPUNIT_ASSERT ( t2 == ( ext::trie < char, int > ( 3, std::map < char, ext::trie < char, int > > { std::make_pair ( 'c', ext::trie < char, int > ( 4 ) ) } ) ) );
	std::swap ( t2.getChildren ( ).begin()->second, t.getChildren().begin()->second );
	CPPUNIT_ASSERT ( t2 == ( ext::trie < char, int > ( 3, std::map < char, ext::trie < char, int > > { std::make_pair ( 'c', ext::trie < char, int > ( 1 ) ) } ) ) );
	CPPUNIT_ASSERT ( t == ( ext::trie < char, int > ( 0, std::map < char, ext::trie < char, int > > { std::make_pair ( 'a', ext::trie < char, int > ( 4 ) ), std::make_pair ( 'b', ext::trie < char, int > ( 2 ) ) } ) ) );
	CPPUNIT_ASSERT ( t2.checkStructure ( ) );
	CPPUNIT_ASSERT ( t.checkStructure ( ) );
	std::swap ( t2.getChildren ( ).begin()->second, t.getChildren().begin()->second );

	CPPUNIT_ASSERT ( t2.checkStructure ( ) );

	t2.insert ( t2.root ( ), t.begin ( ),  t.end ( ) );
	CPPUNIT_ASSERT ( t2.checkStructure ( ) );

	print_tree ( t2, "" );

	t2.erase ( t2.root ( ), std::prev ( t2.getChildren ( ).end ( ) ) );
	CPPUNIT_ASSERT ( t2.checkStructure ( ) );

	print_tree ( t2, "" );

	t2.insert ( & t2.getChildren().begin()->second, 'a', ext::trie < char, int > ( 5 ) );

	CPPUNIT_ASSERT_EQUAL ( ( int ) t2 ( ), 3 );
	CPPUNIT_ASSERT_EQUAL ( ( int ) t2 ( 'a' ), 1 );
	CPPUNIT_ASSERT_EQUAL ( ( int ) t2 ( 'a', 'a' ), 5 );

	t2 ( 'a', 'a' ) = 6;
	CPPUNIT_ASSERT_EQUAL ( ( int ) t2 ( 'a', 'a' ), 6 );

	CPPUNIT_ASSERT ( t2.checkStructure ( ) );

	ext::trie < char, int > cmp1 ( 1 );
	ext::trie < char, int > cmp2 ( 2 );
	ext::trie < char, int > cmp3 ( 3 );

	CPPUNIT_ASSERT ( cmp1 < cmp2 );
	CPPUNIT_ASSERT ( cmp2 < cmp3 );
	CPPUNIT_ASSERT ( cmp2 <= cmp3 );
	CPPUNIT_ASSERT ( cmp2 == cmp2 );
	CPPUNIT_ASSERT ( cmp1 != cmp2 );
}