void CheckInvariant( const TestMap& m )
{	
//	assert( map.__rb_verify() );
    EH_STD::size_t total = 0;
    EH_DISTANCE( m.begin(), m.end(), total );
    assert( m.size() == total );
}

//---------------------------------------------------------------------------
//	@function:
//		CTreeMapTest::EresUnittest_Unrank
//
//	@doc:
//		Rehydrate all trees encoded in the map
//
//---------------------------------------------------------------------------
GPOS_RESULT
CTreeMapTest::EresUnittest_Unrank()
{
	CAutoMemoryPool amp;
	IMemoryPool *pmp = amp.Pmp();
	
	TestMap *ptmap = PtmapLoad(pmp);	
	
	// debug print
	CWStringDynamic str(pmp);
	COstreamString oss(&str);
	
	ULLONG ullCount = ptmap->UllCount();
	
	for (ULONG ulRank = 0; ulRank < ullCount; ulRank++)
	{
		oss << "=== tree rank: " << ulRank << " ===" << std::endl;
		BOOL fFlag = true;
		CNode *pnd = ptmap->PrUnrank(pmp, &fFlag, ulRank);
		(void) pnd->OsPrint(oss);
		
		pnd->Release();
	}
	
	GPOS_TRACE(str.Wsz());
	GPOS_DELETE(ptmap);

	return GPOS_OK;
}

//---------------------------------------------------------------------------
//	@function:
//		CTreeMapTest::PtmapLoad
//
//	@doc:
//		Create a semantically meaningful tree map by simulating a MEMO 
//		layout
//
//---------------------------------------------------------------------------
CTreeMapTest::TestMap *
CTreeMapTest::PtmapLoad
	(
	IMemoryPool *pmp
	)
{
	TestMap *ptmap = GPOS_NEW(pmp) TestMap(pmp, &Pnd);
	
	// init raw data
	for (ULONG ulPos = 0; ulPos < ulElems; ulPos++)
	{
		rgul[ulPos] = ulPos;
	}

	
	// simulate the following MEMO with individual edge insertions
	struct SEdge
	{
		// number of parent node
		ULONG m_ulParent;
		
		// position of child
		ULONG m_ulPos;
		
		// number of child node
		ULONG m_ulChild;
	}
	rgedge[]=
	{
		// root group: Join [4,3], HashJoin[4,3]{8}, HashJoin[3,4]{9}
		{9, 1, 7}, {9, 0, 6}, {9, 0, 5},
		{8, 0, 7}, {8, 1, 5}, {8, 1, 6},
		
		// group 4: C, TabScan{7} 
		
		// group 3: Join[1,2], HashJoin[1,2]{5}, SortMergeJoin[1,2]{6}
		{5, 0, 0}, {5, 0, 1}, {5, 1, 2}, {5, 1, 3}, {5, 1, 4},
		{6, 0, 1}, {6, 1, 3}, {6, 1, 4},
		
		// group 2: B, TabScan{2}, IndexScan{3}, Sort[2]{4}
		{4, 0, 2}
		
		// group 1: A, TabScan{0}, IndexScan{1}
	};
		
	for (ULONG ul = 0; ul < GPOS_ARRAY_SIZE(rgedge); ul++)
	{
		SEdge &edge = rgedge[ul];
		ptmap->Insert(&rgul[edge.m_ulParent], edge.m_ulPos, &rgul[edge.m_ulChild]);
	}

	return ptmap;
}

int main()
{
	TestMap testMap;
	map<int, int> myMap;
	myMap.insert(std::make_pair(2, 4));
	myMap.insert(std::make_pair(6, 8));
	testMap.setMap(myMap);
	myMap.clear();
	myMap.insert(std::make_pair(1, 3));
	myMap.insert(std::make_pair(5, 7));
	testMap.setMap(myMap);
	myMap.clear();
	testMap.getMap();
	system("pause");
	return 0;
}

TEST(CollectionUtilsTest, mapInsertOrReplaceCopy) {
    typedef std::map<std::string, std::string> TestMap;

    TestMap testMap;
    const std::string key("Key");
    std::string value1("Value");
    std::string value2("Value2");
    
    MapUtils::insertOrReplace(testMap, key, value1);
    ASSERT_EQ(1u, testMap.size());
    ASSERT_EQ(value1, testMap[key]);
    
    MapUtils::insertOrReplace(testMap, key, value2);
    ASSERT_EQ(1u, testMap.size());
    ASSERT_EQ(value2, testMap[key]);
}

