#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;
class Exporter;
class ViewCellsParseHandlers;


#define COUNT_ORIGIN_OBJECTS 1

/** View space / object space hierarchy statistics.
*/
class HierarchyStatistics: public StatisticsBase
{
public:
	/// total number of entries in the pvs
	int mPvsEntries;
	/// storage cost in MB
	float mMemory;
	/// total number of nodes
	int mNodes;
	/// maximal reached depth
	int mMaxDepth;
	/// accumulated depth
	int mAccumDepth;
	/// time spent for queue repair
	float mRepairTime;

	// global cost ratio violations
	int mGlobalCostMisses;
	/// total cost of subdivision
	float mTotalCost;
	/// render cost decrease of subdivision
	float mRenderCostDecrease;

	// Constructor
	HierarchyStatistics() 
	{
		Reset();
	}

	int Nodes() const {return mNodes;}
	int Interior() const { return mNodes / 2 - 1; }
	int Leaves() const { return (mNodes / 2) + 1; }
	
	// TODO: computation wrong
	double AvgDepth() const { return mAccumDepth / (double)Leaves();}

	void Reset()
	{
		mGlobalCostMisses = 0;
		mTotalCost = 0;
		mRenderCostDecrease = 0;

		mNodes = 0;
		mMaxDepth = 0;
		mAccumDepth = 0;
		mRepairTime = 0;
		mMemory = 0;
		mPvsEntries = 0;
	}

	void Print(ostream &app) const;

	friend ostream &operator<<(ostream &s, const HierarchyStatistics &stat) 
	{
		stat.Print(s);
		return s;
	} 
};


/** 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
{
public:
	/** Constructor with the view space partition tree and
		the object space hierarchy type as argument.
	*/
	HierarchyManager(const int objectSpaceHierarchyType);
	/** Hack: OspTree will copy the content from this kd tree.
		Only view space hierarchy will be constructed.
	*/
	HierarchyManager(KdTree *kdTree);

	/** Deletes space partition and view space partition.
	*/
	~HierarchyManager();

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

	enum 
	{
		NO_OBJ_SUBDIV,
		KD_BASED_OBJ_SUBDIV,
		BV_BASED_OBJ_SUBDIV
	};

	enum 
	{
		NO_VIEWSPACE_SUBDIV,
		KD_BASED_VIEWSPACE_SUBDIV
	};

	/** The type of object space subdivison
	*/
	int GetObjectSpaceSubdivisionType() const;	
	/** The type of view space space subdivison
	*/
	int GetViewSpaceSubdivisionType() const;
	/** Sets a pointer to the view cells manager.
	*/		
	void SetViewCellsManager(ViewCellsManager *vcm);
	/** Sets a pointer to the view cells tree.
	*/
	void SetViewCellsTree(ViewCellsTree *vcTree);
	/** Exports the object hierarchy to disc.
	*/
	void ExportObjectSpaceHierarchy(OUT_STREAM &stream);
	/** Adds a sample to the pvs of the specified view cell.
	*/
	bool AddSampleToPvs(
		Intersectable *obj, 
		const Vector3 &hitPoint,
		ViewCell *vc,
		const float pdf, 
		float &contribution) const;

	/** Print out statistics.
	*/
	void PrintHierarchyStatistics(ostream &stream) const;

	/** Returns the view space partition tree.
	*/
	VspTree *GetVspTree();

	/** Returns view space bounding box.
	*/
	//AxisAlignedBox3 GetViewSpaceBox() const;

	/** Returns object space bounding box.
	*/
	AxisAlignedBox3 GetObjectSpaceBox() const;

	/** Exports object space hierarchy for visualization.
	*/
	void ExportObjectSpaceHierarchy(Exporter *exporter, 
									const ObjectContainer &objects,
									const AxisAlignedBox3 *bbox,
									const bool exportBounds = true) const;

	/** Returns intersectable pierced by this ray.
	*/
	Intersectable *GetIntersectable(const VssRay &ray, const bool isTermination) const;

	/** Export object space partition bounding boxes.
	*/
	void ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects);

	friend ostream &operator<<(ostream &s, const HierarchyManager &hm) 
	{
		hm.PrintHierarchyStatistics(s);
		return s;
	} 

	HierarchyStatistics &GetHierarchyStats() { return mHierarchyStats; };

	inline bool ConsiderMemory() const { return mConsiderMemory; }
	inline float GetMemoryConst() const { return mMemoryConst; }

float mInitialRenderCost;

