
//////////////////////////////////////////////////////////////////////////////
//
// Asura_UnitTest_HandleTreeTemplate.cpp
//
// Copyright (c) 2006 Rebellion. All rights reserved.
//
// Created by Michael Rennie.
//
// Description:
//
//     Unit tests for Asura_HandleTreeTemplate class
//
//////////////////////////////////////////////////////////////////////////////

// I N C L U D E S ///////////////////////////////////////////////////////////

#if !defined( ASURA_TOOLS )
#error THIS FILE SHOULD ONLY BE COMPILED IN TOOLS BUILDS
#endif // #if !defined( ASURA_TOOLS )

#include "Core/Asura.h"
#include "Core/Asura_Core.h"
#include "Debugging/Asura_Assert.h"

#include "UnitTest/Asura_UnitTest.h"

#include "Core/Asura_HandleTreeTemplate.h"

#ifdef ASURA_SUPPORT_UNITTEST

int g_iIntTreeTotal;
bool IntTreeTraverseAdd(const int i)
{
	g_iIntTreeTotal += i;
	return false;
}

ASURA_UNITTEST(GeneralTests, HandleTreeTemplate)
{
	{	
		const int TREE_SIZE = 50;		
		//MKR 12/09/06: build a very un-balanced tree 
		Asura_HandleTree<int> xIntTree(TREE_SIZE);

		for(int i = 0; i < TREE_SIZE; i++)
		{
			int foo;						
			xIntTree.FindNodeIndex(i + 1, true, &foo);//1 to TREE_SIZE
		}

		//MKR 15/09/06: check that the tree is one long unbalanced tree
		ASURA_UNITTEST_CHECK(xIntTree.GetMaxDepth() == TREE_SIZE);

		//MKR 12/09/06: check if it adds up correctly
		g_iIntTreeTotal = 0;
		xIntTree.TraverseFromRoot(IntTreeTraverseAdd);
		int iTotal = g_iIntTreeTotal;

		xIntTree.Balance();

		//MKR 12/09/06: check if its still correct
		g_iIntTreeTotal = 0;
		xIntTree.TraverseFromRoot(IntTreeTraverseAdd);
		ASURA_UNITTEST_CHECK(g_iIntTreeTotal == iTotal);

		//check if the depth was calculated correctly by Balance()
		ASURA_UNITTEST_CHECK(Asura_Maths::GetCeilLog2(TREE_SIZE + 1) == xIntTree.GetMaxDepth());
	}
	
	// JAT 18/09/06 - taking too long to #if 0 these out
#if 0
	{	
		const int TREE_SIZE = 30000;		
		Asura_HandleTree<int> xIntTree(TREE_SIZE);
		for(int i = 0; i < TREE_SIZE; i++)
		{
			int foo;			
			xIntTree.FindNodeIndex(TREE_SIZE - i, true, &foo);
		}
		ASURA_UNITTEST_CHECK(xIntTree.GetMaxDepth() == TREE_SIZE);
		g_iIntTreeTotal = 0;
		xIntTree.TraverseFromRootNonRecursive(IntTreeTraverseAdd);
		int iTotal = g_iIntTreeTotal;
		xIntTree.Balance();
		g_iIntTreeTotal = 0;
		xIntTree.TraverseFromRootNonRecursive(IntTreeTraverseAdd);
		ASURA_UNITTEST_CHECK(g_iIntTreeTotal == iTotal);
		ASURA_UNITTEST_CHECK(Asura_Maths::GetCeilLog2(TREE_SIZE + 1) == xIntTree.GetMaxDepth());
	}
	
	{	
		const int TREE_SIZE = 30000;		
		Asura_HandleTree<int> xIntTree(TREE_SIZE);
		for(int i = 0; i < TREE_SIZE; i++)
		{
			int foo;			
			xIntTree.FindNodeIndex(rand(), true, &foo);//random
		}		
		g_iIntTreeTotal = 0;
		xIntTree.TraverseFromRootNonRecursive(IntTreeTraverseAdd);
		int iTotal = g_iIntTreeTotal;
		xIntTree.Balance();
		g_iIntTreeTotal = 0;
		xIntTree.TraverseFromRootNonRecursive(IntTreeTraverseAdd);
		ASURA_UNITTEST_CHECK(g_iIntTreeTotal == iTotal);		
	}
#endif // #if 0
}

#endif // #ifdef ASURA_SUPPORT_UNITTEST