/*
 * A new range can compare with existing an existing range in 13
 *  different ways.  Handling them all leads to a _lot_ of code.
 *  Rather than multiple hundreds of lines of nested ifs and code to
 *  handle each one, we basically generate new bands for the new rect,
 *  merging bands as we generate them.  (Similar remarks, but simpler,
 *  apply to rects within a band.)
 *
 * Even in this paradigm, though, we care about the kinds of overlap
 *  between existing intervals and the new interval.  The 13 kinds
 *  (e=existing, n=new, X=both):
 *
 *	..nnnn.eeee.......	1
 *	...nnnneeee.......	2
 *	.....nnXXee.......	3
 *	.....nnXXXX.......	4
 *	.....nnXXXXnn.....	5
 *	.......XXee.......	6
 *	.......XXXX.......	7
 *	.......XXXXnn.....	8
 *	.......eXXe.......	9
 *	.......eeXX.......	10
 *	.......eeXXnn.....	11
 *	.......eeeennnn...	12
 *	.......eeee.nnnn..	13
 *
 *  Note that this enumeration applies to only one band; the presence
 *  of other bands, and what happens when a band has a new rectangle
 *  applied to it, calls for subcases of many of these.
 */

#include <stdlib.h>

#include "rectregion.h"

#ifdef TRACE
#include <stdio.h>
static int trace = 0;
#endif

typedef struct band BAND;
typedef struct rect RECT;

struct rect {
#ifdef TRACE
  RECT *threadf;
  RECT *threadb;
  int line;
#endif
  RECT *link;
  double x0;
  double x1;
  } ;

struct band {
#ifdef TRACE
  BAND *threadf;
  BAND *threadb;
  int line;
#endif
  BAND *link;
  double y0;
  double y1;
  RECT *rects;
  } ;

struct rectregion {
#ifdef TRACE
  RECTREGION *threadf;
  RECTREGION *threadb;
#endif
  BAND *bands;
  } ;

#ifdef TRACE
static RECT *recthead = 0;
static BAND *bandhead = 0;
static RECTREGION *rectregionhead = 0;
#endif

/*
 * panic() exists because there is something wrong with gdb and/or libc
 *  and/or the compiler on one of my dev machines: when calling
 *  abort(), the stack is useless - gdb thinks abort() is the only
 *  frame on the stack, making it impossible to easily find out where
 *  it's being called from, and this is true even if I set a breakpoint
 *  on entry to abort().  So, instead, if we're in a debug version (as
 *  indicated by TESTBED), we throw a routine of our own, panic(),
 *  between the code and abort(), so I can set a breakpoint on panic
 *  and actually see the call stack.  (If not, we #define panic to
 *  abort, so there's no run-time cost.)  I'd be tempted to leave
 *  panic() in even in non-debug versions, but there's little point;
 *  the stack in the coredump will still be trashed.
 *
 * Grrr.
 */
#ifdef TESTBED
static void panic(void) __attribute__((__noreturn__));
static void panic(void)
{
 abort();
}
#else
#define panic abort
#endif

#ifdef TRACE
#define new_rect(a,b) new_rect_((a),(b),__LINE__)
static RECT *new_rect_(double x0, double x1, int lno)
#else
static RECT *new_rect(double x0, double x1)
#endif
{
 RECT *r;

 r = malloc(sizeof(RECT));
#ifdef TRACE
 r->threadf = recthead;
 r->threadb = 0;
 r->line = lno;
 if (recthead) recthead->threadb = r;
 recthead = r;
#endif
 r->x0 = x0;
 r->x1 = x1;
 r->link = 0;
 return(r);
}

static void free_rect(RECT *r)
{
#ifdef TRACE
 if (r->threadf) r->threadf->threadb = r->threadb;
 if (r->threadb) r->threadb->threadf = r->threadf; else recthead = r->threadf;
 r->line = -1;
#endif
 free(r);
}

#ifdef TRACE
#define new_band(a,b) new_band_((a),(b),__LINE__)
static BAND *new_band_(double y0, double y1, int lno)
#else
static BAND *new_band(double y0, double y1)
#endif
{
 BAND *b;

 b = malloc(sizeof(BAND));
#ifdef TRACE
 b->threadf = bandhead;
 b->threadb = 0;
 b->line =lno;
 if (bandhead) bandhead->threadb = b;
 bandhead = b;
#endif
 b->y0 = y0;
 b->y1 = y1;
 b->link = 0;
 b->rects = 0;
 return(b);
}

