#ifndef _ViewCellBsp_H__
#define _ViewCellBsp_H__

#include "Mesh.h"
#include "Containers.h"
#include <stack>

class ViewCell;
class Plane3;
//class Mesh;
class BspTree;  
class BspInterior;
class Polygon3;
class AxisAlignedBox3;


//namespace GtpVisibilityPreprocessor {

/** Container storing a soup of polygons used during BSP tree construction
*/
typedef std::vector<Polygon3 *> PolygonContainer;

struct BspRayTraversalData 
{
    BspNode *mNode;
    Vector3 mExitPoint;
    float mMaxT;
    
    BspRayTraversalData() {}

    BspRayTraversalData(BspNode *n, const Vector3 &p, const float maxt):
    mNode(n), mExitPoint(p), mMaxT(maxt) 
	{}
};

class BspTreeStatistics // TODO: should have common superclass with KdTreeStatistics
{
public:
  // total number of nodes
  int nodes;
  // number of splits
  int splits;
  // totals number of rays
  int rays;
  // maximal reached depth
  int maxDepth;
  // total number of query domains
  int queryDomains;
  // total number of ray references
  int rayRefs;
  // refs in non empty leafs
  int rayRefsNonZeroQuery;
  // total number of query references
  int objectRefs;
  // nodes with zero queries
  int zeroQueryNodes;
  // max depth nodes
  int maxDepthNodes;
  // max number of rays per node
  int maxObjectRefs;
  // number of dynamically added ray refs
  int addedRayRefs;
  // number of dynamically removed ray refs
  int removedRayRefs;
  
  // Constructor
  BspTreeStatistics() 
  {
	  Reset();
  }

  int Nodes() const {return nodes;}
  int Interior() const { return nodes/2; }
  int Leaves() const { return (nodes/2) + 1; }

  void Reset() 
  {
	  nodes = 0;
	  splits = 0;
	  rays = queryDomains = 0;
	  rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
	  zeroQueryNodes = 0;
      maxDepthNodes = 0;
      //minCostNodes = 0;
	  maxObjectRefs = 0;
	  addedRayRefs = removedRayRefs = 0;
  }

  void
  Print(ostream &app) const;

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

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

public:
	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);

protected:

	/// parent of this node
	BspInterior *mParent;
};

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

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

	Plane3 *GetPlane();

	void ReplaceChildLink(BspNode *oldChild, BspNode *newChild);
	void SetupChildLinks(BspNode *b, BspNode *f);

	/** Splits polygons.
		@param polys the polygons to be split
		@param frontPolys returns the polygons in the front of the split plane
		@param backPolys returns the polygons in the back of the split plane
		@param splits number of splits
	*/
	void SplitPolygons(PolygonContainer *polys, PolygonContainer *frontPolys, 
					   PolygonContainer *backPolys, int &splits);

	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 
{
public:
	BspLeaf(ViewCell *viewCell = NULL);

	/** @return true since it is an interior node */
	bool IsLeaf() const;
	ViewCell *GetViewCell();

protected:

	/// polygonal representation of this viewcell
	/// if NULL this note does not correspond to feasible viewcell
	ViewCell *mViewCell;
};


/** Implementation of the ViewCell BSP tree. */
class BspTree 
{
public:
	 	
	/** Additional data which is passed down the BSP tree during traversal.
	*/
	struct BspTraversalData
	{  
		/// the current node
		BspNode *mNode;
		/// parent of current node
		BspInterior *mParent;
		/// polygonal data for splitting
		PolygonContainer *mPolygons;
		/// current depth
		int mDepth;
		
		BspTraversalData() {}
		
		BspTraversalData(BspNode *node, BspInterior *parent, PolygonContainer *polys, const int depth): 
		mNode(node), mParent(parent), mPolygons(polys), mDepth(depth) {}
    };

	typedef std::stack<BspTraversalData> BspTraversalStack;

	/// BSP tree construction type
	enum {VIEWCELLS, SCENE_GEOMETRY};

	/** Default constructor creating an empty tree.
	*/ 
	BspTree();

	~BspTree();

	const BspTreeStatistics &GetStatistics() const; 
  
