/*

 * Copyright © 2004 Carl Worth

 * Copyright © 2006 Red Hat, Inc.

 * Copyright © 2008 Chris Wilson

 *

 * This library is free software; you can redistribute it and/or

 * modify it either under the terms of the GNU Lesser General Public

 * License version 2.1 as published by the Free Software Foundation

 * (the "LGPL") or, at your option, under the terms of the Mozilla

 * Public License Version 1.1 (the "MPL"). If you do not alter this

 * notice, a recipient may use your version of this file under either

 * the MPL or the LGPL.

 *

 * You should have received a copy of the LGPL along with this library

 * in the file COPYING-LGPL-2.1; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA

 * You should have received a copy of the MPL along with this library

 * in the file COPYING-MPL-1.1

 *

 * The contents of this file are subject to the Mozilla Public License

 * Version 1.1 (the "License"); you may not use this file except in

 * compliance with the License. You may obtain a copy of the License at

 * http://www.mozilla.org/MPL/

 *

 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY

 * OF ANY KIND, either express or implied. See the LGPL or the MPL for

 * the specific language governing rights and limitations.

 *

 * The Original Code is the cairo graphics library.

 *

 * The Initial Developer of the Original Code is Carl Worth

 *

 * Contributor(s):

 *	Carl D. Worth <cworth@cworth.org>

 *	Chris Wilson <chris@chris-wilson.co.uk>

 */

/* Provide definitions for standalone compilation */

#include "cairoint.h"

#include "cairo-error-private.h"

#include "cairo-freelist-private.h"

#include "cairo-combsort-inline.h"

#define DEBUG_POLYGON 0

typedef cairo_point_t cairo_bo_point32_t;

typedef struct _cairo_bo_intersect_ordinate {

    int32_t ordinate;

    enum { EXACT, INEXACT } exactness;

} cairo_bo_intersect_ordinate_t;

typedef struct _cairo_bo_intersect_point {

    cairo_bo_intersect_ordinate_t x;

    cairo_bo_intersect_ordinate_t y;

} cairo_bo_intersect_point_t;

typedef struct _cairo_bo_edge cairo_bo_edge_t;

typedef struct _cairo_bo_deferred {

    cairo_bo_edge_t *right;

    int32_t top;

} cairo_bo_deferred_t;

struct _cairo_bo_edge {

    cairo_edge_t edge;

    cairo_bo_edge_t *prev;

    cairo_bo_edge_t *next;

    cairo_bo_deferred_t deferred;

};

/* the parent is always given by index/2 */

#define PQ_PARENT_INDEX(i) ((i) >> 1)

#define PQ_FIRST_ENTRY 1

/* left and right children are index * 2 and (index * 2) +1 respectively */

#define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)

typedef enum {

    CAIRO_BO_EVENT_TYPE_STOP,

    CAIRO_BO_EVENT_TYPE_INTERSECTION,

    CAIRO_BO_EVENT_TYPE_START

} cairo_bo_event_type_t;

typedef struct _cairo_bo_event {

    cairo_bo_event_type_t type;

    cairo_point_t point;

} cairo_bo_event_t;

typedef struct _cairo_bo_start_event {

    cairo_bo_event_type_t type;

    cairo_point_t point;

    cairo_bo_edge_t edge;

} cairo_bo_start_event_t;

typedef struct _cairo_bo_queue_event {

    cairo_bo_event_type_t type;

    cairo_point_t point;

    cairo_bo_edge_t *e1;

    cairo_bo_edge_t *e2;

} cairo_bo_queue_event_t;

typedef struct _pqueue {

    int size, max_size;

    cairo_bo_event_t **elements;

    cairo_bo_event_t *elements_embedded[1024];

} pqueue_t;

typedef struct _cairo_bo_event_queue {

    cairo_freepool_t pool;

    pqueue_t pqueue;

    cairo_bo_event_t **start_events;

} cairo_bo_event_queue_t;

typedef struct _cairo_bo_sweep_line {

    cairo_bo_edge_t *head;

    int32_t current_y;

    cairo_bo_edge_t *current_edge;

} cairo_bo_sweep_line_t;

static cairo_fixed_t

				    cairo_fixed_t y)

