#include <gtk/gtk.h>
#include <glib.h>
#include <cairo.h>

static const cairo_rectangle_int_t rects[] = {
    { 0, 50, 200, 100 },
    { 250, 0, 200, 100 },
    { 500, 0, 50, 350 },
    { 400, 100, 50, 100 },
    { 100, 150, 50, 50 },
    { 50, 200, 150, 150 },
    { 0, 300, 50, 50 },
    { 200, 250, 100, 100 },
    { 250, 150, 100, 100 },
    { 350, 200, 100, 150 },
    { 250, 350, 150, 50 },
#if 0
    { 450, 350, 50, 50 },
#endif
    { 50, 450, 400, 50 },
};

typedef struct hsegment_t hsegment_t;
typedef struct vsegment_t vsegment_t;

struct hsegment_t
{
    int y;
    int x1, x2;		/* includes x1, but not x2 */

    vsegment_t *left;
    vsegment_t *right;
};

struct vsegment_t
{
    int x;
    int y1, y2;

    hsegment_t *top;
    hsegment_t *bottom;
};

static int
compare_hsegments (gconstpointer p1, gconstpointer p2)
{
    const hsegment_t *h1 = p1;
    const hsegment_t *h2 = p2;

    if (h1->y < h2->y)
	return -1;
    else if (h1->y > h2->y)
	return 1;
    else
    {
	if (h1->x1 < h2->x1)
	    return -1;
	else if (h1->x1 > h2->x1)
	    return 1;
	else
	{
	    if (h1->x2 < h2->x2)
		return -1;
	    else if (h1->x2 > h2->x2)
		return 1;
	    else
		return 0;
	}
    }

    return 0;
}

static int
compare_vsegments (gconstpointer p1, gconstpointer p2)
{
    const vsegment_t *v1 = p1;
    const vsegment_t *v2 = p2;

    if (v1->x < v2->x)
	return -1;
    else if (v1->x > v2->x)
	return 1;
    else
    {
	if (v1->y1 < v2->y1)
	    return -1;
	else if (v1->y1 > v2->y1)
	    return 1;
	else
	{
	    /* Should not be reached since there cannot be
	     * two vertical segments starting in the same point
	     */

	    g_assert_not_reached();
	}
    }

    if (v1->y1 < v2->y1)
	return -1;
    else if (v1->y1 > v2->y1)
	return 1;
    else
    {
	if (v1->x < v2->x)
	    return -1;
	else if (v1->x > v2->x)
	    return 1;
	else
	    return 0;
    }
}

static void add_hsegment (cairo_t *cr, hsegment_t *h, gboolean go_right);

static void
add_vsegment (cairo_t *cr, vsegment_t *v, gboolean go_down)
{
    hsegment_t *h;
    gboolean go_right;

    if (!v->bottom)
	return;

    if (go_down)
    {
	cairo_line_to (cr, v->x, v->y2);

	h = v->bottom;
    }
    else
    {
	cairo_line_to (cr, v->x, v->y1);

	h = v->top;
    }

    if (h->left == v)
	go_right = TRUE;
    else
	go_right = FALSE;

    v->top = v->bottom = NULL;

    add_hsegment (cr, h, go_right);
}

static void
add_hsegment (cairo_t *cr, hsegment_t *h, gboolean go_right)
{
    vsegment_t *v;
    gboolean go_down;

    if (!h->left)
	return;

    if (go_right)
    {
	cairo_line_to (cr, h->x2, h->y);

	v = h->right;
    }
    else
    {
	cairo_line_to (cr, h->x1, h->y);

	v = h->left;
    }

    if (v->top == h)
	go_down = TRUE;
    else
	go_down = FALSE;

    h->left = h->right = NULL;

    add_vsegment (cr, v, go_down);
}

