#ifndef _ViewCellBsp_H__
#define _ViewCellBsp_H__

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

class ViewCell;
class Plane3;
//class Mesh;

//namespace GtpVisibilityPreprocessor {
class BspTree;  
class BspInterior;
class Polygon3;

/** Queue storing a soup of polygons used during BSP tree construction
*/
typedef std::queue<Polygon3 *> PolygonQueue;

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(PolygonQueue *polys, PolygonQueue *frontPolys, PolygonQueue *backPolys, int &splits);

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
		PolygonQueue *mPolygons;
		/// current depth
		int mDepth;
		
		BspTraversalData() {}
		
		BspTraversalData(BspNode *node, BspInterior *parent, PolygonQueue *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);


protected:
	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.
	*/
	void Subdivide(BspTraversalStack &tStack, BspTraversalData &tData, ViewCell *viewCell = NULL);

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

	/** 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, 
							PolygonQueue *polys, const int depth, 
							ViewCell *viewCell,
							PolygonQueue *frontPolys, PolygonQueue *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, PolygonQueue *polys, 
						PolygonQueue *frontPolys, PolygonQueue *backPolys);

	/** Extracts the meshes of the objects and copies them into the mesh.
	*/
	static void Copy2PolygonSoup(const ObjectContainer &objects, PolygonQueue &polys);

	/** copy this mesh into polygons.
	*/
	static void CopyMesh2Polygons(Mesh *mesh, PolygonQueue &polys);

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

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

//}; // GtpVisibilityPreprocessor

#endif