/* An implementation of the region abstract data type.

  This code is part of xink, by Raph Levien.

  xink version 0.02

  Copyright 1997 Raph Levien <raph@acm.org>

  This code is free for commercial and non-commercial use or
  redistribution, as long as the source code release, startup screen,
  or product packaging includes this copyright notice.
*/

#include <stdlib.h>
#include "region.h"

/* These two routines might get moved into a common "util" file. */
static int min (int a, int b) {
  return (a > b) ? b : a;
}

static int max (int a, int b) {
  return (a > b) ? a : b;
}

static band *band_pin (band *band) {
  band->refcount++;
  return band;
}

static void band_drop (band *band) {
  if (--(band->refcount) == 0)
    free (band);
}

region *region_pin (region *region) {
  region->refcount++;
  return region;
}

void region_drop (region *region) {
  int i;

  if (--(region->refcount) == 0) {
    for (i = 0; i < region->n_bands; i++)
      band_drop (region->band[i]);
    free (region);
  }
}

region *region_from_rect (const rect *src) {
  region *r;
  band *b;

  if (rect_empty (src)) {
    /* Create the empty region. */
    r = (region *)malloc (sizeof(region) - sizeof(band *));
    r->refcount = 1;
    r->n_bands = 0;
  } else {
    r = (region *)malloc (sizeof(region));
    r->refcount = 1;
    r->n_bands = 1;
    b = (band *)malloc (sizeof(band));
    r->band[0] = b;
    b->refcount = 1;
    b->y0 = src->y0;
    b->y1 = src->y1;
    b->n_ranges = 1;
    b->range[0].x0 = src->x0;
    b->range[0].x1 = src->x1;
  }
  return r;
}

bool region_empty (const region *region) {
  return (region->n_bands == 0);
}

/* Determine whether the x projections of two bands are equal.
   Does not drop its arguments. */
static bool band_eq (const band *b1, const band *b2) {
  int i, n;

  n = b1->n_ranges;
  if (n != b2->n_ranges) return false;
  for (i = 0; i < n; i++)
    if (b1->range[i].x0 != b2->range[i].x0 ||
	b1->range[i].x1 != b2->range[i].x1)
      return false;
  return true;
}

/* Change the band's y projection while maintaining its x projection. */
static band *band_resize (band *b1, int y0, int y1) {
  if (b1->refcount != 1) {
    /* Might split this out into a band_dup function if it might get
       used elsewhere. */
    band *b;
    int i, n;

    if (y0 == b1->y0 && y1 == b1->y1) return b1;
    n = b1->n_ranges;
    b = (band *)malloc (sizeof(band) + (n - 1) * sizeof(range));
    b->refcount = 1;
    b->n_ranges = b1->n_ranges;
    for (i = 0; i < n; i++) {
      b->range[i].x0 = b1->range[i].x0;
      b->range[i].x1 = b1->range[i].x1;
    }
    band_drop (b1);
    b1 = b;
  }
  b1->y0 = y0;
  b1->y1 = y1;
  return b1;
}

#ifdef EXTRA_JUNK
/* This routine isn't needed any more, because we've added the invariant
   that regions are always simplified. */

/* Simplify a region by coalescing identical consecutive bands. */
region *region_simplify (region *r1) {
  region *r;
  int i, i1;

  r = (region *)malloc (sizeof(region) + (r1->n_bands - 1) * sizeof(region));
  r->refcount = 1;
  i = 0;
  for (i1 = 0; i1 < r1->n_bands; i1++) {
    if (i == 0 ||
	r->band[i - 1]->y1 != r1->band[i1]->y0 ||
	!band_eq (r->band[i - 1], r1->band[i1]))
      r->band[i++] = band_pin (r1->band[i1]);
    else
      r->band[i - 1] =
	band_resize (r->band[i - 1], r->band[i - 1]->y0, r1->band[i1]->y1);
  }
  r->n_bands = i;
  region_drop (r1);
  return r;
}
#endif

/* Combine two bands. The x projection of the resulting band is the
   union of the x projections of the two arguments, and the y
   projection is the intersection.

   Doesn't drop the arguments. */
