path: root/region-iter.c

#include <stdlib.h>
#include <stdio.h>
#include <pixman.h>
#include <limits.h>

#define TRUE 1
#define FALSE 0

static const pixman_box32_t sentinel =
{
    INT_MAX, INT_MAX, INT_MAX, INT_MAX
};

typedef struct region_iter_t region_iter_t;
typedef struct row_t row_t;

struct region_iter_t
{
    int				y;
    int				first_row;
    const pixman_box32_t *	first;
    const pixman_box32_t *	last;
};

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

/* region_data manipulation */
static size_t
next_power (size_t n)
{
    size_t r = 1;

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

    return r;
}

static pixman_region32_data_t *
region_data_append (pixman_region32_data_t *data, int n, pixman_box32_t *boxes)
{
    pixman_box32_t *data_boxes;

    if (!data || data->size < data->numRects + n)
    {
	size_t new_size = next_power (n + data->numRects);

	data = realloc (data, sizeof (pixman_region32_data_t) + new_size);

	if (!data)
	    return NULL;

	data->size = new_size;
    }

    data_boxes = (pixman_box32_t *)(data + 1);
    while (n--)
	data_boxes[data->numRects++] = *boxes++;

    return data;
}

/* Region iterator */

static void
region_iter_init (region_iter_t *iter, pixman_region32_t *region)
{
    iter->y = INT_MIN;
    iter->first_row = TRUE;

    if (!region->data)
    {
	iter->first = &(region->extents);
	iter->last = &(region->extents) + 1;
    }
    else if (region->data->numRects == 0)
    {
	iter->first = &sentinel;
	iter->last = &sentinel + 1;
    }
    else
    {
	iter->first = (pixman_box32_t *)(region->data + 1);
	iter->last = iter->first + region->data->numRects;
    }
}

static void
region_iter_get_row (region_iter_t *iter, row_t *row)
{
    /* We always want an initial row of 0 boxes, so we
     * need 'first_row' to deal with the case where the
     * region starts at INT_MIN.
     */
    if (iter->first_row || iter->y < iter->first->y1)
    {
	row->first = NULL;
	row->last = NULL;
	row->y1 = iter->y;
	row->y2 = iter->first->y1;

	iter->y = iter->first->y1;
	iter->first_row = FALSE;
    }
    else
    {
	const pixman_box32_t *box;

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

	row->first = iter->first;
	row->last = box;
	row->y1 = iter->y;
	row->y2 = iter->first->y2;

	iter->y = iter->first->y2;

	if (box == iter->last)
	{
	    iter->first = &sentinel;
	    iter->last = &sentinel + 1;
	}
	else
	{
	    iter->first = box;
	}
    }
}

/* 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,
		      pixman_region32_t *region1, pixman_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);
}

static void
overlapped_iter_get_rows (overlapped_iter_t *iter, row_t *row1, row_t *row2)
{
    int y1, y2;
    
    row1->first = iter->row1.first;
    row1->last = iter->row1.last;
    row2->first = iter->row2.first;
    row2->last = iter->row2.last;

    if (iter->row1.y1 < iter->row2.y1)
    {
	y1 = iter->row1.y1;
	y2 = iter->row2.y1;

	iter->row1.y1 = iter->row2.y1;
    }
    else if (iter->row2.y1 < iter->row1.y1)
    {
	y1 = iter->row2.y1;
	y2 = iter->row1.y1;

	iter->row2.y1 = iter->row1.y1;
    }
    else if (iter->row1.y2 < iter->row2.y2)
    {
	y1 = iter->row1.y1;
	y2 = iter->row1.y2;

	iter->row1.y1 = iter->row1.y2;
	iter->row2.y1 = iter->row1.y2;
    }
    else
    {
	y1 = iter->row2.y1;
	y2 = iter->row2.y2;

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

    row1->y1 = row2->y1 = y1;
    row2->y2 = row2->y2 = y2;
    
    if (iter->row1.y1 == iter->row1.y2)
	region_iter_get_row (&iter->iter1, &iter->row1);

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

/* Segment iter */
typedef enum
{
    ROW1 = 0x01,
    ROW2 = 0x02,
    BOTH = 0x03
} segment_type_t;

typedef struct segment_iter_t segment_iter_t;
struct segment_iter_t
{
    const pixman_box32_t *p1, *p2;
    const pixman_box32_t *row1_end, *row2_end;
    int x1, x2;
};

static void
segment_iter_init (segment_iter_t *iter, const row_t *row1, const row_t *row2)
{
    iter->p1 = row1->first;
    iter->p2 = row2->first;
    iter->row1_end = row1->last;
    iter->row2_end = row2->last;

    iter->x1 = 0;
    iter->x2 = 0;
}