{

    cairo_fixed_t x, dy;

					 dy);

    }

}

static inline int

			   cairo_bo_point32_t const *b)

{

    int cmp;

}

/* Compare the slope of a to the slope of b, returning 1, 0, -1 if the

 * slope a is respectively greater than, equal to, or less than the

 * slope of b.

 *

 * For each edge, consider the direction vector formed from:

 *

 *	top -> bottom

 *

 * which is:

 *

 *	(dx, dy) = (line.p2.x - line.p1.x, line.p2.y - line.p1.y)

 *

 * We then define the slope of each edge as dx/dy, (which is the

 * inverse of the slope typically used in math instruction). We never

 * compute a slope directly as the value approaches infinity, but we

 * can derive a slope comparison without division as follows, (where

 * the ? represents our compare operator).

 *

 * 1.	   slope(a) ? slope(b)

 * 2.	    adx/ady ? bdx/bdy

 * 3.	(adx * bdy) ? (bdx * ady)

 *

 * Note that from step 2 to step 3 there is no change needed in the

 * sign of the result since both ady and bdy are guaranteed to be

 * greater than or equal to 0.

 *

 * When using this slope comparison to sort edges, some care is needed

 * when interpreting the results. Since the slope compare operates on

 * distance vectors from top to bottom it gives a correct left to

 * right sort for edges that have a common top point, (such as two

 * edges with start events at the same location). On the other hand,

 * the sense of the result will be exactly reversed for two edges that

 * have a common stop point.

 */

static inline int

		const cairo_bo_edge_t *b)

{

    /* XXX: We're assuming here that dx and dy will still fit in 32

     * bits. That's not true in general as there could be overflow. We

     * should prevent that before the tessellation algorithm

     * begins.

     */

    /* Since the dy's are all positive by construction we can fast

     * path several common cases.

     */

    /* First check for vertical lines. */

    /* Then where the two edges point in different directions wrt x. */

    /* Finally we actually need to do the general comparison. */

    {

    }

}

/*

 * We need to compare the x-coordinates of a pair of lines for a particular y,

 * without loss of precision.

 *

 * The x-coordinate along an edge for a given y is:

 *   X = A_x + (Y - A_y) * A_dx / A_dy

 *

 * So the inequality we wish to test is:

 *   A_x + (Y - A_y) * A_dx / A_dy ∘ B_x + (Y - B_y) * B_dx / B_dy,

 * where ∘ is our inequality operator.

 *

 * By construction, we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are

 * all positive, so we can rearrange it thus without causing a sign change:

 *   A_dy * B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx * A_dy

 *                                 - (Y - A_y) * A_dx * B_dy

 *

 * Given the assumption that all the deltas fit within 32 bits, we can compute

 * this comparison directly using 128 bit arithmetic. For certain, but common,

 * input we can reduce this down to a single 32 bit compare by inspecting the

 * deltas.

 *

 * (And put the burden of the work on developing fast 128 bit ops, which are

 * required throughout the tessellator.)

 *

 * See the similar discussion for _slope_compare().

 */

static int

			       const cairo_bo_edge_t *b,

			       int32_t y)

{

    /* XXX: We're assuming here that dx and dy will still fit in 32

     * bits. That's not true in general as there could be overflow. We

     * should prevent that before the tessellation algorithm

     * begins.

     */

    int32_t dx;

    int32_t adx, ady;

    int32_t bdx, bdy;

    enum {

       HAVE_NONE    = 0x0,

       HAVE_DX      = 0x1,

       HAVE_ADX     = 0x2,

       HAVE_DX_ADX  = HAVE_DX | HAVE_ADX,

       HAVE_BDX     = 0x4,

       HAVE_DX_BDX  = HAVE_DX | HAVE_BDX,

       HAVE_ADX_BDX = HAVE_ADX | HAVE_BDX,

       HAVE_ALL     = HAVE_DX | HAVE_ADX | HAVE_BDX

    /* don't bother solving for abscissa if the edges' bounding boxes

     * can be used to order them. */

    {

           int32_t amin, amax;

           int32_t bmin, bmax;

           } else {

           }

           } else {

           }

    }

