/*
 * Copyright (c) 1998 by The XFree86 Project, Inc.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 *
 * Except as contained in this notice, the name of the XFree86 Project shall
 * not be used in advertising or otherwise to promote the sale, use or other
 * dealings in this Software without prior written authorization from the
 * XFree86 Project.
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <stdlib.h>

#include <X11/IntrinsicP.h>
#include <X11/Xmu/Xmu.h>

#define XmuMax(a, b)	((a) > (b) ? (a) : (b))
#define XmuMin(a, b)	((a) < (b) ? (a) : (b))

/*
 * Function:
 *	XmuNewArea
 *
 * Parameters:
 *	x1 - Coordinates of the rectangle
 *	y1 - ""
 *	x2 - ""
 *	y2 - ""
 *
 * Description:
 *	Creates a new rectangular clipping area
 */
XmuArea *
XmuNewArea(int x1, int y1, int x2, int y2)
{
  XmuArea *area;

  area = (XmuArea *)XtMalloc(sizeof(XmuArea));
  if (x2 > x1 && y2 > y1)
    {
      area->scanline = XmuNewScanline(y1, x1, x2);
      area->scanline->next = XmuNewScanline(y2, 0, 0);
    }
  else
    area->scanline = (XmuScanline *)NULL;

  return (area);
}

/*
 * Function:
 *	XmuAreaDup
 *
 * Parameters:
 *	area - Area to copy
 *
 * Description:
 *	Returns a copy of its argument
 */
XmuArea *
XmuAreaDup(XmuArea *area)
{
  XmuArea *dst;

  if (!area)
    return ((XmuArea *)NULL);

  dst = XmuCreateArea();
  XmuAreaCopy(dst, area);
  return (dst);
}

/*
 * Function:
 *	XmuAreaCopy
 *
 * Parameters:
 *	dst - destination area
 *	src - source area
 *
 * Description:
 *	Minimizes memory alocation, trying to use already alocated memory
 *	in dst, freeing what is not required anymore.
 */
XmuArea *
XmuAreaCopy(XmuArea *dst, XmuArea *src)
{
  XmuScanline *z, *p, *Z;

  if (!dst || !src || dst == src)
    return (dst);

  z = p = dst->scanline;
  Z = src->scanline;

  /*CONSTCOND*/
  while (1)
    {
      if (!Z)
	{
	  if (z == dst->scanline)
	    {
	      XmuDestroyScanlineList(dst->scanline);
	      dst->scanline = (XmuScanline *)NULL;
	    }
	  else
	    {
	      XmuDestroyScanlineList(p->next);
	      p->next = (XmuScanline *)NULL;
	    }
	  return (dst);
	}
      if (z)
	{
	  XmuScanlineCopy(z, Z);
	  z->y = Z->y;
	}
      else
	{
	  z = XmuNewScanline(Z->y, 0, 0);
	  XmuScanlineCopy(z, Z);
	  if (p == dst->scanline && !dst->scanline)
	    p = dst->scanline = z;
	  else
	    p->next = z;
	}
      p = z;
      z = z->next;
      Z = Z->next;
    }

  return (dst);
}

/*
 * Function:
 *   XmuAreaNot
 *
 * Parameters:
 *	area - area to operate
 *	x1   - retangle to clip the result against
 *	y1   - ""
 *	x2   - ""
 *	y2   - ""
 *
 * Description:
 * (Input)
 * (x1, y1)                                                (x2, y1)
 *                   +-------------+
 *      +------------+             +----+
 *      |                +--------------+
 *      +----------------+
 * (x1, y2)                                                (x2, y2)
 *
 * (Output)
 * (x1, y1)                                                (x2, y1)
 *    +--------------+             +--------------------------+
 *    | +------------+             +----+                     |
 *    | |                +--------------+                     |
 *    +-+                +------------------------------------+
 * (x1, y2)                                                (x2, y2)
 */
XmuArea *
XmuAreaNot(XmuArea *area, int x1, int y1, int x2, int y2)
{
  XmuScanline *z;
  XmuArea *and;

  if (!area)
    return (area);

  if (x1 > x2)
    {
      x1 ^= x2; x2 ^= x1; x1 ^= x2;
    }
    if (y1 > y2)
      {
	y1 ^= y2; y2 ^= y1; y1 ^= y2;
      }
    if (!area->scanline)
      {
	if ((area->scanline = XmuNewScanline(y1, x1, x2)) != NULL)
	  area->scanline->next = XmuNewScanline(y2, 0, 0);
	return (area);
      }
    and = XmuNewArea(x1, y1, x2, y2);
    XmuAreaAnd(area, and);
    XmuDestroyArea(and);
    z = area->scanline;
    if (z->y != y1)
      {
	XmuScanline *q = XmuNewScanline(y1, x1, x2);
	q->next = z;
	area->scanline = q;
      }
    else
      {
	area->scanline = area->scanline->next;
	XmuDestroyScanline(z);
	XmuOptimizeArea(area);
	if((z = area->scanline) == (XmuScanline *)NULL)
	  return (area);
      }

    /* CONSTCOND */
    while (1)
      {
	XmuScanlineNot(z, x1, x2);
	if (!z->next)
	  {
	    z->next = XmuNewScanline(y2, 0, 0);
	    break;
	  }
	if (z->next->y == y2)
	  {
	    XmuDestroyScanlineList(z->next);
	    z->next = XmuNewScanline(y2, 0, 0);
	    break;
	  }
	z = z->next;
      }

    return (area);
}