static void
region_to_path (cairo_t *cr, cairo_region_t *region)
{
    int i;
    GArray *hsegments = g_array_new (TRUE, TRUE, sizeof (hsegment_t));
    GArray *vsegments = g_array_new (TRUE, TRUE, sizeof (vsegment_t));
    hsegment_t h;
    vsegment_t v;

    h.left = h.right = NULL;
    v.top = v.bottom = NULL;

    for (i = 0; i < cairo_region_num_rectangles (region); ++i)
    {
	cairo_rectangle_int_t rect;

	cairo_region_get_rectangle (region, i, &rect);

	h.x1 = rect.x;
	h.x2 = rect.x + rect.width;

	h.y = rect.y;

	g_array_append_val (hsegments, h);

	h.y = rect.y + rect.height;

	g_array_append_val (hsegments, h);

	v.y1 = rect.y;
	v.y2 = rect.y + rect.height;

	v.x = rect.x;

	g_array_append_val (vsegments, v);

	v.x = rect.x + rect.width;

	g_array_append_val (vsegments, v);
    }

    g_array_sort (hsegments, compare_hsegments);
    g_array_sort (vsegments, compare_vsegments);

    /* Deal with overlapping hsegments */
    for (i = 1; i < hsegments->len; ++i)
    {
 	hsegment_t *this = &g_array_index (hsegments, hsegment_t, i);
 	hsegment_t *prev = &g_array_index (hsegments, hsegment_t, i - 1);

	if (this->y == prev->y && this->x1 < prev->x2)
	{
	    int tmp = prev->x2;

#if 0
	    g_print ("[%d: %d %d] and [%d: %d %d]    ->     ",
		     prev->y, prev->x1, prev->x2,
		     this->y, this->x1, this->x2);
#endif

	    prev->x2 = this->x1;
	    this->x1 = tmp;

	    if (this->x1 > this->x2)
	    {
		tmp = this->x2;
		this->x2 = this->x1;
		this->x1 = tmp;
	    }

#if 0
	    g_print ("[%d: %d %d] and [%d: %d %d]\n",
		     prev->y, prev->x1, prev->x2,
		     this->y, this->x1, this->x2);
#endif
	}
    }

    /* Coalesce abutting vsegments */
    for (i = 1; i < vsegments->len; ++i)
    {
	vsegment_t *this = &g_array_index (vsegments, vsegment_t, i);
	vsegment_t *prev = &g_array_index (vsegments, vsegment_t, i - 1);

	if (this->x == prev->x && this->y1 == prev->y2)
	{
#if 0
	    g_print ("   prev %d %d %d \n", this->x, this->y1, this->y2);
#endif

	    /* Add 'prev' into 'this' rather than the other way around.
	     * This way, the next iteration only has to look at its 'prev',
	     * not two steps behind
	     */

	    prev->y2 = prev->y1;
	    this->y1 = prev->y1;

#if 0
	    g_print ("generated segment: %d: %d %d\n", prev->x, prev->y1, prev->y2);
#endif
	}
    }

    /* Finally, for each non-empty hsegment, find the corresponding
     * vsegments
     * FIXME: this should be done with binary search
     */
    for (i = 0; i < hsegments->len; ++i)
    {
	hsegment_t *h = &g_array_index (hsegments, hsegment_t, i);
	int j;

	if (h->x1 == h->x2)
	    continue;

	g_assert (!h->left);
	g_assert (!h->right);

	for (j = 0; j < vsegments->len; ++j)
	{
	    vsegment_t *v = &g_array_index (vsegments, vsegment_t, j);

	    if (v->y1 == v->y2)
		continue;

	    if (v->y1 == h->y)
	    {
		if (v->x == h->x1)
		{
		    if (h->left)
		    {
			g_print ("  [ %d: %d %d ] already has left\n",
				 h->y, h->x1, h->x2);
		    }

		    g_assert (v->top == NULL);
		    g_assert (h->left == NULL);

		    v->top = h;
		    h->left = v;
		}

		if (v->x == h->x2)
		{
		    if (h->right)
		    {
			g_print ("  [ %d: %d %d ] already has right: %d %d %d\n",
				 h->y, h->x1, h->x2,
				 v->x, v->y1, v->y2);
		    }
		    g_assert (v->top == NULL);
		    g_assert (h->right == NULL);

		    v->top = h;
		    h->right = v;
		}
	    }

	    if (v->y2 == h->y)
	    {
		if (v->x == h->x1)
		{
		    g_assert (v->bottom == NULL);
		    g_assert (h->left == NULL);

		    v->bottom = h;
		    h->left = v;
		}

		if (v->x == h->x2)
		{
		    if (h->right)
		    {
			g_print ("  [ %d: %d %d ] already has right: %d %d %d\n",
				 h->y, h->x1, h->x2,
				 v->x, v->y1, v->y2);
		    }

		    g_assert (v->bottom == NULL);
		    g_assert (h->right == NULL);

		    v->bottom = h;
		    h->right = v;
		}
	    }
	}

	if (!h->right)
	{
	    g_print (" No right found for [ %d: %d %d ] \n",
		     h->y, h->x1, h->x2);
	}

	g_assert (h->left);
	g_assert (h->right);
    }

    for (i = 0; i < hsegments->len; ++i)
    {
	hsegment_t *h = &g_array_index (hsegments, hsegment_t, i);

	if (h->x1 != h->x2)
	{
	    g_assert (h->left);
	    g_assert (h->right);
	}
    }

    for (i = 0; i < vsegments->len; ++i)
    {
	vsegment_t *v = &g_array_index (vsegments, vsegment_t, i);

	if (v->y1 != v->y2)
	{
	    if (!v->bottom)
	    {
		g_print ("no bottom for %d %d %d\n", v->x, v->y1, v->y2);
	    }

	    g_assert (v->top);
	    g_assert (v->bottom);
	}
    }

    if (cr)
    {
	for (i = 0; i < hsegments->len; ++i)
	{
	    hsegment_t *h = &g_array_index (hsegments, hsegment_t, i);

	    if (h->left)
	    {
		cairo_move_to (cr, h->x1, h->y);
		add_hsegment (cr, h, TRUE);
	    }
	}
    }

    g_array_free (hsegments, TRUE);
    g_array_free (vsegments, TRUE);
}