static void free_band(BAND *b)
{
 RECT *r;

 while ((r = b->rects))
  { b->rects = r->link;
    free_rect(r);
  }
#ifdef TRACE
 if (b->threadf) b->threadf->threadb = b->threadb;
 if (b->threadb) b->threadb->threadf = b->threadf; else bandhead = b->threadf;
 b->line = -1;
#endif
 free(b);
}

static BAND *new_1rect_band(double y0, double y1, double x0, double x1)
{
 BAND *b;

 b = new_band(y0,y1);
 b->rects = new_rect(x0,x1);
 return(b);
}

static int bands_x_match(BAND *a, BAND *b)
{
 RECT *ra;
 RECT *rb;

 ra = a->rects;
 rb = b->rects;
 while (1)
  { if (! ra) return(!rb);
    if (! rb) return(0);
    if ((ra->x0 != rb->x0) || (ra->x1 != rb->x1)) return(0);
    ra = ra->link;
    rb = rb->link;
  }
}

static RECT *copy_rect(RECT *r)
{
 return(new_rect(r->x0,r->x1));
}

static BAND *copy_band(BAND *b)
{
 BAND *c;
 RECT *r;
 RECT *n;
 RECT **t;

 c = new_band(b->y0,b->y1);
 t = &c->rects;
 for (r=b->rects;r;r=r->link)
  { n = copy_rect(r);
    *t = n;
    t = &n->link;
  }
 *t = 0;
 return(c);
}

static void add_region_to_band(BAND *b, double x0, double x1)
{
 RECT *list;
 RECT *r;
 RECT *last;

 static void save_rect(RECT *r)
  { r->link = 0;
#ifdef TRACE
    if (trace) printf("add_region_to_band saving [%g,%g]\n",r->x0,r->x1);
#endif
    if (last && (last->x1 >= r->x0)) panic();
    if (last)
     { last->link = r;
     }
    else
     { b->rects = r;
     }
    last = r;
  }

 if (x0 == x1) return;
 if (x0 > x1) panic();
#ifdef TRACE
 if (trace)
  { printf("add_region_to_band [%g,%g] to",x0,x1);
    for (r=b->rects;r;r=r->link) printf(" [%g,%g]",r->x0,r->x1);
    printf("\n");
  }
#endif
 if (! b->rects)
  { b->rects = new_rect(x0,x1);
    return;
  }
 list = b->rects;
 b->rects = 0;
 last = 0;
 /* If new rect is finished, break this loop with x0>=x1 */
 while (list)
  { r = list;
    list = r->link;
    if (r->x1 < x0) /* 13 */
     { /* Just save existing rect and advance. */
       save_rect(r);
       continue;
     }
    if (r->x0 > x1) /* 1 */
     { /* Save new rect, this rect, and done. */
       save_rect(new_rect(x0,x1));
       save_rect(r);
       x0 = x1;
       break;
     }
    /* 2 through 12: new rect and existing rect touch. */
    /* Drop existing rect and merge into new. */
    if (r->x0 < x0) x0 = r->x0;
    if (r->x1 > x1) x1 = r->x1;
    free_rect(r);
  }
 if (x0 < x1)
  { /* Some of new rect left - should happen only if we ran out of list. */
    if (list) panic();
    save_rect(new_rect(x0,x1));
    last->link = 0;
  }
 else
  { /* New rect done.  All possible touching handled above, just nconc. */
    last->link = list;
  }
#ifdef TRACE
 if (trace)
  { printf("add_region_to_band returning");
    for (r=b->rects;r;r=r->link) printf(" [%g,%g]",r->x0,r->x1);
    printf("\n");
  }
#endif
}

