#ifndef _ViewCell_H__
#define _ViewCell_H__

#include "Mesh.h"
#include "Containers.h"
#include "Ray.h"
#include "Statistics.h"
//namespace GtpVisibilityPreprocessor {

struct Triangle3;

class BspInterior;
class BspPvs;
class BspLeaf;
class VspKdTree;
class VspKdLeaf;
class KdLeaf;
class ViewCellInterior;
class MergeCandidate;
class ViewCellsManager;

/** Statistics for a view cell partition.
*/

class ViewCellsStatistics: public StatisticsBase
{
public:

	/// number of view cells
	int viewCells;

	/// size of the PVS
	int pvs;

	/// largest PVS of all view cells
	int maxPvs;

	/// smallest PVS of all view cells
	int minPvs;

	/// view cells with empty PVS
	int emptyPvs;

	/// number of leaves covering the view space
	int leaves;

	/// largest number of leaves covered by one view cell
	int maxLeaves;

	int invalid;

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

	double AvgLeaves() const {return (double)leaves / (double)viewCells;};
	double AvgPvs() const {return (double)pvs / (double)viewCells;};

	void Reset()
	{
		viewCells = 0;
		pvs = 0;
		maxPvs = 0;

		minPvs = 999999;
		emptyPvs = 0;
		leaves = 0;
		maxLeaves = 0;
		invalid = 0;
	}

	void Print(ostream &app) const;

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


/**
	View cell with an optional mesh representation
*/


class ViewCell: public MeshInstance
{
public:
	ViewCell();

	/** Constructor taking a mesh representing the shape of	the viewcell.
	*/
	ViewCell(Mesh *mesh);

	/** Default destructor.
	*/
	virtual ~ViewCell() {}

	/** Returns Pvs.
	*/
	const ObjectPvs &GetPvs() const;
	ObjectPvs &GetPvs();

	int Type() const;

	void SetParent(ViewCellInterior *parent);

	/** Adds a passing ray to the passing ray container.
	*/
	void AddPassingRay(const Ray &ray, const int contributions);

	/** Returns volume of the view cell.
	*/
	float GetVolume() const;

	/** Returns area of the view cell.
	*/
	float GetArea() const;

	/** Sets the volume of the view cell.
	*/
	void SetVolume(float volume);
	
	/** Sets the area of the view cell.
	*/
	void SetArea(float area);

	/** Updates the view cell statstics for this particular view cell.
	*/
	virtual void UpdateViewCellsStats(ViewCellsStatistics &vcStat);

	/** if this view cell is the root of a view cell hierarchy
	*/
	bool IsRoot() const;

	/** Returns parent view cell.
	*/
	ViewCellInterior *GetParent() const;

	
	/** Sets the mesh for this view cell.
	*/
	void SetMesh(Mesh *mesh);

	void SetValid(const bool valid);
	bool GetValid() const;




	/// parent view cell in the view cell hierarchy
	ViewCellInterior *mParent;

	/// Rays piercing this view cell.
	RayContainer mPiercingRays;


	/** if this is a view cell correspending to a leaf in a hierarchy.
	*/
	virtual bool IsLeaf() const = 0;

  static bool SmallerPvs(const ViewCell *a,
						 const ViewCell *b) {
	return a->GetPvs().GetSize() < b->GetPvs().GetSize();
  }


	void SetTimeStamp(const int timeStamp);
	int GetTimeStamp() const;
	static void NewMail(const int reserve = 1) {
		sMailId += sReservedMailboxes;
		sReservedMailboxes = reserve;
	}
	void Mail() { mMailbox = sMailId; }
	bool Mailed() const { return mMailbox == sMailId; }

	void Mail(const int mailbox) { mMailbox = sMailId + mailbox; }
	bool Mailed(const int mailbox) const { return mMailbox == sMailId + mailbox; }

	int IncMail() { return ++mMailbox - sMailId; }


						 
	// last mail id -> warning not thread safe!
	// both mailId and mailbox should be unique for each thread!!!
	static int sMailId;
	static int sReservedMailboxes;
	

protected:

	/// the potentially visible objects
	ObjectPvs mPvs;

	float mVolume;
	float mArea;

	int mTimeStamp;

	bool mValid;
};


class ViewCellInterior: public ViewCell
{
public:
	ViewCellInterior();
	~ViewCellInterior();