	/** Constructs tree using the given list of viewcells.
	    A pointer to the appropriate viewcell is stored within each leaf. 
		Many leafs can point to the same viewcell.
	*/
	void Construct(const ViewCellContainer &viewCells);
	/** Constructs tree using the given list of objects. Each leaf is taken as viewcell.
	    No objects are treated as viewcells explicitly.

		@param objects list of objects
	*/
	void Construct(const ObjectContainer &objects);

	int CollectLeafPvs();

	void CollectLeaves(vector<BspLeaf *> &leaves);

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

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

protected:
	
	/** Evaluates plane classification with respect to the plane's 
		contribution for a balanced tree.
	*/
	static inline int EvalForBalancedTree(const int classficiation);
	/** Evaluates plane classification with respect to the plane's 
		contribution for a minimum number splits in the tree.
	*/
	static inline int EvalForLeastSplits(const int classification);

	/** Evaluates the contribution of the candidate split plane.
	*/
	int EvalSplitPlane(PolygonContainer *polygons, const Plane3 &candidatePlane) const;

	/** Evaluates tree stats in the BSP tree leafs.
	*/
	void EvaluateLeafStats(const BspTraversalData &data);

	/** Subdivides node with respect to the traversal data.
	    @param tStack current traversal stack
		@param tData traversal data also holding node to be subdivided
		@param viewCell the view cell that will be represented with this part of the Bsp tree.
		@returns new root of the subtree
	*/
	BspNode *Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCell *viewCell = NULL);

	/** Selects a splitting plane. 
		@param polygons the polygon data on which the split decition is based
	*/
	Plane3 SelectPlane(PolygonContainer *polygons) const;

	/** Filters next viewcell down the tree and inserts it into the appropriate leaves
		(i.e., possibly more than one leaf).
	*/
	void InsertViewCell(ViewCell *viewCell);
	
	/** Subdivide leaf.
		@param leaf the leaf to be subdivided
		@param parent the parent node of this leaf
		@param polys the input polygons
		@param depth the current tree depth
		@param frontPolys the polygons of the front child node as a result from splitting
		@param backPolys the polygons of the back child node as a result from splitting
	*/
	BspNode *SubdivideNode(BspLeaf *leaf, BspInterior *parent, 
							PolygonContainer *polys, const int depth, 
							ViewCell *viewCell,
							PolygonContainer *frontPolys, PolygonContainer *backPolys);

	/** Filters polygons down the tree.
		@param node the current BSP node
		@param polys the polygons to be filtered
		@param frontPolys returns the polygons in front of the split plane
		@param backPolys returns the polygons in the back of the split plane
	*/
	void FilterPolygons(BspInterior *node, PolygonContainer *polys, 
						PolygonContainer *frontPolys, PolygonContainer *backPolys);

	/** Selects the split plane in order to get a balanced tree.
		@param polygons container of polygons
		@param maxTests the maximal number of candidate tests
	*/
	Plane3 SelectPlaneHeuristics(PolygonContainer *polygons, int maxTests) const;

	/** Extracts the meshes of the objects and copies them into the mesh. Also calculcates the bounding box of the tree.
		@param maxPolys the maximal number of objects to be stored as polygons
	*/
	void Copy2PolygonSoup(const ObjectContainer &objects, PolygonContainer &polys, int maxObjects);

	/** Add this mesh as polygons to polygon container.
	*/
	void AddMesh2Polygons(Mesh *mesh, PolygonContainer &polys);

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

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

	/// Pointer to the root cell of the viewspace
	// ViewCell *mRootCell;
		
	BspTreeStatistics mStat;

	/// local maximal polygons (changes depending on method)
	int mTermMaxPolygons;
	int mTermMaxDepth;

	/// Strategies for choosing next split plane.
	enum {NEXT_POLYGON, LEAST_SPLITS, BALANCED_TREE, COMBINED};

	/// box around the whole view domain
	AxisAlignedBox3 mBox;

public:
	/// Parses the environment and stores the global BSP tree parameters
	static void ParseEnvironment();

	/// maximal number of polygons where tree construction is terminated
	static int sTermMaxPolygons;
	/// maximal possible depth
	static int sTermMaxDepth;
	/// strategy to get the best split plane
	static int sSplitPlaneStrategy;
	/// number of candidates evaluated for the next split plane
	static int sMaxCandidates;
};

//}; // GtpVisibilityPreprocessor

#endif