#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(VspTree *vspTree, 
								   const int objectSpaceSubdivisionType):
mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
mVspTree(vspTree), 
mOspTree(NULL), 
mBvHierarchy(NULL)
{
	switch(mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		mOspTree = new OspTree();
		mOspTree->mVspTree = mVspTree;
		
		Debug << "creating osp tree" << endl;
		break;
	case BV_BASED_OBJ_SUBDIV:
        mBvHierarchy = new BvHierarchy();
		mBvHierarchy->mVspTree = mVspTree;
		
		Debug << "creating bv hierachy" << endl;
		break;
	default:
		break;
	}

	if (mVspTree)
		mVspTree->mHierarchyManager = this;

	ParseEnvironment();
}


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

	Debug << "creating osp tree" << endl;

	if (mVspTree)
		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()->GetIntValue(
		"Hierarchy.Termination.maxLeaves", mTermMaxLeaves);

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

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

	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;
}


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


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

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


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


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

	return splitCandidate;
}


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

	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		AddSubdivisionStats(mOspTree->mOspStats.Leaves() + mVspTree->mVspStats.Leaves(),
							costDecr,
							mTotalCost
							);
		break;
	case BV_BASED_OBJ_SUBDIV:
		AddSubdivisionStats(mBvHierarchy->mBvhStats.Leaves() + mVspTree->mVspStats.Leaves(),
							costDecr,
							mTotalCost
							);
		break;
	default:
		AddSubdivisionStats(mVspTree->mVspStats.Leaves(),
							costDecr,
							mTotalCost
							);
		break;
	}
}


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


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


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

	const long startTime = GetTime();
	cout << "Constructing view space / object space tree ... \n";
	
	// use objects for evaluating vsp tree construction in the first levels
	// of the subdivision
	mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
	mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;

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

	// process object space candidates
	RunConstruction(sampleRays, objects, forcedViewSpace);
	
	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
	mHierarchyStats.Stop();
	mVspTree->mVspStats.Stop();
}


void HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
												   const ObjectContainer &objects,
												   AxisAlignedBox3 *forcedViewSpace)
{
	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	SubdivisionCandidate *vsc = 
		mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);

	mTQueue.Push(vsc);
}


void HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
													 const ObjectContainer &objects)
{
	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) 

{
	cout << "starting bv hierarchy construction ... " << endl;

	mBvHierarchy->CreateRoot(objects);

	// compute first candidate
	SubdivisionCandidate *sc =
		mBvHierarchy->PrepareConstruction(sampleRays, objects);

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

    mTQueue.Push(sc);
}


void HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
									  const ObjectContainer &objects)
{
	RayInfoContainer *objectSpaceRays = new RayInfoContainer();

	cout << "starting osp tree construction ... " << endl;

	// 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 << "reseting 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 (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);

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

			if (n->IsLeaf()) // local or global termination criteria failed
				return false;
		}
	}
	return true;//!globalTerminationCriteriaMet;
}


bool HierarchyManager::StartObjectSpaceSubdivision() const
{
	const bool ospDepthReached = 
		(mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth);
    
	return !ObjectSpaceSubdivisionConstructed() && 
		   (mTQueue.Empty() || ((mConstructionType == INTERLEAVED) && ospDepthReached));
}


bool HierarchyManager::StartViewSpaceSubdivision() const
{
	const bool vspDepthReached = 
		(mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth);
    
	return !ViewSpaceSubdivisionConstructed() && 
		   (mTQueue.Empty() || ((mConstructionType == INTERLEAVED) && vspDepthReached));
}


void HierarchyManager::RunConstruction(const VssRayContainer &sampleRays,
									   const ObjectContainer &objects,
									   AxisAlignedBox3 *forcedViewSpace)
{
	mHierarchyStats.nodes = 0;
	mGlobalCostMisses = 0;

	int i = 0;
	while (!FinishedConstruction())
	{
		mCurrentCandidate = NextSubdivisionCandidate();    
		mTotalCost -= mCurrentCandidate->GetRenderCostDecrease();

		// cost ratio of cost decrease / totalCost
		const float costRatio = mCurrentCandidate->GetRenderCostDecrease() / mTotalCost;

		//Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
		if (costRatio < mTermMinGlobalCostRatio)
		{
			++ mGlobalCostMisses;
		}
		
		//-- subdivide leaf node
		if (ApplySubdivisionCandidate(mCurrentCandidate))
		{
			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 (mRepairQueue) RepairQueue();
		}

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

			cout << "starting 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 << "starting view space subdivision at depth " 
				 << mVspTree->mVspStats.maxDepth << " (" 
				 << mMinDepthForObjectSpaceSubdivion << ") " << endl;

			PrepareViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);

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

		DEL_PTR(mCurrentCandidate);
	}

	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
}


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 && mOspTree->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);
	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;

	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);
			return mBvHierarchy->AddLeafToPvs(leaf, vc, pdf, contribution);
		}
	default:
		return false;
	}
}


void HierarchyManager::PrintHierarchyStatistics(ofstream &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
{
	switch (mObjectSpaceSubdivisionType)
	{
	case KD_BASED_OBJ_SUBDIV:
		{
			ExportOspTree(exporter, objects);
			break;
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			ExportBvHierarchy(exporter, objects);
			break;
		}
	default:
		break;
	}
}


void HierarchyManager::ExportBvHierarchy(Exporter *exporter, 
										 const ObjectContainer &objects) const
{
	exporter->SetWireframe();
	exporter->ExportBvHierarchy(*mBvHierarchy, 0);
}


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


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 << "========== END OF Hierarchy statistics ==========\n";
}


}