	ViewCellInterior(Mesh *mesh);
	

	/** Sets pointer from parent to child and vice versa.
	*/
	void SetupChildLink(ViewCell *l);
	void RemoveChildLink(ViewCell *l);
	bool IsLeaf() const;

	ViewCellContainer mChildren;

};

/**
	View cell belonging to a hierarchy.
*/
template<typename T>
class ViewCellLeaf: public ViewCell
{
public:

	ViewCellLeaf<T>(): mLeaf(NULL) {}
	ViewCellLeaf<T>(Mesh *mesh):
		ViewCell(mesh), mLeaf(NULL) {}

	void UpdateViewCellsStats(ViewCellsStatistics &vcStat)
	{
		ViewCell::UpdateViewCellsStats(vcStat);

		//if ((int)mLeaves.size() > vcStat.maxLeaves)
		//	vcStat.maxLeaves = (int)mLeaves.size();
		//vcStat.leaves += (int)mLeaves.size();
	}

	bool IsLeaf() const
	{
		return true;
	}

	/// Leaf of some hierarchy which is part of this view cell.
	T mLeaf;
};


typedef ViewCellLeaf<BspLeaf *> BspViewCell;
typedef ViewCellLeaf<KdLeaf *> KdViewCell;
typedef ViewCellLeaf<VspKdLeaf *> VspKdViewCell;



class ViewCellsTree
{
public:
	ViewCellsTree(ViewCellsManager *vcm);
	~ViewCellsTree();

	/** Returns number of leaves this view cell consists of.
	*/
	int GetSize(ViewCell *vc) const;

	/** Collects leaves corresponding to a view cell.
	*/
	void CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const;

	/** Merges view cells according to some cost heuristics.
	*/
	int ConstructMergeTree(const VssRayContainer &rays, const ObjectContainer &objects);
	
	/** Refines view cells using shuffling, i.e., border leaves 
		of two view cells are exchanged if the resulting view cells
		are tested to be "better" than the old ones.
		@returns number of refined view cells
	*/
	int RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects);

	

	/** Returns optimal set of view cells for a given number of view cells.
	*/
	void CollectBestViewCellSet(ViewCellContainer &viewCells, const int numViewCells);

	/** Root of view cells tree.
	*/
	ViewCell *GetRoot() const;

	/** Returns pvs of view cell.
		@note pvs is returned per reference if tree is not compressed,
		per copy else.
	*/
	void GetPvs(ViewCell *vc, ObjectPvs &pvs) const;

	/** Returns pvs size of view cell.
	*/
	int GetPvsSize(ViewCell *vc) const;

	/** Returns actual number of object in this pvs and the children.
	*/
	int GetNumPvsEntries(ViewCell *vc) const;

	/** Returns memory cost of this view cell.
	*/
	float GetMemoryCost(ViewCell *vc) const;

	/** Compresses the pvs of the view cells from the root.
	*/
	void CompressViewCellsPvs();

	/** If view cells in this tree have compressed pvs.
	*/
	bool IsCompressed() const;

protected:


	//////////////////////////////////////////////////////////////
	//                 merge options                            //
	//////////////////////////////////////////////////////////////
	

	/** Returns cost of this leaf according to current heuristics.
	*/
	float GetCostHeuristics(ViewCell *vc) const;

	/** Returns cost of leaf.
	*/
	float GetRenderCost(ViewCell *vc) const;

	/** Evaluates the merge cost of this merge candidate pair.
	*/
	void EvalMergeCost(MergeCandidate &mc) const;

	/** Variance of leaf.
	*/
	float GetVariance(ViewCell *vc) const;

	/** Standard deviation of leaf.
	*/
	float GetDeviation(ViewCell *vc) const;

	/** Tries to set this merge candidate to valid. 
		@returns false if both view cells are the same
	*/
	bool ValidateMergeCandidate(MergeCandidate &mc) const;

	/** Merge view cells of leaves l1 and l2.
		@returns difference in pvs size
	*/
	ViewCellInterior *MergeViewCells(ViewCell *l, ViewCell *r, int &pvsDiff); //const;

	/** Shuffles, i.e. takes border leaf from view cell 1 and adds it 
		to view cell 2.
	*/
	void ShuffleLeaf(ViewCell *leaf, ViewCellInterior *vc1, ViewCellInterior *vc2) const;	
		