#define L _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy), dx)

#define A _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx, bdy), y - a->edge.line.p1.y)

#define B _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->edge.line.p1.y)

    case HAVE_NONE:

	/* A_dy * B_dy * (A_x - B_x) ∘ 0 */

	/* 0 ∘  - (Y - A_y) * A_dx * B_dy */

	/* 0 ∘ (Y - B_y) * B_dx * A_dy */

	/*  0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */

	    cairo_int64_t adx_bdy, bdx_ady;

	    /* ∴ A_dx * B_dy ∘ B_dx * A_dy */

	} else

	/* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */

	} else {

	    cairo_int64_t ady_dx, dy_adx;

	}

	/* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */

	} else {

	    cairo_int64_t bdy_dx, dy_bdx;

	}

	/* XXX try comparing (a->edge.line.p2.x - b->edge.line.p2.x) et al */

    }

#undef B

#undef A

#undef L

}

/*

 * We need to compare the x-coordinate of a line for a particular y wrt to a

 * given x, without loss of precision.

 *

 * The x-coordinate along an edge for a given y is:

 *   X = A_x + (Y - A_y) * A_dx / A_dy

 *

 * So the inequality we wish to test is:

 *   A_x + (Y - A_y) * A_dx / A_dy ∘ X

 * where ∘ is our inequality operator.

 *

 * By construction, we know that A_dy (and (Y - A_y)) are

 * all positive, so we can rearrange it thus without causing a sign change:

 *   (Y - A_y) * A_dx ∘ (X - A_x) * A_dy

 *

 * Given the assumption that all the deltas fit within 32 bits, we can compute

 * this comparison directly using 64 bit arithmetic.

 *

 * See the similar discussion for _slope_compare() and

 * edges_compare_x_for_y_general().

 */

static int

			      int32_t y,

			      int32_t x)

{

    int32_t adx, ady;

    int32_t dx, dy;

    cairo_int64_t L, R;

}

static int

		       const cairo_bo_edge_t *b,

		       int32_t y)

{

    /* If the sweep-line is currently on an end-point of a line,

     * then we know its precise x value (and considering that we often need to

     * compare events at end-points, this happens frequently enough to warrant

     * special casing).

     */

    enum {

       HAVE_NEITHER = 0x0,

       HAVE_AX      = 0x1,

       HAVE_BX      = 0x2,

       HAVE_BOTH    = HAVE_AX | HAVE_BX

    else

    else

    case HAVE_NEITHER:

    }

}

static inline int

{

}

static int

				    const cairo_bo_edge_t	*a,

				    const cairo_bo_edge_t	*b)

{

    int cmp;

    /* compare the edges if not identical */

	/* The two edges intersect exactly at y, so fall back on slope

	 * comparison. We know that this compare_edges function will be

	 * called only when starting a new edge, (not when stopping an

	 * edge), so we don't have to worry about conditionally inverting

	 * the sense of _slope_compare. */

    }

    /* We've got two collinear edges now. */

}

static inline cairo_int64_t

	  int32_t c, int32_t d)

{

    /* det = a * d - b * c */

			     _cairo_int32x32_64_mul (b, c));

}

static inline cairo_int128_t

	      cairo_int64_t c, int32_t       d)

{

    /* det = a * d - b * c */

			      _cairo_int64x32_128_mul (c, b));

}

/* Compute the intersection of two lines as defined by two edges. The

 * result is provided as a coordinate pair of 128-bit integers.

 *

 * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection or

 * %CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.

 */

static cairo_bool_t

		 cairo_bo_edge_t		*b,

		 cairo_bo_intersect_point_t	*intersection)

