#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 "KdIntersectable.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):
mObjectSpaceSubdivisonType(objectSpaceSubdivisionType),
mVspTree(vspTree), 
mOspTree(NULL), 
mBvHierarchy(NULL)
{
	switch(mObjectSpaceSubdivisonType)
	{
	case KD_BASED_OBJ_SUBDIV:
		mOspTree = new OspTree();
		mOspTree->mVspTree = mVspTree;
		//mOspTree->mHierarchyManager = this;
		Debug << "creating osp tree" << endl;
		break;
	case BV_BASED_OBJ_SUBDIV:
        mBvHierarchy = new BvHierarchy();
		mBvHierarchy->mVspTree = mVspTree;
		//mBvHierarchy->mHierarchyManager = this;
		Debug << "creating bv hierachy" << endl;
		break;
	default:
		break;
	}

	if (mVspTree)
		mVspTree->mHierarchyManager = this;

	ParseEnvironment();
}


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

	//mOspTree->mHierarchyManager = this;
	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);

	Debug << "******** Hierachy Manager Parameters ***********" << endl;
	Debug << "max leaves: " << mTermMaxLeaves << endl;
	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << 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::PrepareConstruction(const VssRayContainer &sampleRays,
										   const ObjectContainer &objects,
										   AxisAlignedBox3 *forcedViewSpace,
										   RayInfoContainer &viewSpaceRays,
										   RayInfoContainer &objectSpaceRays)
{
	mHierarchyStats.Reset();
	mHierarchyStats.Start();

	switch (mObjectSpaceSubdivisonType)
	{
	case KD_BASED_OBJ_SUBDIV:
		{
			SubdivisionCandidate *vsc = 
				mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, viewSpaceRays);
			mTQueue.Push(vsc);

			SubdivisionCandidate *osc;
			osc = mOspTree->PrepareConstruction(sampleRays, objects, objectSpaceRays);
			mTQueue.Push(osc);
			break;
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			mBvHierarchy->CreateRoot(objects);

			SubdivisionCandidate *vsc = 
				mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, viewSpaceRays);
			mTQueue.Push(vsc);

			SubdivisionCandidate *osc;
			osc = mBvHierarchy->PrepareConstruction(sampleRays, objects);
			mTQueue.Push(osc);
			break;
		}
	default:
		break;
	}

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


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

	switch (mObjectSpaceSubdivisonType)
	{
	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)
{
	switch (mConstructionType)
	{
	case 0: 
		ConstructSequential(sampleRays, objects, forcedViewSpace);
		break;
	case 1:
		ConstructInterleaved(sampleRays, objects, forcedViewSpace);
		break;
	default:
		break;
	}
}


void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
											const ObjectContainer &objects,
											AxisAlignedBox3 *forcedViewSpace)
{
	RayInfoContainer *objectSpaceRays = new RayInfoContainer();
	RayInfoContainer *viewSpaceRays = new RayInfoContainer();

	// prepare vsp and osp trees for traversal
	PrepareConstruction(sampleRays, 
						objects, 
						forcedViewSpace, 
						*viewSpaceRays, 
						*objectSpaceRays);

	cout << "Constructing view space / object space tree ... \n";
	const long startTime = GetTime();	
	
	const bool repairQueue = true;
	//const bool repairQueue = false;

	// process object space candidates
	RunConstruction(repairQueue);
	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

	mVspTree->mVspStats.Stop();
}


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

{
	Debug << "\n$$$$$$$$$ bv hierarchy construction $$$$$$$$$$\n" << endl;
	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);

	mBvHierarchy->mBvhStats.Reset();
	mBvHierarchy->mBvhStats.Start();

	const long startTime = GetTime();

	const bool repairQueue = false;
	// process object space candidates
	RunConstruction(repairQueue);

	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;

	mBvHierarchy->mBvhStats.Stop();
}


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

{
	RayInfoContainer *objectSpaceRays = new RayInfoContainer();

	Debug << "\n$$$$$$$$$ osp tree construction $$$$$$$$$$\n" << endl;
	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);

	mOspTree->mOspStats.Reset();
	mOspTree->mOspStats.Start();

	const long startTime = GetTime();
		
	const bool repairQueue = false;
	// process object space candidates
	RunConstruction(repairQueue);

	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
	mOspTree->mOspStats.Stop();

	//////////////////////////
	// matt: only for debugging purpose

	const float rc = mOspTree->EvalRenderCost(sampleRays);
	Debug << "My render cost evalulation: " << rc << endl;
}



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 (mObjectSpaceSubdivisonType == KD_BASED_OBJ_SUBDIV)
		{
			KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);

			if (n->IsLeaf()) // local or global termination criteria failed
				return false;
		}
		else if (mObjectSpaceSubdivisonType == 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;
}


