text: /*
   * 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-boxes-private.h"
  #include "cairo-combsort-inline.h"
  #include "cairo-error-private.h"
  #include "cairo-traps-private.h"
  
  typedef struct _cairo_bo_edge cairo_bo_edge_t;
  typedef struct _cairo_bo_trap cairo_bo_trap_t;
  
  /* A deferred trapezoid of an edge */
  struct _cairo_bo_trap {
      cairo_bo_edge_t *right;
      int32_t top;
  };
  
  struct _cairo_bo_edge {
      cairo_edge_t edge;
      cairo_bo_edge_t *prev;
      cairo_bo_edge_t *next;
      cairo_bo_trap_t deferred_trap;
  };
  
  typedef enum {
      CAIRO_BO_EVENT_TYPE_START,
      CAIRO_BO_EVENT_TYPE_STOP
  } cairo_bo_event_type_t;
  
  typedef struct _cairo_bo_event {
      cairo_bo_event_type_t type;
      cairo_point_t point;
      cairo_bo_edge_t *edge;
  } cairo_bo_event_t;
  
  typedef struct _cairo_bo_sweep_line {
      cairo_bo_event_t **events;
      cairo_bo_edge_t *head;
      cairo_bo_edge_t *stopped;
      int32_t current_y;
      cairo_bo_edge_t *current_edge;
  } cairo_bo_sweep_line_t;
  
  static inline int
  _cairo_point_compare (const cairo_point_t *a,
  		      const cairo_point_t *b)
  {
      int cmp;
  
      cmp = a->y - b->y;
      if (likely (cmp))
  	return cmp;
  
      return a->x - b->x;
  }
  
  static inline int
  _cairo_bo_edge_compare (const cairo_bo_edge_t	*a,
  			const cairo_bo_edge_t	*b)
  {
      int cmp;
  
      cmp = a->edge.line.p1.x - b->edge.line.p1.x;
      if (likely (cmp))
  	return cmp;
  
      return b->edge.bottom - a->edge.bottom;
  }
  
  static inline int
  cairo_bo_event_compare (const cairo_bo_event_t *a,
  			const cairo_bo_event_t *b)
  {
      int cmp;
  
      cmp = _cairo_point_compare (&a->point, &b->point);
      if (likely (cmp))
  	return cmp;
  
      cmp = a->type - b->type;
      if (cmp)
  	return cmp;
  
      return (int)(a - b);
  }
  
  static inline cairo_bo_event_t *
  _cairo_bo_event_dequeue (cairo_bo_sweep_line_t *sweep_line)
  {
      return *sweep_line->events++;
  }
  
  CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
  			cairo_bo_event_t *,
  			cairo_bo_event_compare)
  
  static void
  _cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line,
  			   cairo_bo_event_t	**events,
  			   int			  num_events)
  {
      _cairo_bo_event_queue_sort (events, num_events);
      events[num_events] = NULL;
      sweep_line->events = events;
  
      sweep_line->head = NULL;
      sweep_line->current_y = INT32_MIN;
      sweep_line->current_edge = NULL;
  }
  
  static void
  _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t	*sweep_line,
  			     cairo_bo_edge_t		*edge)
  {
      if (sweep_line->current_edge != NULL) {
  	cairo_bo_edge_t *prev, *next;
  	int cmp;
  
  	cmp = _cairo_bo_edge_compare (sweep_line->current_edge, edge);
  	if (cmp < 0) {
  	    prev = sweep_line->current_edge;
  	    next = prev->next;
  	    while (next != NULL && _cairo_bo_edge_compare (next, edge) < 0)
  		prev = next, next = prev->next;
  
  	    prev->next = edge;
  	    edge->prev = prev;
  	    edge->next = next;
  	    if (next != NULL)
  		next->prev = edge;
  	} else if (cmp > 0) {
  	    next = sweep_line->current_edge;
  	    prev = next->prev;
  	    while (prev != NULL && _cairo_bo_edge_compare (prev, edge) > 0)
  		next = prev, prev = next->prev;
  
  	    next->prev = edge;
  	    edge->next = next;
  	    edge->prev = prev;
  	    if (prev != NULL)
  		prev->next = edge;
  	    else
  		sweep_line->head = edge;
  	} else {
  	    prev = sweep_line->current_edge;
  	    edge->prev = prev;
  	    edge->next = prev->next;
  	    if (prev->next != NULL)
  		prev->next->prev = edge;
  	    prev->next = edge;
  	}
      } else {
  	sweep_line->head = edge;
      }
  
      sweep_line->current_edge = edge;
  }
  
  static void
  _cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t	*sweep_line,
  			     cairo_bo_edge_t	*edge)
  {
      if (edge->prev != NULL)
  	edge->prev->next = edge->next;
      else
  	sweep_line->head = edge->next;
  
      if (edge->next != NULL)
  	edge->next->prev = edge->prev;
  
      if (sweep_line->current_edge == edge)
  	sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
  }
  
  static inline cairo_bool_t
  edges_collinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
  {
      return a->edge.line.p1.x == b->edge.line.p1.x;
  }
  
  static cairo_status_t
  _cairo_bo_edge_end_trap (cairo_bo_edge_t	*left,
  			 int32_t		 bot,
  			 cairo_bool_t		 do_traps,
  			 void			*container)
  {
      cairo_bo_trap_t *trap = &left->deferred_trap;
      cairo_status_t status = CAIRO_STATUS_SUCCESS;
  
      /* Only emit (trivial) non-degenerate trapezoids with positive height. */
      if (likely (trap->top < bot)) {
  	if (do_traps) {
  	    _cairo_traps_add_trap (container,
  				   trap->top, bot,
  				   &left->edge.line, &trap->right->edge.line);
  	    status =  _cairo_traps_status ((cairo_traps_t *) container);
  	} else {
  	    cairo_box_t box;
  
  	    box.p1.x = left->edge.line.p1.x;
  	    box.p1.y = trap->top;
  	    box.p2.x = trap->right->edge.line.p1.x;
  	    box.p2.y = bot;
  	    status = _cairo_boxes_add (container, CAIRO_ANTIALIAS_DEFAULT, &box);
  	}
      }
  
      trap->right = NULL;
  
      return status;
  }
  
  /* Start a new trapezoid at the given top y coordinate, whose edges
   * are `edge' and `edge->next'. If `edge' already has a trapezoid,
   * then either add it to the traps in `traps', if the trapezoid's
   * right edge differs from `edge->next', or do nothing if the new
   * trapezoid would be a continuation of the existing one. */
  static inline cairo_status_t
  _cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t	*left,
  				       cairo_bo_edge_t  *right,
  				       int               top,
  				       cairo_bool_t	 do_traps,
  				       void		*container)
  {
      cairo_status_t status;
  
      if (left->deferred_trap.right == right)
  	return CAIRO_STATUS_SUCCESS;
  
      if (left->deferred_trap.right != NULL) {
  	if (right != NULL && edges_collinear (left->deferred_trap.right, right))
  	{
  	    /* continuation on right, so just swap edges */
  	    left->deferred_trap.right = right;
  	    return CAIRO_STATUS_SUCCESS;
  	}
  
  	status = _cairo_bo_edge_end_trap (left, top, do_traps, container);
  	if (unlikely (status))
  	    return status;
      }
  
      if (right != NULL && ! edges_collinear (left, right)) {
  	left->deferred_trap.top = top;
  	left->deferred_trap.right = right;
      }
  
      return CAIRO_STATUS_SUCCESS;
  }
  
  static inline cairo_status_t
  _active_edges_to_traps (cairo_bo_edge_t		*left,
  			int32_t			 top,
  			cairo_fill_rule_t	 fill_rule,
  			cairo_bool_t		 do_traps,
  			void			*container)
  {
      cairo_bo_edge_t *right;
      cairo_status_t status;
  
      if (fill_rule == CAIRO_FILL_RULE_WINDING) {
  	while (left != NULL) {
  	    int in_out;
  
  	    /* Greedily search for the closing edge, so that we generate the
  	     * maximal span width with the minimal number of trapezoids.
  	     */
  	    in_out = left->edge.dir;
  
  	    /* Check if there is a co-linear edge with an existing trap */
  	    right = left->next;
  	    if (left->deferred_trap.right == NULL) {
  		while (right != NULL && right->deferred_trap.right == NULL)
  		    right = right->next;
  
  		if (right != NULL && edges_collinear (left, right)) {
  		    /* continuation on left */
  		    left->deferred_trap = right->deferred_trap;
  		    right->deferred_trap.right = NULL;
  		}
  	    }
  
  	    /* End all subsumed traps */
  	    right = left->next;
  	    while (right != NULL) {
  		if (right->deferred_trap.right != NULL) {
  		    status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
  		    if (unlikely (status))
  			return status;
  		}
  
  		in_out += right->edge.dir;
  		if (in_out == 0) {
  		    /* skip co-linear edges */
  		    if (right->next == NULL ||
  			! edges_collinear (right, right->next))
  		    {
  			break;
  		    }
  		}
  
  		right = right->next;
  	    }
  
  	    status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
  							    do_traps, container);
  	    if (unlikely (status))
  		return status;
  
  	    left = right;
  	    if (left != NULL)
  		left = left->next;
  	}
      } else {
  	while (left != NULL) {
  	    int in_out = 0;
  
  	    right = left->next;
  	    while (right != NULL) {
  		if (right->deferred_trap.right != NULL) {
  		    status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
  		    if (unlikely (status))
  			return status;
  		}
  
  		if ((in_out++ & 1) == 0) {
  		    cairo_bo_edge_t *next;
  		    cairo_bool_t skip = FALSE;
  
  		    /* skip co-linear edges */
  		    next = right->next;
  		    if (next != NULL)
  			skip = edges_collinear (right, next);
  
  		    if (! skip)
  			break;
  		}
  
  		right = right->next;
  	    }
  
  	    status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
  							    do_traps, container);
  	    if (unlikely (status))
  		return status;
  
  	    left = right;
  	    if (left != NULL)
  		left = left->next;
  	}
      }
  
      return CAIRO_STATUS_SUCCESS;
  }
  
  static cairo_status_t
  _cairo_bentley_ottmann_tessellate_rectilinear (cairo_bo_event_t   **start_events,
  					       int			 num_events,
  					       cairo_fill_rule_t	 fill_rule,
  					       cairo_bool_t		 do_traps,
  					       void			*container)
  {
      cairo_bo_sweep_line_t sweep_line;
      cairo_bo_event_t *event;
      cairo_status_t status;
  
      _cairo_bo_sweep_line_init (&sweep_line, start_events, num_events);
  
      while ((event = _cairo_bo_event_dequeue (&sweep_line))) {
  	if (event->point.y != sweep_line.current_y) {
  	    status = _active_edges_to_traps (sweep_line.head,
  					     sweep_line.current_y,
  					     fill_rule, do_traps, container);
  	    if (unlikely (status))
  		return status;
  
  	    sweep_line.current_y = event->point.y;
  	}
  
  	switch (event->type) {
  	case CAIRO_BO_EVENT_TYPE_START:
  	    _cairo_bo_sweep_line_insert (&sweep_line, event->edge);
  	    break;
  
  	case CAIRO_BO_EVENT_TYPE_STOP:
  	    _cairo_bo_sweep_line_delete (&sweep_line, event->edge);
  
  	    if (event->edge->deferred_trap.right != NULL) {
  		status = _cairo_bo_edge_end_trap (event->edge,
  						  sweep_line.current_y,
  						  do_traps, container);
  		if (unlikely (status))
  		    return status;
  	    }
  
  	    break;
  	}
      }
  
      return CAIRO_STATUS_SUCCESS;
  }
  
  cairo_status_t
  _cairo_bentley_ottmann_tessellate_rectilinear_polygon_to_boxes (const cairo_polygon_t *polygon,
  								cairo_fill_rule_t	  fill_rule,
  								cairo_boxes_t *boxes)
  {
      cairo_status_t status;
      cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
      cairo_bo_event_t *events;
      cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
      cairo_bo_event_t **event_ptrs;
      cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
      cairo_bo_edge_t *edges;
      int num_events;
      int i, j;
  
      if (unlikely (polygon->num_edges == 0))
  	return CAIRO_STATUS_SUCCESS;
  
      num_events = 2 * polygon->num_edges;
  
      events = stack_events;
      event_ptrs = stack_event_ptrs;
      edges = stack_edges;
      if (num_events > ARRAY_LENGTH (stack_events)) {
  	events = _cairo_malloc_ab_plus_c (num_events,
  					  sizeof (cairo_bo_event_t) +
  					  sizeof (cairo_bo_edge_t) +
  					  sizeof (cairo_bo_event_t *),
  					  sizeof (cairo_bo_event_t *));
  	if (unlikely (events == NULL))
  	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  
  	event_ptrs = (cairo_bo_event_t **) (events + num_events);
  	edges = (cairo_bo_edge_t *) (event_ptrs + num_events + 1);
      }
  
      for (i = j = 0; i < polygon->num_edges; i++) {
  	edges[i].edge = polygon->edges[i];
  	edges[i].deferred_trap.right = NULL;
  	edges[i].prev = NULL;
  	edges[i].next = NULL;
  
  	event_ptrs[j] = &events[j];
  	events[j].type = CAIRO_BO_EVENT_TYPE_START;
  	events[j].point.y = polygon->edges[i].top;
  	events[j].point.x = polygon->edges[i].line.p1.x;
  	events[j].edge = &edges[i];
  	j++;
  
  	event_ptrs[j] = &events[j];
  	events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
  	events[j].point.y = polygon->edges[i].bottom;
  	events[j].point.x = polygon->edges[i].line.p1.x;
  	events[j].edge = &edges[i];
  	j++;
      }
  
      status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
  							    fill_rule,
  							    FALSE, boxes);
      if (events != stack_events)
  	free (events);
  
      return status;
  }
  
  cairo_status_t
  _cairo_bentley_ottmann_tessellate_rectilinear_traps (cairo_traps_t *traps,
  						     cairo_fill_rule_t fill_rule)
  {
      cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
      cairo_bo_event_t *events;
      cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
      cairo_bo_event_t **event_ptrs;
      cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
      cairo_bo_edge_t *edges;
      cairo_status_t status;
      int i, j, k;
  
      if (unlikely (traps->num_traps == 0))
  	return CAIRO_STATUS_SUCCESS;
  
      assert (traps->is_rectilinear);
  
      i = 4 * traps->num_traps;
  
      events = stack_events;
      event_ptrs = stack_event_ptrs;
      edges = stack_edges;
      if (i > ARRAY_LENGTH (stack_events)) {
  	events = _cairo_malloc_ab_plus_c (i,
  					  sizeof (cairo_bo_event_t) +
  					  sizeof (cairo_bo_edge_t) +
  					  sizeof (cairo_bo_event_t *),
  					  sizeof (cairo_bo_event_t *));
  	if (unlikely (events == NULL))
  	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  
  	event_ptrs = (cairo_bo_event_t **) (events + i);
  	edges = (cairo_bo_edge_t *) (event_ptrs + i + 1);
      }
  
      for (i = j = k = 0; i < traps->num_traps; i++) {
  	edges[k].edge.top = traps->traps[i].top;
  	edges[k].edge.bottom = traps->traps[i].bottom;
  	edges[k].edge.line = traps->traps[i].left;
  	edges[k].edge.dir = 1;
  	edges[k].deferred_trap.right = NULL;
  	edges[k].prev = NULL;
  	edges[k].next = NULL;
  
  	event_ptrs[j] = &events[j];
  	events[j].type = CAIRO_BO_EVENT_TYPE_START;
  	events[j].point.y = traps->traps[i].top;
  	events[j].point.x = traps->traps[i].left.p1.x;
  	events[j].edge = &edges[k];
  	j++;
  
  	event_ptrs[j] = &events[j];
  	events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
  	events[j].point.y = traps->traps[i].bottom;
  	events[j].point.x = traps->traps[i].left.p1.x;
  	events[j].edge = &edges[k];
  	j++;
  	k++;
  
  	edges[k].edge.top = traps->traps[i].top;
  	edges[k].edge.bottom = traps->traps[i].bottom;
  	edges[k].edge.line = traps->traps[i].right;
  	edges[k].edge.dir = -1;
  	edges[k].deferred_trap.right = NULL;
  	edges[k].prev = NULL;
  	edges[k].next = NULL;
  
  	event_ptrs[j] = &events[j];
  	events[j].type = CAIRO_BO_EVENT_TYPE_START;
  	events[j].point.y = traps->traps[i].top;
  	events[j].point.x = traps->traps[i].right.p1.x;
  	events[j].edge = &edges[k];
  	j++;
  
  	event_ptrs[j] = &events[j];
  	events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
  	events[j].point.y = traps->traps[i].bottom;
  	events[j].point.x = traps->traps[i].right.p1.x;
  	events[j].edge = &edges[k];
  	j++;
  	k++;
      }
  
      _cairo_traps_clear (traps);
      status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
  							    fill_rule,
  							    TRUE, traps);
      traps->is_rectilinear = TRUE;
  
      if (events != stack_events)
  	free (events);
  
      return status;
  }
  