/*
 * TODO:
 *
 *   - builder
 *   - move api from pixman-region.c
 *   - make it generate 'broken' regions when out of memory
 *   - test suite
 * 
 *   - consider an iterator that will combine
 *     rows where the other region has empty space
 *     Useful for speeding up intersection, and
 *     would also be useful for "contains" functions.
 *
 *     Ie., an overlapped iter that will can return one of the following:
 *         - two blank rows
 *         - one multi row, one blank row
 *         - one multi row, one one-box row 
 *         - one single row, one single row
 *
 *     We will need a subroutine row_iter_skip_to_y() that will skip
 *     to the next row with a y2 > y.
 *
 *     It may be that the existing row_t type should simply be renamed to
 *     multi_row_t since it's the same API that we'd want.
 *
 *   - an iterator that will move backwards through a region and then
 *     one that will move backwards through a row would be useful for
 *     scrolling.
 *
 *   - test suite
 *
 */
#include <stdlib.h>
#include <stdio.h>
#include <pixman.h>
#include <limits.h>
#include <assert.h>

#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif

typedef struct region_iter_t region_iter_t;
typedef struct row_t row_t;
typedef struct box32_t box32_t;
typedef struct region32_t region32_t;
typedef struct region32_data_t region32_data_t;

struct box32_t
{
    int32_t x1, y1, x2, y2;
};

struct region32_data_t
{
    long		size;
    long		numRects;
/*  box32_t		rects[size];   in memory but not explicitly declared */
};

struct region32_t
{
    box32_t          extents;
    region32_data_t  *data;
};

typedef enum
{
    FIRST,
    MIDDLE,
    EMPTY,
    FINAL,
    DONE
} state_t;

struct region_iter_t
{
    state_t			state;

    union
    {
	struct
	{
	    region32_t *	region;
	} first;
	struct
	{
	    box32_t *	first;
	    box32_t *	last;
	} middle;
	struct
	{
	    int			y1;
	} final;
    } u;
};

struct row_t
{
    const box32_t *	first;
    const box32_t *	last;
    int				y1;
    int				y2;
};

/* region_data manipulation */

#define BROKEN_DATA  ((region32_data_t *)0x01)

typedef struct region_builder_t region_builder_t;

struct region_builder_t
{
    region32_data_t *	data;
    int			second_last_row;
    int			last_row;
};

static size_t
next_power (size_t n)
{
    size_t r = 1;

    while (r < n)
	r <<= 1;

    return r;
}

static void *
realloc_ab_plus_c (void *m, unsigned int a, unsigned int b, unsigned int c)
{
    if (b && a >= INT32_MAX / b)
	return NULL;

    if (c >= INT32_MAX - a * b)
	return NULL;

    return realloc (m, a * b + c);
}

static region32_data_t *
region_data_append (region32_data_t *data, int n)
{
    size_t new_size, n_rects;

    n_rects = data? data->numRects : 0;
    new_size = next_power (n_rects + n);

    if (data && data->size == new_size)
	return data;

    if ((data = realloc_ab_plus_c (
	     data, new_size, sizeof (box32_t),
	     sizeof (region32_data_t))))
    {
	data->numRects = n_rects;
	data->size = new_size;
    }

    return data;
}

static void
region_builder_init (region_builder_t *builder)
{
    builder->data = NULL;
    builder->second_last_row = -1;
    builder->last_row = 0;
}

static void
region_builder_coalesce_rows (region_builder_t *builder)
{
    region32_data_t *data = builder->data;
    box32_t *old, *new;
    pixman_bool_t coalesce;
    int i, n;

    if (!data)
	return;

    n = builder->last_row - builder->second_last_row;
    if (builder->second_last_row == -1 ||
	data->numRects - builder->last_row != n)
    {
	coalesce = FALSE;
    }
    else
    {
	old = (box32_t *)(data + 1) + builder->second_last_row;
	new = (box32_t *)(data + 1) + builder->last_row;

	coalesce = TRUE;
	for (i = 0; i < n; ++i)
	{
	    if (new[i].y1 != old[i].y2 ||
		new[i].x1 != old[i].x1 ||
		new[i].x2 != old[i].x2)
	    {
		coalesce = FALSE;
		break;
	    }
	}
    }

    if (coalesce)
    {
	for (i = 0; i < n; ++i)
	    old[i].y2 = new[i].y2;

	data->numRects -= n;
    }
    else
    {
	builder->second_last_row = builder->last_row;
	builder->last_row = data->numRects;
    }
}