protected:

	/** Returns true if the global termination criteria were met.
	*/
	bool GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const;

	/** Prepare construction of the hierarchies, set parameters, compute
		first split candidates.
	*/
	SubdivisionCandidate *PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
														const ObjectContainer &objects);


	/** Create bounding box and root.
	*/
	void InitialiseObjectSpaceSubdivision(const ObjectContainer &objects);

	/** Returns memory usage of object space hierarchy.
	*/
	float GetObjectSpaceMemUsage() const;


	//////////////////////////////
	// the main loop

	/** This is for interleaved construction / sequential construction.
	*/
	void RunConstruction(const bool repairQueue,
						 const VssRayContainer &sampleRays,
						 const ObjectContainer &objects,
						 AxisAlignedBox3 *forcedViewSpace);
	
	/** This is for interleaved construction using some objects 
		and some view space splits.
	*/
	int RunConstruction(SplitQueue &splitQueue,
						SubdivisionCandidateContainer &chosenCandidates,
						//const float minRenderCostDecr,
						SubdivisionCandidate *oldCandidate,
						const int minSteps,
						const int maxSteps);

	/** Default subdivision method.
	*/
	void RunConstruction(const bool repairQueue);
		
	////////////////////////////////////////////////

	/** Evaluates the subdivision candidate and executes the split.
	*/
	bool ApplySubdivisionCandidate(SubdivisionCandidate *sc, 
								   SplitQueue &splitQueue,
								   const bool repairQueue);

	/** Tests if hierarchy construction is finished.
	*/
	bool FinishedConstruction() const;

	/** Returns next subdivision candidate from the split queue.
	*/
	SubdivisionCandidate *NextSubdivisionCandidate(SplitQueue &splitQueue);

	/** Repairs the dirty entries of the subdivision candidate queue. The
		list of entries is given in the dirty list.
	*/
	void RepairQueue(const SubdivisionCandidateContainer &dirtyList, 
					 SplitQueue &splitQueue,
					 const bool recomputeSplitPlaneOnRepair);

	/** Collect subdivision candidates which were affected by the splits from the
		chosenCandidates list.
	*/ 
	void CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates, 
								SubdivisionCandidateContainer &dirtyList);

	/** Evaluate subdivision stats for log.
	*/
	void EvalSubdivisionStats();

	void AddSubdivisionStats(const int splits,
							 const float renderCostDecr,
							 const float totalRenderCost,
							 const int totalPvsEntries, 
							 const float memory,
							 const float renderCostPerStorage,
							 const float vspOspRatio);

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

	/** Collect affected view space candidates.
	*/
	void CollectViewSpaceDirtyList(SubdivisionCandidate *sc,
								   SubdivisionCandidateContainer &dirtyList);

	/** Collect affected object space candidates.
	*/
	void CollectObjectSpaceDirtyList(SubdivisionCandidate *sc,
									 SubdivisionCandidateContainer &dirtyList);
		
	/** Export object space partition tree.
	*/
	void ExportOspTree(Exporter *exporter, 
					   const ObjectContainer &objects) const;

	/** Parse the environment variables.
	*/
	void ParseEnvironment();

	bool StartObjectSpaceSubdivision() const;
	bool StartViewSpaceSubdivision() const;


	////////////////////////////
	// Helper function for preparation of subdivision

	/** Prepare bv hierarchy for subdivision
	*/
	SubdivisionCandidate *PrepareBvHierarchy(const VssRayContainer &sampleRays,
									   const ObjectContainer &objects);

	/** Prepare object space kd tree for subdivision.
	*/
	SubdivisionCandidate *PrepareOspTree(const VssRayContainer &sampleRays,
								   const ObjectContainer &objects);

	/** Prepare view space subdivision and add candidate to queue.
	*/
	SubdivisionCandidate *PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
													  const ObjectContainer &objects);

	/** Was object space subdivision already constructed?
	*/
	bool ObjectSpaceSubdivisionConstructed() const;
	
	/** Was view space subdivision already constructed?
	*/
	bool ViewSpaceSubdivisionConstructed() const;

	/** Reset the split queue, i.e., reevaluate the split candidates.
	*/
    void ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane);

	/** After the suddivision has ended, do some final tasks.
	*/
	void FinishObjectSpaceSubdivision(const ObjectContainer &objects, 
									  const bool removeRayRefs = true) const;

	/** Returns depth of object space subdivision.
	*/
	int GetObjectSpaceSubdivisionDepth() const;

	/** Returns number of leaves in object space subdivision.
	*/
	int GetObjectSpaceSubdivisionLeaves() const;
	int GetObjectSpaceSubdivisionNodes() const;

	/** Construct object space partition interleaved with view space partition.
		Each time the best object or view space candidate is selected
		for the next split.
	*/
	void ConstructInterleaved(const VssRayContainer &sampleRays,
							  const ObjectContainer &objects,
							  AxisAlignedBox3 *forcedViewSpace);

	/** Construct object space partition interleaved with view space partition.
		The method chooses a number candidates of each type for subdivision.
		The number is determined by the "gradient", i.e., the render cost decrease.
		Once this render cost decrease is lower than the render cost decrease
		for the splits of previous type, the method will stop current subdivision and
		evaluate if view space or object space would be the beneficial for the 
		next number of split.
	*/
	void ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,
										  const ObjectContainer &objects,
										  AxisAlignedBox3 *forcedViewSpace);

	/** Use iteration to construct the object space hierarchy.
	*/
	void ConstructMultiLevel(const VssRayContainer &sampleRays,
							 const ObjectContainer &objects,
							 AxisAlignedBox3 *forcedViewSpace);

	/** Based on a given subdivision, we try to optimize using an
		multiple iteration over view and object space.
	*/
	void OptimizeMultiLevel(const VssRayContainer &sampleRays,											 
							const ObjectContainer &objects,
							AxisAlignedBox3 *forcedViewSpace);

	/** Reset the object space subdivision. 
		E.g., deletes hierarchy and resets stats.
		so construction can be restarted.
	*/
	SubdivisionCandidate *ResetObjectSpaceSubdivision(const VssRayContainer &rays, 
													  const ObjectContainer &objects);

	SubdivisionCandidate *ResetViewSpaceSubdivision(const VssRayContainer &rays, 
													const ObjectContainer &objects,
													AxisAlignedBox3 *forcedViewSpace);