/*
 * Function:
 *	XmuAreaOrXor
 *
 * Parameters:
 *	dst - destination area
 *	src - source area
 *	or  - or operation if true, else xor operation
 *
 * Description:
 *	Executes Or (Union) or Xor (Reverse intesection) of the areas
 */
XmuArea *
XmuAreaOrXor(XmuArea *dst, XmuArea *src, Bool or)
{
  XmuScanline *z, *p, *Z, *P, *ins, *top;

  if (!dst || !src)
    return (dst);

  if (dst == src)
    {
      if (or)
	return (dst);
      XmuDestroyScanlineList(dst->scanline);
      dst->scanline = (XmuScanline *)NULL;
      return (dst);
    }
  if (!XmuValidArea(src))
    return (dst);
  if (!XmuValidArea(dst))
    {
      XmuAreaCopy(dst, src);
      return (dst);
    }

  p = z = dst->scanline;
  P = Z = src->scanline;
  ins = XmuNewScanline(dst->scanline->y, 0, 0);
  top = XmuNewScanline(dst->scanline->y, 0, 0);
  XmuScanlineCopy(ins, dst->scanline);
  XmuScanlineCopy(top, dst->scanline);

  /*CONSTCOND*/
  while (1)
    {
      if (!Z)
	break;
      else if (Z->y < z->y)
	{
	  XmuScanline  *q = XmuNewScanline(Z->y, 0, 0);
	  XmuScanlineCopy(q, Z);

	  if (z == dst->scanline)
	    {
	      dst->scanline = p = q;
	      q->next = z;
            }
	  else
	    {
	      p->next = q;
	      q->next = z;
	      if (Z->y >= p->y)
		{
		  if (ins->y >= top->y
		      && (p->y != P->y || !XmuScanlineEqu(p, P)
			  || (ins->y <= P->y && !XmuScanlineEqu(ins, P))))
		    {
		      if (or)
			XmuScanlineOr(q, ins);
		      else
			XmuScanlineXor(q, ins);
                    }
		  else if (Z->y >= top->y
			   && (top->y == p->y || top->y > ins->y
			       || !XmuValidScanline(Z)
			       || (p->y == P->y && XmuValidScanline(p)
				   && XmuValidScanline(P))
			       || XmuScanlineEqu(ins, top)))
		    {
		      if (or)
			XmuScanlineOr(q, top);
		      else
			XmuScanlineXor(q, top);
		    }
		  if (ins->y != p->y && p->y != P->y)
		    {
		      XmuScanlineCopy(ins, p);
		      ins->y = p->y;
		    }
		}
	      if (!XmuValidScanline(p) || Z->y <= p->y)
		{
		  XmuScanlineCopy(top, p);
		  top->y = p->y;
                }
	      p = q;
	    }
	  P = Z;
	  Z = Z->next;
	  continue;
        }
      else if (Z->y == z->y)
	{
	  if (top->y != z->y)
	    {
	      XmuScanlineCopy(top, z);
	      top->y = z->y;
	    }
	  if (or)
	    XmuScanlineOr(z, Z);
	  else
	    XmuScanlineXor(z, Z);
	  P = Z;
	  Z = Z->next;
	}
      else if (P != Z)		/* && Z->y > z->y */
	{
	  if (top->y == ins->y && top->y != z->y)
	    {
	      XmuScanlineCopy(top, z);
	      top->y = z->y;
	    }
	  if (ins->y != z->y)
	    {
	      XmuScanlineCopy(ins, z);
	      ins->y = z->y;
	    }
	  if (or)
	    XmuScanlineOr(z, P);
	  else
	    XmuScanlineXor(z, P);
	}
      else if (ins->y != z->y)
	{
	  XmuScanlineCopy(ins, z);
	  ins->y = z->y;
	}
      p = z;
      z = z->next;
      if (!z)
	{
	  while (Z)
	    {
	      p->next = XmuNewScanline(Z->y, 0, 0);
	      XmuScanlineCopy(p->next, Z);
	      p = p->next;
	      Z = Z->next;
	    }
	  break;
	}
      else if (ins->y > top->y && !XmuValidScanline(z)
	       && XmuValidScanline(ins))
	{
	  XmuScanlineCopy(top, ins);
	  top->y = ins->y;
	}
    }
  XmuOptimizeArea(dst);
  XmuDestroyScanline(ins);
  XmuDestroyScanline(top);

  return (dst);
}

