// Vorosweep - Copyright (C) 2010-2014 T. Mouton
//
// See the LICENSE.txt file for license information. Please report all
// bugs and problems to <thibaud.mouton@gmail.com>.

#include <map>
#include "sweepobject.h"
#include "frontline.h"

#ifndef _GRID_INCLUDE
#define _GRID_INCLUDE

namespace vorosweep
{
class Border;

class basic_grid
{
  public:
    static double epsilon;
};

class BBox
{
  private:
    Point min; // min bbox
    Point max; // max bbox
    double lt[2];
    double enlarge;
  public:
    BBox ( double enlarge_factor )
    {
      min.p[0] = min.p[1] = INFINITY;
      max.p[0] = max.p[1] = -INFINITY;
      lt[0] = lt[1] = -INFINITY;
      enlarge = enlarge_factor;
    }
    inline void update ( double *p )
    {
      for ( int i = 0; i < 2; i++ )
      {
        if ( p[i] < min.p[i] )
          min.p[i] = p[i];
        if ( p[i] > max.p[i] )
          max.p[i] = p[i];
      }
    }
    inline void lock()
    {
      for ( int i = 0; i < 2; i++ )
      {
        double dt = ( max.p[i] - min.p[i] ) * enlarge;
        min.p[i] -= dt;
        max.p[i] += dt;
        lt[i] = max.p[i] - min.p[i];
      }
    }
    inline void set(double xmin, double xmax, double ymin, double ymax)
    {
      min.p[0] = xmin;
      min.p[1] = ymin;
      max.p[0] = xmax;
      max.p[1] = ymax;
    }
    inline double *get_min()
    {
      return min.p;
    }
    inline double *get_max()
    {
      return max.p;
    }
    inline double get_lenght ( int i )
    {
      return lt[i];
    }
    inline void print()
    {
      printf ( "bounding box : %lf < x < %lf -- %lf < y < %lf\n", min.p[0], max.p[0], min.p[1], max.p[1] );
    }
};

class BorderBucket
{
  private:
    Point *orig;
    double *dir2d;
    std::set<SweepEdge *> edgelist;
  public:
    inline void insert_sweepedge ( SweepEdge *se )
    {
      edgelist.insert ( se );
    }
    inline std::set<SweepEdge *> &get_edge_list()
    {
      return edgelist;
    }
    inline void set_frame ( Point *zero, double *dir )
    {
      orig = zero;
      dir2d = dir;
    }
    inline double *get_dir()
    {
      return dir2d;
    }
    // convert the 3d point into the 2d border frame
    inline void pt3d_to_pt2d ( double *pt3d, double *pt2d )
    {
      double vec2d[2] = {0.0, 0.0};
      geom::vec2d ( orig->p, pt3d, vec2d );
      pt2d[0] = geom::scalar_product2d ( get_dir(), vec2d );
      pt2d[1] = pt3d[2];
//       printf ( "pt 2d --> %lf %lf\n", pt2d[0], pt2d[1] );
    }
    // convert the 3d vector into the 2d border frame
    inline void dir3d_to_dir2d ( double *vec3d, double *vec2d )
    {
      vec2d[0] = geom::scalar_product3d ( get_dir(), vec3d );
      vec2d[1] = vec3d[2];
//       printf ( "vec 2d --> %lf %lf\n", vec2d[0], vec2d[1] );
    }
    // reverse operation
    inline void pt2d_to_pt3d ( double *pt2d, double *pt3d )
    {
      pt3d[0] = orig->p[0] + pt2d[0] * get_dir() [0];
      pt3d[1] = orig->p[1] + pt2d[0] * get_dir() [1];
      pt3d[2] = pt2d[1];
//       printf ( "pt 3d --> %lf %lf %lf\n", pt3d[0], pt3d[1], pt3d[2] );
    }
    inline void edge3d_to_edge2d ( SweepEdge *se, double *sept2d, double *sedir2d )
    {
      dbgprintf (2, "se %p start 3d --> %lf %lf %lf\n", se, se->get_start()->p[0], se->get_start()->p[1], se->get_start()->p[2] );
      dbgprintf (2, "se %p dir3d --> %lf %lf %lf\n", se, se->get_dir3d() [0], se->get_dir3d() [1], se->get_dir3d() [2] );
      pt3d_to_pt2d ( se->get_start()->p, sept2d );
      dir3d_to_dir2d ( se->get_dir3d(), sedir2d );
      dbgprintf (2, "se start 2d --> %lf %lf\n", sept2d[0], sept2d[1] );
      dbgprintf (2, "se dir2d --> %lf %lf\n", sedir2d[0], sedir2d[1] );
    }
    int potential_crash ( double *start0, double *start1, double *dir0, double *dir1, double *crashpos );
    void generate_edgecrash_events ( SweepEdge *se, double ctime, int gid, Container<Event> *econt, Event **eventlist, int &nbe );
};

class Grid1d
{
  private:
    Point *pt[2];
    double dir[3];
    double plane[3];
    double lt;
    int nbx; // subdivisions
    double blx; // size bucket
    BorderBucket *objectgrid;
  public:
    Grid1d ( Point *pt0, Point *pt1 )
    {
      dbgprintf(2, "new grid 1d --> %lf %lf -- %lf %lf\n", pt0->p[0], pt0->p[1], pt1->p[0], pt1->p[1]);
//       printf("new grid 1d --> %lf %lf -- %lf %lf\n", pt0->p[0], pt0->p[1], pt1->p[0], pt1->p[1]);
      pt[0] = pt0;
      pt[1] = pt1;
      dir[0] = pt[1]->p[0]-pt[0]->p[0];
      dir[1] = pt[1]->p[1]-pt[0]->p[1];
      lt = geom::norm2d ( dir );
      dir[0] /= lt;
      dir[1] /= lt;
      dir[2] = 0.0;
      plane[0] = dir[1];
      plane[1] = -dir[0];
      plane[2] = 0.0;
      nbx = 0;
    }
    inline double get_parameter ( double *pt )
    {
      double vec[2];
      geom::vec2d(get_point ( 0 )->p, pt, vec);
      return geom::scalar_product2d(dir, vec);        
//       return geom::distance2d ( get_point ( 0 )->p, pt );
    }
    inline int get_index ( double t )
    {
      int id = ( int ) ( t / blx );
//       if (id < 0 || id >= nbx)
//         id = -1;
      return id;
    }
    inline int get_index ( double *pt )
    {
      double t = get_parameter ( pt );
      if ( t < 0.0 || t > lt)
        return -1;
      return get_index ( t );
    }
    inline int get_bucket_size ( )
    {
      return nbx;
    }
    inline BorderBucket *get_bucket ( int i )
    {
//       if (i < 0 || i >= nbx)
//       {
//         printf("/!\\ --> index %d not in range %d -- %d\n", i, 0, nbx);
//         getchar();
//       }
      ASSERT_ERROR(i >= 0 && i < nbx, "index %d not in range %d -- %d\n", i, 0, nbx);
      return &objectgrid[i];
    }
    inline double *get_dir()
    {
      return dir;
    }
    inline Point *get_point ( int i )
    {
      return pt[i];
    }
    inline double *get_plane()
    {
      return plane;
    }
    inline void insert_sweepedge ( SweepEdge *se, int index )
    {
      dbgprintf(3, "border grid --> inserting edge %p into bucket %d\n", se, index);
      get_bucket ( index )->insert_sweepedge ( se );
    }
    inline void dir3d_to_dir2d ( double *dir3d, double *dir2d )
    {
      dir2d[0] = geom::scalar_product3d ( get_dir(), dir3d );
      dir2d[1] = dir3d[2];
      printf ( "dir 2d --> %lf %lf\n", dir2d[0], dir2d[1] );
    }
    inline void init ( int nb )
    {
      nbx = nb;
      objectgrid = new BorderBucket[nbx];
      for ( int i = 0; i < nbx; i++ )
        objectgrid[i].set_frame ( pt[0], get_dir() );
      blx = lt / ( double ) nb;
      dbgprintf ( 2, "Init border grid --> %d ( dx %lf )\n", nbx, blx );
    }
    void compute_exit ( int gid, double* orig, double* dir, int &ngid, double* exit );
    void print();
};

class Bucket
{
//   public:
//     static double epsilon;
  private:
    std::set<SweepEdge *> edgelist;
    std::set<SweepFacet *> facetlist;
    std::pair<std::set<SweepFacet *>::iterator,bool> fret;
    std::set<Border *> borderlist;
    std::set<std::pair<Border *, int > > borderpointlist;
//     std::set<Border *> borderpointlist;