static void drop_region_from_band(BAND *b, double x0, double x1)
{
 RECT *list;
 RECT *r;
 RECT *last;
 RECT *r2;

 static void save_rect(RECT *r)
  { r->link = 0;
#ifdef TRACE
    if (trace) printf("drop_region_from_band saving [%g,%g]\n",r->x0,r->x1);
#endif
    if (last && (last->x1 >= r->x0)) panic();
    if (last)
     { last->link = r;
     }
    else
     { b->rects = r;
     }
    last = r;
  }

 if (x0 == x1) return;
 if (x0 > x1) panic();
#ifdef TRACE
 if (trace)
  { printf("drop_region_from_band [%g,%g] from",x0,x1);
    for (r=b->rects;r;r=r->link) printf(" [%g,%g]",r->x0,r->x1);
    printf("\n");
  }
#endif
 if (! b->rects) return;
 list = b->rects;
 b->rects = 0;
 last = 0;
 /* Break this loop when no more changes possible. */
 while (list)
  { r = list;
    list = r->link;
    if (r->x1 <= x0) /* 12, 13 */
     { /* Just save existing rect and advance. */
       save_rect(r);
       continue;
     }
    if (r->x0 >= x1) /* 1, 2 */
     { /* Done! */
       save_rect(r);
       x0 = x1;
       break;
     }
    /* 3 through 11 */
    if (r->x0 > x0) /* 3, 4, 5 */
     { /* Drop irrelevant part of rect and retry. */
       x0 = r->x0;
       r->link = list;
       list = r;
       continue;
     }
    if (r->x0 < x0) /* 9, 10, 11 */
     { /* Save initial part of existing rect and retry. */
       r2 = copy_rect(r);
       r2->x1 = x0;
       save_rect(r2);
       r->x0 = x0;
       r->link = list;
       list = r;
       continue;
     }
    /* 6, 7, 8 */
    if (r->x1 < x1) /* 8 */
     { /* Drop rect and retry with rest. */
       x0 = r->x1;
       free_rect(r);
       continue;
     }
    if (r->x1 > x1) /* 6 */
     { /* Drop beginning of rect, save, done. */
       r->x0 = x1;
       save_rect(r);
       x0 = x1;
       break;
     }
    /* 7 */
    /* Drop rect, done. */
    free_rect(r);
    x0 = x1;
    break;
  }
 if (x0 < x1)
  { /* Some of new rect left - should happen only if we ran out of list. */
    if (list) panic();
  }
 else
  { /* New rect done.  All possible touching handled above, just nconc. */
  }
 if (last)
  { last->link = list;
  }
 else
  { b->rects = list;
  }
#ifdef TRACE
 if (trace)
  { printf("drop_region_from_band returning");
    for (r=b->rects;r;r=r->link) printf(" [%g,%g]",r->x0,r->x1);
    printf("\n");
  }
#endif
}

RECTREGION *rrgn_init(void)
{
 RECTREGION *rr;

 rr = malloc(sizeof(RECTREGION));
#ifdef TRACE
 rr->threadf = rectregionhead;
 rr->threadb = 0;
 if (rectregionhead) rectregionhead->threadb = rr;
 rectregionhead = rr;
#endif
 rr->bands = 0;
 return(rr);
}