static pixman_bool_t
region_builder_add_box (region_builder_t *builder,
			int x1, int y1, int x2, int y2)
{
    box32_t *last_box;
    region32_data_t *data;

    if (builder->data == BROKEN_DATA)
	return FALSE;

    if (!(data = region_data_append (builder->data, 1)))
    {
	free (builder->data);
	builder->data = BROKEN_DATA;
	return FALSE;
    }

    builder->data = data;

    if (data->numRects == 0)
	last_box = NULL;
    else
	last_box = ((box32_t *)(data + 1)) + data->numRects - 1;

    if (last_box)
    {
	if (y1 != last_box->y1)
	{
	    region_builder_coalesce_rows (builder);
	}
	else if (x1 == last_box->x2)
	{
	    last_box->x2 = x2;
	    return TRUE;
	}
    }

    last_box = (box32_t *)(data + 1) + data->numRects++;
    last_box->x1 = x1;
    last_box->y1 = y1;
    last_box->x2 = x2;
    last_box->y2 = y2;

    return TRUE;
}

static pixman_bool_t
region_builder_add_row (region_builder_t *builder, const row_t *row)
{
    box32_t *last_box;
    const box32_t *first;
    region32_data_t *data;
    int n_boxes;

    if (builder->data == BROKEN_DATA)
	return FALSE;

    n_boxes = row->last - row->first;
    
    if (!(data = region_data_append (builder->data, n_boxes)))
    {
	free (builder->data);
	builder->data = BROKEN_DATA;
	return FALSE;
    }

    builder->data = data;

    if (data->numRects == 0)
	last_box = NULL;
    else
	last_box = ((box32_t *)(data + 1)) + data->numRects - 1;

    first = row->first;
    if (last_box)
    {
	if (row->y1 != last_box->y1)
	{
	    region_builder_coalesce_rows (builder);
	}
	else if (row->first->x1 == last_box->x2)
	{
	    last_box->x2 = row->first->x2;
	    first = row->first + 1;
	    n_boxes--;
	}
    }

    while (first != row->last)
    {
	box32_t *box = (box32_t *)(data + 1) + data->numRects++;

	box->x1 = first->x1;
	box->x2 = first->x2;
	box->y1 = row->y1;
	box->y2 = row->y2;

	first++;
    }

    return TRUE;
}

static const box32_t region32_empty_box_ = { 0, 0, 0, 0 };
static const region32_data_t region32_empty_data_ = { 0, 0 };
#if defined (__llvm__) && !defined (__clang__)
static const volatile region_data32_t region32_broken_data_ = { 0, 0 };
#else
static const region32_data_t region32_broken_data_ = { 0, 0 };
#endif

static box32_t *region32_empty_box =
    (box32_t *)&region32_empty_box_;
static region32_data_t *region32_empty_data =
    (region32_data_t *)&region32_empty_data_;
static region32_data_t *region32_broken_data =
    (region32_data_t *)&region32_broken_data_;

void
region32_init (region32_t *region)
{
    region->extents = *region32_empty_box;
    region->data = region32_empty_data;
}

void
region32_fini (region32_t *region)
{
    GOOD (region);
    FREE_DATA (region);
}

#warning FIXME: this used to be pixman_log_error
#define log_error(s)
    
void
region32_init_rect (region32_t *	region,
		    int			x,
		    int			y,
		    unsigned int	width,
		    unsigned int	height)
{
    region->extents.x1 = x;
    region->extents.y1 = y;
    region->extents.x2 = x + width;
    region->extents.y2 = y + height;

    if (!GOOD_RECT (&region->extents))
    {
        if (BAD_RECT (&region->extents))
            log_error ("Invalid rectangle passed");
        region32_init (region);
        return;
    }

    region->data = NULL;
}