static gboolean
on_expose (GtkWidget *widget, GdkEvent *event, gpointer data)
{
    cairo_t *cr;

    if (GTK_WIDGET_DRAWABLE (widget))
    {
	cairo_region_t *region;
	cairo_rectangle_int_t rect;
	int i;

	region = cairo_region_create();

	for (i = 0; i < sizeof (rects) / sizeof (rects[0]); ++i)
	    cairo_region_union_rectangle (region, &rects[i]);

	cr = gdk_cairo_create (widget->window);

#if 0
	cairo_region_get_extents (region, &rect);
#endif

#if 0
	rect.x = 100;
	rect.y = 250;
	rect.width = 50;
	rect.height = 50;

	cairo_region_subtract_rectangle (region, &rect);
#endif

	region_to_path (cr, region);

	cairo_set_source_rgba (cr, 0.2, 0.8, 0.2, 0.6);

	cairo_fill_preserve (cr);

	cairo_set_source_rgba (cr, 0.0, 0.0, 0.0, 1.0);

	cairo_stroke (cr);

#if 0
	cairo_new_path (cr);

	cairo_rectangle (cr, rect.x, rect.y, rect.width, rect.height);
	cairo_set_source_rgba (cr, 0, 0, 1, 1);
	cairo_fill (cr);
#endif

	cairo_destroy (cr);

	cairo_region_destroy (region);
    }

    return TRUE;
}

int
main (int argc, char **argv)
{
    GtkWindow *window;

    gtk_init (&argc, &argv);

    window = gtk_window_new (GTK_WINDOW_TOPLEVEL);

    gtk_window_set_default_size (window, 1200, 768);

    g_signal_connect (window, "expose_event", G_CALLBACK (on_expose), NULL);

    gtk_widget_show_all (window);

    gtk_main ();

    return 0;

}