#include	"defs.h"



/*
 * scan all signals and minimise wire length.
 * cptr points to chip whose nets to be minimised.
 * if cptr==0 do all nets
 */

minroute(cptr) 
	CHP cptr;
{
	REG PIN pptr, pp;
	PIN pend, pstart;
	INT	pincnt;

	if (cptr)
	{
		pstart = &cptr->pins[0];
		pend = &cptr->pins[cptr->siz];
	}
	else	{
		pstart = nets;
		pend = Enets;
	}
	for (pptr = pstart; pptr < pend; pptr++)
	{
		pincnt = 1;
		for (pp = CHAIN(pptr); pp != pptr; pp = CHAIN(pp))
		{
			pincnt++;
			if (pp < pptr && cptr == 0) goto ignore;
		}
		if (pincnt >= NDPIN)
			goto ignore;
		pp = CHAIN(pptr);
		if (pp == pptr || pptr == CHAIN(pp))
		{
			if (pptr->x & UNPLAC)
				pp = pptr;
			pp->chain = CHAIN(pp);
			pp = pp->chain;
			if (pp->x & UNPLAC)
				pp->chain = CHAIN(pp);
			else pp->chain = SETBIT(pp->chain);
			goto ignore;
		}
		setroute(pptr);
ignore:;
	}
	if (cptr == 0) okroute = 1;
}



/* set route for net. */

CHOSE chosevec[] = {
	chosex, chosey, chosen, nil(CHOSE)};

LOC VOID setroute(pptr)
	PIN pptr;
{
	CHOSE *chose;
	L_INT	sum, bsum;

	nbuild(pptr);
	if (npins > 2)
	{
		bsum = MAXLONG;
		for (chose = &chosevec[0]; *chose; chose++)
		{
			nsort(*chose);
			dfill();
			nroute();
			sum = dsum();
			if (sum < bsum)
			{
				putback();
				bsum = sum;
			}
			if (npins < 4) break;
		}
	}
	else
		putback();
}


/*
 * wire routing based upon traveling saleseman algorithm
 * developed by S. Lin and called the "2-optimal"
 * algorithm.   The technique is to look for a substring
 * within the current string of nodes, such that by reversing
 * the sequence of nodes in the substring, the total wire
 * length is reduced. e.g. 1,2,3,4,5,6,7,8 might be changed to
 * 1,2,7,6,5,4,3,8.
 * We do three tries at optimisation based on three starting positions.
 * fist order the pins on increasing x coord.
 * second order the pins on increasing y coord.
 * third order the pins by first taking the one that is
 *    farthest from the centre of gravity then take the
 *    pin nearest to the last one taken.
 *
 * An alternative algorithm is described in "Computer Solutions
 * to The Traveling Salesman Problem", BSTJ 44,10 (Dec 1965)
 * by S. Lin.   That is the 3-opt algorithm and is better
 * then the 2-optimum one programmed here.
 * In case it is needed, the 3-opt algorithm is as follows:
 * Let n = number of points.
 * Connect the points randomly into a sequence 1 ... n
 * For n times do
 *	{
 * 	For k = 1(1)n-3
 *		{
 *    		For j = k+1(1)n-1
 *			{
 *			Consider the following changes:
 *			deletetion of j -> j+1 -> j+2 and k -> k+1
 *			then either
 *				addition of n -> k+1, j ->1, k -> j+1
 *			or
 *				addition of n -> k+1, j -> k, 1 -> j+1
 *			define new ends to be j+2 and j+1
 *			If an improvement can be made start the entrire
 *			process over with the improved sequence.
 *			}
 *		}
 *	rotate the set of points one place.
 *	}
 */





/* build pinvec for a given net */

LOC VOID nbuild(pptr) 
	PIN pptr;
{
	REG PIN pp;
	PIN up;
	REG DPIN dv;

	dv = &pinvec[0];
	up = 0;
	npins = 0;
	pp = pptr;
	do	{
		pp->chain = CHAIN(pp);
		if (pp->x & UNPLAC)
		{
			if (up == 0) up = pp;
		}
		else	{
			dv->pinp = pp;
			if (npins++ == 0)
				pp->chain = SETBIT(pp->chain);
			dv++;
		}
		pp = CHAIN(pp);
	} 
	while (pp != pptr);
	tpins = npins;
	if (pp = up) do
	    {
		if (pp->x & UNPLAC)
		{
			tpins++;
			dv->pinp = pp;
			dv++;
		}
		pp = CHAIN(pp);
	} 
	while (pp != pptr);
}


/* restructure net according the result in pinvec[]
 * return ptr to first pin in net */

LOC VOID putback()
{
	REG PIN pp, opp;
	REG DPIN dv;

	pp = pinvec[tpins-1].pinp;
	for (dv = &pinvec[0]; dv < &pinvec[tpins]; dv++)
	{
		opp = pp;
		pp = dv->pinp;
		opp->chain = pp;
	}
	pp = pinvec[0].pinp;
	pp->chain = SETBIT(pp->chain);
}