#include <stack>
#include <time.h>
#include <iomanip>

#include "ViewCell.h"
#include "Plane3.h"
#include "HierarchyManager.h"
#include "Mesh.h"
#include "common.h"
#include "Environment.h"
#include "Polygon3.h"
#include "Ray.h"
#include "AxisAlignedBox3.h"
#include "Exporter.h"
#include "Plane3.h"
#include "ViewCellsManager.h"
#include "Beam.h"
#include "KdTree.h"
#include "IntersectableWrapper.h"
#include "VspTree.h"
#include "OspTree.h"
#include "BvHierarchy.h"


namespace GtpVisibilityPreprocessor {


#define USE_FIXEDPOINT_T 0


/*******************************************************************/
/*              class HierarchyManager implementation              */
/*******************************************************************/


HierarchyManager::HierarchyManager(const int objectSpaceSubdivisionType):
mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
mOspTree(NULL), 
mBvHierarchy(NULL)
{
	switch(mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		mOspTree = new OspTree();
		mOspTree->mVspTree = mVspTree;
		mOspTree->mHierarchyManager = this;
		break;
	case BV_BASED_OBJ_SUBDIV:
        mBvHierarchy = new BvHierarchy();
		mBvHierarchy->mHierarchyManager = this;
		break;
	default:
		break;
	}

	// hierarchy manager links view space partition and object space partition
	mVspTree = new VspTree();
	mVspTree->mHierarchyManager = this;
	
	ParseEnvironment();
}


HierarchyManager::HierarchyManager(KdTree *kdTree): 
mObjectSpaceSubdivisionType(KD_BASED_OBJ_SUBDIV),
mBvHierarchy(NULL)
{
	mOspTree = new OspTree(*kdTree);
	mOspTree->mVspTree = mVspTree;

	mVspTree = new VspTree();
	mVspTree->mHierarchyManager = this;

	ParseEnvironment();
}


void HierarchyManager::ParseEnvironment()
{
	char subdivisionStatsLog[100];
	Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", 
		subdivisionStatsLog);
	mSubdivisionStats.open(subdivisionStatsLog);

	Environment::GetSingleton()->GetFloatValue(
		"Hierarchy.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);

	Environment::GetSingleton()->GetBoolValue(
		"Hierarchy.Construction.startWithObjectSpace", mStartWithObjectSpace);

	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Termination.maxLeaves", mTermMaxLeaves);

	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Construction.type", mConstructionType);

	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Construction.minDepthForOsp", mMinDepthForObjectSpaceSubdivion);

	Environment::GetSingleton()->GetIntValue(
		"Hierarchy.Construction.minDepthForVsp", mMinDepthForViewSpaceSubdivion);
	
	Environment::GetSingleton()->GetBoolValue(
		"Hierarchy.Construction.repairQueue", mRepairQueue);

	Environment::GetSingleton()->GetBoolValue(
		"Hierarchy.Construction.useMultiLevel", mUseMultiLevelConstruction);

	 mUseMultiLevelConstruction;
	Debug << "******** Hierachy Manager Parameters ***********" << endl;
	Debug << "max leaves: " << mTermMaxLeaves << endl;
	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
	Debug << "construction type: " << mConstructionType << endl;
	Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
	Debug << "repair queue: " << mRepairQueue << endl;
	Debug << endl;
}


HierarchyManager::~HierarchyManager()
{
	DEL_PTR(mOspTree);
	DEL_PTR(mVspTree);
	DEL_PTR(mBvHierarchy);
}


int HierarchyManager::GetObjectSpaceSubdivisionType() const
{
	return mObjectSpaceSubdivisionType;
}


int HierarchyManager::GetViewSpaceSubdivisionType() const
{
	return mViewSpaceSubdivisionType;
}


void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
{
	mVspTree->SetViewCellsManager(vcm);

	if (mOspTree)
	{
		mOspTree->SetViewCellsManager(vcm);
	}
	else if (mBvHierarchy)
	{
		mBvHierarchy->SetViewCellsManager(vcm);
	}
}


void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
{
	mVspTree->SetViewCellsTree(vcTree);
}


VspTree *HierarchyManager::GetVspTree() 
{ 
	return mVspTree; 
}

/*
AxisAlignedBox3 HierarchyManager::GetViewSpaceBox() const
{
	return mVspTree->mBoundingBox;
}*/


AxisAlignedBox3 HierarchyManager::GetObjectSpaceBox() const
{
	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		return mOspTree->mBoundingBox;
	case BV_BASED_OBJ_SUBDIV:
		return mBvHierarchy->mBoundingBox;
	default:
		// hack: empty box
		return AxisAlignedBox3();
	}
}


SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate()
{
	SubdivisionCandidate *splitCandidate = mTQueue.Top();
	mTQueue.Pop();

	return splitCandidate;
}


void HierarchyManager::EvalSubdivisionStats(const SubdivisionCandidate &tData)
{
	const float costDecr = tData.GetRenderCostDecrease();

	AddSubdivisionStats(mHierarchyStats.Leaves(),
						costDecr,
						mTotalCost,
						mTotalPvsEntries
						);
}


void HierarchyManager::AddSubdivisionStats(const int splits,
										   const float renderCostDecr,
										   const float totalRenderCost,
										   const int pvsEntries)
{
	mSubdivisionStats
			<< "#Splits\n" << splits << endl
			<< "#RenderCostDecrease\n" << renderCostDecr << endl 
			<< "#TotalPvsEntries\n" << pvsEntries << endl
			<< "#TotalRenderCost\n" << totalRenderCost << endl;
}


bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
{
	const bool terminationCriteriaMet = 
		(0
		|| (mHierarchyStats.Leaves() >= mTermMaxLeaves) 
		|| (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
		|| (candidate->GlobalTerminationCriteriaMet())
		);

	if (0 && terminationCriteriaMet)
	{
		Debug << "hierarchy global termination criteria met:" << endl;
		Debug << "leaves: " << mHierarchyStats.Leaves() << " " << mTermMaxLeaves << endl;
		Debug << "cost misses: " << mHierarchyStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
	}
	return terminationCriteriaMet;
}


void HierarchyManager::Construct(const VssRayContainer &sampleRays,
								 const ObjectContainer &objects,
								 AxisAlignedBox3 *forcedViewSpace)
{
	if (mUseMultiLevelConstruction)
	{
		ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
	}
	else
	{
		ConstructInterleaved(sampleRays, objects, forcedViewSpace);
	}
}


void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
											const ObjectContainer &objects,
											AxisAlignedBox3 *forcedViewSpace)
{
	mHierarchyStats.Reset();
	mHierarchyStats.Start();
	mHierarchyStats.nodes = 2; // two nodes for view space and object space

	mTotalCost = (float)objects.size();
	Debug << "setting total cost to " << mTotalCost << endl;

	const long startTime = GetTime();
	cout << "Constructing view space / object space tree ... \n";
	
	// compute view space bounding box
	mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);

	// use objects for evaluating vsp tree construction in the first levels
	// of the subdivision
	mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
	mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;

	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;

	// start with view space subdivison: prepare vsp tree for traversal
	if (StartViewSpaceSubdivision())
	{
		mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
		PrepareViewSpaceSubdivision(sampleRays, objects);
	}
	
	// start object space subdivision immediately?
	if (StartObjectSpaceSubdivision())
	{
		mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
		PrepareObjectSpaceSubdivision(sampleRays, objects);
	}

	// process object space candidates
	RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
	
	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

/*#if _DEBUG
	cout << "view space: " << GetViewSpaceBox() << endl;
	cout << "object space:  " << GetObjectSpaceBox() << endl;
#endif*/

	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;

	mHierarchyStats.Stop();
	mVspTree->mVspStats.Stop();
	FinishObjectSpaceSubdivision(objects);
}


void HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
												   const ObjectContainer &objects)
{
	cout << "\nstarting view space hierarchy construction ... " << endl;
	 // hack: reset global cost misses
	mHierarchyStats.mGlobalCostMisses = 0;

	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	SubdivisionCandidate *vsc = 
		mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);

	mTotalCost = mVspTree->mTotalCost;
	Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;

	mTQueue.Push(vsc);
}


void HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
													 const ObjectContainer &objects)
{
	mHierarchyStats.mGlobalCostMisses = 0; // hack: reset global cost misses

	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	{
		PrepareOspTree(sampleRays, objects);
	}
	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	{
		PrepareBvHierarchy(sampleRays, objects);
	}
}


void HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
										  const ObjectContainer &objects) 

{
	const long startTime = GetTime();

	cout << "preparing bv hierarchy construction ... " << endl;
	
	// compute first candidate
	SubdivisionCandidate *sc =
		mBvHierarchy->PrepareConstruction(sampleRays, objects);

	mTotalCost = mBvHierarchy->mTotalCost;
	Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;

    mTQueue.Push(sc);
	cout << "finished bv hierarchy preparation in " 
		 << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
}


void HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
									  const ObjectContainer &objects)
{
	cout << "starting osp tree construction ... " << endl;

	RayInfoContainer *objectSpaceRays = new RayInfoContainer();

	// start with one big kd cell - all objects can be seen from everywhere
	// note: only true for view space = object space

	// compute first candidate
	SubdivisionCandidate *osc =
		mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);

	mTotalCost = mOspTree->mTotalCost;
	Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;
	
    mTQueue.Push(osc);
}


bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc)
{
	const bool globalTerminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
	const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);

	if (!globalTerminationCriteriaMet)
	{
		// cost ratio of cost decrease / totalCost
		const float costRatio = mCurrentCandidate->GetRenderCostDecrease() / mTotalCost;
		//Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
	
		if (costRatio < mTermMinGlobalCostRatio)
		{
			++ mHierarchyStats.mGlobalCostMisses;
		}

		mTotalCost -= mCurrentCandidate->GetRenderCostDecrease();
	}

	if (vspSplit)
	{
		VspNode *n = mVspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);

		if (n->IsLeaf()) // local or global termination criteria failed
			return false;
	}
	else
	{
		if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
		{
			KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
			// local or global termination criteria failed
			if (n->IsLeaf()) 
				return false;
		}
		else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
		{
			BvhNode *n = mBvHierarchy->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
			// local or global termination criteria failed
			if (n->IsLeaf())
				return false;
		}
	}

	return true;
}


int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
{
	int maxDepth = 0;

	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	{
		maxDepth = mOspTree->mOspStats.maxDepth;
	}
	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	{
		maxDepth = mBvHierarchy->mBvhStats.maxDepth;
	}

	return maxDepth;
}


bool HierarchyManager::StartObjectSpaceSubdivision() const
{
	// view space construction already started
	if (ObjectSpaceSubdivisionConstructed())
		return false;

	// start immediately with object space subdivision?
	if (mStartWithObjectSpace)
		return true;

	// is the queue empty again?
	if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
		return true;

	// has the depth for subdivision been reached?
	return 
		((mConstructionType == INTERLEAVED) && 
		 (mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth));
}


bool HierarchyManager::StartViewSpaceSubdivision() const
{
	// view space construction already started
	if (ViewSpaceSubdivisionConstructed())
		return false;

	// start immediately with view space subdivision?
	if (!mStartWithObjectSpace)
		return true;

	// is the queue empty again?
	if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
		return true;

	// has the depth for subdivision been reached?
	return 
		((mConstructionType == INTERLEAVED) && 
		 (mMinDepthForViewSpaceSubdivion <= GetObjectSpaceSubdivisionDepth()));
}


