#ifndef lint
static char sccsid[] = "@(#)gensh_vect.c 9.2 88/01/19 Copyright 1985 Sun Micro";
#endif

/*
 * Copyright (c) 1985 by Sun Microsystems, Inc.
 */

/*-
	Generic module for drawing vectors clipped to shapes

	gensh_vector, Thu Oct 10 15:51:14 1985

		James Gosling,
		Sun Microsystems
 */

#include <stdio.h>
#ifdef REF
#include <sys/types.h>
#include <ref/config.h>
#endif
#include "qalloc.h"
#include "shape.h"

generic_shapevector(pr, shape, x0, y0, x1, y1, op, color)
    register struct pixrect *pr;
    register struct shape *shape;
{
    int         left,
                right,
                top,
                bottom;
    if (shape == 0)
	return 0;
    left = 0;
    right = pr->pr_width;
    top = 0;
    bottom = pr->pr_height;
    {
	register    xmin,
	            xmax;
	if (y1 < y0) {
	    xmin = y1;
	    y1 = y0;
	    y0 = xmin;
	    xmin = x1;
	    x1 = x0;
	    x0 = xmin;
	}
	if ((xmin = shape->pos.x) > left)
	    left = xmin;
	if ((xmin = shape->pos.x + shape->size.x) < right)
	    right = xmin;
	if ((xmin = shape->pos.y) > top)
	    top = xmin;
	if ((xmin = shape->pos.y + shape->size.y) < bottom)
	    bottom = xmin;
	if (x0 < x1)
	    xmin = x0, xmax = x1;
	else
	    xmin = x1, xmax = x0;
	if (x0 == x1) {		/* Vertical line */
	    struct shape tshape;
	    tshape = *shape;
	    if (x0 < left || x0 >= right)
		return 0;
	    if (y0 < top)
		y0 = top;
	    if (y1 > bottom)
		y1 = bottom;
	    tshape.pos.x = x0;
	    tshape.pos.y = y0;
	    tshape.size.x = 1;
	    if ((tshape.size.y = y1 - y0 + 1) <= 0)
		return 0;
	    return pr_shaperop(pr, &tshape, op | PIX_COLOR(color), 0, 0, 0);
	}
	if (y0 == y1) {		/* Horizontal line */
	    struct shape tshape;
	    tshape = *shape;
	    if (y0 < top || y0 >= bottom)
		return 0;
	    if (xmin < left)
		xmin = left;
	    if (xmax > right)
		xmax = right;
	    tshape.pos.x = xmin;
	    tshape.pos.y = y0;
	    if ((tshape.size.x = xmax - xmin + 1) <= 0)
		return 0;
	    tshape.size.y = 1;
	    return pr_shaperop(pr, &tshape, op | PIX_COLOR(color), 0, 0, 0);
	}
	if (top >= y1 || bottom <= y0 || right <= xmin || left >= xmax)
	    return 0;
	if (y0 < top || y1 > bottom || xmin < left || xmax > right)
	    goto hard_case;
	if (!shape->is_rect) {
	    register struct shape_trapezon *t = shape->trapset;
	    /*
	     * Search for a trapezon that completely contains the vector
	     */
	    for (t = shape->trapset; t; t = t->next) {
		register struct shape_trapseg *p;
		register    lo,
		            hi;
		if (t->top >= y1 || t->bottom <= y0 || t->top >= y0 || t->bottom <= y1)
		    continue;
		lo = 0;
		hi = t->used - 1;
		while (lo < hi) {
		    register    mid;
		    mid = (hi + lo + 1) >> 1;
		    if (t->segs[mid].y <= y0)
			lo = mid;
		    else
			hi = mid - 1;
		}
		p = &t->segs[lo];
		while (p->y < y1) {
		    if (p->x1 > xmin || p->x2 < xmax)
			goto next_case;
		    p++;
		}
		return pr_vector(pr, x0, y0, x1, y1, op | PIX_DONTCLIP, color);
	next_case:;
	    }
	    goto hard_case;
	}
	return pr_vector(pr, x0, y0, x1, y1, op | PIX_DONTCLIP, color);
    }
hard_case:

    /*
     * This is really a half-hearted attempt to deal with clipping vectors to
     * shapes.  It's half-hearted because the real right thing to do is to
     * integrate clipping with the vector routines, but there are some ugly
     * historical problems with pixrects that I don't personally have the
     * energy to deal with -- JAG
     */

    {				/* Convert a vector into a curve */
	/*
	 * On machines where division is real slow, this might be done better
	 * with a bresenham line follower
	 */
	static      curvesize;
	static struct shape_dcurve *dc;
	register    dx,
	            dy,
	            error,
	            count;
	register short *yp;
	fract       x;
	register fract delta;
	count = y1 - y0 + 1;
	assert(y0 < y1);
	if (curvesize <= count) {
	    curvesize = count + 10;
	    if (dc)
		QFREE(dc);
	    QALLOC(dc, (sizeof(struct shape_dcurve) + sizeof(short) * curvesize), (struct shape_dcurve *));
	    dc->x = (short *) (((char *) dc) + sizeof(struct shape_dcurve));
	    dc->direction = 1;
	    dc->next = 0;
	    dc->refcnt = 999;
	}
	dc->x0 = x0;
	dc->x1 = x1;
	dc->y0 = y0;
	dc->y1 = y1;

#ifdef undef
	if (x0 < x1)
	    dc->left = x0, dc->right = x1;
	else
	    dc->left = x1, dc->right = x0;
	yp = dc->x;
	delta = fracti(x1 - x0) / (y1 - y0);
	x = fracti(x0) + (delta >> 1) + fraction(1, 2);
	dc->x[d] = x1;
	d--;
	*yp++ = x0;
	while (--d >= 0) {
	    *yp++ = cfloorfr(x);
	    x += delta;
	}
#else
	dx = x1 - x0;
	dy = y1 - y0;
#define swap(a,b,t) ((t)=(a),(a)=(b),(b)=(t))
	if (dx < 0) {
	    /* force vector to scan left to right */
	    dx = -dx;
	    dy = -dy;
	    swap(x0, x1, count);
	    swap(y0, y1, count);
	}
	if (x0 < dc->left)
	    dc->left = x0;
	if (x1 > dc->right)
	    dc->right = x1;
	yp = &dc->x[y0 - dc->y0];
	if (dy < 0) {		/* runs upward */
	    dc->x[y1 - dc->y0] = x1;
	    yp++;
	    dy = -dy;
	    if (dx < dy) {	/* y major, up */
		*yp = x0;
		error = -(dy >> 1);
		for (count = dy; --count >= 0;) {
		    if ((error += dx) > 0)
			error -= dy, x0++;
		    *--yp = x0;
		}
	    }
	    else {		/* x major, up */
		*yp = x0++; /*++x0*/
		error = -(dx >> 1);
		for (count = dx; --count >= 0;) {
		    if ((error += dy) > 0)
			error -= dx, *--yp = x0;
		    x0++;
		}
	    }
	}
	else {			/* runs downward */
	    dc->x[y1 - dc->y0 + 1] = x1;
	    *yp++ = x0;
	    if (dx < dy) {	/* y major, down */
		error = -(dy >> 1);
		for (count = dy; --count >= 0;) {
		    *yp++ = x0;
		    if ((error += dx) > 0)
			error -= dy, x0++;
		}
	    }
	    else {		/* x major, down */
		error = -(dx >> 1);
		for (count = dx; --count >= 0;) {
		    if ((error += dy) > 0)
			error -= dx, *yp++ = x0;
		    x0++;
		}
	    }
	}
#endif

	pr_shapecurve(pr, shape, dc, PIX_COLOR(color) | op, 0, 0);
    }
}