/*
 * Function:
 *	XmuAreaAnd(dst, src)
 *
 * Parameters:
 *	dst - destination area
 *	src - source area
 *
 * Description:
 *	Executes And (intersection) of the areas
 */
XmuArea *
XmuAreaAnd(XmuArea *dst, XmuArea *src)
{
  XmuScanline *z, *p, *Z, *P, *top;

  if (!dst || !src || dst == src)
    return (dst);
  if (!XmuValidArea(dst) || !XmuValidArea(src))
    {
      XmuDestroyScanlineList(dst->scanline);
      dst->scanline = (XmuScanline *)NULL;
      return (dst);
    }
  z = p = dst->scanline;
  Z = P = src->scanline;
  top = XmuNewScanline(dst->scanline->y, 0, 0);
  XmuScanlineCopy(top, dst->scanline);

  while (z)
    {
      while (Z->next && Z->next->y < z->y)
	{
	  P = Z;
	  Z = Z->next;
	  if (Z->y >= p->y)
	    {
	      XmuScanline *q = XmuNewScanline(Z->y, 0, 0);
	      XmuScanlineCopy(q, Z);

	      XmuScanlineAnd(q, top);
	      if (p->y != P->y)
		{
		  XmuScanlineAnd(p, P);
		  p->y = XmuMax(p->y, P->y);
		}
	      p->next = q;
	      q->next = z;
	      p = q;
	    }
	}
      if (!z->next)
	{
	  z->y = XmuMax(z->y, Z->y);
	  break;
        }
      while (Z->y >= z->next->y)
	{
	  if (z == dst->scanline)
	    {
	      p = dst->scanline = dst->scanline->next;
	      XmuDestroyScanline(z);
	      z = dst->scanline;
	    }
	  else
	    {
	      p->next = z->next;
	      XmuDestroyScanline(z);
	      z = p;
	    }
	  if (!z || !z->next)
	    {
	      XmuOptimizeArea(dst);
	      XmuDestroyScanline(top);

	      return (dst);
	    }
	}
      if (Z->y > p->y)
	z->y = XmuMax(z->y, Z->y);
      if (top->y != z->y)
	{
	  XmuScanlineCopy(top, z);
	  top->y = z->y;
	}
      XmuScanlineAnd(z, Z);
      p = z;
      z = z->next;
    }
  XmuOptimizeArea(dst);
  XmuDestroyScanline(top);

  return (dst);
}

/*
 * Function:
 *   XmuValidArea(area)
 *
 * Parameters:
 *	area - area to verify
 *
 * Description:
 *	Verifies if the area is valid and/or useful
 */
Bool
XmuValidArea(XmuArea *area)
{
  XmuScanline *at;

  if (!area || !area->scanline)
    return (False);

  at = area->scanline;
  while (at)
    {
      if (XmuValidScanline(at))
	return (True);
      at = at->next;
    }

  return (False);
}

/*
 * Function:
 *	XmuValidScanline
 *
 * Parameters:
 *	scanline - scanline to verify
 *
 * Description:
 *	Verifies if a scanline is useful
 */
Bool
XmuValidScanline(XmuScanline *scanline)
{
  XmuSegment *z;

  if (!scanline)
    return (False);

  z = scanline->segment;
  while (z)
    {
      if (XmuValidSegment(z))
	return (True);
      z = z->next;
    }

  return (False);
}

/*
 * Function:
 *   XmuScanlineEqu
 *
 * Parameters:
 *	s1 - scanline 1
 *	s2 - scanline 2
 *
 * Description:
 *	Checks if s1 and s2 are equal
 */
Bool
XmuScanlineEqu(XmuScanline *s1, XmuScanline *s2)
{
  XmuSegment *z, *Z;

  if ((!s1 && !s2) || s1 == s2)
    return (True);
  if (!s1 || !s2)
    return (False);

  z = s1->segment;
  Z = s2->segment;

  /*CONSTCOND*/
  while (1)
    {
      if (!z && !Z)
	return (True);
      if (!z || !Z)
	return (False);
      if (!XmuSegmentEqu(z, Z))
	return (False);
      z = z->next;
      Z = Z->next;
    }
  /*NOTREACHED*/
}