static band *band_union_combine (band *b1, band *b2) {
  band *b;
  int i, i1, i2;
  int x_last;

  b = (struct band *)malloc (sizeof(band) +
			     ((b1->n_ranges + b2->n_ranges) - 1) *
			     sizeof(range));
  b->refcount = 1;
  b->y0 = max (b1->y0, b2->y0);
  b->y1 = min (b1->y1, b2->y1);
  i = 0;
  i1 = 0;
  i2 = 0;
  /* Invariant: b->range[i - 1].x0 < b1->range[i1].x0,
     and similarly for b2->range[i2]. */
  /* Invariant: x_last = b->range[i - 1].x1, or -1 if not defined. */
  x_last = -INF;
  while (i1 < b1->n_ranges || i2 < b2->n_ranges) {
    /* Perhaps the code duplication of these two branches could be
       eliminated. */
    if (i2 == b2->n_ranges ||
	(i1 < b1->n_ranges && b1->range[i1].x0 < b2->range[i2].x0)) {
      /* Add in the b1->range[i1]. */
      if (b1->range[i1].x0 <= x_last) {
	/* New range overlaps with last one. */
	if (b1->range[i1].x1 > x_last)
	  x_last = b->range[i - 1].x1 = b1->range[i1].x1;
      } else {
	b->range[i].x0 = b1->range[i1].x0;
	x_last = b->range[i++].x1 = b1->range[i1].x1;
      }
      i1++;
    } else {
      /* Add in the b2->range[i2]. */
      if (b2->range[i2].x0 <= x_last) {
	/* New range overlaps with last one. */
	if (b2->range[i2].x1 > x_last)
	  x_last = b->range[i - 1].x1 = b2->range[i2].x1;
      } else {
	b->range[i].x0 = b2->range[i2].x0;
	x_last = b->range[i++].x1 = b2->range[i2].x1;
      }
      i2++;
    }
  }
  b->n_ranges = i;
#if 0
  band_drop (b1);
  band_drop (b2);
#endif
  return b;
}

/* Add a band to a region, simplifying. The psrc and src arguments
   allow the band equality check to be simplified in cases where
   band information is derived from already simplified regions. Codes
   1 and 2 refer to existing regions, and 3 to combination data. */
static void add_band (region *r, band *b, int *psrc, int src) {
  int n;

  /* Note: this test isn't necessary when being called from region_union,
     but is included here anyway to avoid having two separate versions
     of add_band. */
  if (b->n_ranges == 0) {
    band_drop (b);
    return;
  }
  n = r->n_bands;
  if (n == 0 ||
      (src != 3 && src == *psrc) ||
      !band_eq (r->band[n - 1], b)) {
    r->band[n] = b;
    r->n_bands++;
  } else {
    r->band[n - 1] =
      band_resize (r->band[n - 1], r->band[n - 1]->y0, b->y1);
    band_drop (b);
  }
  *psrc = src;
}

/* Return the union of two regions. */
region *region_union (region *r1, region *r2) {
  region *r;
  int i1, i2;
  int y;
  int src;

  /* This bound may not be strict. */
  r = (region *)malloc (sizeof(region) +
			  ((r1->n_bands + r2->n_bands) * 2 - 1) *
			  sizeof(band *));
  r->refcount = 1;
  r->n_bands = 0;
  i1 = 0;
  i2 = 0;
  src = 0;
  /* Invariant: y = r->band[i - 1].y1, or 0 if not defined */
  y = -INF;
  while (i1 < r1->n_bands || i2 < r2->n_bands) {
    if (i2 == r2->n_bands ||
	(i1 < r1->n_bands && r1->band[i1]->y1 <= r2->band[i2]->y0)) {
      add_band (r, band_resize (band_pin (r1->band[i1]),
				 max (y, r1->band[i1]->y0),
				 r1->band[i1]->y1),
		&src, 1);
      y = r1->band[i1++]->y1;
    } else if (i1 == r1->n_bands ||
	       (i2 < r2->n_bands && r2->band[i2]->y1 <= r1->band[i1]->y0)) {
      add_band (r, band_resize (band_pin (r2->band[i2]),
				max (y, r2->band[i2]->y0),
				r2->band[i2]->y1),
		&src, 2);
      y = r2->band[i2++]->y1;
    } else {
      /* Combine two bands - output the next band beginning with y or
	 greater. */

      /* Advance y to y0 of actual next band. */
      y = max (y, min (r1->band[i1]->y0, r2->band[i2]->y0));

      /* Output the part where there is a deficiency in the y
	 projection of the other region. */
      if (r2->band[i2]->y0 > y) {	
        add_band (r, band_resize (band_pin (r1->band[i1]),
				  y,
				  r2->band[i2]->y0),
		  &src, 1);
	y = r2->band[i2]->y0;
      } else if (r1->band[i1]->y0 > y) {
	add_band (r, band_resize (band_pin (r2->band[i2]),
				    y,
				    r1->band[i1]->y0),
		  &src, 2);
	y = r1->band[i1]->y0;
      }

      /* Output the part where the y projections of the two bands
	 overlap. */
      add_band (r, band_union_combine (r1->band[i1], r2->band[i2]), &src, 3);

      /* Advance y to the next band to output. */
      if (r1->band[i1]->y1 < r2->band[i2]->y1)
	y = r1->band[i1++]->y1;
      else if (r1->band[i1]->y1 > r2->band[i2]->y1)
	y = r2->band[i2++]->y1;
      else {
	i1++;
	i2++;
      }
    }
  }
  region_drop (r1);
  region_drop (r2);
  return r;
}

