#ifndef _ViewCell_H__
#define _ViewCell_H__

#include "Mesh.h"
#include "Containers.h"
#include "Ray.h"
#include "Statistics.h"
#include "Material.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 pvsSize;

	/// 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)pvsSize / (double)viewCells;};

	void Reset()
	{
		viewCells = 0;
		pvsSize = 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
{
	friend class ViewCellsTree;
	friend class ViewCellsManager;
	friend class VspBspViewCellsManager;
	friend class BspViewCellsManager;
	friend class VspBspTree;
	friend class FromPointVisibilityTree;
	friend class BspTree;


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

	/** Type of view cells.
	*/
	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);


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

	/** Returns estimated render cost of this view cell.
	*/
	float GetRenderCost() const;

	/** set color for visiualizations.
	*/
	void SetColor(const RgbColor &color);

	/** get color for visualuzations.
	*/
    RgbColor GetColor() 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();
  }

 static bool SmallerRenderCost(const ViewCell *a, const ViewCell *b) 
 {
	 return a->GetRenderCost() < b->GetRenderCost();
 }

 static bool LargerRenderCost(const ViewCell *a, const ViewCell *b) 
 {
	 return a->GetRenderCost() > b->GetRenderCost();
 }

	void SetMergeCost(const float mergeCost);
	float GetMergeCost() 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; }


	/** Sets this view cell to be an active view cell.
	*/
	void SetActive();
	/** Returns if this view cell is active.
	*/
	bool IsActive() const;


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

	static int sLastUpdated;
	
protected:

	/// the potentially visible objects
	ObjectPvs mPvs;

	float mVolume;
	float mArea;

	float mMergeCost;

	bool mValid;

	int mLastUpdated;
	bool mIsActive;
	/** color used for consistent visualization */
	RgbColor mColor;

	
	/// pvs size, used for lazy pvs computation
	int mPvsSize;
	bool mPvsSizeValid;

};


class ViewCellInterior: public ViewCell
{
	friend class ViewCellsManager;
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;

  void SetCost(const float c) {
	mCost = c;
  }
  float GetCost() const {
	return mCost;
  }
  
protected:
  /** overall cost resulting from the merge */
  float mCost;
};

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

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

	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
{
	friend class ViewCellsManager;


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

	/** Returns number of leaves this view cell consists of.
	*/
	int GetNumInitialViewCells(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);
	
	/** Assign colors to the viewcells so that they can be renderered interactively without
	  color flickering.
	  */
	void AssignRandomColors();

	/** Updates view cell stats for this particular view cell
	*/
	void UpdateViewCellsStats(ViewCell *vc, ViewCellsStatistics &vcStat);


	/** Get costs resulting from each merge step. */
	void GetCostFunction(vector<float> &costFunction);

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

	/** Sets method of storage for view cells.
	*/
	void SetViewCellsStorage(int type);

	/** pvs storage methods */
	enum {PVS_IN_INTERIORS, COMPRESSED, PVS_IN_LEAVES};

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

	/** Returns active view cell that is in the path of this view cell.
	*/
	ViewCell *GetActiveViewCell(ViewCell *vc) const;

	/** Sets the leaves to be the currently active view cells.
	*/
    void SetActiveSetToLeaves();

	/** Propagates pvs up the tree to the root and downwards the tree.
	*/
	void PropagatePvs(ViewCell *vc);

	bool Export(ofstream &stream);

	/** Export statistics of this view cell tree.
	*/
	void ExportStats(const string &mergeStats);

	/** Sets root of hierarchy.
	*/
	void SetRoot(ViewCell *root);

	//float ComputeVolume(ViewCell *vc);

	/** Assignes unique ids to view cells.
	*/
	void CreateUniqueViewCellsIds();

	/** Resets pvs of whole tree.
	*/
	void ResetPvs();

protected:


	//////////////////////////////////////////////////////////////
	//                 merge related stuff                      //
	//////////////////////////////////////////////////////////////

	/** Computes render cost of the merged pvs.
	*/
	float ComputeMergedPvsCost(const ObjectPvs &pvs1, const ObjectPvs &pvs2) const;

	/** 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 PullUpVisibility(ViewCellInterior *interior);

	void CompressViewCellsPvs(ViewCell *root);

	/** Returns memory usage of view cells.
	*/
	float GetMemUsage() const;
	
	/**
		Exports single view cell.
		NOTE: should be in exporter!!
	*/
	void ExportViewCell(ViewCell *viewCell, ofstream &stream);



	/// if the view cell tree hold compressed pvs
	int mViewCellsStorage;

	ViewCellsManager *mViewCellsManager;
	ViewCell *mRoot;

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

	
	/** intermediate container of merged view cells.
*/
	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;

	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;

	/** Returns leaf view cell initially associated with this merge candidate.
	*/
	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