  public:
//     inline void set_bbox ( double minx, double miny, double maxx, double maxy )
//     {
//       min[0] = minx;
//       min[1] = miny;
//       max[0] = maxx;
//       max[1] = maxy;
//     }
//     inline int inside ( double *pt )
//     {
//       if (pt[0] < min[0] || pt[0] > max[0])
//         return 0;
//       if (pt[1] < min[1] || pt[1] > max[1])
//         return 0;
//       return 1;
//     }
    inline void insert_border_point ( Border *bo, int i )
    {
      borderpointlist.insert ( std::pair<Border *, int>(bo, i) );
    }
//     inline void insert_border_point ( Border *bo )
//     {
//       borderpointlist.insert ( bo );
//     }
    inline void insert_border ( Border *bo )
    {
      borderlist.insert ( bo );
    }
    inline void insert_sweepedge ( SweepEdge *se )
    {
      edgelist.insert ( se );
    }
    inline int insert_sweepfacet ( SweepFacet *sf )
    {
      fret = facetlist.insert ( sf );
      return fret.second;
    }
    inline int get_sweepedge_size()
    {
      return edgelist.size();
    }
    inline int get_sweepfacet_size()
    {
      return facetlist.size();
    }
    inline std::set<SweepEdge *> &get_edge_list()
    {
      return edgelist;
    }
    int potential_crash ( SweepEdge *se, SweepFacet *sf, double *crashpos );
    int potential_crash ( SweepEdge *se, Border *bo, double *crashpos );
    void generate_facetcrash_events ( SweepFacet *sf, double ctime, int gid, Container<Event> *econt, Event **eventlist, int &nbe );
    void generate_facetcrash_events ( SweepEdge *se, double ctime, int gid, Container<Event> *econt, Event **eventlist, int &nbe );
    void generate_bordercrash_events ( SweepEdge *se, double ctime, int gid, Container<Event> *econt, Event **eventlist, int &nbe );
    void generate_bordercrash_events ( SweepFacet *sf, double ctime, int gid, Container<Event> *econt, Event **eventlist, int &nbe );
    int vertical_crash ( double *pt, double z, SweepFacet *sf, double *crashpos );
    int point_already_covered ( double *pt, double ctime );
};

class Grid2d
{
  private:
    BBox *bb;
    int nb[2]; // subdivision /x and /y
    double bl[2]; // size bucket /x and /y
    Bucket *objectgrid;
  public:
    Grid2d ( double enlarge )
    {
      bb = new BBox ( enlarge );
    }
    inline void insert_sweepedge ( SweepEdge *se, int index )
    {
      objectgrid[index].insert_sweepedge ( se );
    }
    inline int insert_sweepfacet ( SweepFacet *sf, int index )
    {
      return objectgrid[index].insert_sweepfacet ( sf );
    }
    inline void get_indices ( int id, int &i, int &j )
    {
      j = ( int ) ( id/nb[0] );
      i = id%nb[0];
    }
    inline int get_index ( int i, int j )
    {
//       printf("--> %d %d : %d %d %d %d\n", i, j, (i < 0), (i >= nb[0]), (j < 0), (j >= nb[1]));
      if ( ( i < 0 ) || ( i >= nb[0] ) || ( j < 0 ) || ( j >= nb[1] ) )
        return -1;
      return i+nb[0]*j;
    }
    inline void get_indices ( double *p, int &i, int &j )
    {
      i = ( int ) ( ( p[0] - bb->get_min() [0] ) / bl[0] );
      j = ( int ) ( ( p[1] - bb->get_min() [1] ) / bl[1] );
    }
    inline int get_index ( double *p )
    {
      int i, j;
      get_indices ( p, i, j );
      return get_index ( i, j );
    }
    inline void get_cell ( int i, int j, double *minc, double *maxc )
    {
      minc[0] = bb->get_min() [0] + i*bl[0];
      minc[1] = bb->get_min() [1] + j*bl[1];
      maxc[0] = minc[0] + bl[0];
      maxc[1] = minc[1] + bl[1];
    }
    inline void get_vertex ( int i, int j, double *pt )
    {
      pt[0] = bb->get_min() [0] + i*bl[0];
      pt[1] = bb->get_min() [1] + j*bl[1];
    }
    inline BBox *get_bbox()
    {
      return bb;
    }
    inline Bucket *get_bucket ( int i )
    {
      return &objectgrid[i];
    }
    void init ( int nbx, int nby );
    void compute_exit ( int gid, double* orig, double* dir, int &ngid, double* exit );
    void export_vtk ( const char *name );
};

};

#endif