segment iters

1 files changed, 113 insertions, 134 deletions

diff --git a/region-iter.c b/region-iter.c
index 8f730cd..eba633c 100644
--- a/region-iter.c
+++ b/region-iter.c
@@ -162,9 +162,6 @@ overlapped_iter_get_rows (overlapped_iter_t *iter,
 			  const pixman_box32_t **row2_begin, const pixman_box32_t **row2_end,
 			  int *y1, int *y2)
 {
-    int py1, py2;
-    const pixman_box32_t *r1_begin, *r1_end, *r2_begin, *r2_end;
-
     *row1_begin = iter->row1_first;
     *row1_end = iter->row1_last;
     *row2_begin = iter->row2_first;
@@ -214,159 +211,126 @@ overlapped_iter_get_rows (overlapped_iter_t *iter,
     }
 }
 
-/* Region ops */
-static pixman_region32_data_t *
-add_box (pixman_region32_data_t *data, int b1, int b2, int x1, int x2, int y1, int y2)
+/* Segment iter */
+typedef struct segment_iter_t segment_iter_t;
+struct segment_iter_t
 {
-    printf ("box: %d %d (%d %d %d %d) %s\n", b1, b2, x1, y1, x2, y2,
-	    (x1 == x2 || y1 == y2)? "[empty]" : "");
-
-#if 0
-    switch (op)
-    {
-    case UNION:
-	add = b1 | b2;
-	break;
-
-    case INTERSECT:
-	add = b1 & b2;
-	break;
-
-    case SUBTRACT:
-	add = b1 & ~b2;
-	break;
-
-    case XOR:
-	add = b1 ^ b2;
-	break;
-    }
+    const pixman_box32_t *p1, *p2;
+    const pixman_box32_t *row1_end, *row2_end;
+    int x1, x2;
+};
 
-    if (add)
-	data = region_data_append (data, 1, [ x1, y1, x2, y2 ]);
+static void
+segment_iter_init (segment_iter_t *iter,
+		   const pixman_box32_t *row1_begin, const pixman_box32_t *row1_end,
+		   const pixman_box32_t *row2_begin, const pixman_box32_t *row2_end)
+{
+    iter->p1 = row1_begin;
+    iter->p2 = row2_begin;
+    iter->row1_end = row1_end;
+    iter->row2_end = row2_end;
 
-    return data;
-#endif
-    return NULL;
+    iter->x1 = 0;
+    iter->x2 = 0;
 }
 
