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

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


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;

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


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)
{
	SubdivisionCandidate *vsc = 
		mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, viewSpaceRays);
	mTQueue.Push(vsc);

	SubdivisionCandidate *osc = 
		mOspTree->PrepareConstruction(sampleRays, objects, forcedViewSpace, objectSpaceRays);

	mTQueue.Push(osc);
}


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

	//mTotalCost -= costDecr;
	//mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;

	AddSubdivisionStats(mOspTree->mOspStats.Leaves() + mVspTree->mVspStats.Leaves(),
						costDecr,
						mTotalCost
						);
}


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
{
	// TODO matt: make virtual by creating superclasss for traveral data
	return candidate->GlobalTerminationCriteriaMet();
}


void HierarchyManager::Construct(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);

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

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

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

	mVspTree->mVspStats.Stop();
}


bool HierarchyManager::SubdivideSubdivisionCandidate(SubdivisionCandidate *sc)
{
	const bool globalTerminationCriteriaMet = 
			GlobalTerminationCriteriaMet(sc);

	const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);

	if (vspSplit)
	{
		VspNode *n = mVspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
	}
	else
	{
		KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
	}
	
	return !globalTerminationCriteriaMet;
}


void HierarchyManager::RunConstruction(const bool repair)
{
	int numNodes = 0;

	while (!FinishedConstruction())
	{
		SubdivisionCandidate *splitCandidate = NextSubdivisionCandidate();
	    
		mTotalCost -= splitCandidate->GetRenderCostDecrease();

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

		if (costRatio < mTermMinGlobalCostRatio)
			++ mGlobalCostMisses;
	
		/*Debug << "\n**********" << endl
			  << "total cost: " << mTotalCost << " render cost decr: " 
			  << splitCandidate->GetRenderCostDecrease() 
			  << " cost ratio: " << costRatio << endl << endl;*/

		//-- subdivide leaf node

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

			cout << "candidate: " << splitCandidate->Type() << ", priority: " << splitCandidate->GetPriority() << endl;
		}

		DEL_PTR(splitCandidate);
	}
}


void HierarchyManager::Construct2(const VssRayContainer &sampleRays,
								  const ObjectContainer &objects,
								  AxisAlignedBox3 *forcedViewSpace)
{
	// rays clipped in view space and in object space
	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	RayInfoContainer *objectSpaceRays = new RayInfoContainer();


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

#if 0
	// makes no sense otherwise because only one kd cell available
	// during view space partition
	const bool savedCountMethod = mVspTree.mUseKdPvsForHeuristics;
	const bool savedStoreMethod = mVspTree.mStoreObjectPvs;
	
	mVspTree.mUseKdPvsForHeuristics = false;
	mVspTree.mStoreObjectPvs = false;
#endif
	SubdivisionCandidate *vsc = 
		mVspTree->PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);
	
	// add to queue
	mTQueue.Push(vsc);

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

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

	int i = 0;

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


	/////////////////////////////////////////////////////////////
	// object space partition
	/////////////////////////////////////////////////////////////


	Debug << "\n$$$$$$$$$ osp tree construction $$$$$$$$$$\n" << endl;
	cout << "starting osp contruction ... " << 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, forcedViewSpace, *objectSpaceRays);

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

    mTQueue.Push(osc);

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

	startTime = GetTime();
	
	// 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;

#if 0
	// reset parameters
	mVspTree->mUseKdPvsForHeuristics = savedCountMethod;
	mVspTree->mStoreObjectPvs = savedStoreMethod;
#endif
}


void HierarchyManager::Construct3(const VssRayContainer &sampleRays,
								  const ObjectContainer &objects,
								  AxisAlignedBox3 *forcedViewSpace)
{
	// construct only view space partition
	// object kd tree is taken for osp

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

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

	mTQueue.Push(sc);

	cout << "starting vsp contruction ... " << endl;

	long startTime = GetTime();

	RunConstruction(false);

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


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);
			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()
{
	// 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;
	CollectDirtyCandidates(dirtyList);
	
	//-- reevaluate the dirty list
	vector<SubdivisionCandidate *>::const_iterator sit, sit_end = dirtyList.end();

	for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
	{
		SubdivisionCandidate* sc = *sit;

		mTQueue.Erase(sc);

		// reevaluate
		sc->EvalPriority();

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


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::ExportObjectSpaceHierarchyForViz(const ObjectContainer &objects) const
{
	if (mOspTree && mOspTree->GetRoot()) 
	{	
		//-- export final object partition
		Exporter *exporter = Exporter::GetExporter("final_object_partition.wrl");
		
		if (exporter)
		{
			cout << "exporting object space partition ... ";

			if (1)
			{
				exporter->ExportGeometry(objects);
			}
			
#if 0		
			// export rays
			exporter->ExportRays(visRays, RgbColor(0, 1, 0));
#endif

			exporter->SetWireframe();
	
			const int colorCode = 0;
			const int maxPvs = 0;//mOspTree.GetStatistics().maxPvs;

			exporter->ExportOspTree(*mOspTree, 0);

			delete exporter;

			cout << "finished" << endl;
		}
	}
}

}