/*
 * Function:
 *	XmuNewSegment
 *
 * Parameters:
 *	x1 - coordinates of the segment
 *	x2 - ""
 *
 * Description:
 *	Creates a new segments with the coordinates x1 and x2
 *
 * Returns:
 *	New Segment of NULL
 */
XmuSegment *
XmuNewSegment(int x1, int x2)
{
  XmuSegment *segment;

  if ((segment = (XmuSegment *)XtMalloc(sizeof(XmuSegment))) == NULL)
    return (segment);

  segment->x1 = x1;
  segment->x2 = x2;
  segment->next = (XmuSegment *)NULL;

  return (segment);
}

/*
 * Function:
 *	XmuDestroySegmentList
 *
 * Parameters:
 *	segment - Segment to destroy
 *
 * Description:
 *	Frees the memory used by the list headed by segment
 */
void
XmuDestroySegmentList(XmuSegment *segment)
{
  XmuSegment *z;

  if (!segment)
    return;

  while (segment)
    {
      z = segment;
      segment = segment->next;
      XmuDestroySegment(z);
    }
}

/*
 * Function:
 *	XmuScanlineCopy
 *
 * Parameters:
 *	dst - destination scanline
 *	src - source scanline
 *
 * Description:
 *	Makes dst contain the same data as src
 */
XmuScanline *
XmuScanlineCopy(XmuScanline *dst, XmuScanline *src)
{
  XmuSegment *z, *p, *Z;

  if (!dst || !src || dst == src)
    return (dst);

  z = p = dst->segment;
  Z = src->segment;

  /*CONSTCOND*/
  while (1)
    {
      if (!Z)
	{
	  if (z == dst->segment)
	    dst->segment = (XmuSegment *)NULL;
	  else
	    p->next = (XmuSegment *)NULL;
	  XmuDestroySegmentList(z);
	  return (dst);
	}
      if (z)
	{
	  z->x1 = Z->x1;
	  z->x2 = Z->x2;
	}
      else
	{
	  z = XmuNewSegment(Z->x1, Z->x2);
	  if (p == dst->segment && !dst->segment)
	    p = dst->segment = z;
	  else
	    p->next = z;
	}
      p = z;
      z = z->next;
      Z = Z->next;
    }
  /*NOTREACHED*/
}

/*
 * Function:
 *	XmuAppendSegment
 *
 * Parameters:
 *	segment - destination segment
 *	append  - segment to add
 *
 * Description:
 *	Adds a copy of the append list at the end of the segment list
 */
Bool
XmuAppendSegment(XmuSegment *segment, XmuSegment *append)
{
  if (!segment || !append)
    return (False);

  if (segment->next)
    /* Should not happen! */
    XmuDestroySegmentList(segment->next);

  while (append)
    {
      if (XmuValidSegment(append))
	{
	  if ((segment->next = XmuNewSegment(append->x1, append->x2)) == NULL)
	    return (False);
	  segment = segment->next;
	}
      append = append->next;
    }

  return (True);
}

/*
 * Function:
 *	XmuOptimizeScanline
 *
 * Parameters:
 *	scanline - scanline to optimize
 *
 * Description:
 *	  Some functions, when transforming Segments of Scanlines, left these
 *	with unnecessary data (that may cause error in these same functions).
 *	  This function corrects these incorrect segments.
 */
XmuScanline *
XmuOptimizeScanline(XmuScanline *scanline)
{
  XmuSegment *z, *p;

  while (scanline->segment && !XmuValidSegment(scanline->segment))
    {
      XmuSegment *s = scanline->segment;

      scanline->segment = scanline->segment->next;
      XmuDestroySegment(s);
    }
  for (z = p = scanline->segment; z; p = z, z = z->next)
    {
      if (!XmuValidSegment(z))
	{
	  p->next = z->next;
	  XmuDestroySegment(z);
	  z = p;
	}
    }
  return (scanline);
}

/*
 * Name:
 *	XmuScanlineNot(scanline, minx, maxx)
 *
 * Parameters:
 *	scanline - scanlines operate
 *	minx	 - minimum x coordinate
 *	maxx	 - maximum x coordinate
 *
 * Description:
 *         (minx)                                                        (maxx)
 *           +                                                             +
 * (input)         +---------+     +--------+        +--------+
 * (output)  +-----+         +-----+        +--------+        +------------+
 */