{

    cairo_int64_t a_det, b_det;

    /* XXX: We're assuming here that dx and dy will still fit in 32

     * bits. That's not true in general as there could be overflow. We

     * should prevent that before the tessellation algorithm begins.

     * What we're doing to mitigate this is to perform clamping in

     * cairo_bo_tessellate_polygon().

     */

    cairo_int64_t den_det;

    cairo_int64_t R;

    cairo_quorem64_t qr;

     /* Q: Can we determine that the lines do not intersect (within range)

      * much more cheaply than computing the intersection point i.e. by

      * avoiding the division?

      *

      *   X = ax + t * adx = bx + s * bdx;

      *   Y = ay + t * ady = by + s * bdy;

      *   ∴ t * (ady*bdx - bdy*adx) = bdx * (by - ay) + bdy * (ax - bx)

      *   => t * L = R

      *

      * Therefore we can reject any intersection (under the criteria for

      * valid intersection events) if:

      *   L^R < 0 => t < 0, or

      *   L<R => t > 1

      *

      * (where top/bottom must at least extend to the line endpoints).

      *

      * A similar substitution can be performed for s, yielding:

      *   s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by)

      */

    } else {

    }

    } else {

    }

    /* We now know that the two lines should intersect within range. */

		      a->edge.line.p2.x, a->edge.line.p2.y);

		      b->edge.line.p2.x, b->edge.line.p2.y);

    /* x = det (a_det, dx1, b_det, dx2) / den_det */

						       b_det, dx2),

					 den_det);

#if 0

    intersection->x.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;

#else

				       _cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1));

	} else

    }

#endif

    /* y = det (a_det, dy1, b_det, dy2) / den_det */

						       b_det, dy2),

					 den_det);

#if 0

    intersection->y.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;

#else

				       _cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1));

	} else

    }

#endif

}

static int

					 int32_t			b)

{

    /* First compare the quotient */

    /* With quotient identical, if remainder is 0 then compare equal */

    /* Otherwise, the non-zero remainder makes a > b */

}

/* Does the given edge contain the given point. The point must already

 * be known to be contained within the line determined by the edge,

 * (most likely the point results from an intersection of this edge

 * with another).

 *

 * If we had exact arithmetic, then this function would simply be a

 * matter of examining whether the y value of the point lies within

 * the range of y values of the edge. But since intersection points

 * are not exact due to being rounded to the nearest integer within

 * the available precision, we must also examine the x value of the

 * point.

 *

 * The definition of "contains" here is that the given intersection

 * point will be seen by the sweep line after the start event for the

 * given edge and before the stop event for the edge. See the comments

 * in the implementation for more details.

 */

static cairo_bool_t

					 cairo_bo_intersect_point_t	*point)

{

    int cmp_top, cmp_bottom;

    /* XXX: When running the actual algorithm, we don't actually need to

     * compare against edge->top at all here, since any intersection above

     * top is eliminated early via a slope comparison. We're leaving these

     * here for now only for the sake of the quadratic-time intersection

     * finder which needs them.

     */

						       edge->edge.top);

							  edge->edge.bottom);

    {

    }

    {

    }

    /* At this stage, the point lies on the same y value as either

     * edge->top or edge->bottom, so we have to examine the x value in

     * order to properly determine containment. */

    /* If the y value of the point is the same as the y value of the

     * top of the edge, then the x value of the point must be greater

     * to be considered as inside the edge. Similarly, if the y value

     * of the point is the same as the y value of the bottom of the

     * edge, then the x value of the point must be less to be

     * considered as inside. */

	cairo_fixed_t top_x;

						    edge->edge.top);

    } else { /* cmp_bottom == 0 */

	cairo_fixed_t bot_x;

						    edge->edge.bottom);

    }

}

/* Compute the intersection of two edges. The result is provided as a

 * coordinate pair of 128-bit integers.

 *

 * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection

 * that is within both edges, %CAIRO_BO_STATUS_NO_INTERSECTION if the

 * intersection of the lines defined by the edges occurs outside of

 * one or both edges, and %CAIRO_BO_STATUS_PARALLEL if the two edges

 * are exactly parallel.

 *

 * Note that when determining if a candidate intersection is "inside"

 * an edge, we consider both the infinitesimal shortening and the

 * infinitesimal tilt rules described by John Hobby. Specifically, if

 * the intersection is exactly the same as an edge point, it is

 * effectively outside (no intersection is returned). Also, if the

 * intersection point has the same

 */

static cairo_bool_t

			  cairo_bo_edge_t	*b,

			  cairo_bo_point32_t	*intersection)