static pixman_bool_t
region_builder_finish (region_builder_t *builder, region32_t *region)
{
    if (builder->data == BROKEN_DATA)
	return FALSE;

    region_builder_coalesce_rows (builder);

    if (!builder->data || builder->data->numRects == 0)
    {
	region32_init (region);
	return TRUE;
    }
    else if (builder->data->numRects == 1)
    {
	box32_t *b = (box32_t *)(builder->data + 1);

	region32_init_rect (
	    region, b->x1, b->y1, b->x2 - b->x1, b->y2 - b->y1);

	return TRUE;
    }
    else
    {
	box32_t extents = { INT32_MAX, INT32_MAX, INT32_MIN, INT32_MIN };
	int i;

	for (i = 0; i < builder->data->numRects; ++i)
	{
	    box32_t *b = (box32_t *)(builder->data + 1 + i);

	    if (b->x1 < extents.x1)
		extents.x1 = b->x1;
	    if (b->y1 < extents.y1)
		extents.y1 = b->y1;
	    if (b->x2 > extents.x2)
		extents.x2 = b->x2;
	    if (b->y2 > extents.y2)
		extents.y2 = b->y2;
	}

	region->extents = extents;
	region->data = builder->data;

	return TRUE;
    }
}

/* Region iterator */
static void
region_iter_init (region_iter_t *iter, region32_t *region)
{
    iter->state = FIRST;
    iter->u.first.region = region;
}

static pixman_bool_t
region_iter_get_row (region_iter_t *iter, row_t *row)
{
    box32_t *first;
    box32_t *last;
    box32_t *box;

    switch (iter->state)
    {
    case FIRST:
	row->y1 = INT_MIN;
	row->first = NULL;
	row->last = NULL;

	if (!iter->u.first.region->data)
	{
	    iter->state = MIDDLE;
	    first = &(iter->u.first.region->extents);
	    last = &(iter->u.first.region->extents) + 1;
	}
	else if (iter->u.first.region->data->numRects == 0)
	{
	    row->y2 = INT_MAX;
	    iter->state = DONE;
	}
	else
	{
	    iter->state = MIDDLE;
	    first = (box32_t *)(iter->u.first.region->data + 1);
	    last = first + iter->u.first.region->data->numRects;
	}

	if (iter->state == MIDDLE)
	{
	    row->y2 = first->y1;
	    iter->u.middle.first = first;
	    iter->u.middle.last = last;
	}
	break;

    case MIDDLE:
	assert (iter->u.middle.last - iter->u.middle.first > 0);

	for (box = iter->u.middle.first; box != iter->u.middle.last; ++box)
	{
	    if (box->y1 != iter->u.middle.first->y1)
		break;
	}

	row->y1 = iter->u.middle.first->y1;
	row->y2 = iter->u.middle.first->y2;
	row->first = iter->u.middle.first;
	row->last = box;

	if (box != iter->u.middle.last)
	{
	    if (box->y1 != row->y2)
		iter->state = EMPTY;

	    iter->u.middle.first = box;
	}
	else
	{
	    iter->state = FINAL;
	    iter->u.final.y1 = row->y2;
	}
	break;

    case EMPTY:
	row->y1 = (iter->u.middle.first - 1)->y2;
	row->y2 = iter->u.middle.first->y1;
	row->first = NULL;
	row->last = NULL;

	iter->state = MIDDLE;
	break;

    case FINAL:
	row->first = NULL;
	row->last = NULL;
	row->y1 = iter->u.final.y1;
	row->y2 = INT_MAX;
	iter->state = DONE;
	break;

    case DONE:
	return FALSE;
    }

    return TRUE;
}

/* In time O(log n), locate the first box whose y2 is greater than y.
 * Return @end if no such box exists.
 */
static box32_t *
find_box_for_y (box32_t *begin, box32_t *end, int y)
{
    while (end - begin > 0)
    {
	box32_t *mid = begin + (end - begin) / 2;

	if (mid->y2 > y)
	    end = mid;
	else
	    begin = mid + 1;
    }

    return end;
}

