#ifndef _VspBspTree_H__
#define _VspBspTree_H__

#include "Mesh.h"
#include "Containers.h"
#include "Polygon3.h"
#include <stack>
#include "Statistics.h"
#include "VssRay.h"
#include "RayInfo.h"
#include "ViewCellBsp.h"

class ViewCell;
//class BspViewCell;
class Plane3;
class VspBspTree;  
class BspInterior;
class BspNode;
class AxisAlignedBox3;
class Ray;
class ViewCellsStatistics;
class ViewCellsManager;
class MergeCandidate;
class Beam;
class ViewCellsTree;


struct BspRay;


/**
    BspNode abstract class serving for interior and leaf node implementation
*/
class BspNode 
{
	friend class BspTree;

public:
	BspNode();
	virtual ~BspNode(){};
	BspNode(BspInterior *parent);

	/** Determines whether this node is a leaf or not
	@return true if leaf
	*/
	virtual bool IsLeaf() const = 0;

	/** Determines whether this node is a root
	@return true if root
	*/
	virtual bool IsRoot() const;

	/** Returns parent node.
	*/
	BspInterior *GetParent();

	/** Sets parent node.
	*/
	void SetParent(BspInterior *parent);

	/** Returns true if this node is a sibling of node n.
	*/
	bool IsSibling(BspNode *n) const;

	/** returns depth of the node.
	*/
	int GetDepth() const;

	/** returns true if the whole subtree is valid
	*/
	bool TreeValid() const;

	void SetTreeValid(const bool v);

	//-- mailing options

	void Mail() { mMailbox = sMailId; }
	static void NewMail() { ++ sMailId; }
	bool Mailed() const { return mMailbox == sMailId; }

	static int sMailId;
	int mMailbox;

	int mTimeStamp;

protected:

	/// if this sub tree is a completely valid view space region
	bool mTreeValid;
	/// parent of this node
	BspInterior *mParent;
};

/** BSP interior node implementation 
*/
class BspInterior: public BspNode 
{
	friend class BspTree;
public:
	/** Standard contructor taking split plane as argument.
	*/
	BspInterior(const Plane3 &plane);
	~BspInterior();
	/** @return false since it is an interior node 
	*/
	bool IsLeaf() const;

	BspNode *GetBack();
	BspNode *GetFront();

	/** Returns split plane.
	*/
	Plane3 GetPlane() const;

	/** Replace front or back child with new child.
	*/
	void ReplaceChildLink(BspNode *oldChild, BspNode *newChild);
	/** Replace front and back child.
	*/
	void SetupChildLinks(BspNode *b, BspNode *f);

	friend ostream &operator<<(ostream &s, const BspInterior &A)
	{
		return s << A.mPlane;
	}

protected:

	/// Splitting plane corresponding to this node
	Plane3 mPlane;

	/// back node
	BspNode *mBack;
	/// front node
	BspNode *mFront;
};

/** BSP leaf node implementation.
*/
class BspLeaf: public BspNode 
{
	friend class BspTree;

public:
	BspLeaf();
	BspLeaf(ViewCell *viewCell);
	BspLeaf(BspInterior *parent);
	BspLeaf(BspInterior *parent, ViewCell *viewCell);

	~BspLeaf();

	/** @return true since it is an interior node 
	*/
	bool IsLeaf() const;
	
	/** Returns pointer of view cell.
	*/
	ViewCell *GetViewCell() const;

	/** Sets pointer to view cell.
	*/
	void SetViewCell(ViewCell *viewCell);

	/// Rays piercing this leaf.
	VssRayContainer mVssRays;
	
	/// leaf pvs
	ObjectPvs *mPvs;

	/// Probability that the view point lies in this leaf
	float mProbability;

protected:
	
	/// if NULL this does not correspond to feasible viewcell
	ViewCell *mViewCell;
};

/**
	This bsp tree spatially organizes the view cells.  
*/
class ViewCellBspTree 
{
public:		
	/** Default constructor creating an empty tree.
	*/ 
	VspBspTree();

	/** Default destructor.
	*/
	~VspBspTree();

	/** Returns list of BSP leaves with pvs smaller than
		a certain threshold.
		@param onlyUnmailed if only the unmailed leaves should be considered
		@param maxPvs the maximal pvs (-1 means unlimited)
	*/
	void CollectLeaves(vector<BspLeaf *> &leaves, 
					   const bool onlyUnmailed = false,
					   const int maxPvs = -1) const;

	/** Returns box which bounds the whole tree.
	*/
	AxisAlignedBox3 GetBoundingBox() const;

	/** Returns root of BSP tree.
	*/
	BspNode *GetRoot() const;

	/** Collects the leaf view cells of the tree
		@param viewCells returns the view cells 
	*/
	void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const;

	/** A ray is cast possible intersecting the tree.
		@param the ray that is cast.
		@returns the number of intersections with objects stored in the tree.
	*/
	int CastRay(Ray &ray);

	/** finds neighbouring leaves of this tree node.
	*/
	int FindNeighbors(BspNode *n, 
					  vector<BspLeaf *> &neighbors, 
					  const bool onlyUnmailed) const;

	/** Constructs geometry associated with the half space intersections 
		leading to this node.
	*/
	void ConstructGeometry(BspNode *n, BspNodeGeometry &geom) const;
	
	/** Construct geometry of view cell.
	*/
	void ConstructGeometry(ViewCell *vc, BspNodeGeometry &geom) const;

	/** Returns random leaf of BSP tree.
		@param halfspace defines the halfspace from which the leaf is taken.
	*/
	BspLeaf *GetRandomLeaf(const Plane3 &halfspace);

	/** Returns random leaf of BSP tree.
		@param onlyUnmailed if only unmailed leaves should be returned.
	*/
	BspLeaf *GetRandomLeaf(const bool onlyUnmailed = false);

	/** Casts line segment into the tree.
		@param origin the origin of the line segment
		@param termination the end point of the line segment
		@returns view cells intersecting the line segment.
	*/
    int CastLineSegment(const Vector3 &origin,
						const Vector3 &termination,
						ViewCellContainer &viewcells);

	/** Returns view cell the current point is located in.
	*/
	ViewCell *GetViewCell(const Vector3 &point);


	/** Returns true if this view point is in a valid view space,
		false otherwise.
	*/
	bool ViewPointValid(const Vector3 &viewPoint) const;

	/** Returns view cell corresponding to 
		the invalid view space.
	*/
	BspViewCell *GetOutOfBoundsCell();



protected:

	
	
	/// Pointer to the root of the tree
	BspNode *mRoot;
		
};




#endif