XmuScanline *
XmuScanlineNot(XmuScanline *scanline, int minx, int maxx)
{
  XmuSegment *z;
  static XmuSegment x = { 0, 0, NULL };
  static XmuScanline and = { 0, &x, NULL };

  if (!scanline)
    return (scanline);

  XmuOptimizeScanline(scanline);
  if (minx > maxx)
    {
      minx ^= maxx; maxx ^= minx; minx ^= maxx;
    }
  and.segment->x1 = minx;
  and.segment->x2 = maxx;
  XmuScanlineAnd(scanline, &and);
  if (!scanline->segment)
    {
      scanline->segment = XmuNewSegment(minx, maxx);
      return (scanline);
    }
  z = scanline->segment;
  if (z->x1 != minx)
    {
      XmuSegment *q = XmuNewSegment(minx, z->x1);

      q->next = z;
      scanline->segment = q;
    }

  /*CONSTCOND*/
  while (1)
    {
      z->x1 = z->x2;
      if (!z->next)
	{
	  z->x2 = maxx;
	  break;
	}
      z->x2 = z->next->x1;
      if (z->next->x2 == maxx)
	{
	  XmuDestroySegment(z->next);
	  z->next = (XmuSegment *)NULL;
	  break;
	}
      z = z->next;
    }

  return (scanline);
}


#ifndef notdef
/*
 * Function:
 *	XmuScanlineOrSegment
 *
 * Parameters:
 *	dst - destionation scanline
 *	src - source segment
 *
 * Description:
 * (input)      +-----------+  +--------+    +---------+
 * (src)              +-------------------+
 * (output)     +-------------------------+  +---------+
 */
XmuScanline *
XmuScanlineOrSegment(XmuScanline *dst, XmuSegment *src)
{
  XmuSegment *z, *p, ins;

  if (!src || !dst || !XmuValidSegment(src))
    return (dst);

  if (!dst->segment)
    {
      dst->segment = XmuNewSegment(src->x1, src->x2);
      return (dst);
    }

  z = p = dst->segment;
  ins.x1 = src->x1;
  ins.x2 = src->x2;

  /*CONSTCOND*/
  while (1)
    {
      if (!z)
	{
            XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);

	    if (p == dst->segment && z == p)
	      dst->segment = q;
	    else
	      p->next = q;
	    break;
	}
      else if (ins.x2 < z->x1)
	{
	  XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);

	  if (p == dst->segment && z == p)
	    {
	      q->next = dst->segment;
	      dst->segment = q;
	    }
	  else
	    {
	      p->next = q;
	      q->next = z;
	    }
	  break;
        }
      else if (ins.x2 <= z->x2)
	{
	  z->x1 = XmuMin(z->x1, ins.x1);
	  break;
	}
      else if (ins.x1 <= z->x2)
	{
	  ins.x1 = XmuMin(z->x1, ins.x1);
	  if (!z->next)
	    {
	      z->x1 = ins.x1;
	      z->x2 = ins.x2;
	      break;
	    }
	  else
	    {
	      if (z == dst->segment)
		{
		  p = dst->segment = dst->segment->next;
		  XmuDestroySegment(z);
		  z = dst->segment;
		  continue;
		}
	      else
		{
		  p->next = z->next;
		  XmuDestroySegment(z);
		  z = p;
		}
	    }
	}
      p = z;
      z = z->next;
    }

  return (dst);
}

/*
 * Function:
 *	XmuScanlineAndSegment
 *
 * Parameters:
 *	dst - destination scanline
 *	src - source segment
 *
 * Description:
 * (input)      +------------+   +------+     +----------+
 * (src)             +---------------------+
 * (output)          +-------+   +------+
 */
XmuScanline *
XmuScanlineAndSegment(XmuScanline *dst, XmuSegment *src)
{
  XmuSegment *z, *p;

  if (!dst || !src)
    return (dst);

  if (!XmuValidSegment(src))
    {
      XmuDestroySegmentList(dst->segment);
      dst->segment = (XmuSegment *)NULL;
      return (dst);
    }
  if (!dst->segment)
    return (dst);

  z = p = dst->segment;
  while (z)
    {
      if (src->x2 <= z->x1 || src->x1 >= z->x2)
	{
	  if (z == dst->segment)
	    {
	      p = dst->segment = dst->segment->next;
	      XmuDestroySegment(z);
	      z = dst->segment;
	      continue;
	    }
	  else
	    {
	      p->next = z->next;
	      XmuDestroySegment(z);
	      z = p;
	    }
	}
      else
	{
	  z->x1 = XmuMax(z->x1, src->x1);
	  z->x2 = XmuMin(z->x2, src->x2);
	}
      p = z;
      z = z->next;
    }

  return (dst);
}

/*
 * Function:
 *	XmuScanlineXorSegment
 *
 * Parameters:
 *	dst - destionation scanline
 *	src - source segment
 *
 * Descriptipn:
 * (input)     +------------+  +----------+    +-----------+
 * (src)           +------------------------+
 * (output)    +---+        +--+          +-+  +-----------+
 */