int main( int argc, const char** argv)
{
	try
	{
		if (argc < 3)
		{
			throw std::runtime_error( "missing arguments <nof inserts> <nof queries>");
		}
		unsigned int nofInserts;
		unsigned int nofQueries;
		try
		{
			nofInserts = strus::utils::toint( argv[1]);
			nofQueries = strus::utils::toint( argv[2]);
		}
		catch (const std::exception& e)
		{
			throw std::runtime_error( std::string("bad values for arguments <nof inserts> <nof queries> (2 non negative integers expected): ") + e.what());
		}
		initRand();
		typedef strus::StringMap<strus::Index> TestMap;
		TestMap testmap;
		conotrie::CompactNodeTrie origmap;
		std::vector<std::string> keyar;

		std::size_t ii = 0;
		for (; ii<nofInserts; ++ii)
		{
			std::string key;
			do
			{
				key = randomKey( 32);
			}
			while (testmap.find(key) != testmap.end());

			testmap[ key] = ii+1;
			keyar.push_back( key);
		}
		testmap.clear();

		std::clock_t start;
		double duration;
		start = std::clock();

		for (ii=0; ii<nofInserts; ++ii)
		{
			testmap[ keyar[ ii]] = ii+1;
		}
		duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
		std::cerr << "inserted " << nofInserts << " keys in STL map in " << doubleToString(duration) << " seconds" << std::endl;

		start = std::clock();
		for (ii=0; ii<nofInserts; ++ii)
		{
			origmap.set( keyar[ ii].c_str(), ii+1);
		}
		duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
		std::cerr << "inserted " << nofInserts << " keys in variable size node tree in " << doubleToString(duration) << " seconds" << std::endl;

		start = std::clock();
		for (ii=0; ii<nofQueries; ++ii)
		{
			unsigned int keyidx = RANDINT(0,nofInserts);
			TestMap::const_iterator
				mi = testmap.find( keyar[ keyidx]);
			if (mi == testmap.end() || mi->second != (strus::Index)keyidx+1)
			{
				throw std::logic_error("TESTMAP LOOKUP FAILED");
			}
		}
		duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
		std::cerr << "queried boost unordered map with " << nofQueries << " random selected keys in " << doubleToString(duration) << " seconds" << std::endl;

		start = std::clock();
		for (ii=0; ii<nofQueries; ++ii)
		{
			unsigned int keyidx = RANDINT(0,nofInserts);
			conotrie::CompactNodeTrie::NodeData val;
			if (!origmap.get( keyar[ keyidx].c_str(), val)
			||  val != keyidx+1)
			{
				throw std::runtime_error( "VARIABLE SIZE NODE LOOKUP FAILED");
			}
		}
		duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
		std::cerr << "queried variable size node tree " << nofQueries << " random selected keys in " << doubleToString(duration) << " seconds" << std::endl;

		TestMap::const_iterator
			ti = testmap.begin(), te = testmap.end();

		for (; ti != te; ++ti)
		{
			conotrie::CompactNodeTrie::NodeData val;
			if (!origmap.get( ti->first, val))
			{
				throw std::runtime_error( std::string( "inserted key '") + ti->first + "' disapeared in variable size node tree");
			}
		}

		conotrie::CompactNodeTrie::const_iterator
//.........这里部分代码省略.........

// Executes all tests and returns the number of failures.
int ExecuteAll() {
    const int num_tests = tests.size();
    std::cout << "Executing " << num_tests << " tests..." << std::endl;
    std::vector<std::string> failures;
    int passing = 0;
    for (auto it = tests.begin(); it != tests.end(); ++it) {
        sel::State state{true};
        const bool result = it->second(state);
        if (result) {
            passing += 1;
            std::cout << "." << std::flush;
        } else {
            std::cout << "x" << std::flush;
            failures.push_back(std::string{"Test \""} +
                               it->first + "\" failed.");
        }
        int size = state.Size();
        if (size != 0)
            failures.push_back(std::string{"Test \""} + it->first
                               + "\" leaked " + std::to_string(size) + " values");
    }
    std::cout << std::endl << passing << " out of "
              << num_tests << " tests finished successfully." << std::endl;
    std::cout << std::endl;
    for_each(failures.begin(), failures.end(),
             [](std::string failure) {
                 std::cout << failure << std::endl;
             });
    return num_tests - passing;
}

// Executes all tests and returns the number of failures.
int ExecuteAll() {
	_CrtSetDbgFlag( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF );
	//_CrtSetBreakAlloc(77928);

	const int num_tests = tests.size();
	std::cout << "Executing " << num_tests << " tests..." << std::endl;
	std::vector<std::string> failures;
	int passing = 0;
	for (auto it = tests.begin(); it != tests.end(); ++it) {
		sel::State state{true};
		char progress_marker = 'E';
		bool leaked = false;
		try {
			const bool result = it->second(state);
			int const leak_count = state.Size();
			leaked = leak_count != 0;
			if (result) {
				if (!leaked) {
					passing += 1;
					progress_marker = '.';
				} else {
					failures.push_back(std::string{"Test \""} + it->first
									   + "\" leaked " + std::to_string(leak_count) + " values");
					progress_marker = 'l';
				}
			} else {
				progress_marker = 'x';
				failures.push_back(std::string{"Test \""} +
								   it->first + "\" failed.");
			}
		} catch(std::exception & e) {
			progress_marker = 'e';
			failures.push_back(std::string{"Test \""} + it->first + "\" raised an exception: \"" + e.what() + "\".");
		} catch(...) {
			progress_marker = 'e';
			failures.push_back(std::string{"Test \""} + it->first + "\" raised an exception of unknown type.");
		}
		std::cout << progress_marker << std::flush;
		if (leaked) {
			std::cout << state << std::endl;
		}
	}
	std::cout << std::endl << passing << " out of "
			  << num_tests << " tests finished successfully." << std::endl;
	std::cout << std::endl;
	for_each(failures.begin(), failures.end(),
			 [](std::string failure) {
				 std::cout << failure << std::endl;
			 });
	return num_tests - passing;
}

// Not used in general runs. For debugging purposes
bool ExecuteTest(const char *test) {
    sel::State state{true};
    auto it = tests.find(test);
    const bool result = it->second(state);
    const std::string pretty_result = result ? "pass!" : "fail.";
    std::cout << "Ran test " << test << " with result: "
              << pretty_result << std::endl;
    return result;
}

// Not used in general runs. For debugging purposes
bool ExecuteTest(const char *test) {
    sel::State state{true};
    auto it = tests.find(test);
    return it->second(state);
}