#ifndef _GtpVisibilityHierarchyInterface_H__
#define _GtpVisibilityHierarchyInterface_H__

#include "DistanceQueue.h"
#include "VisibilityMesh.h"
#include <stack>

namespace GtpVisibility {

enum  CullingType {QUERY_CULLED, FRUSTUM_CULLED};

typedef std::vector<HierarchyNode *> NodeVector;
typedef std::vector<GtpVisibility::Mesh *> GeometryVector;
typedef std::vector<GtpVisibility::Patch *> PatchVector;
typedef std::pair<HierarchyNode *, OcclusionQuery *> QueryPair;
typedef std::pair<HierarchyNode *, bool> PendingQuery;
typedef std::queue<QueryPair> QueryQueue;
typedef std::queue<PendingQuery> PendingQueue;


/**	Class which implements a hierarchy interface for a scene hierarchy. It has to be implemented
	for any rendering engine to use the CHC algorithm.
*/
class HierarchyInterface
{
public:
	/** Default constructor.
	*/
	HierarchyInterface();
	virtual ~HierarchyInterface();
	/** Returns true if current node is leaf of the hierarchy. 
		@param node hierarchy node
		@returns true if node is leaf
	*/
    virtual bool IsLeaf(HierarchyNode *node) const = 0;
	/** Traverses and renders the hierarchy from the given node. 
		@param node the hierarchy node
	*/
	virtual void TraverseNode(HierarchyNode *node) = 0;
	/** Renders the given hierarchy node.
		@param node current hierarchy node to be rendered
	*/
	virtual void RenderNode(HierarchyNode *node) = 0;
	/** Pulls up the visibility from the current node recursively to the parent nodes. 
		@param node the current node 
	*/
	virtual void PullUpVisibility(HierarchyNode *node) const = 0;
	/** Issue a occlusion query for this node. 
		@param node the current hierarchy node
		@param wasVisible if the node was visible in the last frame: based
		on this the method can decide on the way of querying
		@returns occlusion query for this node
	*/
	virtual OcclusionQuery *IssueNodeOcclusionQuery(HierarchyNode *node, 
													const bool wasVisible = false) = 0;
	/** Sets the root of the scene hierarchy.
		@param root the hierarchy root
	*/
	void SetHierarchyRoot(HierarchyNode *root);
    /** Get the root of the scene hierarchy.
		@return the hierarchy root
	*/
	HierarchyNode *GetHierarchyRoot() const;
	/** Sets the scene root and initialises this hierarchy interface for a traversal.		
		@remark also resets the statistics evaluated in the last traversal
	*/
	void InitTraversal();
	/** Returns current frame id.
		@returns frame id
	*/
	unsigned int GetFrameId() const;
	/** Returns a pointer to the distance queue.
		@returns current distance queue.
		@remark the distance queue stores hierarchy nodes in a front-to-back order
	*/
	DistanceQueue *GetQueue();
	
	/** Returns distance of the node to the view plane.
		@param node the hierarchy node
	*/			
	virtual float GetSquaredDistance(HierarchyNode *node) const = 0;
	/** Checks if the node is visible from the current view frustum.
		@param node the current node
		@param intersects returns true if the current node intersects the near plane
	*/
	virtual bool CheckFrustumVisible(HierarchyNode *node, 
									 bool &intersects) = 0;
	/** Checks if the node is visible from the current view frustum.
		@param node the current node
	*/
	bool CheckFrustumVisible(HierarchyNode *node);
	/** Returns next available occlusion query or creates new one.
		@return the next occlusion query
	*/
	virtual OcclusionQuery *GetNextOcclusionQuery() = 0;
	/** Returns true if there is renderable geometry attached to this node
		@param node the current node
		@returns if the node has renderable geometry
	*/
    virtual bool HasGeometry(HierarchyNode *node) const = 0;
	/** Sets the visible flag for this node.
		@param node the current node
		@param visible the visible flag
	*/
	virtual void SetNodeVisible(HierarchyNode *node, 
								const bool visible) const = 0;
	/** Returns true if node has the visible flag set. See set
	*/
	virtual bool IsNodeVisible(HierarchyNode *node) const = 0;
	/** Sets the last visited frame id for this node.
		@param node the current node
		@param frameId the current frame id
	*/
	virtual void SetLastVisited(HierarchyNode *node, 
								const unsigned int frameId) const = 0;
	/** Returns frame id when this node was last visited by the traverser. See set
	*/
	virtual unsigned int LastVisited(HierarchyNode *node) const = 0;
	/** Returns number of traversed nodes.
	*/
	unsigned int GetNumTraversedNodes();
	/** Returns number of rendered nodes.
	*/
	unsigned int GetNumRenderedNodes();
		
	//bool mIsShadowPass;

	/** Visualization of a culled node, dependent on the culling type. 
		@param node the hierarchy node to be visualized
		@param type can be one of FRUSTUM_CULLED, QUERY_CULLED
	*/
	virtual void VisualizeCulledNode(HierarchyNode *node, 
									 CullingType type) const = 0;

	/** Returns vector of visible hierarchy nodes from previous render.
	*/
	std::vector<HierarchyNode *> *GetVisibleNodes();
	/** Returns vector of previoulsy rendered geometry.
	*/
	
	/** Returns the geometry of a given hierarchy node. 
		@param node the hierarchy node containing the geometry
		@param geometryList geometry is returned in this list
		@param includeChildren if the geometry of the children should be taken into account
	*/
	virtual void GetNodeGeometryList(GtpVisibility::HierarchyNode *node,	
					 				 GeometryVector *geometryList, 
									 bool includeChildren) = 0;

	
	/** This is an optimization when issuing the occlusion test. 
		The test is done with actual geometry rather than the bounding 
		box of leave nodes previously marked as visible.

		@param testGeometry if this optimization should be used
		@remark this option is only useful for the coherent hierarchical culling algorithm
	*/
	void TestGeometryForVisibleLeaves(bool testGeometry);


	virtual void DetermineFullVisibility(GtpVisibility::HierarchyNode *node) const = 0;

	virtual void TraverseNode2(GtpVisibility::HierarchyNode *node) = 0;

	virtual HierarchyNode *GetRandomLeaf(HierarchyNode *root) = 0;
	virtual bool IsNodeFullyVisible(GtpVisibility::HierarchyNode *node) const = 0;

protected:


	/// chc optimization for testing geometry of leaves instead of bounding box
	bool mTestGeometryForVisibleLeaves;
	/// the current frame number
	unsigned int mFrameId;
	/// index of the lcurrent occlusion query in the array of queries
	/// NOTE: should rather be iterator
	int mCurrentTestIdx;
	
	/// number of traversed nodes
	unsigned int mNumTraversedNodes;

	/// The queue is useful for rendering hierarchy nodes in front to back order.
	DistanceQueue *mDistanceQueue;

	/// the root of the hierarchy
	HierarchyNode *mHierarchyRoot;
	
	/// buffer for a node pointer
	HierarchyNode *mSavedNode;
	/// list of rendered hierarchy nodes (e.g., useful for exact visibility queries)
	std::vector<HierarchyNode *> mVisibleNodes;
};
} // namespace GtpVisibility

#endif // GtpVisisibilityHierarchyInterface_H