XmuScanline *
XmuScanlineXorSegment(XmuScanline *dst, XmuSegment *src)
{
  XmuSegment *p, *z, ins;
  int tmp1, tmp2;

  if (!dst || !src || !XmuValidSegment(src))
    return (dst);
  if (!dst->segment)
    {
      dst->segment = XmuNewSegment(src->x1, src->x2);
      return (dst);
    }

  p = z = dst->segment;
  ins.x1 = src->x1;
  ins.x2 = src->x2;

  /*CONSTCOND*/
  while (1)
    {
      if (!XmuValidSegment((&ins)))
	break;
      if (!z || ins.x2 < z->x1)
	{
	  XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);

	  q->next = z;
	  if (z == dst->segment)
	    dst->segment = q;
	  else
	    p->next = q;
	  break;
	}
      else if (ins.x2 == z->x1)
	{
	  z->x1 = ins.x1;
	  break;
	}
      else if (ins.x1 < z->x2)
	{
	  if (ins.x1 < z->x1)
	    {
	      tmp1 = ins.x2;
	      tmp2 = z->x2;
	      ins.x2 = XmuMax(ins.x2, z->x2);
	      z->x2 = z->x1;
	      z->x1 = ins.x1;
	      ins.x1 = XmuMin(tmp1, tmp2);
	    }
	  else if (ins.x1 > z->x1)
	    {
	      tmp1 = ins.x1;
	      ins.x1 = XmuMin(ins.x2, z->x2);
	      ins.x2 = XmuMax(z->x2, ins.x2);
	      z->x2 = tmp1;
	    }
	  else	/* ins.x1 == z->x1 */
	    {
	      if (ins.x2 < z->x2)
		{
		  z->x1 = ins.x2;
		  break;
		}
	      else
		{
		  ins.x1 = z->x2;
		  if (z == dst->segment)
		    p = dst->segment = dst->segment->next;
		  else
		    p->next = z->next;
		  XmuDestroySegment(z);
		  z = p;
		  continue;
		}
	    }
	}
      else if (ins.x1 == z->x2)
	{
	  ins.x1 = z->x1;
	  if (z == dst->segment)
	    p = dst->segment = dst->segment->next;
	  else
	    p->next = z->next;
	  XmuDestroySegment(z);
	  z = p;
	  continue;
	}
      p = z;
      z = z->next;
    }

  return (dst);
}
#endif /* notdef */

/*
 * Function:
 *	ScanlineOr
 *
 * Parameters:
 *	dst - destionation scanline
 *	src - source scanline
 *
 * Description:
 * (input)    +--------------+  +-----+    +----------+
 * (src)          +---------------------+       +-----------+
 * (output)   +-------------------------+  +----------------+
 */
XmuScanline *
XmuScanlineOr(XmuScanline *dst, XmuScanline *src)
{
  XmuSegment *z, *p, *Z, ins;

  if (!src || !src->segment || !dst || dst == src)
    return (dst);
  if (!dst->segment)
    {
      XmuScanlineCopy(dst, src);
      return (dst);
    }

  z = p = dst->segment;
  Z = src->segment;
  ins.x1 = Z->x1;
  ins.x2 = Z->x2;

  /*CONSTCOND*/
  while (1)
    {
      while (!XmuValidSegment((&ins)))
	{
	  if ((Z = Z->next) == (XmuSegment *)NULL)
	    return (dst);
	  ins.x1 = Z->x1;
	  ins.x2 = Z->x2;
	}
        if (!z)
	  {
            XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);

            if (p == dst->segment && z == p)
	      dst->segment = p = q;
            else
	      {
		p->next = q;
		p = q;
	      }
	    Z = Z->next;
	    XmuAppendSegment(p, Z);
	    break;
	  }
        else if (ins.x2 < z->x1)
	  {
	    XmuSegment *r = XmuNewSegment(ins.x1, ins.x2);

	    if (p == dst->segment && z == p)
	      {
		r->next = dst->segment;
		dst->segment = p = r;
	      }
	    else
	      {
		p->next = r;
		r->next = z;
		p = r;
	      }
	    Z = Z->next;
            if (!Z)
	      break;
            else
	      {
		ins.x1 = Z->x1;
		ins.x2 = Z->x2;
		continue;
	      }
	  }
	else if (ins.x2 <= z->x2)
	  {
	    z->x1 = XmuMin(z->x1, ins.x1);
	    Z = Z->next;
	    if (!Z)
	      break;
            else
	      {
		ins.x1 = Z->x1;
		ins.x2 = Z->x2;
		continue;
	      }
	  }
	else if (ins.x1 <= z->x2)
	  {
	    ins.x1 = XmuMin(z->x1, ins.x1);
	    if (!z->next)
	      {
		z->x1 = ins.x1;
		z->x2 = ins.x2;
		p = z;
		Z = Z->next;
		XmuAppendSegment(p, Z);
		break;
	      }
            else
	      {
		if (z == dst->segment)
		  {
		    p = dst->segment = dst->segment->next;
		    XmuDestroySegment(z);
		    z = p;
		    continue;
		  }
                else
		  {
		    p->next = z->next;
		    XmuDestroySegment(z);
		    z = p;
		  }
	      }
	  }
	p = z;
	z = z->next;
    }

  return (dst);
}