/* Skips forward to the first row whose y2 > @y */
static pixman_bool_t
region_iter_get_row_for_y (region_iter_t *iter, int y, row_t *row)
{
    box32_t *box;

    while (iter->state != MIDDLE)
    {
	if (!region_iter_get_row (iter, row))
	    return FALSE;

	if (row->y2 > y)
	    return TRUE;
    }

    box = find_box_for_y (iter->u.middle.first, iter->u.middle.last, y);

    if (box != iter->u.middle.last)
    {
	if (box->y1 > y)
	    iter->state = EMPTY;

	iter->u.middle.first = box;
    }
    else
    {
	iter->state = FINAL;
	iter->u.final.y1 = row->y2;
    }

    return region_iter_get_row (iter, row);
}

/* Overlapped iter
 */
typedef struct overlapped_iter_t overlapped_iter_t;
struct overlapped_iter_t
{
    region_iter_t iter1;
    region_iter_t iter2;
    row_t	  row1;
    row_t	  row2;
};

static void
overlapped_iter_init (overlapped_iter_t *iter,
		      region32_t *region1, region32_t *region2)
{
    region_iter_init (&iter->iter1, region1);
    region_iter_init (&iter->iter2, region2);

    region_iter_get_row (&iter->iter1, &iter->row1);
    region_iter_get_row (&iter->iter2, &iter->row2);
}

#define MIN(a, b) (((a) < (b)) ? (a) : (b))

static pixman_bool_t
overlapped_iter_get_rows (overlapped_iter_t *iter, row_t *row1, row_t *row2)
{
    int m;

    *row1 = iter->row1;
    *row2 = iter->row2;

    m = MIN (iter->row1.y2, iter->row2.y2);

    row1->y1 = row2->y1 = iter->row1.y1;
    row1->y2 = row2->y2 = m;

    iter->row2.y1 = iter->row1.y1 = m;

    if (iter->row1.y1 == iter->row1.y2)
    {
	if (!region_iter_get_row (&iter->iter1, &iter->row1))
	    return FALSE;
    }

    if (iter->row2.y1 == iter->row2.y2)
    {
	if (!region_iter_get_row (&iter->iter2, &iter->row2))
	    return FALSE;
    }

    return TRUE;
}

/* Row iter */
typedef enum
{
    /* These are used when iterating a single row */
    OFF = 0x00,
    ON = 0x01,

    /* These are used when iterating two rows */
    ROW1 = 0x01,
    ROW2 = 0x02,
    BOTH = 0x03
} segment_type_t;

typedef struct segment_t segment_t;
struct segment_t
{
    segment_type_t type;
    int x1, x2;
};

typedef struct row_iter_t row_iter_t;

struct row_iter_t
{
    state_t	state;

    union
    {
	struct
	{
	    const row_t *row;
	} first;

	struct
	{
	    const box32_t *first;
	    const box32_t *last;
	} middle;

	struct
	{
	    int x1;
	} final;
    } u;
};

static void
row_iter_init (row_iter_t *iter, const row_t *row)
{
    iter->state = FIRST;

    iter->u.first.row = row;
}

static pixman_bool_t
row_iter_get_segment (row_iter_t *iter, segment_t *segment)
{
    switch (iter->state)
    {
    case FIRST:
	segment->type = OFF;
	segment->x1 = INT_MIN;

	if (iter->u.first.row->first)
	{
	    const box32_t *first, *last;

	    segment->x2 = iter->u.first.row->first->x1;

	    iter->state = MIDDLE;

	    first = iter->u.first.row->first;
	    last = iter->u.first.row->last;

	    iter->u.middle.first = first;
	    iter->u.middle.last = last;
	}
	else
	{
	    segment->x2 = INT_MAX;
	    iter->state = DONE;
	}
	break;

    case MIDDLE:
	segment->type = ON;
	segment->x1 = iter->u.middle.first->x1;
	segment->x2 = iter->u.middle.first->x2;

	iter->u.middle.first++;
	if (iter->u.middle.first == iter->u.middle.last)
	{
	    iter->state = FINAL;
	    iter->u.final.x1 = segment->x2;
	}
	else
	{
	    iter->state = EMPTY;
	}
	break;

    case EMPTY:
	segment->type = OFF;
	segment->x1 = (iter->u.middle.first - 1)->x2;
	segment->x2 = iter->u.middle.first->x1;
	iter->state = MIDDLE;
	break;

    case FINAL:
	segment->type = OFF;
	segment->x1 = iter->u.final.x1;
	segment->x2 = INT_MAX;
	iter->state = DONE;
	break;

    case DONE:
	return FALSE;
	break;
    }
    return TRUE;
}