-typedef void (* box_func_t) (int x1, int x2, int row1, int row2, void *data);
-
-/* This function processes two rows. A *segment* is a line (x1, x2)
- * where there is either a box on both rows, a box on the first row
- * and none on the other, or a box on the second row and none on the
- * first. For each such segment, the box_func function will be
- * called with the segment and with an indication of which boxes are
- * present.
- */
-static void
-process_rows (const pixman_box32_t *row1_begin, const pixman_box32_t *row1_end,
-	      const pixman_box32_t *row2_begin, const pixman_box32_t *row2_end,
-	      int y1, int y2)
+static pixman_bool_t
+segment_iter_get_segment (segment_iter_t *iter, int *x1, int *x2, int *b1, int *b2)
 {
-    pixman_region32_data_t *data = NULL;
-    const pixman_box32_t *p1, *p2;
-    int x1, x2;
-    int begin, end, row1, row2;
-
-    p1 = row1_begin;
-    p2 = row2_begin;
+    if (iter->p1 == iter->row1_end && iter->p2 == iter->row2_end)
+	return FALSE;
 
-    x1 = p1->x1;
-    x2 = p2->x1;
+    if (iter->p1 == iter->row1_end)
+    {
+	*x1 = iter->p2->x1 + iter->x2;
+	*x2 = iter->p2->x2;
+	*b1 = FALSE;
+	*b2 = TRUE;
+
+	iter->p2++;
+	iter->x2 = 0;
+	return TRUE;
+    }
 
-    while (p1 != row1_end || p2 != row2_end)
+    if (iter->p2 == iter->row2_end)
     {
-	if (p1 == row1_end)
-	{
-	    row1 = 0;
-	    row2 = 1;
-	    begin = x2;
-	    end = p2->x2;
+	*x1 = iter->p1->x1 + iter->x1;
+	*x2 = iter->p1->x2;
+	*b1 = TRUE;
+	*b2 = FALSE;
+
+	iter->p1++;
+	iter->x2 = 0;
+	return TRUE;
+    }
 
-	    x2 = p2->x2;
-	}
-	else if (p2 == row2_end)
-	{
-	    row1 = 1;
-	    row2 = 0;
-	    begin = x1;
-	    end = p1->x2;
+    if (iter->p1->x1 + iter->x1 < iter->p2->x1 + iter->x2)
+    {
+	*x1 = iter->p1->x1 + iter->x1;
+	*b1 = TRUE;
+	*b2 = FALSE;
 
-	    x1 = p1->x2;
-	}
-	else if (p1->x2 < x2)
+	if (iter->p1->x2 <= iter->p2->x1 + iter->x2)
 	{
-	    row1 = 1;
-	    row2 = 0;
-	    begin = x1;
-	    end = p1->x2;
-
-	    x1 = p1->x2;
+	    *x2 = iter->p1->x2;
+	    iter->p1++;
+	    iter->x1 = 0;
 	}
-	else if (p2->x2 < x1)
+	else
 	{
-	    row1 = 0;
-	    row2 = 1;
-	    begin = x2;
-	    end = p2->x2;
-
-	    x2 = p2->x2;
+	    *x2 = iter->p2->x1 + iter->x2;
+	    iter->x1 = iter->p2->x1 + iter->x2 - iter->p1->x1;
 	}
-	else if (x1 < x2)
-	{
-	    row1 = 1;
-	    row2 = 0;
-	    begin = x1;
-	    end = x2;
+	return TRUE;
+    }
 
-	    x1 = x2;
-	}
-	else if (x2 < x1)
-	{
-	    row1 = 0;
-	    row2 = 1;
-	    begin = x2;
-	    end = x1;
+    if (iter->p2->x1 + iter->x2 < iter->p1->x1 + iter->x1)
+    {
+	*x1 = iter->p2->x1 + iter->x2;
+	*b1 = FALSE;
+	*b2 = TRUE;
 
-	    x2 = x1;
-	}
-	else if (p1->x2 < p2->x2)
+	if (iter->p2->x2 <= iter->p1->x1 + iter->x1)
 	{
-	    row1 = 1;
-	    row2 = 1;
-	    begin = x1;
-	    end = p1->x2;
-
-	    x1 = x2 = p1->x2;
+	    *x2 = iter->p2->x2;
+	    iter->p2++;
+	    iter->x2 = 0;
 	}
 	else
 	{
-	    row1 = 1;
-	    row2 = 1;
-	    begin = x2;
-	    end = p2->x2;
-
-	    x1 = x2 = p2->x2;
+	    *x2 = iter->p1->x1 + iter->x1;
+	    iter->x2 = iter->p1->x1 + iter->x1 - iter->p2->x1;
 	}
+	return TRUE;
+    }
 
-	data = add_box (data, row1, row2, begin, end, y1, y2);
-
-	if (x1 == p1->x2 && p1 != row1_end)
-	{
-	    p1++;
+    /* If we get here, the two segments start at the same X */
+    *x1 = iter->p1->x1 + iter->x1;
+    *b1 = TRUE;
+    *b2 = TRUE;
 
-	    if (p1 != row1_end)
-		x1 = p1->x1;
-	}
-
-	if (x2 == p2->x2 && p2 != row2_end)
-	{
-	    p2++;
+    if (iter->p1->x2 < iter->p2->x2)
+    {
+	*x2 = iter->p1->x2;
+	iter->p1++;
+	iter->x1 = 0;
+	return TRUE;
+    }
 
-	    if (p2 != row2_end)
-		x2 = p2->x1;
-	}
+    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;
 }
 
 static void
@@ -383,17 +347,24 @@ region_op (pixman_region32_t *dst,
     {
 	const pixman_box32_t *row1_begin, *row1_end;
 	const pixman_box32_t *row2_begin, *row2_end;
+	segment_iter_t seg_iter;
+	int x1, x2, b1, b2;
 
 	overlapped_iter_get_rows (&iter, &row1_begin, &row1_end, &row2_begin, &row2_end, &y1, &y2);
 
-	process_rows (row1_begin, row1_end,
-		      row2_begin, row2_end,
-		      y1, y2);
+	segment_iter_init (&seg_iter, row1_begin, row1_end, row2_begin, row2_end);
+	while (segment_iter_get_segment (&seg_iter, &x1, &x2, &b1, &b2))
+	{
+	    if (b1 | b2)
+	    {
+		printf ("box: %d %d (%d %d %d %d) %s\n", b1, b2, x1, y1, x2, y2,
+			(x1 == x2 || y1 == y2)? "[empty]" : "");
+	    }
+	}
     }
     while (y1 != INT_MAX);
 }
 
-
 static void
 dump_region (const char *title, pixman_region32_t *region)
 {
@@ -490,6 +461,14 @@ main ()
 
     pixman_region32_init_rect (&region2, 150, 50, 10, 520);
 
+    region_op (NULL, &region1, &region2);
+
+    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);