void rrgn_add1(RECTREGION *rr, double x0, double y0, double x1, double y1)
{
 BAND *list;
 BAND *b;
 BAND *last;
 double t;
 BAND *b2;

 static void save_band(BAND *b)
  { b->link = 0;
#ifdef TRACE
    if (trace)
     { RECT *r;
       printf("rrgn_add1 saving band [%g,%g] x",b->y0,b->y1);
       for (r=b->rects;r;r=r->link) printf(" [%g,%g]",r->x0,r->x1);
       printf("\n");
     }
#endif
    if (last && (last->y1 > b->y0)) panic();
    if (last)
     { if ((last->y1 == b->y0) && bands_x_match(last,b))
	{ last->y1 = b->y1;
#ifdef TRACE
	  if (trace) printf("rrgn_add1 merging into previous band\n");
#endif
	  free_band(b);
	  return;
	}
       last->link = b;
     }
    else
     { rr->bands = b;
     }
    last = b;
  }

 if (x0 == x1) return;
 if (y0 == y1) return;
 if (x0 > x1)
  { t = x0;
    x0 = x1;
    x1 = t;
  }
 if (y0 > y1)
  { t = y0;
    y0 = y1;
    y1 = t;
  }
 list = rr->bands;
 rr->bands = 0;
 last = 0;
#ifdef TRACE
 if (trace)
  { printf("rrgn_add1 %g,%g - %g,%g\n",x0,y0,x1,y1);
    printf("rrgn_add1 initial rr:\n");
    for (b=list;b;b=b->link)
     { RECT *r;
       printf("\t[%g,%g] x",b->y0,b->y1);
       for (r=b->rects;r;r=r->link)
	{ printf(" [%g,%g]",r->x0,r->x1);
	}
       printf("\n");
     }
  }
#endif
 /* If new rect is finished, break this loop with y0>=y1 */
 while (list)
  { b = list;
    list = b->link;
#ifdef TRACE
    if (trace) printf("rrgn_add1 band [%g,%g]\n",b->y0,b->y1);
#endif
    if (b->y1 <= y0) /* 12, 13 */
     { /* Just save existing band and advance. */
#ifdef TRACE
       if (trace) printf("rrgn_add1 case 12/13\n");
#endif
       save_band(b);
       continue;
     }
    if (b->y0 < y0) /* 9, 10, 11 */
     { /* Save part of existing band and retry with rest. */
#ifdef TRACE
       if (trace) printf("rrgn_add1 case 9/10/11\n");
#endif
       b2 = copy_band(b);
       b->y1 = y0;
       save_band(b);
       b2->y0 = y0;
       b2->link = list;
       list = b2;
       continue;
     }
    if (b->y0 == y0) /* 6, 7, 8 */
     { if (b->y1 < y1) /* 8 */
	{ /* Modify existing band and retry with rest of new rect. */
#ifdef TRACE
	  if (trace) printf("rrgn_add1 case 8\n");
#endif
	  add_region_to_band(b,x0,x1);
	  save_band(b);
	  y0 = b->y1;
	  continue;
	}
       if (b->y1 > y1) /* 6 */
	{ /* Split existing band, modify first part, save both, done. */
#ifdef TRACE
	  if (trace) printf("rrgn_add1 case 6\n");
#endif
	  b2 = copy_band(b);
	  add_region_to_band(b,x0,x1);
	  b->y1 = y1;
	  save_band(b);
	  b2->y0 = y1;
	  save_band(b2);
	  y0 = y1;
	  break;
	}
       /* 7 */
       /* Modify existing band, save, done. */
#ifdef TRACE
       if (trace) printf("rrgn_add1 case 7\n");
#endif
       add_region_to_band(b,x0,x1);
       save_band(b);
       y0 = y1;
       break;
     }
    /* 1, 2, 3, 4, 5 */
    if (b->y0 >= y1) /* 1, 2 */
     { /* Save new band and current band, done. */
#ifdef TRACE
       if (trace) printf("rrgn_add1 case 1/2\n");
#endif
       b2 = new_1rect_band(y0,y1,x0,x1);
       save_band(b2);
       save_band(b);
       y0 = y1;
       break;
     }
    /* 3, 4, 5 */
    /* Save new band holding part of new rect and retry with rest. */
#ifdef TRACE
    if (trace) printf("rrgn_add1 case 3/4/5\n");
#endif
    b2 = new_1rect_band(y0,b->y0,x0,x1);
    save_band(b2);
    y0 = b->y0;
    b->link = list;
    list = b;
  }
 if (y0 < y1)
  { /* Some of new rect left - should happen only if we ran out of bands. */
#ifdef TRACE
    if (trace) printf("rrgn_add1 leftover rect [%g,%g]\n",y0,y1);
#endif
    if (list) panic();
    b = new_1rect_band(y0,y1,x0,x1);
    save_band(b);
  }
 else
  { /* New rect done.  Save next band in case of collapse, then nconc rest. */
#ifdef TRACE
    if (trace) printf("rrgn_add1 no leftover rect\n");
#endif
    if (list)
     { b = list;
       list = b->link;
       save_band(b);
     }
  }
 if (last)
  { last->link = list;
  }
 else
  { rr->bands = list;
  }
#ifdef TRACE
 if (trace)
  { printf("rrgn_add1 return rr:\n");
    for (b=rr->bands;b;b=b->link)
     { RECT *r;
       printf("\t[%g,%g] x",b->y0,b->y1);
       for (r=b->rects;r;r=r->link)
	{ printf(" [%g,%g]",r->x0,r->x1);
	}
       printf("\n");
     }
  }
#endif
}