/* Segment iter */
typedef struct segment_iter_t segment_iter_t;
struct segment_iter_t
{
    row_iter_t	row1;
    row_iter_t	row2;
    segment_t	segment1;
    segment_t	segment2;
};

static void
segment_iter_init (segment_iter_t *iter, const row_t *row1, const row_t *row2)
{
    row_iter_init (&iter->row1, row1);
    row_iter_init (&iter->row2, row2);

    row_iter_get_segment (&iter->row1, &iter->segment1);
    row_iter_get_segment (&iter->row2, &iter->segment2);
}

static pixman_bool_t
segment_iter_get_segment (segment_iter_t *iter, segment_t *segment)
{
    int m = MIN (iter->segment1.x2, iter->segment2.x2);

    segment->x1 = iter->segment1.x1;
    segment->x2 = m;

    segment->type = (iter->segment1.type | (iter->segment2.type << 1));

    iter->segment1.x1 = iter->segment2.x1 = m;

    if (iter->segment1.x1 == iter->segment1.x2)
    {
	if (!row_iter_get_segment (&iter->row1, &iter->segment1))
	    return FALSE;
    }

    if (iter->segment2.x1 == iter->segment2.x2)
    {
	if (!row_iter_get_segment (&iter->row2, &iter->segment2))
	    return FALSE;
    }

    return TRUE;
}


pixman_bool_t
region_contains_point (region32_t *region,
		       int                x,
		       int                y,
		       box32_t    *box)
{
    region_iter_t iter;
    row_t row;

    region_iter_init (&iter, region);
    if (region_iter_get_row_for_y (&iter, y, &row) && row.y1 < y)
    {
	const box32_t *b;

	for (b = row.first; b != row.last && b->x1 <= x; ++b)
	{
	    if (x < b->x2)
	    {
		if (box)
		    *box = *b;

		return TRUE;
	    }
	}
    }

    return FALSE;
}

pixman_region_overlap_t
region_contains_rectangle (region32_t *region,
			   box32_t    *prect)
{
    pixman_bool_t part_in = FALSE;
    pixman_bool_t part_out = FALSE;
    region_iter_t iter;
    row_t row;

    region_iter_init (&iter, region);
    if (!region_iter_get_row_for_y (&iter, prect->y1, &row))
	return PIXMAN_REGION_OUT;

    if (row.y1 >= prect->y2)
	return PIXMAN_REGION_OUT;
    
    do
    {
	row_iter_t row_iter;
	segment_t segment;

	row_iter_init (&row_iter, &row);
	while (row_iter_get_segment (&row_iter, &segment) &&
	       segment.x1 <= prect->x2)
	{
	    if (segment.x2 >= prect->x1)
	    {
		if (segment.type == ON)
		    part_in = TRUE;
		else
		    part_out = TRUE;
	    }

	    if (part_in && part_out)
		return PIXMAN_REGION_PART;
	}
    }
    while (region_iter_get_row (&iter, &row) && row.y1 < prect->y2);

    if (part_in)
	return PIXMAN_REGION_IN;
    else
	return PIXMAN_REGION_OUT;
}

typedef enum
{
    INTERSECT	= (1 << BOTH),
    SUBTRACT	=		(1 << ROW1),
    XOR		=		(1 << ROW1) | (1 << ROW2),
    UNION	= (1 << BOTH) | (1 << ROW1) | (1 << ROW2),
} ops_t;

