#ifndef _BSPTREE_H_
#define _BSPTREE_H_

#include "Triangle.h"
#include <list>
#include <cmath>

class BSPTree {
  private:
    class Plane {
      public:
        Plane() : d(0) {}
        Plane(const Vector &n, float d0) : normal(n), d(d0) {}
        Plane(const Triangle &t) : normal(t.getNormal()), d(t.getVertex(0).dot(normal)) {}

        bool contains(const Vertex &v) {
          return (fabsf(normal.dot(v) - d) < 1E-6);
        }

        bool isBehind(const Vertex &v) {
          return (normal.dot(v) - d) < 0;
        }

        bool isInFront(const Vertex &v) {
          return (normal.dot(v) - d) > 0;
        }


        bool contains(const Triangle &t) {
          for(int i = 0; i < 3; ++i) {
            if(!contains(t.getVertex(i)))
              return false;
          }

          return true;
        }

        bool isBehind(const Triangle &t) {
          for(int i = 0; i < 3; ++i) {
            if(!isBehind(t.getVertex(i)) && !contains(t.getVertex(i)))
              return false;
          }

          return true;
        }

        bool isInFront(const Triangle &t) {
          for(int i = 0; i < 3; ++i) {
            if(!isInFront(t.getVertex(i)) && !contains(t.getVertex(i)))
              return false;
          }

          return true;
        }


        const Vector& getNormal() {
          return normal;
        }

      private:
        Vector normal;
        float d;
    };

  public:
    BSPTree(const std::list<Triangle> &triangles);
    virtual ~BSPTree() {
      if(frontTree)
        delete frontTree;

      if(backTree)
        delete backTree;
    }

    template<typename T>
    void visit(const T& visitor, const Vector &v) {
      if(plane.getNormal().dot(v) > 0) {
        if(frontTree)
          frontTree->visit(visitor, v);

        for(std::list<Triangle>::iterator t = triangles.begin(); t != triangles.end(); ++t) {
          visitor(*t);
        }

        if(backTree)
          backTree->visit(visitor, v);
      }
      else {
        if(backTree)
          backTree->visit(visitor, v);

        for(std::list<Triangle>::iterator t = triangles.begin(); t != triangles.end(); ++t) {
          visitor(*t);
        }

        if(frontTree)
          frontTree->visit(visitor, v);
      }
    }

    template<typename T>
    void visit(T& visitor, const Vector &v) {
      if(plane.getNormal().dot(v) > 0) {
        if(frontTree)
          frontTree->visit(visitor, v);

        for(std::list<Triangle>::iterator t = triangles.begin(); t != triangles.end(); ++t) {
          visitor(*t);
        }

        if(backTree)
          backTree->visit(visitor, v);
      }
      else {
        if(backTree)
          backTree->visit(visitor, v);

        for(std::list<Triangle>::iterator t = triangles.begin(); t != triangles.end(); ++t) {
          visitor(*t);
        }

        if(frontTree)
          frontTree->visit(visitor, v);
      }
    }

  private:
    Plane plane;
    std::list<Triangle> triangles;
    BSPTree *frontTree, *backTree;

    static Vertex findCenter(const std::list<Triangle> &triangles);
    static const Triangle* findNearestTriangle(const std::list<Triangle> &triangles, const Vertex &v);
};

#endif /* _BSPTREE_H_ */