void HierarchyManager::RunConstruction(const bool repairQueue,
									   const VssRayContainer &sampleRays,
									   const ObjectContainer &objects,
									   AxisAlignedBox3 *forcedViewSpace)
{
	int i = 0;
	while (!FinishedConstruction())
	{
		mCurrentCandidate = NextSubdivisionCandidate();    
			
		///////////////////
		//-- subdivide leaf node

		if (ApplySubdivisionCandidate(mCurrentCandidate))
		{
			cout << mCurrentCandidate->Type() << " ";
		
			// update stats
			mHierarchyStats.nodes += 2;
			mHierarchyStats.pvsEntries += mCurrentCandidate->GetPvsEntriesIncr();
			mHierarchyStats.memory += 0; // TODO
			// subdivision successful
			EvalSubdivisionStats(*mCurrentCandidate);
		
			// reevaluate candidates affected by the split for view space splits, 
			// this would be object space splits and other way round
			if (repairQueue) 
			{	
				RepairQueue();
			}
		}

		// we use objects for evaluating vsp tree construction until 
		// a certain depth once a certain depth existiert ...
		if (StartObjectSpaceSubdivision())
		{
			mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;

			cout << "\nstarting object space subdivision at depth " 
				 << mVspTree->mVspStats.maxDepth << " (" 
				 << mMinDepthForObjectSpaceSubdivion << ") " << endl;

			PrepareObjectSpaceSubdivision(sampleRays, objects);

			cout << "reseting queue ... ";
			ResetQueue();
			cout << "finished" << endl;
		}

		if (StartViewSpaceSubdivision())
		{
			mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;

			cout << "\nstarting view space subdivision at depth " 
				 << GetObjectSpaceSubdivisionDepth() << " (" 
				 << mMinDepthForViewSpaceSubdivion << ") " << endl;

			PrepareViewSpaceSubdivision(sampleRays, objects);

			cout << "reseting queue ... ";
			ResetQueue();
			cout << "finished" << endl;
		}

		DEL_PTR(mCurrentCandidate);
	}
}



void HierarchyManager::RunConstruction(const bool repairQueue)
{
	int i = 0;
	while (!FinishedConstruction())
	{
		mCurrentCandidate = NextSubdivisionCandidate();    
			
		///////////////////
		//-- subdivide leaf node

		if (ApplySubdivisionCandidate(mCurrentCandidate))
		{
			cout << mCurrentCandidate->Type() << " ";
			if (0) cout << "subdividing candidate " << ++ i << " of type " 
						<< mCurrentCandidate->Type() << endl;
			mHierarchyStats.nodes += 2;

			// subdivision successful
			EvalSubdivisionStats(*mCurrentCandidate);
		
			// reevaluate candidates affected by the split for view space splits, 
			// this would be object space splits and other way round
			if (repairQueue) RepairQueue();
		}

		DEL_PTR(mCurrentCandidate);
	}
}


void HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays, 
												   const ObjectContainer &objects)
{
#if 0	
		DEL_PTR(mBvHierarchy);
		mBvHierarchy = new BvHierarchy();
		mBvHierarchy->mHierarchyManager = this;

		PrepareObjectSpaceSubdivision(sampleRays, objects);
		return;
#endif

	if (!ObjectSpaceSubdivisionConstructed())
	{
		return PrepareObjectSpaceSubdivision(sampleRays, objects);
	}

	switch (mObjectSpaceSubdivisionType)
	{
	case BV_BASED_OBJ_SUBDIV:
		cout << "\nreseting bv hierarchy" << endl;
        Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
	
		mHierarchyStats.nodes -= mBvHierarchy->mBvhStats.nodes;
		mTQueue.Push(mBvHierarchy->Reset(sampleRays, objects));
		mTotalCost = mBvHierarchy->mTotalCost;
		break;

	case KD_BASED_OBJ_SUBDIV:
		// TODO
		break;
	default:
		break;
	}
}


void HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays, 
												 const ObjectContainer &objects)
{
	DEL_PTR(mBvHierarchy);
	mBvHierarchy = new BvHierarchy();
	mBvHierarchy->mHierarchyManager = this;

	PrepareViewSpaceSubdivision(sampleRays, objects);
	return;
}