static pixman_bool_t
region_op (ops_t              op,
	   region32_t *dst,
	   region32_t *src1,
	   region32_t *src2)
{
    overlapped_iter_t iter;
    region_builder_t builder;
    row_t row1, row2;

    region_builder_init (&builder);

    overlapped_iter_init (&iter, src1, src2);
    while (overlapped_iter_get_rows (&iter, &row1, &row2))
    {
	segment_iter_t seg_iter;
	segment_t segment;

	if (!row1.first && !row2.first)
	{
	    /* Both are blank - nothing to do */
	}
	else if (!row1.first)
	{
	    /* row1 is blank, row2 is not */
	    if (op & (1 << ROW2))
		region_builder_add_row (&builder, &row2);
	}
	else if (!row2.first)
	{
	    /* row2 is blank, row1 is not */
	    if (op & (1 << ROW1))
		region_builder_add_row (&builder, &row1);
	}
	else
	{
	    /* Both are non blank */
	    segment_iter_init (&seg_iter, &row1, &row2);
	    while (segment_iter_get_segment (&seg_iter, &segment))
	    {
		if (op & (1 << segment.type))
		{
		    region_builder_add_box (
			&builder, segment.x1, row1.y1, segment.x2, row1.y2);
		}
	    }
	}
    }

    region32_fini (dst);

    return region_builder_finish (&builder, dst);
}

static pixman_bool_t
make_region_from_sorted (region32_t *region,
			 const box32_t *boxes, int n_boxes)
{
    if (n_boxes == 1)
    {
	region32_init_rect (region,
			    boxes[0].x1, boxes[0].y1,
			    boxes[0].x2, boxes[0].y2);
    }
    else
    {
	region32_t tmp;
	int n_left = n_boxes / 2;
	int n_right = n_boxes - n_left;

	if (!make_region_from_sorted (region, boxes, n_left))
	    return FALSE;

	if (!make_region_from_sorted (&tmp, boxes + n_left, n_right))
	{
	    region32_fini (region);
	    return FALSE;
	}

	if (!region_op (UNION, region, region, &tmp))
	{
	    region32_fini (region);
	    region32_fini (&tmp);

	    return FALSE;
	}
    }

    return TRUE;
}

static int
compare_boxes (const void *box1v, const void *box2v)
{
    const box32_t *box1 = box1v;
    const box32_t *box2 = box2v;

    if (box1->y1 == box2->y1)
	return 0;
    else if (box1->y1 < box2->y2)
	return -1;
    else
	return 1;
}

pixman_bool_t
region_from_boxes (region32_t *region,
		   const box32_t *boxes, int n_boxes)
{
    if (n_boxes == 0)
    {
	region32_init (region);
	return TRUE;
    }
    else
    {
	box32_t *copy = malloc (sizeof (box32_t) * n_boxes);
	int displacement, i;
	pixman_bool_t ret;

	if (!copy)
	    return FALSE;

	displacement = 0;
	for (i = 0; i < n_boxes; ++i)
	{
	    const box32_t *box = boxes + i;

	    if (box->x1 >= box->x2 || box->y1 >= box->y2)
		displacement++;
	    else
		copy[i - displacement] = boxes[i];
	}

	qsort (copy, i - displacement, sizeof (box32_t), compare_boxes);

	ret = make_region_from_sorted (region, copy, i - displacement);

	free (copy);

	return ret;
    }
}

typedef struct corner_t corner_t;

struct corner_t
{
    int		x;
    int		y;

    int		next;
};

static int *
add_active (int *actives, int *n_actives, int corner)
{
    int idx = (*n_actives)++;

    actives = realloc (actives, next_power (*n_actives) * sizeof (int));

    actives[idx] = corner;

    return actives;
}

static corner_t *
add_corners (corner_t *corners, int *n_corners, int *new1, int *new2)
{
    *new1 = (*n_corners)++;
    *new2 = (*n_corners)++;

    return realloc (corners, next_power (*n_corners) * sizeof (corner_t));
}

