TrieTest.cpp

#include <catch2/catch.hpp>
#include <alib/compare>
#include <alib/trie>

namespace {
	struct RankedArityChecker {
		bool operator ()( char symbol, unsigned wantedRank ) const {
			switch ( symbol ) {
				case 'a':
					return wantedRank == 2;

				case 'b':
					return wantedRank == 1;

				default:
					return wantedRank == 0;
			}
		}

	};

	static void 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 + " " );
		}
	}
}

TEST_CASE ( "Trie", "[unit][std][container]" ) {
	SECTION ( "Trie Std Structure" ) {
		ext::trie < char, int > t ( 0, ext::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 );
		CHECK ( t2 == ( ext::trie < char, int > ( 3 ) ) );

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

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

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

		CHECK ( t2.checkStructure ( ) );

		t2.insert ( t.begin ( ),  t.end ( ) );
		CHECK ( t2.checkStructure ( ) );

		print_tree ( t2, "" );

		t2.erase ( std::prev ( t2.getChildren ( ).end ( ) ) );
		CHECK ( t2.checkStructure ( ) );

		print_tree ( t2, "" );

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

		CHECK ( ( int ) t2 ( ) == 3 );
		CHECK ( ( int ) t2 ( 'a' ) == 1 );
		CHECK ( ( int ) t2 ( 'a', 'a' ) == 5 );

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

		CHECK ( t2.checkStructure ( ) );

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

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