#ifndef _ViewCell_H__
#define _ViewCell_H__

#include "Mesh.h"
#include "Containers.h"
#include "Ray.h"
#include "Statistics.h"
#include "Material.h"
#include "gzstream.h"


namespace GtpVisibilityPreprocessor {

struct Triangle3;

class BspInterior;
class BspPvs;
class BspLeaf;
class VspLeaf;
class KdLeaf;
class ViewCellInterior;
class MergeCandidate;
class ViewCellsManager;
class ViewCellLeaf;
//class Environment;


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

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;

	/** Returns pvs.
	*/
	ObjectPvs &GetPvs();

	/** Completely substitutes the pvs.
	*/
	void SetPvs(const ObjectPvs &pvs);

	/** Type of view cells.
	*/
	int Type() const;

	
	/** 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 parent of this view cell.
	*/
	void SetParent(ViewCellInterior *parent);


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

	/** Sets this view cell to be a valid view cell according to some criteria.
	*/
	void SetValid(const bool valid);
	/** Returns true if this view cell is considered to be valid according to
		some criteria.
	*/
	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;

	/** Adds a sample to the pvs.
		@param sample the sample to be added
		@param pdf a continuos measure of visibility
		@param contribution returns the contribution of this sample to the pvs
	*/
	bool AddPvsSample(Intersectable *sample, const float pdf, float &contribution);
  


	/// 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) 
	{
		// HACK: take scalar value because pvs may not have been stored properly
#if 1
		return a->mPvsSize < b->mPvsSize;
#else
		return a->GetPvs().GetSize() < b->GetPvs().GetSize();
#endif
	}

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

	/** Sets merge cost used for merging this view cell from other cells. 
		@hack The function is available for leaves also to have a common interface,
		but it should be less than zero for leaves.
		*/
	void SetMergeCost(const float mergeCost);

	/** Returns merge cost needed to merge this leaf from other cells.
		@hack The function is available for leaves also to have a common interface,
		but it should be less than zero for leaves.
	*/
	float GetMergeCost() const;



	////////////////////////////////////////////
	//       mailing stuff


	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:

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

	/// the potentially visible objects
	ObjectPvs mPvs;

	float mVolume;
	float mArea;

	float mMergeCost;

	bool mValid;

	/// color used for consistent visualization
	RgbColor mColor;

	
	/// store pvs size, used for evaluation purpose when pvss are stored only in the leaves
	int mPvsSize;
	/// if the pvs size scalar is up to date and corresponding to the real pvs size
	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;
};


/**
	Leaf of the view cell.
*/
class ViewCellLeaf: public ViewCell
{
public:
	ViewCellLeaf()  {  mActiveViewCell = this; }
	ViewCellLeaf(Mesh *mesh):
	ViewCell(mesh) { mActiveViewCell = this; }

	bool IsLeaf() const
	{
		return true;
	}

	/** Returns if this view cell is active.
	*/
	ViewCell *GetActiveViewCell() const 
	{ return mActiveViewCell; }

	/** Sets this view cell to be an active view cell.
	*/
	void SetActiveViewCell(ViewCell *vc)
	{ mActiveViewCell = vc;}

	
	/** points to the currently active view cell. This is the
		view cell representing the current brach.
	*/
	ViewCell *mActiveViewCell;
};

/**
	Leaf of the view cell hierarchy corresponding to a leaf in a spatial hierarchy.
*/
template<typename T>
class HierarchyLeafViewCell: public ViewCellLeaf
{
public:

	HierarchyLeafViewCell<T>(): ViewCellLeaf() {  }
	HierarchyLeafViewCell<T>(Mesh *mesh):
	ViewCellLeaf(mesh) {  }
		

	bool IsLeaf() const
	{
		return true;
	}


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


typedef HierarchyLeafViewCell<VspLeaf *> VspViewCell;
typedef HierarchyLeafViewCell<BspLeaf *> BspViewCell;
typedef HierarchyLeafViewCell<KdLeaf *> KdViewCell;




class ViewCellsTree
{
	friend class ViewCellsManager;


public:
	/** View cells tree constructor taking a view cell mnanager as parameter
	*/
	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(ViewCellLeaf *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);

	/** Exports view cells to file.
	*/
#if ZIPPED_VIEWCELLS
	bool Export(ogzstream &stream, const bool exportPvs = false);
#else
	bool Export(ofstream &stream, const bool exportPvs = false);
#endif

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

	/** Helper function pullling pvs as high up in the tree as possible.
	*/ 
	void PullUpVisibility(ViewCellInterior *interior);

	/** Compress pvs of view cell and children.
	*/
	void CompressViewCellsPvs(ViewCell *root);

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

	/**	Exports single view cell.
		NOTE: should be in exporter!!
	*/
#if ZIPPED_VIEWCELLS
	void ExportViewCell(ViewCell *viewCell, ogzstream &stream, const bool exportPvs);
#else
	void ExportViewCell(ViewCell *viewCell, ofstream &stream, const bool exportPvs);	
#endif

	/** Exports pvs of a view cell.
	*/
#if ZIPPED_VIEWCELLS
	void ExportPvs(ViewCell *viewCell, ogzstream &stream);
#else
	void ExportPvs(ViewCell *viewCell, ofstream &stream);
#endif


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

	/// if merged view cells are refined.
	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;
	/// the area is used for pvs heuristics
	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;

	int mMaxMergesPerPass;
	float mAvgCostMaxDeviation;
};


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