void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,											 
										   const ObjectContainer &objects,
										   AxisAlignedBox3 *forcedViewSpace)
{
	mHierarchyStats.Reset();
	mHierarchyStats.Start();
	mHierarchyStats.nodes = 2;
	
	mTotalCost = (float)objects.size();
	Debug << "setting total cost to " << mTotalCost << endl;

	const long startTime = GetTime();
	cout << "Constructing view space / object space tree ... \n";
	
	// compute view space bounding box
	mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);

	// use sah for evaluating object space construction for the first run
	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
	
	const int limit = 4;
	int i = 0;

	// render cost optimization
	// start with object space partiton
	// then optimizate view space partition for the current osp
	// and vice versa until iteration depth is reached.
	while (1)
	{
       	// first run object space subdivision
		ResetObjectSpaceSubdivision(sampleRays, objects);

		// process object space candidates
		RunConstruction(false);

		if ((++ i) >= limit)
			break;

		/////////////////
		// do view space subdivison with respect to the object space partition
		ResetViewSpaceSubdivision(sampleRays, objects);

		// process view space candidates
		RunConstruction(false);
		mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
		
		if ((++ i) >= limit)
			break;

		cout << "iteration " << i << " of " << limit << " finished" << endl;
	}
	
	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

/*#if _DEBUG
	cout << "view space: " << GetViewSpaceBox() << endl;
	cout << "object space:  " << GetObjectSpaceBox() << endl;
#endif*/

	mHierarchyStats.Stop();
	mVspTree->mVspStats.Stop();
	FinishObjectSpaceSubdivision(objects);
}


bool HierarchyManager::FinishedConstruction() const
{
	return mTQueue.Empty();
}


bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
{
	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		return mOspTree && mOspTree->GetRoot();
	case BV_BASED_OBJ_SUBDIV:
		return mBvHierarchy && mBvHierarchy->GetRoot();
	default:
        return false;
	}
}


bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
{
	return mVspTree && mVspTree->GetRoot();
}


void HierarchyManager::CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
{
	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		{
			OspTree::OspSubdivisionCandidate *sc = 
				dynamic_cast<OspTree::OspSubdivisionCandidate *>(mCurrentCandidate);

			mOspTree->CollectDirtyCandidates(sc, dirtyList);
			break;
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			BvHierarchy::BvhSubdivisionCandidate *sc = 
				dynamic_cast<BvHierarchy::BvhSubdivisionCandidate *>(mCurrentCandidate);

			mBvHierarchy->CollectDirtyCandidates(sc, dirtyList);
			break;
		}
	default:
		break;
	}
}


void HierarchyManager::CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
{
	VspTree::VspSubdivisionCandidate *sc = 
		dynamic_cast<VspTree::VspSubdivisionCandidate *>(mCurrentCandidate);

	mVspTree->CollectDirtyCandidates(sc, dirtyList);
}


void HierarchyManager::CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList)
{
	// we have either a object space or view space split
	if (mCurrentCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
	{
		CollectViewSpaceDirtyList(dirtyList);
	}
	else // object space split
	{
		CollectObjectSpaceDirtyList(dirtyList);
	}
}


void HierarchyManager::RepairQueue()
{
	// for each update of the view space partition:
	// the candidates from object space partition which
	// have been afected by the view space split (the kd split candidates
	// which saw the view cell which was split) must be reevaluated 
	// (maybe not locally, just reinsert them into the queue)
	//
	// vice versa for the view cells
	// for each update of the object space partition
	// reevaluate split candidate for view cells which saw the split kd cell
	// 
	// the priority queue update can be solved by implementing a binary heap
	// (explicit data structure, binary tree)
	// *) inserting and removal is efficient
	// *) search is not efficient => store queue position with each
	// split candidate

	// collect list of "dirty" candidates
	long startTime = GetTime();
   
	vector<SubdivisionCandidate *> dirtyList;
	CollectDirtyCandidates(dirtyList);
	if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
	
	/////////////////////////////////
	//-- reevaluate the dirty list

	SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
	
	for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
	{
		SubdivisionCandidate* sc = *sit;
		const float rcd = sc->GetRenderCostDecrease();
		
		mTQueue.Erase(sc); // erase from queue
		sc->EvalPriority(); // reevaluate
		
		/*
		Debug << "candidate " << sc << " reevaluated\n" 
			  << "render cost decrease diff " <<  rcd - sc->GetRenderCostDecrease()
			  << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;*/
		if (0)
		{
			const float rcDiff =  rcd - sc->GetRenderCostDecrease();
			mTotalCost += rcDiff;
		}
		mTQueue.Push(sc); // reinsert
	}

	long endTime = GetTime();
	Real timeDiff = TimeDiff(startTime, endTime);

	mHierarchyStats.repairTime += timeDiff;

	if (0) cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
}


void HierarchyManager::ResetQueue()
{
	SubdivisionCandidateContainer mCandidateBuffer;

	// remove from queue
	while (!mTQueue.Empty())
	{
		SubdivisionCandidate *candidate = NextSubdivisionCandidate();
		candidate->EvalPriority(); // reevaluate
		cout << ".";
		mCandidateBuffer.push_back(candidate);
	}

	// put back into queue
	SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
    for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
	{cout << ":";
		mTQueue.Push(*sit);
	}
}


void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
{
	// the type of the view cells hierarchy
	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
		mOspTree->Export(stream);
		stream << endl << "</ObjectSpaceHierarchy>" << endl;
		break;		
	case BV_BASED_OBJ_SUBDIV:
		stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
		mBvHierarchy->Export(stream);
		stream << endl << "</ObjectSpaceHierarchy>" << endl;
		break;
	}
}