void rrgn_sub1(RECTREGION *rr, double x0, double y0, double x1, double y1)
{
 BAND *list;
 BAND *b;
 BAND *last;
 double t;
 BAND *b2;

 static void save_band(BAND *b)
  { b->link = 0;
#ifdef TRACE
    if (trace)
     { RECT *r;
       printf("rrgn_sub1 saving band [%g,%g] x",b->y0,b->y1);
       for (r=b->rects;r;r=r->link) printf(" [%g,%g]",r->x0,r->x1);
       printf("\n");
     }
#endif
    if (! b->rects)
     { free_band(b);
#ifdef TRACE
       if (trace) printf("rrgn_sub1 NOT saving empty band\n");
#endif
       return;
     }
    if (last && (last->y1 > b->y0)) panic();
    if (last)
     { if ((last->y1 == b->y0) && bands_x_match(last,b))
	{ last->y1 = b->y1;
	  free_band(b);
#ifdef TRACE
	  if (trace) printf("rrgn_sub1 merging into previous band\n");
#endif
	  return;
	}
       last->link = b;
     }
    else
     { rr->bands = b;
     }
    last = b;
  }

 if (x0 == x1) return;
 if (y0 == y1) return;
 if (x0 > x1)
  { t = x0;
    x0 = x1;
    x1 = t;
  }
 if (y0 > y1)
  { t = y0;
    y0 = y1;
    y1 = t;
  }
 list = rr->bands;
 rr->bands = 0;
 last = 0;
#ifdef TRACE
 if (trace)
  { printf("rrgn_sub1 %g,%g - %g,%g\n",x0,y0,x1,y1);
    printf("rrgn_sub1 initial rr:\n");
    for (b=list;b;b=b->link)
     { RECT *r;
       printf("\t[%g,%g] x",b->y0,b->y1);
       for (r=b->rects;r;r=r->link)
	{ printf(" [%g,%g]",r->x0,r->x1);
	}
       printf("\n");
     }
  }
#endif
 /* Break this loop when no more changes possible. */
 while (list)
  { b = list;
    list = b->link;
#ifdef TRACE
    if (trace) printf("rrgn_sub1 band [%g,%g]\n",b->y0,b->y1);
#endif
    if (b->y1 <= y0) /* 12, 13 */
     { /* Just save existing band and advance. */
#ifdef TRACE
       if (trace) printf("rrgn_sub1 case 12/13\n");
#endif
       save_band(b);
       continue;
     }
    if (b->y0 < y0) /* 9, 10, 11 */
     { /* Save part of existing band and retry with rest. */
#ifdef TRACE
       if (trace) printf("rrgn_sub1 case 9/10/11\n");
#endif
       b2 = copy_band(b);
       b->y1 = y0;
       save_band(b);
       b2->y0 = y0;
       b2->link = list;
       list = b2;
       continue;
     }
    if (b->y0 == y0) /* 6, 7, 8 */
     { if (b->y1 < y1) /* 8 */
	{ /* Modify existing band and retry with rest of new rect. */
#ifdef TRACE
	  if (trace) printf("rrgn_sub1 case 8\n");
#endif
	  drop_region_from_band(b,x0,x1);
	  save_band(b);
	  y0 = b->y1;
	  continue;
	}
       if (b->y1 > y1) /* 6 */
	{ /* Split existing band, modify first part, save both, done. */
#ifdef TRACE
	  if (trace) printf("rrgn_sub1 case 6\n");
#endif
	  b2 = copy_band(b);
	  drop_region_from_band(b,x0,x1);
	  b->y1 = y1;
	  save_band(b);
	  b2->y0 = y1;
	  save_band(b2);
	  y0 = y1;
	  break;
	}
       /* 7 */
       /* Modify existing band, save, done. */
#ifdef TRACE
       if (trace) printf("rrgn_sub1 case 7\n");
#endif
       drop_region_from_band(b,x0,x1);
       save_band(b);
       y0 = y1;
       break;
     }
    /* 1, 2, 3, 4, 5 */
    if (b->y0 >= y1) /* 1, 2 */
     { /* Save this band and done. */
#ifdef TRACE
       if (trace) printf("rrgn_sub1 case 1/2\n");
#endif
       save_band(b);
       y0 = y1;
       break;
     }
    /* 3, 4, 5 */
    /* Drop pre-band part of new rect and retry with rest. */
#ifdef TRACE
    if (trace) printf("rrgn_sub1 case 3/4/5\n");
#endif
    y0 = b->y0;
    b->link = list;
    list = b;
  }
 if (y0 < y1)
  { /* Some of new rect left - should happen only if we ran out of bands. */
    if (list) panic();
#ifdef TRACE
    if (trace) printf("rrgn_sub1 leftover rect [%g,%g]\n",y0,y1);
#endif
  }
 else
  { /* New rect done.  Save next band in case of collapse, then nconc rest. */
#ifdef TRACE
    if (trace) printf("rrgn_sub1 no leftover rect\n");
#endif
    if (list)
     { b = list;
       list = b->link;
       save_band(b);
     }
  }
 if (last)
  { last->link = list;
  }
 else
  { rr->bands = list;
  }
#ifdef TRACE
 if (trace)
  { printf("rrgn_sub1 return rr:\n");
    for (b=rr->bands;b;b=b->link)
     { RECT *r;
       printf("\t[%g,%g] x",b->y0,b->y1);
       for (r=b->rects;r;r=r->link)
	{ printf(" [%g,%g]",r->x0,r->x1);
	}
       printf("\n");
     }
  }
#endif
}

