#ifndef _MeshKdTree_H__
#define _MeshKdTree_H__

#include <functional>
using namespace std;

#include "Containers.h"
#include "AxisAlignedBox3.h"
#include "Ray.h"

namespace GtpVisibilityPreprocessor {

class MeshKdNode;
class MeshKdLeaf;
class MeshKdInterior;
  
/** Abstract class for kd-tree node */
class MeshKdNode {
public:
  MeshKdNode() {}
  
  /** Determines whether this node is a leaf or interior node
      @return true if leaf
  */
  virtual bool IsLeaf() const = 0;
  virtual ~MeshKdNode() {}
};

/** Implementation of the kd-tree interior node */
class MeshKdInterior : public MeshKdNode {
  
public:
  MeshKdInterior():MeshKdNode(),
		   mBack(NULL), mFront(NULL) {}
  
  /** \sa KdNode::IsLeaf() */
  virtual bool IsLeaf() const { return false; }

  /** splitting axis */
  int mAxis;
  /** splitting position, absolute position within the bounding box of this node */
  float mPosition;
  
  /** back node */
  MeshKdNode *mBack;
  /** front node */
  MeshKdNode *mFront;

  void SetupChildLinks(MeshKdNode *b, MeshKdNode *f) {
    mBack = b;
    mFront = f;
  }
  
  void ReplaceChildLink(MeshKdNode *oldChild, MeshKdNode *newChild) {
    if (mBack == oldChild)
      mBack = newChild;
    else
      mFront = newChild;
  }
  
  ~MeshKdInterior() {
    delete mBack;
    delete mFront;
  }
};
  
  
/** Implementation of the kd-tree leaf node */
class MeshKdLeaf : public MeshKdNode {
public:
  MeshKdLeaf():MeshKdNode() {
  }

  MeshKdLeaf(const vector<int> &faces):MeshKdNode() {
    mFaces = faces;
  }
  
  /** \sa KdNode::IsLeaf() */
  virtual bool IsLeaf() const { return true; }
  
  /** indices of contained faces */
  vector<int> mFaces;
  
};



/** KdTree for indexing scene entities - occluders/occludees/viewcells */
class MeshKdTree {
  
protected:
  struct TraversalData
  {  
    MeshKdNode *mNode;
    MeshKdInterior *mParent;
    AxisAlignedBox3 mBox;
    int mDepth;
    float mPriority;
    
    TraversalData() {}
    
    TraversalData(MeshKdNode *n, const float p):
      mNode(n), mPriority(p)
    {}
    
    TraversalData(MeshKdNode *n,
		  MeshKdInterior *p,
		  const AxisAlignedBox3 &b,
		  const int d):
      mNode(n), mParent(p), mBox(b), mDepth(d) {}
    
    
    bool operator<(
		   const TraversalData &b) const {
      MeshKdLeaf *leafa = (MeshKdLeaf *) mNode;
      MeshKdLeaf *leafb = (MeshKdLeaf *) b.mNode;
      return 
	leafa->mFaces.size()*mBox.SurfaceArea()
	<
	leafb->mFaces.size()*b.mBox.SurfaceArea();
    }
    
  };

  

public:

  enum {SPLIT_OBJECT_MEDIAN,
	SPLIT_SPATIAL_MEDIAN,
	SPLIT_SAH};
  

  MeshKdTree(Mesh *mesh);
  ~MeshKdTree() {
    if (mSplitCandidates)
      delete mSplitCandidates;
    
    if (mRoot)
      delete mRoot;
  }
  
  virtual bool Construct();

  /** Check whether subdivision criteria are met for the given subtree.
      If not subdivide the leafs of the subtree. The criteria are specified in
      the environment as well as the subdivision method. By default surface area
      heuristics is used.
	
      @param subtree root of the subtree

      @return true if subdivision was performed, false if subdivision criteria
      were already met
  */
  virtual MeshKdNode *Subdivide(const TraversalData &tdata);
  
  /** Get the root of the tree */
  MeshKdNode *GetRoot() const {
    return mRoot;
  }
  
  AxisAlignedBox3 GetBox() const { return mMesh->mBox; }

  int
  CastRay(
	  Ray &ray,
	  MeshInstance *instance
	  );


protected:
  
  struct RayTraversalData {
    MeshKdNode *mNode;
    Vector3 mExitPoint;
    float mMaxT;
    
    RayTraversalData() {}
    RayTraversalData(MeshKdNode *n,
		     const Vector3 &p,
		     const float maxt):
      mNode(n), mExitPoint(p), mMaxT(maxt) {}
  };

  // --------------------------------------------------------------
  // For sorting objects
  // --------------------------------------------------------------
  struct  SortableEntry
  {
    enum {
      FACE_MIN,
      FACE_MAX
    };
    
    int type;
    float value;
    int face;
    
    SortableEntry() {}
    SortableEntry(const int t, const float v, const int f):type(t),
							   value(v),
							   face(f) {}
    
    bool operator<(const SortableEntry &b) const {
      return value < b.value;
    }
    
  };
  

  float
  BestCostRatio(
		MeshKdLeaf *node,
		const AxisAlignedBox3 &box,
		const int axis,
		float &position,
		int &objectsBack,
		int &objectsFront
		);

  void
  SortSplitCandidates(
		      MeshKdLeaf *node,
		      const int axis
		      );

  MeshKdNode *
  SubdivideNode(
		MeshKdLeaf *leaf,
		MeshKdInterior *parent,
		const AxisAlignedBox3 &box,
		const int depth,
		AxisAlignedBox3 &backBBox,
		AxisAlignedBox3 &frontBBox
		);

  bool
  TerminationCriteriaMet(const MeshKdLeaf *leaf, const int depth);
  
  int
  SelectPlane(MeshKdLeaf *leaf,
	      const AxisAlignedBox3 &box,
	      float &position
	      );

  /// pointer to the mesh owning the tree
  Mesh *mMesh;
  
  /// root of the tree
  MeshKdNode *mRoot;
  
  /// reusable array of split candidates
  vector<SortableEntry> *mSplitCandidates;

public:
  static void ParseEnvironment();
  static float mSplitBorder;
  static int mTermMaxDepth;
  static int mTermMinCost;
  static float mMaxCostRatio;
  static float mCt_div_ci;
  static int mSplitMethod;

};
  


}


#endif