/* Combine two bands. The x projection of the resulting band is the
   difference of the x projections of the two arguments, and the y
   projection is the intersection.

   Doesn't drop the arguments. */
static band *band_minus_combine (band *b1, band *b2) {
  band *b;
  int i, i1, i2;
  int x_suppress;

  b = (struct band *)malloc (sizeof(band) +
			     ((b1->n_ranges + b2->n_ranges) - 1) *
			     sizeof(range));
  b->refcount = 1;
  b->y0 = max (b1->y0, b2->y0);
  b->y1 = min (b1->y1, b2->y1);
  i = 0;
  i1 = 0;
  i2 = 0;
  /* Invariant: b->range[i - 1].x0 < b1->range[i1].x0,
     and similarly for b2->range[i2]. */
  x_suppress = -INF;
  while (i1 < b1->n_ranges || i2 < b2->n_ranges) {
    if (i2 == b2->n_ranges ||
	(i1 < b1->n_ranges && b1->range[i1].x0 < b2->range[i2].x0)) {
      /* Add in the b1->range[i1]. */
      if (b1->range[i1].x1 > x_suppress) {
	b->range[i].x0 = max (b1->range[i1].x0, x_suppress);
	b->range[i++].x1 = b1->range[i1].x1;
      }
      i1++;
    } else {
      /* Subtract b2->range[i2] from last range. */
      if (i > 0 && b->range[i - 1].x1 > b2->range[i2].x0) {
	/* b2 range overlaps with last range */
	if (b->range[i - 1].x1 > b2->range[i2].x1) {
	  /* Need to split last range in two. */
	  b->range[i].x0 = b2->range[i2].x1;
	  b->range[i].x1 = b->range[i - 1].x1;
	  b->range[i - 1].x1 = b2->range[i2].x0;
	  i++;
	} else {
	  /* Just chop the last range. */
	  b->range[i - 1].x1 = b2->range[i2].x0;
	}
      }
      x_suppress = b2->range[i2].x1;
      i2++;
    }
  }
  b->n_ranges = i;
#if 0
  band_drop (b1);
  band_drop (b2);
#endif
  return b;
}

/* Return the difference of two regions. */
region *region_minus (region *r1, region *r2) {
  region *r;
  int i1, i2;
  int y;
  int src;

  /* This routine has very analogous structure to region_union. The
     main difference is that bands from r2 are skipped over in the
     absence of any band from r1, whereas in region_union, they are
     transferred to the output. */

  /* This bound may not be strict. */
  r = (region *)malloc (sizeof(region) +
			  ((r1->n_bands + r2->n_bands) * 2 - 1) *
			  sizeof(band *));
  r->refcount = 1;
  r->n_bands = 0;
  i1 = 0;
  i2 = 0;
  src = 0;
  /* Invariant: y = r->band[i - 1].y1, or 0 if not defined */
  y = -INF;
  while (i1 < r1->n_bands || i2 < r2->n_bands) {
    if (i2 == r2->n_bands ||
	(i1 < r1->n_bands && r1->band[i1]->y1 <= r2->band[i2]->y0)) {
      add_band (r, band_resize (band_pin (r1->band[i1]),
				 max (y, r1->band[i1]->y0),
				 r1->band[i1]->y1),
		&src, 1);
      y = r1->band[i1++]->y1;
    } else if (i1 == r1->n_bands ||
	       (i2 < r2->n_bands && r2->band[i2]->y1 <= r1->band[i1]->y0)) {
      y = r2->band[i2++]->y1;
    } else {
      /* Combine two bands - output the next band beginning with y or
	 greater. */

      /* Advance y to y0 of actual next band. */
      y = max (y, min (r1->band[i1]->y0, r2->band[i2]->y0));

      /* Output the part where there is a deficiency in the y
	 projection of the other region. */
      if (r2->band[i2]->y0 > y) {	
        add_band (r, band_resize (band_pin (r1->band[i1]),
				  y,
				  r2->band[i2]->y0),
		  &src, 1);
	y = r2->band[i2]->y0;
      } else if (r1->band[i1]->y0 > y) {
	y = r1->band[i1]->y0;
      }

      /* Output the part where the y projections of the two bands
	 overlap. */
      add_band (r, band_minus_combine (r1->band[i1], r2->band[i2]), &src, 3);

      /* Advance y to the next band to output. */
      if (r1->band[i1]->y1 < r2->band[i2]->y1)
	y = r1->band[i1++]->y1;
      else if (r1->band[i1]->y1 > r2->band[i2]->y1)
	y = r2->band[i2++]->y1;
      else {
	i1++;
	i2++;
      }
    }
  }
  region_drop (r1);
  region_drop (r2);
  return r;
}