static corner_t *
region_path (region32_t *region, int *n)
{
    region_iter_t iter;
    row_t row1, row2;
    corner_t *corners = NULL;
    int *active = NULL;
    int n_corners = 0;
    int n_active = 0;

    region_iter_init (&iter, region);

    active = NULL;
    n_active = 0;

    corners = NULL;
    n_corners = 0;

    region_iter_get_row (&iter, &row1);
    while (region_iter_get_row (&iter, &row2))
    {
	segment_iter_t seg_iter;
	segment_t segment;

	int *old_active;
	int old_n_active;
	int current;

	old_active = active;
	old_n_active = n_active;

	active = NULL;
	n_active = 0;
	current = 0;

	segment_iter_init (&seg_iter, &row1, &row2);
	while (segment_iter_get_segment (&seg_iter, &segment))
	{
	    if (segment.type == ROW1 || segment.type == ROW2)
	    {
		int c1, c2;
		int p1 = -1;
		int p2 = -1;

		while (current < old_n_active &&
		       corners[old_active[current]].x <= segment.x2)
		{
		    int c = old_active[current];

		    if (corners[c].x == segment.x1)
			p1 = c;
		    else if (corners[c].x == segment.x2)
			p2 = c;
		    else
			active = add_active (active, &n_active, c);

		    current++;
		}

		corners = add_corners (corners, &n_corners, &c1, &c2);
		corners[c1].x = segment.x1;
		corners[c1].y = row1.y2;
		corners[c2].x = segment.x2;
		corners[c2].y = row1.y2;

		if (p1 != -1)
		{
		    if (segment.type == ROW1)
			corners[p1].next = c1;
		    else
			corners[c1].next = p1;
		}
		else
		{
		    active = add_active (active, &n_active, c1);
		}

		if (p2 != -1)
		{
		    if (segment.type == ROW1)
			corners[c2].next = p2;
		    else
			corners[p2].next = c2;
		}
		else
		{
		    active = add_active (active, &n_active, c2);
		}

		if (segment.type == ROW1)
		    corners[c1].next = c2;
		else
		    corners[c2].next = c1;
	    }
	}

	while (current < old_n_active)
	    active = add_active (active, &n_active, old_active[current++]);

	free (old_active);
	row1 = row2;
    }

    *n = n_corners;
    return corners;
}

static void
dump_region (const char *title, region32_t *region)
{
    region_iter_t iter;
    row_t row;

    printf (" =- %s\n", title);

    region_iter_init (&iter, region);
    while (region_iter_get_row (&iter, &row))
    {
	int n_boxes = row.last - row.first;

	printf ("Row of %d boxes %d %d\n", n_boxes, row.y1, row.y2);
    }
}

static void
dump_corners (corner_t *corners, int n_corners)
{
    int i;

    printf ("%d (%p - %p)\n", n_corners, corners, corners + n_corners);

    for (i = 0; i < n_corners; ++i)
    {
	corner_t *corner = &(corners[i]);

	while (corner->next != -1)
	{
	    int next = corner->next;

	    printf ("   %p Corner: %d %d\n", corner, corner->x, corner->y);

	    corner->next = -1;
	    corner = &(corners[next]);
	}
    }
}

/* Convenience function for performing union of region with a
 * single rectangle
 */
pixman_bool_t
region32_union_rect (region32_t *   dest,
		     region32_t *   source,
		     int            x,
		     int            y,
		     unsigned int   width,
		     unsigned int   height)
{
    region32_t region;

    region.extents.x1 = x;
    region.extents.y1 = y;
    region.extents.x2 = x + width;
    region.extents.y2 = y + height;

    if (!GOOD_RECT (&region.extents))
    {
        if (BAD_RECT (&region.extents))
            log_error ("Invalid rectangle passed");
	return region32_copy (dest, source);
    }

    region.data = NULL;

    return region_op (UNION, dest, source, &region);
}

pixman_bool_t
region32_copy (region32_t *dst, region32_t *src)
{
    GOOD (dst);
    GOOD (src);

    if (dst == src)
	return TRUE;
    
    dst->extents = src->extents;

    if (!src->data || !src->data->size)
    {
	FREE_DATA (dst);
	dst->data = src->data;
	return TRUE;
    }
    
    if (!dst->data || (dst->data->size < src->data->numRects))
    {
	FREE_DATA (dst);

	dst->data = alloc_data (src->data->numRects);

	if (!dst->data)
	    return pixman_break (dst);

	dst->data->size = src->data->numRects;
    }

    dst->data->numRects = src->data->numRects;

    memmove ((char *)PIXREGION_BOXPTR (dst), (char *)PIXREGION_BOXPTR (src),
             dst->data->numRects * sizeof(box_type_t));

    return TRUE;
}

#ifndef NO_MAIN

