#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <pixman.h>
#include <gtk/gtk.h>

typedef pixman_fixed_16_16_t	fixed_t;


#define fixed_e			((fixed_t) 1)
#define fixed_1			(int_to_fixed(1))
#define fixed_1_minus_e		(fixed_1 - fixed_e)
#define fixed_to_int(f)		((int) ((f) >> 16))
#define int_to_fixed(i)		((fixed_t) ((i) << 16))
#define fixed_frac(f)		((f) & pixman_fixed_1_minus_e)
#define fixed_floor(f)		((f) & ~pixman_fixed_1_minus_e)
#define fixed_ceil(f)		pixman_fixed_floor ((f) + pixman_fixed_1_minus_e)
#define fixed_mod_2(f)		((f) & (pixman_fixed1 | pixman_fixed_1_minus_e))

#define fixed_to_double(f)	(double) ((f) / (double) pixman_fixed_1)
#define double_to_fixed(d)	((pixman_fixed_t) ((d) * 65536.0))

typedef enum
{
    WINDING,
    EVEN_ODD
} fill_rule_t;


/*
 *    +--------------------------------------------------+
 *    |                           <Y_FRAC_FIRST>         |
 *    | <X_FRAC_FIRST> * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                          | <BIG_STEP>            |
 *    +--------------------------------------------------+
 */

#define MAX_ALPHA(n)	((1 << (n)) - 1)
#define N_Y_FRAC(n)	((n) == 1 ? 1 : (1 << ((n)/2)) - 1)
#define N_X_FRAC(n)	((n) == 1 ? 1 : (1 << ((n)/2)) + 1)

#define STEP_Y_SMALL(n)	(fixed_1 / N_Y_FRAC(n))
#define STEP_Y_BIG(n)	(fixed_1 - (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n))

#define Y_FRAC_FIRST(n)	(STEP_Y_SMALL(n) / 2)
#define Y_FRAC_LAST(n)	(Y_FRAC_FIRST(n) + (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n))

#define STEP_X_SMALL(n)	(pixman_fixed_1 / N_X_FRAC(n))
#define STEP_X_BIG(n)	(pixman_fixed_1 - (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))

#define X_FRAC_FIRST(n)	(STEP_X_SMALL(n) / 2)
#define X_FRAC_LAST(n)	(X_FRAC_FIRST(n) + (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))

typedef struct edge_t edge_t;
struct edge_t
{
    fixed_t			x0;
    fixed_t			y0;
    fixed_t			x1;
    fixed_t			y1;
};

#define N_GRID_X 17
#define N_GRID_Y 15

static fixed_t
next_sample_x (fixed_t x)
{
    pixman_fixed_t   f = pixman_fixed_frac(x);
    pixman_fixed_t   i = pixman_fixed_floor(x);

    f = ((f + Y_FRAC_FIRST(N_GRID_X)) / STEP_Y_SMALL(N_GRID_X)) * STEP_Y_SMALL(N_GRID_X) + Y_FRAC_FIRST(N_GRID_X);
    if (f > Y_FRAC_LAST(N_GRID_X))
    {
	f = Y_FRAC_FIRST(N_GRID_X);
	i += pixman_fixed_1;
    }
    return (i | f);
}

static fixed_t
next_sample_y (fixed_t y)
{
    pixman_fixed_t   f = pixman_fixed_frac(y);
    pixman_fixed_t   i = pixman_fixed_floor(y);

    f = ((f + Y_FRAC_FIRST(N_GRID_Y)) / STEP_Y_SMALL(N_GRID_Y)) * STEP_Y_SMALL(N_GRID_Y) + Y_FRAC_FIRST(N_GRID_Y);
    if (f > Y_FRAC_LAST(N_GRID_Y))
    {
	f = Y_FRAC_FIRST(N_GRID_Y);
	i += pixman_fixed_1;
    }
    return (i | f);
}

static fixed_t
sample_step_x (fixed_t x)
{
    (void)x;
    
    return 1.0;
}

static fixed_t
sample_step_y (fixed_t y)
{
    if (pixman_fixed_frac (y) == Y_FRAC_LAST (N_GRID_Y))
    {
	return STEP_Y_BIG (N_GRID_Y);
    }
    else
    {
	return STEP_Y_SMALL (N_GRID_Y);
    }
}

static void
dda (fixed_t x0, fixed_t y0, fixed_t x1, fixed_t y1)
{
    fixed_t y = next_sample_y (y0);
    fixed_t dxdy = (y1 - y0) / (x1 - x0);

    printf ("line %f %f %f %f\n",
	    pixman_fixed_to_double (x0),
	    pixman_fixed_to_double (y0),
	    pixman_fixed_to_double (x1),
	    pixman_fixed_to_double (y1));

    printf ("bottom: %f\n", pixman_fixed_to_double (next_sample_y (y1)));
    
    while (y < next_sample_y (y1))
    {
	fixed_t dy = y - y0;
	fixed_t dx = x1 - x0;
	fixed_t x = ((((y - y0) * (pixman_fixed_48_16_t)(x1 - x0)))) / (y1 - y0) + x0;

	x = next_sample_x (x);
	
	printf ("  %f %f\n",
		pixman_fixed_to_double (x),
		pixman_fixed_to_double (y));
	
	y += sample_step_y (y);
    }
}

static void
ddda (double x0, double y0, double x1, double y1)
{
    dda (pixman_double_to_fixed (x0),
	 pixman_double_to_fixed (y0),
	 pixman_double_to_fixed (x1),
	 pixman_double_to_fixed (y1));
}

static int
compare_edges (const void *e1, const void *e2)
{
    const edge_t *edge1 = e1;
    const edge_t *edge2 = e2;

    if (edge1->y0 == edge2->y0)
	return edge1->x0 - edge2->x0;
    else
	return edge1->y0 - edge2->y0;
}

static void
scan_convert (int n_edges, edge_t *edges, fill_rule_t fill_rule)
{
    int i;
    
    /* First sort the edges
     */
    qsort (edges, n_edges, sizeof (edge_t), compare_edges);

}

#define df(a) pixman_double_to_fixed(a)

int
main (int argc, char **argv)
{
    edge_t pentagon[] = {
	{ df  (2.2), df (10.2), df (11.3),  df (2.2) },
	{ df (11.3), df  (2.2), df (15.7),  df (5.5) },
	{ df (15.7), df  (5.5), df (20.8), df (15.8) },
	{ df (20.8), df (15.8), df (13.2), df (25.2) },
	{ df (13.2), df (25.2), df (2.2),  df (10.2) } };
    
    gtk_init (&argc, &argv);

    scan_convert (5, pentagon, WINDING);
    
    
#if 0
    ddda (0.5, 0.5, 2.5, 1.6);
    ddda (0.3, 0.2, 3.7, 2.2);
    ddda (3.7, 2.2, 7.2, 2.8);
    ddda (3.7, 2.2, 4.2, 7.2);
    ddda (0.5, 0.5, 1.5, 1.5);
    ddda (0.5, 0.5, 2.5, 2.5);
#endif
    
    return 0;
}