#include	"defs.h"

LOC INT	bestdist;

DL findL(s)
	STRING	s;
{
	REG DL	op;

	if ((op = findname('L', s)) == 0) {
		op = newdln(BEFORE, last('L'), 'L', 0, s, nil(STRING));
		newdlw(AFTER, op, 'x', 0, point(0,0), 0);
	}

	return(op);
}

/*
 * find the shape or circle instance containing pt x.
 *
 * h is addr of header.
 * return(0) if no instance found.
 */
DL finda(h, x)
	REG DL h, x;
{
	REG DL q;

	q = h;
	while(q=nexta(h->type, q)) {
		if( (q->flag & START)
		    && within(q,x,succa(q)))
			return(q);
	}
	return(nil(DL));
}

/*
 * Find the closest entry of a given type to a position.
 *
 * t = type
 * h = item head
 * q = position to compare
 * return = closest entry of type t, 0 if none
 */
DL findclose(t, h, q)
	REG DL h;
	DL q;
{
	REG DL p;
	REG INT i;
	DL bestp;
	INT bestdist;

	bestp = nil(DL);
	bestdist = 640>>gscale;
	p = h;
	while(p=nexta(h->type, p)) {
		if((p->type == t)
		    && ((i = xydist(p, q)) < bestdist)){
			bestdist = i;
			bestp = p;
		}
	}
	return(bestp);
}

/*
 * find chip or wire at cross hairs
 */
DL findx()
{
	REG DL	f, g;
	DL1	p;

	cursor(p);
	f=findhead('w', p);
	if(bestdist) {
		g=findhead('c', p);
		if(g)
			f=g;
	}
	if(f==nil(DL))
		error("cannot find it");
	return(f);
}

/*
 * Find the header of an item closest to a given position.
 *
 * t = entry type character
 * x = position
 * return = pointer to item header that contains an entry closest to x; 0 if none
 */
DL findhead(t, x)
	S_POS t;
	DL x;
{
	REG DL	p, q;
	REG INT i;
	DL	bestp, tp, r, z;

	bestp = 0;
	bestdist = 640>>gscale;
	p=dstart;
	while(p=next(t,p)) {
		q=p;
		while(q=nexta(t,q)) {
			switch(q->type){
			case 'a':
			case 'o':
				if ((q->flag & START) && within(q, x, succa(q)))
					return(p);
				break;
			case 'e':
				z = q;
				if(!(q->flag & END)) {
					r = succa(q);
					tp = (r->y==q->y)? point(x->x,q->y) : point(q->x,x->y);
					if(between(dlw(q),dlw(tp),dlw(r))) {
						z = tp;
					}
				}
				if((i = xydist(x,z)) < bestdist) {
					bestdist = i;
					bestp = p;
				}
				break;
			case 'h':
			case 'v':
			case 'V':
			case 'p':
				if((i = xydist(q, x)) < bestdist){
					bestdist = i;
					bestp = p;
				}
			}
			if(bestdist == 0)
				return(bestp);
		}
	}
	return(bestp);
}

/*
 * Find item given its name.
 *
 * t = type of item
 * s = name to find
 * return = item pointer of 0 if not found
 */
DL findname(t, s)
	STRING s;
{
	REG DL p;

	p = dstart;
	if (s!=nil(STRING)) {
		while(p=next(t,p)) {
			if(equstr(s, dln(p)->name))
				return(p);
		}
	}
	return(nil(DL));
}

/*
 * Find the point closest to a given position.
 *
 * h = item head
 * q = position
 * return = closest 'e' entry, 0 if none
 */
DL findpt(h, q)
	DL h, q;
{
	return(findclose('e', h, q));
}

/*
 *
 * Find the line segment (p1, p2) such that the perpendicular from z
 * to (p1, p2) intersects at point p3 on the open interval (p1, p2)
 * and the distance from p3 to z is minimal.
 *
 * h = item header
 * z = (cursor) position
 * returns p1 where p2=succa(p1), or nil if no points satisfy the conditions
 *
 */

DL findseg(h, z)
	DL h, z;
{
	DL p, q;
	DL tp, bestp;
	DL1	zp;
	INT m, bestdist;

	bestp = nil(DL);
	bestdist = 640>>gscale;

	p=h;
	while(p=nexta(h->type,p)) {
		if(p->type=='e'){
			if((m=xydist(p,z))<bestdist){
				bestdist=m;
				bestp = p;
				copypt(p,zp);
			}
			if(p->flag&END) continue;
			q=succa(p);
			tp = (p->y==q->y) ? point(z->x,p->y) : point(p->x, z->y);
			if(between(dlw(p), dlw(tp), dlw(q)) && ((m=xydist(tp, z)) <= bestdist)){
				copypt(tp,zp);
				bestp=p;
				bestdist=m;
			}
		}
	}

	copypt(zp,z);
	return(bestp);
}

/*
 * Find an entry of a given type at the exact position given.
 *
 * t = type
 * h = item head
 * q = position
 * return = first entry with position q, 0 if none
 */
DL findxact(t, h, q)
	REG DL h, q;
{
	REG DL p;

	p = h;
	while(p=nexta(h->type,p)) {
		if((p->type == t) && xysame(p, q))
			return(p);
	}
	return(nil(DL));
}