void rrgn_scan(RECTREGION *rr, void (*cb)(double, double, double, double))
{
 BAND *b;
 RECT *r;

 for (b=rr->bands;b;b=b->link)
  { for (r=b->rects;r;r=r->link)
     { (*cb)(r->x0,b->y0,r->x1,b->y1);
     }
  }
}

void rrgn_done(RECTREGION *rr)
{
 BAND *b;

 while ((b = rr->bands))
  { rr->bands = b->link;
    free_band(b);
  }
#ifdef TRACE
 if (rr->threadf) rr->threadf->threadb = rr->threadb;
 if (rr->threadb) rr->threadb->threadf = rr->threadf; else rectregionhead = rr->threadf;
#endif
 free(rr);
}

RECTREGION *rrgn_clone(RECTREGION *rr)
{
 BAND *b;
 BAND *n;
 BAND **t;
 RECTREGION *c;

 c = rrgn_init();
 t = &c->bands;
 for (b=rr->bands;b;b=b->link)
  { n = copy_band(b);
    *t = n;
    t = &n->link;
  }
 *t = 0;
 return(c);
}

#ifdef TESTBED

#include <stdio.h>
#include <stdarg.h>
#include <strings.h>

#define X 25
#define Y 25

extern const char *__progname;

static unsigned long int seed;
static char prev[X][Y];
static char ours[X][Y];
static char its[X][Y];
static RECTREGION *rr;
static RECTREGION *prevrr;
static int pix0;
static int piy0;
static int pix1;
static int piy1;
static int ppiy0;
static int ppiy1;
static int ix0;
static int iy0;
static int ix1;
static int iy1;
static void (*checkprint)(void);
static void (*opfn)(RECTREGION *, double, double, double, double);
static char *action = 0;
static unsigned int steps;

static void clear(void)
{
 bzero(&ours,sizeof(ours));
}

static void fail(const char *, ...)
	__attribute__((__format__(__printf__,1,2),__noreturn__));
static void fail(const char *fmt, ...)
{
 va_list ap;

 printf("On step %d\n",steps);
 va_start(ap,fmt);
 vprintf(fmt,ap);
 va_end(ap);
 (*checkprint)();
 trace = 1;
 (*opfn)(prevrr,ix0,iy0,ix1,iy1);
 exit(1);
}