int
main ()
{
    region32_t region;
    region32_t region1, region2;
    corner_t *corners;
    int n_corners;

    /* empty region */
    region32_init (&region);
    dump_region ("empty region", &region);

    /* one box */
    region32_init_rect (&region, -50, -50, 100, 100);
    dump_region ("one box", &region);

    /* Slightly more complex region */
    region32_init_rect (&region, 0, 0, 100, 100);
    region32_union_rect (&region, &region, 50, 50, 100, 100);
    dump_region ("slightly more complex", &region);

    /* INT_MAX box */
    region32_init_rect (&region,
			       100, 100, INT_MAX - 100, INT_MAX - 100);

    dump_region ("giant box", &region);

    /* full region */
    region32_init_rect (&region,
			       INT_MIN, INT_MIN, INT_MAX, INT_MAX);

    dump_region ("full", &region);

    /* Even fuller */
    region32_init_rect (&region,
			INT_MIN, INT_MIN, INT_MAX, INT_MAX);
    region32_union_rect (&region, &region,
			 -1, -1, INT_MAX, INT_MAX);
    region32_union_rect (&region, &region,
			 INT_MIN, -1, INT_MAX, INT_MAX);
    region32_union_rect (&region, &region,
			 -1, INT_MIN, INT_MAX, INT_MAX);
    dump_region ("fuller", &region);

    /* Covering all */
    region32_init_rect (&region,
			0, INT_MIN, 10, INT_MAX);
    region32_union_rect (&region, &region,
			 20, -234, 10, INT_MAX);
    region32_union_rect (&region, &region,
			 50, INT_MAX - 234, 10, 234);
    dump_region ("all of the y axis", &region);

    /* two rows */
    region32_init_rect (&region,
			100, 100, 200, 50);
    region32_union_rect (&region, &region,
			 100, 200, 200, 50);
    dump_region ("two rows", &region);

    /* op */
    printf ("-=- op\n");
    region32_init_rect (&region1, 100, 100, 200, 200);
    region32_init_rect (&region2, 200, 200, 200, 200);

    region_op (UNION, &region, &region1, &region2);

    dump_region ("union: ", &region);

    printf ("-=- op2\n");
    region32_init_rect (&region1, 100, 100, 200, 200);
    region32_union_rect (&region1, &region1, 100, 400, 200, 50);

    dump_region ("input: ", &region1);

    region32_init_rect (&region2, 150, 50, 10, 520);

    region_op (INTERSECT, &region, &region1, &region2);

    printf ("-=- op2\n");
    region32_init_rect (&region1, 100, 100, 200, 200);
    region32_union_rect (&region1, &region1, 100, 400, 200, 50);

    region32_init_rect (&region2, 150, 50, 10, 520);
    region32_union_rect (&region2, &region2, 10, 10, 342, 23);

    region_op (XOR, &region, &region1, &region2);

    printf ("-=- path\n");
    region32_init_rect (&region1, 100, 100, 200, 200);

    corners = region_path (&region1, &n_corners);

    dump_corners (corners, n_corners);

    /* Slightly more complex region */
    region32_init_rect (&region, 0, 0, 100, 100);
    region32_union_rect (&region, &region, 50, 50, 100, 100);

    assert (region_contains_point (&region, 75, 75, NULL));
    assert (!region_contains_point (&region, 25, 125, NULL));
    
    printf ("-=- more complex path\n");

    corners = region_path (&region, &n_corners);

    dump_corners (corners, n_corners);

    /* even more complex region */
    region32_init_rect (&region, 0, 0, 100, 100);
    region32_union_rect (&region, &region, 50, 50, 100, 100);
    region32_union_rect (&region, &region, 200, 0, 50, 50);

    printf ("-=- more complex path\n");

    corners = region_path (&region, &n_corners);

    dump_corners (corners, n_corners);

    /* even more complex region */
    region32_init_rect (&region, 0, 0, 100, 100);
    region32_union_rect (&region, &region, 50, 50, 100, 100);
    region32_union_rect (&region, &region, 150, 0, 50, 50);
    region32_init_rect (&region2, 75, 75, 50, 50);
    region32_subtract (&region, &region, &region2);

    printf ("-=- more complex path\n");

    corners = region_path (&region, &n_corners);

    dump_corners (corners, n_corners);

    return 0;
}

#endif