	/** Shuffles the leaves, i.e., tests if exchanging
		the leaves helps in improving the view cells.
	*/
	bool ShuffleLeaves(MergeCandidate &mc) const;

	/** Calculates cost for merge of view cell 1 and 2.
	*/
	float EvalShuffleCost(ViewCell *leaf, 
						  ViewCellInterior *vc1, 
						  ViewCellInterior *vc2) const;

	/** Exports a snapshot of the merged view cells to disc.
	*/
	void ExportMergedViewCells(ViewCellContainer &viewCells, 
							   const ObjectContainer &objects,
							   const int numNewViewCells);

	/** merge queue must be reset after some time because expected value
		may not be valid.
	*/
	void ResetMergeQueue();

	/** Updates the current top level of view cells.
		@returns number of newly merged view cells
	*/
	int UpdateActiveViewCells(ViewCellContainer &viewCells);

	void PropagateUpVisibility(ViewCellInterior *interior);

	void CompressViewCellsPvs(ViewCell *root);

	/** Returns memory usage of view cells.
	*/
	float GetMemUsage() const;


	/// if the view cell tree hold compressed pvs
	bool mIsCompressed;

	ViewCellsManager *mViewCellsManager;
	ViewCell *mRoot;

	/// if merge visualization should be shown
	bool mExportMergedViewCells;

	
		
	ViewCellContainer mMergedViewCells;
	

	bool mRefineViewCells;

	/// weights between variance and render cost increase (must be between zero and one)
	float mRenderCostWeight;

	/// overall cost used to normalize cost ratio
	float mOverallCost;
	float mExpectedCost;
    float mDeviation;
	float mAvgRenderCost;

	int mUseAreaForPvs;

	int mNumActiveViewCells;

	/// minimal number of view cells
	int mMergeMinViewCells;
	/// maximal cost ratio for the merge
	float mMergeMaxCostRatio;

	ofstream mStats;

	typedef priority_queue<MergeCandidate> MergeQueue;

	MergeQueue mMergeQueue;

	float mMaxMemory;

};


/**
	Candidate for leaf merging based on priority.
*/
class MergeCandidate
{  
	friend class ViewCellsTree;

public:

	MergeCandidate(ViewCell *l, ViewCell *r);

	/** If this merge pair is still valid.
	*/
	bool IsValid() const;

	
	friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb)
	{
		return leafb.GetMergeCost() < leafa.GetMergeCost();
	}

	void SetLeftViewCell(ViewCell *l);
	void SetRightViewCell(ViewCell *l);

	ViewCell *GetLeftViewCell() const;
	ViewCell *GetRightViewCell() const;

	ViewCell *GetInitialLeftViewCell() const;
	ViewCell *GetInitialRightViewCell() const;

	/** Returns the increase of the standard deviation of this merge candidate.
	*/
	float GetDeviationIncr() const;

	/** Merge cost of this candidate pair.
	*/
	float GetMergeCost() const;

	/** Render cost of this candidate.
	*/
	float GetRenderCost() const;
	
	static float sRenderCostWeight;

protected:

	/// render cost increase by this merge
	float mRenderCost;
	/// increase / decrease of standard deviation
	float mDeviationIncr;

	ViewCell *mLeftViewCell;
	ViewCell *mRightViewCell;

	ViewCell *mInitialLeftViewCell;
	ViewCell *mInitialRightViewCell;
};


class MergeStatistics: public StatisticsBase
{
public:
	
	int merged;
	int siblings;
	int candidates;
	int nodes;

	int accTreeDist;
	int maxTreeDist;
	
	Real collectTime;
	Real mergeTime;

	Real overallCost;

	Real expectedRenderCost;
	Real deviation;
	Real heuristics;

	// Constructor
	MergeStatistics() 
	{
		Reset();
	}
	
	double AvgTreeDist() const {return (double)accTreeDist / (double)merged;}; 

	void Reset() 
	{
		nodes = 0;
		merged = 0;
		siblings = 0;
		candidates = 0;
	
		accTreeDist = 0;
		maxTreeDist = 0;

		collectTime = 0;
		mergeTime = 0;
		overallCost = 0;

		expectedRenderCost = 0;
		deviation = 0;
		heuristics = 0;

	}

	void Print(ostream &app) const;

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

#endif