static void testscan(double x0, double y0, double x1, double y1)
{
 int ix0;
 int iy0;
 int ix1;
 int iy1;
 int x;
 int y;

 ix0 = x0;
 iy0 = y0;
 ix1 = x1;
 iy1 = y1;
 if ( (x0 < 0) || (y0 < 0) || (x1 > X) || (y1 > Y) ||
      (x0 >= x1) || (y0 >= y1) ||
      (x0 != ix0) || (y0 != iy0) || (x1 != ix1) || (y1 != iy1) )
  { fail("Impossible rectangle: (%g,%g) - (%g,%g)\n",x0,y0,x1,y1);
  }
 if ((iy0 == piy0) && (iy1 == piy1))
  { if (ix0 <= pix1) fail("Improper banding: [%d,%d] band has rects [%d,%d] and [%d,%d]\n",iy0,iy1,pix0,pix1,ix0,ix1);
  }
 else
  { if (iy0 < piy1) fail("Improper banding: successive bands [%d,%d] and [%d,%d]\n",piy0,piy1,iy0,iy1);
    if ((ppiy0 >= 0) && (ppiy1 == piy0))
     { for (x=0;x<X;x++)
	{ if (its[x][ppiy0] != its[x][piy0]) break;
	}
       if (x >= X) fail("Improper banding: adjacent bands [%d,%d] and [%d,%d] should have been collapsed\n",ppiy0,ppiy1,piy0,piy1);
     }
    ppiy0 = piy0;
    ppiy1 = piy1;
  }
 for (y=iy0;y<iy1;y++)
  { for (x=ix0;x<ix1;x++)
     { its[x][y] = 1;
     }
  }
 pix0 = ix0;
 pix1 = ix1;
 piy0 = iy0;
 piy1 = iy1;
}

static void check(void (*print)(void))
{
 int x;
 int y;

 checkprint = print;
 bzero(&its,sizeof(its));
 ppiy0 = -4;
 ppiy1 = -3;
 pix0 = -2;
 piy0 = -2;
 pix1 = -1;
 piy1 = -1;
 rrgn_scan(rr,&testscan);
 for (x=0;x<X;x++)
  { for (y=0;y<Y;y++)
     { if (its[x][y] != ours[x][y]) fail("Contents differ: [%d][%d] is %d, should be %d\n",x,y,its[x][y],ours[x][y]);
     }
  }
}

static void step(void)
{
 int t;
 int x;
 int y;
 int val;

 bcopy(&ours,&prev,sizeof(ours));
 rrgn_done(prevrr);
 prevrr = rrgn_clone(rr);
 do
  { ix0 = random() % (X+1);
    ix1 = random() % (X+1);
  } while (ix0 == ix1);
 if (ix0 > ix1)
  { t = ix0;
    ix0 = ix1;
    ix1 = t;
  }
 do
  { iy0 = random() % (Y+1);
    iy1 = random() % (Y+1);
  } while (iy0 == iy1);
 if (iy0 > iy1)
  { t = iy0;
    iy0 = iy1;
    iy1 = t;
  }
 free(action);
 if (random() & 1)
  { asprintf(&action,"add (%d,%d) - (%d,%d)",ix0,iy0,ix1,iy1);
    opfn = &rrgn_add1;
    val = 1;
  }
 else
  { asprintf(&action,"sub (%d,%d) - (%d,%d)",ix0,iy0,ix1,iy1);
    opfn = &rrgn_sub1;
    val = 0;
  }
 (*opfn)(rr,ix0,iy0,ix1,iy1);
 for (x=ix0;x<ix1;x++)
  { for (y=iy0;y<iy1;y++)
     { ours[x][y] = val;
     }
  }
}

static void print_initial(void)
{
 printf("On initial clearing\n");
}

static void print_prev(void)
{
 int x;
 int y;

 printf("Initial:\n");
 printf("   ");
 for (x=0;x<X;x++) printf("%3d",x);
 printf("\n");
 for (y=0;y<Y;y++)
  { printf("%2d ",y);
    for (x=0;x<X;x++) printf("  %c",prev[x][y]?'x':'.');
    printf("\n");
  }
 printf("%s:\n",action);
 printf("   ");
 for (x=0;x<X;x++) printf("%3d",x);
 printf("\n");
 for (y=0;y<Y;y++)
  { printf("%2d ",y);
    for (x=0;x<X;x++) printf("  %c",ours[x][y]?its[x][y]?'x':'*':its[x][y]?'X':'.');
    printf("\n");
  }
}

int main(int, char **);
int main(int ac, char **av)
{
 if (ac != 2)
  { fprintf(stderr,"Usage: %s randomseed\n",__progname);
    exit(1);
  }
 seed = strtoul(av[1],0,0);
 srandom(seed);
 clear();
 prevrr = rrgn_init();
 rr = rrgn_init();
 check(&print_initial);
 steps = 1;
 while (1)
  { step();
    check(&print_prev);
    if (! (steps % 100000)) printf("%d\n",steps);
    steps ++;
  }
}

#endif