#ifndef _HierarchyManager_H__
#define _HierarchyManager_H__

#include <stack>

#include "Mesh.h"
#include "Containers.h"
#include "Statistics.h"
#include "VssRay.h"
#include "RayInfo.h"
#include "gzstream.h"
#include "SubdivisionCandidate.h"



namespace GtpVisibilityPreprocessor {

class ViewCellLeaf;
class OspTree;
class VspTree;
class Plane3;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class MergeCandidate;
class Beam;
class ViewCellsTree;
class Environment;
class VspInterior;
class VspLeaf;
class VspNode;
class KdNode;
class KdInterior;
class KdLeaf;
class OspTree;
class KdIntersectable;
class KdTree;
class VspTree;
class KdTreeStatistics;
class BvHierarchy;


#if 0
template <typename T> class GtPriority
{
public:
	bool operator() (const T c1, const T c2) const
	{
		//return false;
		return c1->GetPriority() < c2->GetPriority();
	}
};

typedef std::priority_queue<SubdivisionCandidate *, 
							std::vector<SubdivisionCandidate *>, 
							GtPriority<std::vector<SubdivisionCandidate *>::value_type> > SplitQueue;
#endif


typedef FlexibleHeap<SubdivisionCandidate *> SplitQueue;

/** This class implements a structure holding two different hierarchies,
	one for object space partitioning and one for view space partitioning.

	The object space and the view space are subdivided using a cost heuristics.
	If an object space split or a view space split is chosen is also evaluated
	based on the heuristics. 
	
	The view space heuristics is evaluated by weighting and adding the pvss of the back and
	front node of each specific split. unlike for the standalone method vspbsp tree,
	the pvs of an object would not be the pvs of single object but that of all objects
	which are contained in the same leaf of the object subdivision. This could be done
	by storing the pointer to the object space partition parent, which would allow access to all children.
	Another possibility is to include traced kd-cells in the ray casing process.

	Accordingly, the object space heuristics is evaluated by storing a pvs of view cells with each object.
	the contribution to an object to the pvs is the number of view cells it can be seen from.

	@note
	There is a potential efficiency problem involved in a sense that once a certain type
	of split is chosen for view space / object space, the candidates for the next split of 
	object space / view space must be reevaluated.
	
*/
class HierarchyManager
{
	friend VspTree;
	friend OspTree;
	friend BvHierarchy;

public:
	/** Constructor taking an object space partition and a view space partition tree.
	*/
	HierarchyManager(VspTree &vspTree, OspTree &ospTree);

	/** Constructs the view space and object space subdivision from a given set of rays
		and a set of objects.
		@param sampleRays the set of sample rays the construction is based on
		@param objects the set of objects
	*/
	void Construct(const VssRayContainer &sampleRays,
				   const ObjectContainer &objects,
				   AxisAlignedBox3 *forcedViewSpace);

	/** Constructs first view cells, then object space partition.
	*/
	void Construct2(const VssRayContainer &sampleRays,
					const ObjectContainer &objects,
					AxisAlignedBox3 *forcedViewSpace);

	/** Constructs only vsp tree.
	*/
	void Construct3(const VssRayContainer &sampleRays,
					const ObjectContainer &objects,
					AxisAlignedBox3 *forcedViewSpace);

	enum 
	{
		NO_OBJ_SUBDIV,
		KD_BASED_OBJ_SUBDIV,
		BV_BASED_OBJ_SUBDIV
	};

	/** The type of object space subdivison
	*/
	inline int GetObjectSpaceSubdivisonType() const
	{
		return mObjectSpaceSubdivisonType;
	}
	
protected:

	bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const;

	/** Prepare construction of the hierarchies, set parameters, compute
		first split candidates.
	*/
	void PrepareConstruction(
		const VssRayContainer &sampleRays,
		const ObjectContainer &objects,
		AxisAlignedBox3 *forcedViewSpace,
		RayInfoContainer &viewSpaceRays,
		RayInfoContainer &objectSpaceRays);

	void RunConstruction(const bool repair);
	bool SubdivideSubdivisionCandidate(SubdivisionCandidate *sc);

	bool FinishedConstruction() const;

	SubdivisionCandidate *NextSubdivisionCandidate();

	void RepairQueue();

	void CollectDirtyCandidates(vector<SubdivisionCandidate *> &dirtyList);

	void EvalSubdivisionStats(const SubdivisionCandidate &tData);

	void AddSubdivisionStats(
		const int splits,
		const float renderCostDecr,
		const float totalRenderCost);

	void CollectObjectSpaceDirtyList();
	void CollectViewSpaceDirtyList();

	bool AddSampleToPvs(Intersectable *obj, 
						const float pdf,
						float &contribution) const;

	void CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList);
	void CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList);
		

protected:

	int mObjectSpaceSubdivisonType;

	VspTree *mVspTree;
	OspTree *mOspTree;
	BvHierarchy *mBvHierarchy;

	AxisAlignedBox3 mBoundingBox;

	SplitQueue mTQueue;

	SubdivisionCandidate *mCurrentCandidate;

	//-- global criteria
	float mTermMinGlobalCostRatio;
	int mTermGlobalCostMissTolerance;
	int mGlobalCostMisses;

	/// keeps track of cost during subdivision
	float mTotalCost;

	ofstream mSubdivisionStats;
};

}

#endif