static pixman_bool_t
segment_iter_get_segment (segment_iter_t *iter, int *x1, int *x2, segment_type_t *type)
{
    if (iter->p1 == iter->row1_end && iter->p2 == iter->row2_end)
	return FALSE;

    if (iter->p1 == iter->row1_end)
    {
	*x1 = iter->p2->x1 + iter->x2;
	*x2 = iter->p2->x2;
	*type = ROW2;

	iter->p2++;
	iter->x2 = 0;
	return TRUE;
    }

    if (iter->p2 == iter->row2_end)
    {
	*x1 = iter->p1->x1 + iter->x1;
	*x2 = iter->p1->x2;
	*type = ROW1;

	iter->p1++;
	iter->x1 = 0;
	return TRUE;
    }

    if (iter->p1->x1 + iter->x1 < iter->p2->x1 + iter->x2)
    {
	*x1 = iter->p1->x1 + iter->x1;
	*type = ROW1;

	if (iter->p1->x2 <= iter->p2->x1 + iter->x2)
	{
	    *x2 = iter->p1->x2;
	    iter->p1++;
	    iter->x1 = 0;
	}
	else
	{
	    *x2 = iter->p2->x1 + iter->x2;
	    iter->x1 = iter->p2->x1 + iter->x2 - iter->p1->x1;
	}
	return TRUE;
    }

    if (iter->p2->x1 + iter->x2 < iter->p1->x1 + iter->x1)
    {
	*x1 = iter->p2->x1 + iter->x2;
	*type = ROW2;

	if (iter->p2->x2 <= iter->p1->x1 + iter->x1)
	{
	    *x2 = iter->p2->x2;
	    iter->p2++;
	    iter->x2 = 0;
	}
	else
	{
	    *x2 = iter->p1->x1 + iter->x1;
	    iter->x2 = iter->p1->x1 + iter->x1 - iter->p2->x1;
	}
	return TRUE;
    }

    /* If we get here, the two segments start at the same X */
    *x1 = iter->p1->x1 + iter->x1;
    *type = BOTH;

    if (iter->p1->x2 < iter->p2->x2)
    {
	*x2 = iter->p1->x2;
	iter->p1++;
	iter->x1 = 0;
	return TRUE;
    }

    if (iter->p2->x2 < iter->p1->x2)
    {
	*x2 = iter->p2->x2;
	iter->p2++;
	iter->x2 = 0;
	return TRUE;
    }

    *x2 = iter->p2->x2;
    iter->p2++;
    iter->p1++;
    iter->x2 = 0;
    iter->x1 = 0;
    return TRUE;
}

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

static void
region_op (pixman_region32_t *dst,
	   pixman_region32_t *src1,
	   pixman_region32_t *src2,
	   ops_t              op)
{
    overlapped_iter_t iter;
    row_t row1, row2;

    overlapped_iter_init (&iter, src1, src2);

    do
    {
	segment_iter_t seg_iter;
	segment_type_t type;
	int x1, x2;

	overlapped_iter_get_rows (&iter, &row1, &row2);

	segment_iter_init (&seg_iter, &row1, &row2);
	while (segment_iter_get_segment (&seg_iter, &x1, &x2, &type))
	{
	    if (op & (1 << type))
	    {
		printf ("box at %d %d %d %d %s\n",
			x1, row1.y1, x2, row1.y2, (x1 == x2 || row1.y1 == row2.y2)? "[empty]" : "");
	    }
	}
    }
    while (row1.y1 != INT_MAX);
}

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

    printf ("-=- %s\n", title);
    region_iter_init (&iter, region);
    do
    {
	int n_boxes;

	region_iter_get_row (&iter, &row);

	if (row.first == &sentinel)
	    n_boxes = 0;
	else
	    n_boxes = row.last - row.first;

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

static void
region_path (pixman_region32_t *region)
{
    region_iter_t iter;
    row_t row1, row2;

    region_iter_init (&iter, region);

    region_iter_get_row (&iter, &row1);
    do
    {
	segment_iter_t seg_iter;
	segment_type_t type;
	int x1, x2;

	region_iter_get_row (&iter, &row2);

	segment_iter_init (&seg_iter, &row1, &row2);
	while (segment_iter_get_segment (&seg_iter, &x1, &x2, &type))
	{
	    
	}

	row1 = row2;
	region_iter_get_row (&iter, &row1);
    } while (row1.y1 != INT_MAX);
}

int
main ()
{
    pixman_region32_t region;
    pixman_region32_t region1, region2;

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

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

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

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

    dump_region ("giant box", &region);

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

    dump_region ("full", &region);

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

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

    /* two rows */
    pixman_region32_init_rect (&region,
			       100, 100, 200, 50);
    pixman_region32_union_rect (&region, &region,
				100, 200, 200, 50);
    dump_region ("two rows", &region);

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

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

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

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

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

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

    pixman_region32_init_rect (&region2, 150, 50, 10, 520);
    pixman_region32_union_rect (&region2, &region2, 10, 10, 342, 23);

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

    printf ("-=- dump segments\n");

    return 0;
}