#include <CGAL/Cartesian.h>
#include <CGAL/Point_2.h>
#include <CGAL/convex_hull_traits_2.h>
#include <CGAL/IO/Qt_widget.h>
#include <CGAL/IO/Qt_widget_layer.h>
#include <qapplication.h>

typedef CGAL::Cartesian<double>		    Rep;
typedef CGAL::Point_2<Rep>		    Point;
typedef CGAL::Segment_2<Rep>                Segment;
typedef CGAL::Convex_hull_traits_2<Rep>     Traits;
Traits my_traits;
Traits::Less_rotate_ccw_2 less_rotate_ccw = 
                       my_traits.less_rotate_ccw_2_object();
Traits::Less_yx_2 less_yx = my_traits.less_yx_2_object();


/////////////////////////////////////////////////////////
//  Les objets affiches sont declares ici en variable globales

Point    the_point=Point(-1,-1);
std::list<Point>	  list_of_points, ch_points;

/////////////////////////////////////////////////////////
 // Completer la function suivante "my_jarvis_ch"
/////////////////////////////////////////////////////////

/* a partir d'une liste de points "input", "output" devra etre la
   liste des points de l'enveloppe convexe ordonnes dasn le sens
   contraire des aiguilles d'une montre (ccw = conter clock wise).
  
   Utiliser le comparateur "less_yx", voir la donc CGAL dont voici un
   extrait: 
   ConvexHullTraits_2::Less_xy_2
   Binary predicate object type comparing Point_2s
   lexicographically. Must provide bool operator()(Point_2 p, Point_2
   q) where true is returned iff p <xy q. We have p<xyq, iff px < qx
   or px = qx and py < qy, where px and py denote x and y coordinate
   of point p, respectively.

   ainsi que le comparateur "less_rotate_ccw": 
   ConvexHullTraits_2::Less_rotate_ccw_2
   Predicate object type that must provide bool operator()(Point_2 e,
   Point_2 p,Point_2 q), where true is returned iff a tangent at e to
   the point set {e,p,q} hits p before q when rotated counterclockwise
   around e. Ties are broken such that the point with larger distance
   to e is smaller!
*/

void my_jarvis_ch(std::list<Point> input, std::list<Point>& output)
{
  std::list<Point>::iterator itb;

  //cas particulier: s'il y a moins de 3 points en entree
  if (input.size() < 3)
    {
      output = input;
      return;
    }

  //trouve start, le point le plus bas en y, qui est le premier point
  //  de l'env. conv.
  std::list<Point>::iterator  p_start = input.begin();
  for (itb = input.begin(); itb != input.end(); itb++)
    if ( less_yx(*itb, *p_start) ) p_start = itb;
  Point start = *p_start;
  output.push_back(start);
  input.erase(p_start);

  std::list<Point>::iterator  p1 = input.begin(),
    p2 = input.begin();
  for (; p2 != input.end(); p2++)
    if ( !less_rotate_ccw(start, *p1, *p2) ) p1 = p2;
  //p1 est le suivant sur ch
  input.push_back(start);

  for (; *p1 != start;)
    {
      Point p0 = *p1;
      output.push_back(p0);
      input.erase(p1);
      p1 = input.begin();
      for ( p2 = input.begin(); p2 != input.end(); p2++)
	if ( !less_rotate_ccw(p0, *p1, *p2) ) p1 = p2;
      //p1 est le suivant sur ch
    }
}

/////////////////////////////////////////////////////////
//  l'affichage est fait dans la methode "draw" ci dessous

class My_layer : public CGAL::Qt_widget_layer{
  void draw()
    {
      widget->lock();
      //affichage de la liste des points
      *widget << CGAL::PointSize(3);
      *widget << CGAL::GREEN;
      std::list<Point>::iterator itp = list_of_points.begin();
      while(itp!=list_of_points.end())
	{
	  *widget << (*itp++);
	}
      //affichage de the_point
      *widget << CGAL::PointSize(6) << CGAL::BLUE << the_point ;
      //affichage des points de la conv hull
      std::list<Segment>	Sl;
      if( ch_points.size() > 1 ) {
	Point pakt,prev,pstart;
	
	std::list<Point>::const_iterator it;
	it=ch_points.begin();
	prev= *it; pstart=prev;
	it++;
	
	for(; it != ch_points.end(); ++it) {
	  pakt= *it;
	  Sl.push_back(Segment(prev,pakt));
	  prev=pakt;
	}
	Sl.push_back(Segment(pakt,pstart));
	
	*widget << CGAL::RED;
	std::list<Segment>::iterator its = Sl.begin();
	while(its!=Sl.end())
	  {
	    *widget << (*its++);
	  }
      }
      widget->unlock();
    }
};

class My_window : public CGAL::Qt_widget {
public:
  My_window(int x, int y)
  {
    resize(x,y);
    attach(&layer);
  };
private:
  //this method is called when the user presses the mouse
  void mousePressEvent(QMouseEvent *e)
  {
    Qt_widget::mousePressEvent(e);

    /////////////////////////////////////////////////////////////
    //  C'EST ICI QUE CA SE PASSE QUAND ON CLIQUE !
    //
    if (e->button() == Qt::LeftButton)
      {
	list_of_points.push_back(Point(x_real(e->x()),
				       y_real(e->y())));
	//compute ch
	ch_points.clear();
	my_jarvis_ch(list_of_points, ch_points);
      }
    if (e->button() == Qt::MidButton)
      std::cout << Point(x_real(e->x()), y_real(e->y())) << std::endl;
    if (e->button() == Qt::RightButton)
      the_point =  Point(x_real(e->x()), y_real(e->y()));
    /////////////////////////////////////////////////////////////

    redraw();
  }
  My_layer layer;
};

int main( int argc, char **argv )
{
    QApplication app( argc, argv );
    My_window *W = new My_window(400,400);
    app.setMainWidget(W);
    W->show();
    W->set_window(0, 400, 0, 400);
    return app.exec();
}


/* pour utiliser CGAL:

#include <CGAL/convex_hull_2.h> 

et appel de:

CGAL::convex_hull_2(list_of_points.begin(),
                    list_of_points.end(),
		    std::back_inserter(ch_points));
*/