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

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

/*-
	An assortment of functions to make queries about shapes

	shqueries.c, Sun Aug 25 17:24:38 1985

		James Gosling,
		Sun Microsystems
 */

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

cv_pointinnonrectshape(sh,x,y)
register struct shape *sh; {
    register struct shape_trapezon *t;
    for (t = sh->trapset; t; t = t->next)
	if (y >= t->top && y < t->bottom) {
	    register    lo,
	                hi;
	    lo = 0;
	    hi = t->used - 1;
	    while (lo < hi) {
		register    mid;
		mid = (hi + lo + 1) >> 1;
		if (t->segs[mid].y <= y)
		    lo = mid;
		else
		    hi = mid - 1;
	    }
	    {
		register struct shape_trapseg *lop = &t->segs[lo];
		if (lop->x1 <= x && x < lop->x2)
		    return 1;
	    }
	}
    return 0;
}

struct band_state {
    short       leftout,
                leftin,
                rightin,
                rightout;
};

struct band_state *band_in_trap(t,y0,y1)
register struct shape_trapezon *t; {
    register    min1,
                max1,
                min2,
                max2;
    static struct band_state ret;
    int         allslow = 0;
    register struct shape_trapseg *p;
    if (y1 <= t->top || y0 >= t->bottom)
	return 0;
    if (y0 <= t->top) {
	if (y0 < t->top)
	    allslow = 1;
	p = t->segs;
    }
    else {
	register    lo,
	            hi;
	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];
    }
    if (y1 > t->bottom) {
	y1 = t->bottom;
	allslow = 1;
    }
    min1 = p->x1;
    max1 = min1;
    min2 = p->x2;
    max2 = min2;
    while ((++p)->y < y1) {
	register    t;
	if ((t = p->x1) < min1)
	    min1 = t;
	if (t > max1)
	    max1 = t;
	if ((t = p->x2) < min2)
	    min2 = t;
	if (t > max2)
	    max2 = t;
    }
    if (allslow || max1 >= min2) {
	ret.leftout = min1;
	ret.leftin = max2;
	ret.rightin = max2;
	ret.rightout = max2;
    }
    else {
	ret.leftout = min1;
	ret.leftin = max1;
	ret.rightin = min2;
	ret.rightout = max2;
    }
    return &ret;
}