bool HierarchyManager::AddSampleToPvs(Intersectable *obj, 
									  const Vector3 &hitPoint,
									  ViewCell *vc,
									  const float pdf, 
									  float &contribution) const
{
	if (!obj) return false;

	switch (mObjectSpaceSubdivisionType)
	{
	case NO_OBJ_SUBDIV:
		{
			// potentially visible objects
			return vc->AddPvsSample(obj, pdf, contribution);
		}
	case KD_BASED_OBJ_SUBDIV:
		{
			// potentially visible kd cells
			KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
			return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
			BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
			
			return vc->AddPvsSample(bvhObj, pdf, contribution);
		}
	default:
		return false;
	}
}


void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
{
	stream << mHierarchyStats << endl;
	stream << "\nview space:" << endl << endl;
	stream << mVspTree->GetStatistics() << endl;
	stream << "\nobject space:" << endl << endl;

	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		{
			stream << mOspTree->GetStatistics() << endl;
			break;
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			stream << mBvHierarchy->GetStatistics() << endl;
			break;
		}
	default:
		break;
	}
}


void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
												  const ObjectContainer &objects,
												  const AxisAlignedBox3 *bbox,
												  const bool exportBounds) const
{
	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		{
			ExportOspTree(exporter, objects);
			break;
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
			break;
		}
	default:
		break;
	}
}


void HierarchyManager::ExportOspTree(Exporter *exporter, 
									 const ObjectContainer &objects) const
{
	if (0) exporter->ExportGeometry(objects);
			
	exporter->SetWireframe();
	exporter->ExportOspTree(*mOspTree, 0);
}


Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray, 
												  const bool isTermination) const
{

	Intersectable *obj;
	Vector3 pt;
	KdNode *node;

	ray.GetSampleData(isTermination, pt, &obj, &node);
	
	if (!obj) return NULL;

	switch (mObjectSpaceSubdivisionType)
	{
	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
		{
			KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
			return mOspTree->GetOrCreateKdIntersectable(leaf);
		}
	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
		{
			BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
			return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
		}
	default:
		return obj;
	}
}


void HierarchyStatistics::Print(ostream &app) const
{
	app << "=========== Hierarchy statistics ===============\n";

	app << setprecision(4);

	app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
	
	app << "#N_RTIME  ( Repair time [s] )\n" << repairTime * 1e-3f << " \n";

	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";

	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";

	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";

	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;

	app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
	
	app << "========== END OF Hierarchy statistics ==========\n";
}


static void RemoveRayRefs(const ObjectContainer &objects)
{
	ObjectContainer::const_iterator oit, oit_end = objects.end();
	for (oit = objects.begin(); oit != oit_end; ++ oit)
	{
		(*oit)->mVssRays.clear();
	}
}


void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects) const
{
	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		{
			mOspTree->mOspStats.Stop();
			break;
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			mBvHierarchy->mBvhStats.Stop();
			RemoveRayRefs(objects);
			break;
		}
	default:
		break;
	}
}

}