/*
 * Function:
 *	XmuScanlineAnd
 *
 * Parameters:
 *	dst - destination scanline
 *	src - source scanline
 *
 * Description:
 * (input)    +--------------+  +-----+    +----------+
 * (src)          +---------------------+       +-----------+
 * (output)       +----------+  +-----+         +-----+
 */
XmuScanline *
XmuScanlineAnd(XmuScanline *dst, XmuScanline *src)
{
  XmuSegment  *z, *p, *Z;

  if (!dst || !src || dst == src || !dst->segment) {
        return (dst);
  }
  if (!src->segment)
    {
      XmuDestroySegmentList(dst->segment);
      dst->segment = (XmuSegment *)NULL;
      return (dst);
    }
  z = p = dst->segment;
  Z = src->segment;

  while (z)
    {
      while (!XmuValidSegment(Z) || Z->x2 <= z->x1)
	{
	  Z = Z->next;
	  if (!Z)
	    {
	      if (z == dst->segment)
		dst->segment = (XmuSegment *)NULL;
	      else
		p->next = (XmuSegment *)0;
	      XmuDestroySegmentList(z);
	      return (dst);
	    }
	}
      if (Z->x1 >= z->x2)
	{
	  if (z == dst->segment)
	    {
	      p = dst->segment = dst->segment->next;
	      XmuDestroySegment(z);
	      z = dst->segment;
	    }
	  else
	    {
	      p->next = z->next;
	      XmuDestroySegment(z);
	      z = p->next;
	    }
	  if (!z)
	    return (dst);
	  else
	    continue;
	}
        z->x1 = XmuMax(z->x1, Z->x1);
	if (z->x2 > Z->x2)
	  {
            if (Z->next)
	      {
                XmuSegment *q = XmuNewSegment(Z->x2, z->x2);

		q->next = z->next;
		z->next = q;
	      }
	    z->x2 = Z->x2;
	  }
	p = z;
	z = z->next;
    }

  return (dst);
}

/*
 * Function:
 *	ScanlineXor
 *
 * Parameters:
 *	dst - destination scanline
 *	src - source scanline
 *
 * Description:
 * (input)    +--------------+  +-----+    +----------+
 * (src)          +---------------------+       +-----------+
 * (output)   +---+          +--+     +-+  +----+     +-----+
 */
XmuScanline *
XmuScanlineXor(XmuScanline *dst, XmuScanline *src)
{
  XmuSegment *z, *p, *Z, ins;
  int tmp1, tmp2;

  if (!src || !dst || !src->segment)
    return (dst);
  if (src == dst)
    {
      XmuDestroySegmentList(dst->segment);
      dst->segment = (XmuSegment *)NULL;
      return (dst);
    }
  if (!dst->segment)
    {
      XmuScanlineCopy(dst, src);
      return (dst);
    }

  z = p = dst->segment;
  Z = src->segment;
  ins.x1 = Z->x1;
  ins.x2 = Z->x2;

  /*CONSTCOND*/
  while (1)
    {
      while (!XmuValidSegment((&ins)))
	{
	  if ((Z = Z->next) == (XmuSegment *)NULL)
	    return (dst);
	  ins.x1 = Z->x1;
	  ins.x2 = Z->x2;
	}
      if (!z)
	{
	  XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);

            if (!dst->segment)
	      dst->segment = q;
            else
	      p->next = q;
	    p = q;
	    Z = Z->next;
	    XmuAppendSegment(p, Z);
	    break;
	}
      else if (ins.x2 < z->x1)
	{
	  XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);

	  q->next = z;
	  if (z == dst->segment)
	    dst->segment = q;
	  else
	    p->next = q;
	  if ((Z = Z->next) == (XmuSegment *)NULL)
	    return (dst);

	  p = q;
	  ins.x1 = Z->x1;
	  ins.x2 = Z->x2;
	  continue;
	}
      else if (ins.x2 == z->x1)
	{
	  z->x1 = ins.x1;
	  if ((Z = Z->next) == (XmuSegment *)NULL)
	    break;
	  ins.x1 = Z->x1;
	  ins.x2 = Z->x2;
	  continue;
	}
      else if (ins.x1 < z->x2)
	{
	  if (ins.x1 == z->x1)
	    {
	      if (ins.x2 < z->x2)
		{
		  z->x1 = ins.x2;
		  if ((Z = Z->next) == (XmuSegment *)NULL)
		    break;
		  ins.x1 = Z->x1;
		  ins.x2 = Z->x2;
		  continue;
		}
	      else
		{
		  ins.x1 = z->x2;
		  if (z == dst->segment)
		    p = dst->segment = dst->segment->next;
		  else
		    p->next = z->next;
		  XmuDestroySegment(z);
		  z = p;
		  continue;
		}
	    }
	  else
	    {
	      if (Z->x2 < z->x2)
		{
		  XmuSegment  *q = XmuNewSegment(XmuMin(ins.x1, z->x1),
						 XmuMax(z->x1, ins.x1));

		  q->next = z;
		  if (z == dst->segment)
		    dst->segment = q;
		  else
		    p->next = q;
		  ins.x1 = z->x2;
		  z->x1 = ins.x2;
		  p = q;
		  continue;
		}
	      else
		{
		  tmp1 = ins.x2;
		  tmp2 = z->x2;
		  ins.x2 = XmuMax(ins.x2, z->x2);
		  z->x2 = XmuMax(z->x1, ins.x1);
		  z->x1 = XmuMin(ins.x1, z->x1);
		  ins.x1 = XmuMin(tmp1, tmp2);
		}
	    }
	}
      else if (ins.x1 == z->x2)
	{
	  ins.x1 = z->x1;
	  if (z == dst->segment)
	    p = dst->segment = dst->segment->next;
	  else
	    p->next = z->next;
	  XmuDestroySegment(z);
	  z = p;
	  continue;
	}
      p = z;
      z = z->next;
    }

  return (dst);
}

