/*********************************************************************
 * algorithm.h
 * ===========
 * This file defines:
 * (1) The basic geometric data types the algorithm works with - 
 *     NT (the number type, which is leda_real), Point, Polygon, etc.
 * (2) A 'command_t' structure, which contains a single command
 *     to the algorithm ("insert", "delete", or "draw").
 * (3) A 'solution_t' structure, which contains a combinatorial
 *     representation of a solution, i.e., defines the leftmost
 *     center of a disc that covers all the currently active points.
 *     See below for more details.
 * (4) The basic interface of the 'Algorithm' class that you are
 *     expected to implement, which includes two functions:
 *       a) init()   - part 1 of the program;
 *       b) update() - part 2 of the program.
 *     Of course, you may add members/methods to the class as
 *     you like, but you may NOT change these two functions.
 *********************************************************************/

#ifndef __ALGORITHM_H
#define __ALGORITHM_H


#include <CGAL/basic.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <iostream.h>
#include <fstream.h>
#include <strstream.h>

#include <vector.h>
#include <list.h>
#include <algo.h>

#include <CGAL/Cartesian.h>
#include <CGAL/Point_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/leda_real.h>


//---------------------------------------------------------------
// Basic geometric entities
//---------------------------------------------------------------
typedef leda_real                  NT;
typedef CGAL_Cartesian<NT>         R;
typedef CGAL_Polygon_traits_2<R>   Poly_traits;
typedef CGAL_Point_2<R>            Point;
typedef CGAL_Segment_2<R>          Segment;
typedef CGAL_Polygon_2<Poly_traits, vector<Point> > Polygon;


//---------------------------------------------------------------
// Useful iterators
//---------------------------------------------------------------
typedef vector<Point>::const_iterator   PointIterator;
typedef vector<Polygon>::const_iterator PolygonIterator;
typedef CGAL_Polygon_2<Poly_traits, vector<Point> >::Vertex_const_iterator 
          VertexIterator;
typedef CGAL_Polygon_2<Poly_traits, vector<Point> >::Edge_const_iterator 
          EdgeIterator;
typedef CGAL_Polygon_2<Poly_traits, vector<Point> >::Vertex_const_circulator 
          VertexCirculator;


//---------------------------------------------------------------
// command_t - a command for the algorithm
//---------------------------------------------------------------
typedef struct command_t {
    int  type;      // Can be COMM_INSERT, COMM_DELETE, or COMM_DRAW
    int  pt_index;  // Index of point to insert/delete (0,1,...)
} command_t;

enum command_type_e { COMM_INSERT = 1, COMM_DELETE, COMM_DRAW };


//---------------------------------------------------------------
// solution_t - describes the (bottom-)leftmost solution point
//---------------------------------------------------------------
typedef struct solution_t {
    int  type;        // Can be SOL_NONE, SOL_POINT, SOL_POINT_POINT, 
                      //    SOL_POINT_EDGE, or SOL_VERTEX
    int  point1;      // Index of first point (for type=SOL_POINT_xxx)
    int  point2;      // Index of 2nd point (for type=SOL_POINT_POINT)
    int  polygon;     // Index of polygon (for type=SOL_POINT_EDGE,SOL_VERTEX)
    int  edge;        // Index of edge (for type=SOL_POINT_EDGE)
    int  vertex;      // Index of vertex (for type=SOL_VERTEX)
} solution_t;

enum solution_type_e { 
    SOL_NONE = 0,     // No solution
    SOL_POINT,        // Solution is defined by one point:
                      //   index of point should be supplied in 'point1'.
                      // (If the solution is defined by a vertex and one
                      //  or more points, use SOL_VERTEX)
    SOL_POINT_POINT,  // Solution is defined by two (or more) points:
                      //   supply the point with the minimal index
                      //   as 'point1', and the point with the second-
                      //   most minimal index as 'point2'.
    SOL_POINT_EDGE,   // Solution is defined by a point and an edge:
                      //   supply the point in 'point1' (again, if there
                      //   is more than one, give the minimal index),
                      //   the index of the polygon in 'polygon',
                      //   and the index of the edge within the polygon
                      //   in 'edge'.
    SOL_VERTEX        // Solution is defined by a vertex:
                      //   supply the index of the polygon in 'polygon',
                      //   and the index of the vertex in 'vertex'.
};


//---------------------------------------------------------------
// The algorithm class
//---------------------------------------------------------------
class Algorithm {

 public:
    
    //======================================================
    // init
    //======================================================
    void init (const vector<Point>   &points,    // input
               const vector<Polygon> &polygons,  // input
               NT radius,                        // input
               solution_t &solution);            // output

    //======================================================
    // update
    //======================================================
    void update (command_t comm,                 // input
                 solution_t &solution);          // output

};



#endif