void EvaluateSubdivision(const VssRayContainer &sampleRays,											 
						const ObjectContainer &objects,
						const string &filename);

void ExportStats(const string &mergeStats, const ObjectContainer &objects, VspTree *oldVspTree);
protected:

	/** construction types
		sequential: construct first view space, then object space
		interleaved: construct view space and object space fully interleaved
		gradient: construct view space / object space until a threshold is reached
		multilevel: iterate until subdivisions converge to the optimum.
	*/
	enum {SEQUENTIAL, INTERLEAVED, GRADIENT, MULTILEVEL};

	/// type of hierarchy construction
	int mConstructionType;

	/// Type of object space partition
	int mObjectSpaceSubdivisionType;
	/// Type of view space partition
    int mViewSpaceSubdivisionType;

	/// the traversal queue
	SplitQueue mTQueue;
	
	////////////
	//-- helper variables
	
	// the original osp type
	int mSavedObjectSpaceSubdivisionType;
	// the original vsp type
	int mSavedViewSpaceSubdivisionType;
	/// the current subdivision candidate
	//SubdivisionCandidate *mCurrentCandidate;


	///////////////////
	// Hierarchies

	/// view space hierarchy
	VspTree *mVspTree;
	/// object space partition kd tree
	OspTree *mOspTree;

	public:
	/// bounding volume hierarchy
	BvHierarchy *mBvHierarchy;
	
protected:


	//////////
	//-- global termination criteria

	/// the mininal acceptable cost ratio for a split
	float mTermMinGlobalCostRatio;
	/// the threshold for global cost miss tolerance
	int mTermGlobalCostMissTolerance;
	/// maximum number of leaves
	int mTermMaxLeaves;
	/// Maximal allowed memory consumption.
	float mTermMaxMemory;


	////////////////////

	/// number of minimal steps of the same type
	int mMinStepsOfSameType;

	/// statistics about the hierarchy
	HierarchyStatistics mHierarchyStats;

	int mMinDepthForObjectSpaceSubdivion;
	int mMinDepthForViewSpaceSubdivion;
	
	//int mMinRenderCostDecrease;

	ofstream mSubdivisionStats;

	/// if the queue should be repaired after a subdivision steps
	bool mRepairQueue;

	bool mStartWithObjectSpace;
	/** if multi level construction method should be used
		where we iterate over both hierarchies until we
		converge to the optimum.
	*/
	bool mUseMultiLevelConstruction;

	/// number of iteration steps for multilevel approach	
	int mNumMultiLevels;

	/** if split plane should be recomputed for the repair.
		Otherwise only the priority is recomputed, the
		split plane itself stays the same
	*/
	bool mRecomputeSplitPlaneOnRepair;

	/** If memory should be considered during choosing
		of the next split type during gradient method.
	*/
	bool mConsiderMemory;

	/// constant value for driving the heuristics
	float mMemoryConst;
	
	bool mConsiderMemory2;

	int mTimeStamp;
	friend VspTree;
	friend OspTree;
	friend BvHierarchy;
	friend ViewCellsParseHandlers;

};

}

#endif