/* Return the number of pixels enclosed in the rectangle */
static int compute_weight (region *reg, rect *rec) {
  int i, j;
  int band_height;
  int weight, width;
  band *b;

  weight = 0;
  for (i = 0; i < reg->n_bands && reg->band[i]->y1 >= rec->y0; i++);
  for (; i < reg->n_bands && reg->band[i]->y0 < rec->y1; i++) {
    b = reg->band[i];
    band_height = min (b->y1, rec->y1) - max (b->y0, rec->y0);
    if (band_height > 0) { /* can we prove it will always be positive? */
      for (j = 0; j < b->n_ranges && b->range[j].x1 >= rec->x0; j++);
      for (; j < b->n_ranges && b->range[j].x0 < rec->x1; j++) {
	width = min (b->range[j].x0, rec->x0) -
	  max (b->range[j].x1, rec->x1);
	/* again, it may be possible to prove that width > 0 */
	if (width > 0) weight += width * band_height;
      }
    }
  }
  return weight;
}

/* Find a tile from the region, satisfying the following constraints:

   + it includes the leftmost pixel of the topmost scan line in the region

   + the size is no greater than (max_xs, max_ys)

   + the ratio of actual pixels to (waste + wasted pixels) is maximized

   The last constraint may be satisfied only approximately, in the interest
   of speed.

   This routine is useful for decomposing a region into tiles. In general,

   while (!region_empty (reg)) {
     region_tile (&rec, reg, ...);
     ...process rec...
     reg = region_minus (reg, region_from_rect (&rec));
   }

   */
void region_tile (rect *dst, region *src, int max_xs, int max_ys, int waste) {

  /* This implementation doesn't even try to optimize for waste. */

  if (region_empty (src)) {
    dst->x0 = 0;
    dst->x1 = 0;
    dst->y0 = 0;
    dst->y1 = 0;
    return;
  }
  dst->x0 = src->band[0]->range[0].x0;
  dst->x1 = min (src->band[0]->range[0].x1, dst->x0 + max_xs);
  dst->y0 = src->band[0]->y0;
  dst->y1 = min (src->band[0]->y1, dst->y0 + max_ys);
}

/* Render a region into a bitmap. This is 8bpp, just to keep things simple.
   (I may borrow some code from the alpha xink to render 1bpp bitmaps,
   but this is only for testing, so I may not bother). */
void region_to_bitmap (region *r, byte *buf, int xs, int ys) {
  int i, j;
  int x, y;
  band *b;
  int n;

  i = 0;
  for (y = 0; y < ys; y++) {
    if (i == r->n_bands ||
	y < r->band[i]->y0 ||
	y >= r->band[i]->y1) {
      /* an empty scan line */
      for (x = 0; x < xs; x++)
	buf[y * xs + x] = 0;
    } else {
      /* a filled scan line */
      b = r->band[i];
      n = b->n_ranges;
      j = 0;
      while (j != n && b->range[j].x0 < 0) j++;
      x = 0;
      while (j != n && x < xs) {
	while (x < xs && x < b->range[j].x0)
	  buf[y * xs + x++] = 0;
	while (x < xs && x < b->range[j].x1)
	  buf[y * xs + x++] = 255;
	j++;
      }
      while (x < xs)
	buf[y * xs + x++] = 0;
      if (y + 1 == b->y1) i++;
    }
  }
}