{

    cairo_bo_intersect_point_t quorem;

    /* Now that we've correctly compared the intersection point and

     * determined that it lies within the edge, then we know that we

     * no longer need any more bits of storage for the intersection

     * than we do for our edge coordinates. We also no longer need the

     * remainder from the division. */

}

static inline int

			const cairo_bo_event_t *b)

{

    int cmp;

}

static inline void

{

static inline void

{

static cairo_status_t

{

    cairo_bo_event_t **new_elements;

					 sizeof (cairo_bo_event_t *));

		sizeof (pq->elements_embedded));

    } else {

					  sizeof (cairo_bo_event_t *));

    }

}

static inline cairo_status_t

{

    cairo_bo_event_t **elements;

    int i, parent;

	cairo_status_t status;

    }

    {

    }

}

static inline void

{

    cairo_bo_event_t *tail;

    int child, i;

    }

    {

	{

	}

    }

}

static inline cairo_status_t

			      cairo_bo_event_type_t	 type,

			      cairo_bo_edge_t		*e1,

			      cairo_bo_edge_t		*e2,

			      const cairo_point_t	 *point)

{

    cairo_bo_queue_event_t *event;

}

static void

			      cairo_bo_event_t	     *event)

{

static cairo_bo_event_t *

{

    cairo_bo_event_t *event, *cmp;

    {

    }

    else

    {

    }

}

			cairo_bo_event_t *,

			cairo_bo_event_compare)

static void

			    cairo_bo_event_t		**start_events,

			    int				  num_events)

{

			  sizeof (cairo_bo_queue_event_t));

static cairo_status_t

				   cairo_bo_edge_t		*edge)

{

    cairo_bo_point32_t point;

						  point.y);

					 CAIRO_BO_EVENT_TYPE_STOP,

					 edge, NULL,

					 &point);

}

static void

{

static inline cairo_status_t

							   cairo_bo_edge_t	*left,

							   cairo_bo_edge_t *right)

{

    cairo_bo_point32_t intersection;

    /* The names "left" and "right" here are correct descriptions of

     * the order of the two edges within the active edge list. So if a

     * slope comparison also puts left less than right, then we know

     * that the intersection of these two segments has already

     * occurred before the current sweep line position. */

					 CAIRO_BO_EVENT_TYPE_INTERSECTION,

					 left, right,

					 &intersection);

}

static void

{

static cairo_status_t

			     cairo_bo_edge_t		*edge)

{

	cairo_bo_edge_t *prev, *next;

	int cmp;

						  edge);

						       next, edge) < 0)

	    {

	    }

						       prev, edge) > 0)

	    {

	    }

	    else

	} else {

	}

    } else {

    }

}

static void

			     cairo_bo_edge_t	*edge)

{

    else

static void

			   cairo_bo_edge_t		*left,

			   cairo_bo_edge_t		*right)

{

    else

static inline cairo_bool_t

{

    /* The choice of y is not truly arbitrary since we must guarantee that it

     * is greater than the start of either line.

     */

    } else {

    }

}

static void

		    int32_t		 bot,

		    cairo_polygon_t	*polygon)

{

				 d->top, bot,

				 1);

				 d->top, bot,

				 -1);

    }

static inline void

				  cairo_bo_edge_t	*right,

				  int			 top,

				  cairo_polygon_t	*polygon)

{

	{

	    /* continuation on right, so just swap edges */

	}

    }

    }

}

static inline void

			  int32_t			 top,

			  cairo_fill_rule_t		 fill_rule,

			  cairo_polygon_t	        *polygon)

{

    cairo_bo_edge_t *right;

    unsigned int mask;

    else

		/* continuation on left */

	    }

	}

		/* skip co-linear edges */

		    break;

	    }

	}

    }

static cairo_status_t

					    int			 num_events,

					    cairo_fill_rule_t	 fill_rule,

					    cairo_polygon_t	*polygon)

{

    cairo_bo_event_queue_t event_queue;

    cairo_bo_sweep_line_t sweep_line;

    cairo_bo_event_t *event;

    cairo_bo_edge_t *left, *right;

    cairo_bo_edge_t *e1, *e2;

				      sweep_line.current_y,

				      fill_rule, polygon);

	}

	    }

	    }

	    }