void HierarchyManager::RunConstruction(const bool repair)
{
	mHierarchyStats.nodes = 0;
	mGlobalCostMisses = 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))
		{
			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 (repair) RepairQueue();

			Debug << "candidate: " << mCurrentCandidate->Type() << ", priority: " 
				  << mCurrentCandidate->GetPriority() << endl;
		}
		
		DEL_PTR(mCurrentCandidate);
	}
}


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


void HierarchyManager::CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
{
	switch (mObjectSpaceSubdivisonType)
	{
	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);

sc->mParentData.mNode->SetSubdivisionCandidate(NULL); // HACK
			break;
		}
	default:
		break;
	}
}


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

	mVspTree->CollectDirtyCandidates(sc, dirtyList);

sc->mParentData.mNode->SetSubdivisionCandidate(NULL); // HACK
}


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


void HierarchyManager::RepairQueue()
{
	// TODO
	// 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
	vector<SubdivisionCandidate *> dirtyList;
	Debug << "collecting dirty candidates" << endl;
	CollectDirtyCandidates(dirtyList);
	
	//-- reevaluate the dirty list
	vector<SubdivisionCandidate *>::const_iterator sit, sit_end = dirtyList.end();
	
	Debug << "collected " << (int)dirtyList.size() << " candidates" << endl;

	for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
	{
		SubdivisionCandidate* sc = *sit;
		float rcd = sc->GetRenderCostDecrease();
		Debug << "here6 " << rcd << endl;
		Debug << "here84 " << endl;
		Debug << "here7 " << sc << endl;
		Debug << "here90 " << sc->GetPosition() << endl;
		Debug << "here91 " << sc->Type() << endl;
		//Debug << "here1191" << sc->Type() << endl;
		//Debug << "sc: " << sc << " " << sc->GetPosition() << " " << sc->Type() << endl;
		
		Debug << "here11" << endl;
		mTQueue.Erase(sc); // erase from queue
		Debug << "here2" << endl;

		sc->EvalPriority(); // reevaluate
		
	/*	cout << "render cost decrease diff " << rcd - sc->GetRenderCostDecrease() 
			 << " old: " << rcd << " new " << sc->GetRenderCostDecrease()
			 << " type " << sc->Type() << endl;*/

		mTQueue.Push(sc); // reinsert
	}
}


void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
{
	// the type of the view cells hierarchy
	switch (mObjectSpaceSubdivisonType)
	{
	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 (mObjectSpaceSubdivisonType)
	{
	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::PrintObjectSpaceHierarchyStatistics(ofstream &stream) const
{
	switch (mObjectSpaceSubdivisonType)
	{
	case KD_BASED_OBJ_SUBDIV:
		{
			stream << mOspTree->GetStatistics();
			break;
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			stream << mBvHierarchy->GetStatistics();
			break;
		}
	default:
		break;
	}
}


void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
												  const ObjectContainer &objects) const
{
	switch (mObjectSpaceSubdivisonType)
	{
	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 HierarchyManager::ConstructSequential(const VssRayContainer &sampleRays,
										   const ObjectContainer &objects,
										   AxisAlignedBox3 *forcedViewSpace)
{
	// rays clipped in view space and in object space
	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	

	/////////////////////////////////////////////////////////////
	// view space space partition
	/////////////////////////////////////////////////////////////


	// use objects for evaluating vsp tree construction
	const int savedobjectSpaceSubdivisionType = mObjectSpaceSubdivisonType;
	mObjectSpaceSubdivisonType = NO_OBJ_SUBDIV;

	SubdivisionCandidate *vsc = 
		mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);
	
	// add to queue
	mTQueue.Push(vsc);

	long startTime = GetTime();
	cout << "starting vsp construction ... " << endl;

	mVspTree->mVspStats.Reset();
	mVspTree->mVspStats.Start();

	// all objects can be seen from everywhere
	mTotalCost = (float)dynamic_cast<VspTree::VspSubdivisionCandidate *>(vsc)->mParentData.mPvs;

	const bool repairQueue = false;
	// process view space candidates
	RunConstruction(repairQueue);

	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
	mVspTree->mVspStats.Stop();

	// reset subdivision type
	mObjectSpaceSubdivisonType = savedobjectSpaceSubdivisionType;


	/////////////////////////////////////////////////////////////
	// object space partition
	/////////////////////////////////////////////////////////////
	
	
	switch (mObjectSpaceSubdivisonType)
	{
	case KD_BASED_OBJ_SUBDIV:
		{
			ConstructOspTree(sampleRays, objects);
			break;
		}
	case BV_BASED_OBJ_SUBDIV:
		{
			ConstructBvHierarchy(sampleRays, objects);
			break;
		}
	default:
		break;
	}
}


}