/*
 * Function:
 *	XmuNewScanline
 *
 * Parameters:
 *	y  - y coordinate
 *	x1 - left coordinate
 *	x2 - right coordinate
 *
 * Description:
 *	Creates a new Scanline
 */
XmuScanline *
XmuNewScanline(int y, int x1, int x2)
{
  XmuScanline *scanline;

  scanline = (XmuScanline *)XtMalloc(sizeof(XmuScanline));
  scanline->y = y;
  if (x1 < x2)
    scanline->segment = XmuNewSegment(x1, x2);
  else
    scanline->segment = (XmuSegment *)NULL;

  scanline->next = (XmuScanline *)NULL;

  return (scanline);
}

/*
 * Function:
 *	XmuDestroyScanlineList
 *
 * Parameters:
 *	scanline - scanline list to destroy
 *
 * Description:
 *	Destroy a scanline list
 *
 * Observation:
 *	Use as follow:
 *	XmuDestroyScanlineList(area->scanline);
 *	area->scanline = (XmuScanline *)NULL;
 */
void
XmuDestroyScanlineList(XmuScanline *scanline)
{
  XmuScanline *z;

  if (!scanline)
    return;

  while (scanline)
    {
      z = scanline;
      scanline = scanline->next;
      XmuDestroyScanline(z);
    }
}

/*
 * Function:
 *	XmuOptimizeArea
 *
 * Parameters:
 *	area - area to optimize
 *
 * Description:
 *	  Optimizes an area. This function is called when finishing a
 *	operation between areas, since they can end with redundant data,
 *	and the algorithms for area combination waits a area with
 *	correct data (but can left unnecessary data in the area, to avoid
 *	to much paranoia tests).
 */
XmuArea *XmuOptimizeArea(XmuArea *area)
{
  XmuScanline *pr, *at;

  if (!area || !area->scanline)
    return (area);

  if (!area->scanline->next)
    {
      XmuDestroyScanlineList(area->scanline);
      area->scanline = (XmuScanline *)0;
      return (area);
    }

  pr = area->scanline;
  at = area->scanline->next;
  while (area->scanline && (!XmuValidScanline(area->scanline)
			    || (area->scanline->next && area->scanline->y
				>= area->scanline->next->y)))
    {
      area->scanline = area->scanline->next;
      XmuDestroyScanline(pr);
      pr = area->scanline;
      if (pr)
	at = pr->next;
    }

  for (; at; pr = at, at = at->next)
    {
      if (XmuScanlineEqu(at, pr)
	  || (!XmuValidScanline(at) && !XmuValidScanline(pr))
	  || (at->next && at->y >= at->next->y))
	{
	  pr->next = at->next;
	  XmuDestroyScanline(at);
	  at = pr;
	}
    }
  if (pr && XmuValidScanline(pr))
    {
      XmuDestroySegmentList(pr->segment);
      pr->segment = (XmuSegment *)NULL;
    }
  if (area->scanline && !area->scanline->next)
    {
      XmuDestroyScanlineList(area->scanline);
      area->scanline = (XmuScanline *)NULL;
    }

  return (area);
}