
#ifndef lint
static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/resis/ResMakeRes.c,v 1.3 2010/06/24 12:37:56 tim Exp $";
#endif  /* not lint */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

#include "utils/magic.h"
#include "utils/geometry.h"
#include "utils/geofast.h"
#include "tiles/tile.h"
#include "utils/hash.h"
#include "database/database.h"
#include "utils/malloc.h"
#include "textio/textio.h"
#include "extract/extract.h"
#include "extract/extractInt.h"
#include "windows/windows.h"
#include "dbwind/dbwind.h"
#include "utils/tech.h"
#include "textio/txcommands.h"
#include "resis/resis.h"
#include "cif/CIFint.h"

/* C99 compat */
#include "cif/cif.h"

/* Forward declarations */
bool ResCalcNearDevice();
bool ResCalcNorthSouth();
bool ResCalcEastWest();


/*
 *--------------------------------------------------------------------------
 *
 * ResCalcTileResistance-- Given a set of partitions for a tile, the tile can
 *	be converted into resistors. To do this, nodes are sorted in the
 *	direction of current flow. Resistors are created by counting squares
 *	between successive breakpoints. Breakpoints with the same coordinate
 *	are combined.
 *
 *   Results: returns TRUE if the startnode was involved in a merge.
 *
 *   Side Effects:  Resistor structures are produced.  Some nodes may be
 *		    eliminated.
 *--------------------------------------------------------------------------
 */

bool
ResCalcTileResistance(tile, info, pendingList, doneList)
    Tile 	*tile;
    resInfo 	*info;
    resNode	**pendingList, **doneList;

{
    int 	MaxX = MINFINITY, MinX = INFINITY;
    int		MaxY = MINFINITY, MinY = INFINITY;
    int		device;
    bool	merged;
    Breakpoint 	*p1;

    merged = FALSE;
    device = FALSE;

    if ((p1 = info->breakList) == NULL) return FALSE;
    for (; p1; p1 = p1->br_next)
    {
	int	x = p1->br_loc.p_x;
	int	y = p1->br_loc.p_y;
	if (x > MaxX) MaxX = x;
	if (x < MinX) MinX = x;
	if (y > MaxY) MaxY = y;
	if (y < MinY) MinY = y;

	if (p1->br_this->rn_why == RES_NODE_DEVICE)
	    device = TRUE;
    }

    /* Finally, produce resistors for partition. Keep track of	*/
    /* whether or not the node was involved in a merge.		*/

    if (device)
    {
	merged |= ResCalcNearDevice(tile, pendingList, doneList, &ResResList);
    }
    else if (MaxY-MinY > MaxX-MinX)
    {
	merged |= ResCalcNorthSouth(tile, pendingList, doneList, &ResResList);
    }
    else
    {
	merged |= ResCalcEastWest(tile, pendingList, doneList, &ResResList);
    }

    /*
     * For all the new resistors, propagate the resistance from the origin
     * to the new nodes.
     */

    return(merged);
}


/*
 *-------------------------------------------------------------------------
 *
 * ResCalcEastWest-- Makes resistors from an EastWest partition.
 *
 * Results: Returns TRUE if the sacredNode was involved in a merge.
 *
 * Side Effects: Makes resistors. Frees breakpoints.
 *
 *-------------------------------------------------------------------------
 */

bool
ResCalcEastWest(tile, pendingList, doneList, resList)
    Tile	*tile;
    resNode	**pendingList, **doneList;
    resResistor	**resList;
{
    int 	count, height;
    bool	merged;
    TileType	ttype;
    Breakpoint	*p1, *p2, *p3;
    resResistor	*resistor;
    resElement	*element;
    resNode	*currNode;
    float	rArea;
    resInfo	*info = (resInfo *)TiGetClientPTR(tile);
    HashTable	BreakTable;
    HashEntry	*he;

    merged = FALSE;
    height = TOP(tile) - BOTTOM(tile);

    /*
     * One Breakpoint?  No resistors need to be made.  Free up the first
     * breakpoint, then return.
     */

    p1 = info->breakList;
    if   (p1->br_next == NULL)
    {
	p1->br_this->rn_float.rn_area += height * (LEFT(tile) - RIGHT(tile));
	freeMagic((char *)p1);
	info->breakList = NULL;
	return(merged);
    }

    /* Simplified split tile handling */
    if (IsSplit(tile))
    {
	ttype = TiGetLeftType(tile);
	if (TiGetLeftType(tile) == TT_SPACE)
	    ttype = TiGetRightType(tile);
    }
    else
	ttype = TiGetTypeExact(tile);

    /* Re-sort nodes left to right. */
    count = ResSortBreaks(&info->breakList, TRUE);

    /* For long lists (defined as >= 16 entries), make a hash table of
     * the node pointer conversions so that each node can be updated
     * as we walk the list, instead of walking the rest of the list in
     * a nested loop for each entry.
     */
    if (count >= 16)
	HashInit(&BreakTable, HT_DEFAULTSIZE, HT_CLIENTKEYS);

    /*
     * Eliminate breakpoints with the same X coordinate and merge
     * their nodes.
     */

    p2 = info->breakList;

    /* Add extra left area to leftmost node */

    p2->br_this->rn_float.rn_area += height * (p2->br_loc.p_x - LEFT(tile));
    while (p2->br_next != NULL)
    {
	p1 = p2;
	p2 = p2->br_next;

	/* Has the node been recorded as needing to be replaced? */
	if (count >= 16)
	{
	    while (TRUE)
	    {
		he = HashLookOnly(&BreakTable, (char *)p2->br_this);
		if (!he) break;
		p2->br_this = (resNode *)HashGetValue(he);
	    }
	}

	if (p2->br_loc.p_x == p1->br_loc.p_x)
	{
	    if (p2->br_this == p1->br_this)
	    {
		 currNode = NULL;
		 p1->br_next = p2->br_next;
		 freeMagic((char *)p2);
		 p2 = p1;
	    }
	    else if (p2->br_this == resCurrentNode)
	    {
		 currNode = p1->br_this;
	    	 ResMergeNodes(p2->br_this, p1->br_this, pendingList, doneList);
		 merged = TRUE;
		 freeMagic((char *)p1);
	    }
	    else if (p1->br_this == resCurrentNode)
	    {
		 currNode = p2->br_this;
		 p1->br_next = p2->br_next;
	    	 ResMergeNodes(p1->br_this, p2->br_this, pendingList, doneList);
		 merged = TRUE;
		 freeMagic((char *)p2);
		 p2 = p1;
	    }
	    else
	    {
		 currNode = p1->br_this;
	    	 ResMergeNodes(p2->br_this, p1->br_this, pendingList, doneList);
		 freeMagic((char *)p1);
	    }

	    /*
	     * Was the node used in another info or breakpoint?
	     * If so, replace the old node with the new one.
	     *
	     * Short lists:  Walk the list to the end and change
	     * nodes on the fly.
	     * Long lists:  Record the change to be made in the
	     * hash table so that it can be executed as each list
	     * entry is encountered.
	     */
	    if (count >= 16)
	    {
		he = HashFind(&BreakTable, (char *)currNode);
		HashSetValue(he, (char *)p2->br_this);
	    }
	    else
	    {
		p3 = p2->br_next;
		while (p3 != NULL)
		{
		    if (p3->br_this == currNode)
			p3->br_this = p2->br_this;

		    p3 = p3->br_next;
		}
	    }
	}

	/*
	 * If the X coordinates don't match, make a resistor between
	 * the breakpoints.
	 */

	else
	{
            resistor = (resResistor *)mallocMagic((unsigned)sizeof(resResistor));
            resistor->rr_nextResistor = (*resList);
            resistor->rr_lastResistor = NULL;
            if ((*resList) != NULL) (*resList)->rr_lastResistor = resistor;
            (*resList) = resistor;
            resistor->rr_connection1 = p1->br_this;
            resistor->rr_connection2 = p2->br_this;
            element = (resElement *)mallocMagic((unsigned)sizeof(resElement));
            element->re_nextEl = p1->br_this->rn_re;
            element->re_thisEl = resistor;
            p1->br_this->rn_re = element;
            element = (resElement *)mallocMagic((unsigned)sizeof(resElement));
            element->re_nextEl = p2->br_this->rn_re;
            element->re_thisEl = resistor;
            p2->br_this->rn_re = element;
	    resistor->rr_cl = (TOP(tile) + BOTTOM(tile)) >> 1;
	    resistor->rr_width = height;
	    resistor->rr_tt = ttype;

	    if (IsSplit(tile))
	    {
		resistor->rr_status = RES_DIAGONAL;
		resistor->rr_status |= (SplitDirection(tile)) ? RES_NS
			: RES_EW;
	    }
	    else
	    {
		resistor->rr_status = RES_EW;
	    }
	    resistor->rr_value =
			(float)ExtCurStyle->exts_sheetResist[resistor->rr_tt]
			* (float)(p2->br_loc.p_x - p1->br_loc.p_x)
			/ (float)height;
	    rArea = ((p2->br_loc.p_x - p1->br_loc.p_x) * height) / 2;
	    resistor->rr_connection1->rn_float.rn_area += rArea;
	    resistor->rr_connection2->rn_float.rn_area += rArea;
	    resistor->rr_float.rr_area = 0;

	    freeMagic((char *)p1);
	}
    }

    if (count >= 16) HashKill(&BreakTable);

    p2->br_this->rn_float.rn_area += height * (RIGHT(tile) - p2->br_loc.p_x);
    freeMagic((char *)p2);
    info->breakList = NULL;
    return merged;
}


/*
 *-------------------------------------------------------------------------
 *
 * ResCalcNorthSouth-- Makes resistors from a NorthSouth partition
 *
 * Results: Returns TRUE if the resCurrentNode was involved in a merge.
 *
 * Side Effects: Makes resistors. Frees breakpoints
 *
 *-------------------------------------------------------------------------
 */

bool
ResCalcNorthSouth(tile, pendingList, doneList, resList)
    Tile	*tile;
    resNode	**pendingList, **doneList;
    resResistor	**resList;
{
    int 	count, width;
    bool	merged;
    TileType	ttype;
    Breakpoint	*p1, *p2, *p3;
    resResistor	*resistor;
    resElement	*element;
    resNode	*currNode;
    float	rArea;
    resInfo	*info = (resInfo *)TiGetClientPTR(tile);
    HashTable	BreakTable;
    HashEntry	*he;

    merged = FALSE;
    width = RIGHT(tile) - LEFT(tile);

    /*
     * One Breakpoint? No resistors need to be made. Free up the first
     * breakpoint, then return.
     */

    p1 = info->breakList;
    if (p1->br_next == NULL)
    {
	p1->br_this->rn_float.rn_area += width * (TOP(tile) - BOTTOM(tile));
     	freeMagic((char *)p1);
	info->breakList = NULL;
	return(merged);
    }

    /* Re-sort nodes south to north. */
    count = ResSortBreaks(&info->breakList, FALSE);

    /* For long lists (defined as >= 16 entries), make a hash table of
     * the node pointer conversions so that each node can be updated
     * as we walk the list, instead of walking the rest of the list in
     * a nested loop for each entry.
     */
    if (count >= 16)
	HashInit(&BreakTable, HT_DEFAULTSIZE, HT_CLIENTKEYS);

    /* Simplified split tile handling */
    if (IsSplit(tile))
    {
	ttype = TiGetLeftType(tile);
	if (TiGetLeftType(tile) == TT_SPACE)
	    ttype = TiGetRightType(tile);
    }
    else
	ttype = TiGetTypeExact(tile);

    /*
     * Eliminate breakpoints with the same Y coordinate and merge
     * their nodes.
     */

    p2 = info->breakList;

    /* Add extra left area to leftmost node */

    p2->br_this->rn_float.rn_area += width * (p2->br_loc.p_y - BOTTOM(tile));
    while (p2->br_next != NULL)
    {
	p1 = p2;
	p2 = p2->br_next;

	/* Has the node been recorded as needing to be replaced? */
	if (count >= 16)
	{
	    while (TRUE)
	    {
		he = HashLookOnly(&BreakTable, (char *)p2->br_this);
		if (!he) break;
		p2->br_this = (resNode *)HashGetValue(he);
	    }
	}

	if (p1->br_loc.p_y == p2->br_loc.p_y)
	{
	    if (p2->br_this == p1->br_this)
	    {
		currNode = NULL;
		p1->br_next = p2->br_next;
		freeMagic((char *)p2);
		p2 = p1;
	    }
	    else if (p2->br_this == resCurrentNode)
	    {
		currNode = p1->br_this;
	    	ResMergeNodes(p2->br_this, p1->br_this, pendingList, doneList);
		freeMagic((char *)p1);
		merged = TRUE;
	    }
	    else if (p1->br_this == resCurrentNode)
	    {
		currNode = p2->br_this;
		p1->br_next = p2->br_next;
	    	ResMergeNodes(p1->br_this, p2->br_this, pendingList, doneList);
		merged = TRUE;
		freeMagic((char *)p2);
		p2 = p1;
	    }
	    else
	    {
		currNode = p1->br_this;
	    	ResMergeNodes(p2->br_this, p1->br_this, pendingList, doneList);
		freeMagic((char *)p1);
	    }

	    /*
	     * Was the node used in another info or breakpoint?
	     * If so, replace the old node with the new one.
	     *
	     * Short lists:  Walk the list to the end and change
	     * nodes on the fly.
	     * Long lists:  Record the change to be made in the
	     * hash table so that it can be executed as each list
	     * entry is encountered.
	     */
	    if (count >= 16)
	    {
		he = HashFind(&BreakTable, (char *)currNode);
		HashSetValue(he, (char *)p2->br_this);
	    }
	    else
	    {
		p3 = p2->br_next;
		while (p3 != NULL)
		{
		    if (p3->br_this == currNode)
			p3->br_this = p2->br_this;

		    p3 = p3->br_next;
		}
	    }
	}

	/*
	 * If the Y coordinates don't match, make a resistor between
	 * the breakpoints.
	 */

	else
	{
	    resistor = (resResistor *) mallocMagic((unsigned) (sizeof(resResistor)));
	    resistor->rr_nextResistor = (*resList);
	    resistor->rr_lastResistor = NULL;
	    if ((*resList) != NULL) (*resList)->rr_lastResistor = resistor;
	    (*resList) = resistor;
	    resistor->rr_connection1 = p1->br_this;
	    resistor->rr_connection2 = p2->br_this;
	    element = (resElement *) mallocMagic((unsigned) (sizeof(resElement)));
	    element->re_nextEl = p1->br_this->rn_re;
	    element->re_thisEl = resistor;
	    p1->br_this->rn_re = element;
	    element = (resElement *) mallocMagic((unsigned) (sizeof(resElement)));
	    element->re_nextEl = p2->br_this->rn_re;
	    element->re_thisEl = resistor;
	    p2->br_this->rn_re = element;
	    resistor->rr_cl = (LEFT(tile) + RIGHT(tile)) >> 1;
	    resistor->rr_width = width;
	    resistor->rr_tt = ttype;
	    if (IsSplit(tile))
	    {
		resistor->rr_status = RES_DIAGONAL;
		resistor->rr_status |= (SplitDirection(tile)) ? RES_NS
			: RES_EW;
	    }
	    else
	    {
		resistor->rr_status = RES_NS;
	    }
	    resistor->rr_value =
			(float)ExtCurStyle->exts_sheetResist[resistor->rr_tt]
			* (float)(p2->br_loc.p_y - p1->br_loc.p_y)
			/ (float)width;
	    rArea = ((p2->br_loc.p_y - p1->br_loc.p_y) * width) / 2;
	    resistor->rr_connection1->rn_float.rn_area += rArea;
	    resistor->rr_connection2->rn_float.rn_area += rArea;
	    resistor->rr_float.rr_area = 0;
	    freeMagic((char *)p1);
	}
    }
    p2->br_this->rn_float.rn_area += width * (TOP(tile) - p2->br_loc.p_y);
    freeMagic((char *)p2);
    info->breakList = NULL;
    return(merged);
}


/*
 *-------------------------------------------------------------------------
 *
 * ResCalcNearDevice-- Calculating the direction of current flow near
 *	devices is tricky because there are two adjoining regions with
 *	vastly different sheet resistances.  ResCalcNearDevice is called
 *	whenever a diffusion tile adjoining a real tile is found.  It makes
 *	a guess at the correct direction of current flow, removes extra
 *	breakpoints, and call either ResCalcEastWest or ResCalcNorthSouth
 *
 * Results:
 *	TRUE if merging occurred, FALSE if not.
 *
 * Side Effects: Makes resistors. Frees breakpoints
 *
 *-------------------------------------------------------------------------
 */

bool
ResCalcNearDevice(tile, pendingList, doneList, resList)
    Tile	*tile;
    resNode	**pendingList, **doneList;
    resResistor	**resList;

{
    bool 	merged;
    int		devcount, devedge, deltax, deltay;
    Breakpoint	*p1, *p2, *p3;
    resInfo	*info = (resInfo *)TiGetClientPTR(tile);

    merged = FALSE;

    /*
     *  One Breakpoint?  No resistors need to be made.  Free up the first
     *	breakpoint, then return.
     */

    if (info->breakList->br_next == NULL)
    {
     	freeMagic((char *)info->breakList);
	info->breakList = NULL;
	return(merged);
    }

    /* Count the number of device breakpoints	*/
    /* Mark which edge they connect to		*/

    devcount = 0;
    devedge = 0;
    for (p1 = info->breakList; p1 != NULL; p1 = p1->br_next)
    {
	if (p1->br_this->rn_why == RES_NODE_DEVICE)
	{
	    devcount++;
	    if (p1->br_loc.p_x == LEFT(tile)) devedge |= LEFTEDGE;
	    else if (p1->br_loc.p_x == RIGHT(tile)) devedge |= RIGHTEDGE;
	    else if (p1->br_loc.p_y == TOP(tile)) devedge |= TOPEDGE;
	    else if (p1->br_loc.p_y == BOTTOM(tile)) devedge |= BOTTOMEDGE;
	}
    }

    /* Use distance from device to next breakpoint as determinant   */
    /* If there is only one device or if all the devices are along  */
    /* the same edge.						    */

    if (devcount == 1 ||
        (devedge & LEFTEDGE) == devedge	||
        (devedge & RIGHTEDGE) == devedge ||
        (devedge & TOPEDGE) == devedge 	||
        (devedge & BOTTOMEDGE) == devedge)
    {
	ResSortBreaks(&info->breakList, TRUE);
        p2 = NULL;
        for (p1 = info->breakList; p1 != NULL; p1 = p1->br_next)
        {
	    if (p1->br_this->rn_why == RES_NODE_DEVICE)
	        break;

	    if (p1->br_next != NULL &&
	       	     (p1->br_loc.p_x != p1->br_next->br_loc.p_x ||
	       	      p1->br_loc.p_y != p1->br_next->br_loc.p_y))
	       	p2 = p1;
        }
	deltax = INFINITY;
	for (p3 = p1->br_next; p3 != NULL &&
	       p3->br_loc.p_x == p1->br_loc.p_x &&
	       p3->br_loc.p_y == p1->br_loc.p_y; p3 = p3->br_next);
	if (p3 != NULL)
	{
	    if (p3->br_crect)
	    {
	       	if (p3->br_crect->r_ll.p_x > p1->br_loc.p_x)
		{
		    deltax = p3->br_crect->r_ll.p_x - p1->br_loc.p_x;
		}
	       	else if (p3->br_crect->r_ur.p_x < p1->br_loc.p_x)
		{
		    deltax = p1->br_loc.p_x - p3->br_crect->r_ur.p_x;
		}
		else
		{
		    deltax = 0;
		}
	    }
	    else
	    {
	        deltax = abs(p1->br_loc.p_x - p3->br_loc.p_x);
	    }
	}
	if (p2 != NULL)
	{
	    if (p2->br_crect)
	    {
	        if (p2->br_crect->r_ll.p_x > p1->br_loc.p_x)
		{
		    deltax = MIN(deltax, p2->br_crect->r_ll.p_x - p1->br_loc.p_x);
		}
	       	else if (p2->br_crect->r_ur.p_x < p1->br_loc.p_x)
		{
		    deltax = MIN(deltax, p1->br_loc.p_x - p2->br_crect->r_ur.p_x);
		}
		else
		{
		    deltax = 0;
		}
	    }
	    else
	    {
	        deltax = MIN(deltax, abs(p1->br_loc.p_x - p2->br_loc.p_x));
	    }
	}

        /* Re-sort nodes south to north. */
	ResSortBreaks(&info->breakList, FALSE);
        p2 = NULL;
        for (p1 = info->breakList; p1 != NULL; p1 = p1->br_next)
        {
	    if (p1->br_this->rn_why == RES_NODE_DEVICE)
	    {
	        break;
	    }
	    if (p1->br_next != NULL &&
	       	     (p1->br_loc.p_x != p1->br_next->br_loc.p_x ||
	       	      p1->br_loc.p_y != p1->br_next->br_loc.p_y))
	    {
	       	p2 = p1;
	    }
        }
	deltay = INFINITY;
	for (p3 = p1->br_next; p3 != NULL &&
	       p3->br_loc.p_x == p1->br_loc.p_x &&
	       p3->br_loc.p_y == p1->br_loc.p_y; p3 = p3->br_next);
	if (p3 != NULL)
	{
	    if (p3->br_crect)
	    {
	       	if (p3->br_crect->r_ll.p_y > p1->br_loc.p_y)
		{
		    deltay = p3->br_crect->r_ll.p_y - p1->br_loc.p_y;
		}
	       	else if (p3->br_crect->r_ur.p_y < p1->br_loc.p_y)
		{
		    deltay = p1->br_loc.p_y - p3->br_crect->r_ur.p_y;
		}
		else
		{
		    deltay = 0;
		}
	    }
	    else
	    {
	        deltay = abs(p1->br_loc.p_y - p3->br_loc.p_y);
	    }
	}
	if (p2 != NULL)
	{
	    if (p2->br_crect)
	    {
	       	if (p2->br_crect->r_ll.p_y > p1->br_loc.p_y)
		{
		    deltay = MIN(deltay, p2->br_crect->r_ll.p_y - p1->br_loc.p_y);
		}
	       	else if (p2->br_crect->r_ur.p_y < p1->br_loc.p_y)
		{
		    deltay = MIN(deltay, p1->br_loc.p_y - p2->br_crect->r_ur.p_y);
		}
		else
		{
		    deltay = 0;
		}
	    }
	    else
	    {
	        deltay = MIN(deltay, abs(p1->br_loc.p_y - p2->br_loc.p_y));
	    }
	}
	if (deltay > deltax)
	{
	    return ResCalcNorthSouth(tile, pendingList, doneList, resList);
	}
	else
	{
	    return ResCalcEastWest(tile, pendingList, doneList, resList);
	}
    }

    /* Multiple devices connected to the partition */

    else
    {
     	if (devedge == 0)
	{
	    TxError("Error in device current direction routine\n");
	    return(merged);
	}

	/* Check to see if the current flow is north-south	    */
	/* Possible north-south conditions:			    */
	/* 1. There are devices along the top and bottom edges	    */
	/*    but not along the left or right			    */
	/* 2. There are devices along two sides at right angles,    */
	/*    and the tile is wider than it is tall.		    */

	if (((devedge & TOPEDGE) && (devedge & BOTTOMEDGE) &&
	      !(devedge & LEFTEDGE) && !(devedge & RIGHTEDGE)) ||
	      ((devedge & TOPEDGE || devedge & BOTTOMEDGE) &&
	      (devedge & LEFTEDGE || devedge & RIGHTEDGE) &&
	      (RIGHT(tile) - LEFT(tile)) > (TOP(tile) - BOTTOM(tile))))
	{
            /* re-sort nodes south to north. */
	    ResSortBreaks(&info->breakList, FALSE);

	    /* eliminate duplicate S/D pointers */
	    for (p1 = info->breakList; p1 != NULL; p1 = p1->br_next)
	    {
	      	if  (p1->br_this->rn_why == RES_NODE_DEVICE &&
		       (p1->br_loc.p_y == BOTTOM(tile) ||
		        p1->br_loc.p_y == TOP(tile)))
		{
		    p3 = NULL;
		    p2 = info->breakList;
		    while (p2 != NULL)
		    {
			if (p2->br_this == p1->br_this && p2 != p1 &&
				 p2->br_loc.p_y != BOTTOM(tile) &&
				 p2->br_loc.p_y != TOP(tile))
			{
			    if (p3 == NULL)
			    {
				info->breakList = p2->br_next;
				freeMagic((char *) p2);
				p2 = info->breakList;
			    }
			    else
			    {
				p3->br_next = p2->br_next;
				freeMagic((char *) p2);
				p2 = p3->br_next;
			    }
			}
			else
			{
			    p3 = p2;
			    p2 = p2->br_next;
			}
		    }
		}
	    }
	    return ResCalcNorthSouth(tile, pendingList, doneList, resList);
	}
	else
	{
	    /* Eliminate duplicate S/D pointers */
	    for (p1 = info->breakList; p1 != NULL; p1 = p1->br_next)
	    {
	      	if (p1->br_this->rn_why == RES_NODE_DEVICE &&
		       (p1->br_loc.p_x == LEFT(tile) ||
		        p1->br_loc.p_x == RIGHT(tile)))
		{
		    p3 = NULL;
		    p2 = info->breakList;
		    while (p2 != NULL)
		    {
			if (p2->br_this == p1->br_this	&& p2 != p1 &&
				 p2->br_loc.p_x != LEFT(tile) &&
				 p2->br_loc.p_x != RIGHT(tile))
			{
			    if (p3 == NULL)
			    {
				info->breakList = p2->br_next;
				freeMagic((char *) p2);
				p2 = info->breakList;
			    }
			    else
			    {
				p3->br_next = p2->br_next;
				freeMagic((char *) p2);
				p2 = p3->br_next;
			    }
			}
			else
			{
			    p3 = p2;
			    p2 = p2->br_next;
			}
		    }
		}
	    }
	    return ResCalcEastWest(tile, pendingList, doneList, resList);
	}
    }
}

/*
 *-------------------------------------------------------------------------
 *
 * ResDoContacts-- Add node (or nodes) for a contact.  If there are contact
 *	resistances, also add a resistor.
 *
 * Results:
 *	None.
 *
 * Side Effects: Creates nodes and resistors
 *
 *-------------------------------------------------------------------------
 */

void
ResDoContacts(contact, nodes, resList)
    ResContactPoint	*contact;
    resNode		**nodes;
    resResistor		**resList;
{
    resNode	 *resptr;
    cElement	 *ccell;
    int		 tilenum, squaresx, squaresy, viawidth;
    int 	 minside, spacing, border, cscale;
    float	 squaresf;
    resResistor	 *resistor;
    resElement	 *element;
    static int	 too_small = 1;

    minside = CIFGetContactSize(contact->cp_type, &viawidth, &spacing, &border);
    cscale = CIFCurStyle->cs_scaleFactor;

    if ((ExtCurStyle->exts_viaResist[contact->cp_type] == 0) || (viawidth == 0))
    {
	int x = contact->cp_center.p_x;
	int y = contact->cp_center.p_y;

	resptr = (resNode *) mallocMagic((unsigned) (sizeof(resNode)));
	InitializeResNode(resptr, x, y, RES_NODE_CONTACT);
	ResAddToQueue(resptr, nodes);

 	ccell = (cElement *) mallocMagic((unsigned) (sizeof(cElement)));
	ccell->ce_nextc = resptr->rn_ce;
	resptr->rn_ce = ccell;
	ccell->ce_thisc = contact;

	/* Add 1 celement for each layer of contact  */

	for (tilenum = 0; tilenum < contact->cp_currentcontact; tilenum++)
	{
	    Tile *tile = contact->cp_tile[tilenum];

	    contact->cp_cnode[tilenum] = resptr;
	    ResNewBreak(resptr, tile, contact->cp_center.p_x,
			contact->cp_center.p_y, &contact->cp_rect);
        }
    }
    else
    {
	if (((contact->cp_width * cscale) < minside) ||
		    ((contact->cp_height * cscale) < minside))
	{
	    if (too_small)
	    {
		TxError("Warning: %s at %d %d smaller than extract section allows\n",
	            DBTypeLongNameTbl[contact->cp_type],
	            contact->cp_center.p_x, contact->cp_center.p_y);
	        too_small = 0;
	    }
	    squaresx = squaresy = 1;
	}
	else
	{
	    viawidth += spacing;
	    squaresf = (float)((contact->cp_width * cscale) - minside);
	    squaresf /= (float)viawidth;
	    squaresx = (int)squaresf;
	    squaresx++;

	    squaresf = (float)((contact->cp_height * cscale) - minside);
	    squaresf /= (float)viawidth;
	    squaresy = (int)squaresf;
	    squaresy++;
	}
        for (tilenum = 0; tilenum < contact->cp_currentcontact; tilenum++)
	{
      	    int  x = contact->cp_center.p_x;
      	    int  y = contact->cp_center.p_y;
	    Tile *tile = contact->cp_tile[tilenum];

	    resptr = (resNode *) mallocMagic((unsigned) (sizeof(resNode)));
	    InitializeResNode(resptr, x, y, RES_NODE_CONTACT);
	    ResAddToQueue(resptr, nodes);

 	    /* Add contact pointer to node  */

	    ccell = (cElement *) mallocMagic((unsigned) (sizeof(cElement)));
	    ccell->ce_nextc = resptr->rn_ce;
	    resptr->rn_ce = ccell;
	    ccell->ce_thisc = contact;

	    contact->cp_cnode[tilenum] = resptr;
	    ResNewBreak(resptr, tile, contact->cp_center.p_x,
			contact->cp_center.p_y, &contact->cp_rect);

	    /* Add resistors here */

	    if (tilenum > 0)
	    {
	        resistor = (resResistor *) mallocMagic((unsigned) (sizeof(resResistor)));
	        resistor->rr_nextResistor = (*resList);
	        resistor->rr_lastResistor = NULL;
	        if ((*resList) != NULL) (*resList)->rr_lastResistor = resistor;
	        (*resList) = resistor;
	        resistor->rr_connection1 = contact->cp_cnode[tilenum - 1];
	        resistor->rr_connection2 = contact->cp_cnode[tilenum];

	        element = (resElement *) mallocMagic((unsigned) (sizeof(resElement)));
	        element->re_nextEl = contact->cp_cnode[tilenum - 1]->rn_re;
	        element->re_thisEl = resistor;
	        contact->cp_cnode[tilenum - 1]->rn_re = element;
	        element = (resElement *) mallocMagic((unsigned)(sizeof(resElement)));
	        element->re_nextEl = contact->cp_cnode[tilenum]->rn_re;
	        element->re_thisEl = resistor;
	        contact->cp_cnode[tilenum]->rn_re = element;

		/* Need to figure out how to handle the multiple nodes	*/
		/* and multiple resistors necessary to determine the 	*/
		/* correct geometry for the geometry extractor.  For	*/
		/* now, extract as one big glob.			*/

		/* rr_cl doesn't need to represent centerline; use for	*/
		/* # squares in y direction instead; use rr_width for	*/
		/* # squares in x direction.				*/

		resistor->rr_cl = squaresy;
		resistor->rr_width = squaresx;

		resistor->rr_value =
		    	(float)ExtCurStyle->exts_viaResist[contact->cp_type] /
			(float)(squaresx * squaresy);
		resistor->rr_tt = contact->cp_type;
		resistor->rr_float.rr_area = 0;
		resistor->rr_status = 0;
	    }
	}
    }
}

/*
 *-------------------------------------------------------------------------
 *
 * BreakCompare --
 *
 *	Helper routine for MergeSortBreaks() (below).  Simple
 *	comparison of the breakpoint position.  Comparison is
 *	done for the X position if "xsort" is TRUE, and the Y
 *	position if "xsort" is FALSE.
 *
 * Return value:
 *	Return -1 if the (x or y) position of a is less than the
 *	(x or y) position of b;  return +1 if the position of a is
 *	greater than the position of b;  and return 0 if they have
 *	equal positions.
 *
 * Side effect:
 *	None.
 *
 *-------------------------------------------------------------------------
 */

int
BreakCompare(
    Breakpoint *a,
    Breakpoint *b,
    int xsort)
{
    if (xsort == TRUE)
    {
	if (a->br_loc.p_x < b->br_loc.p_x) return -1;
	if (a->br_loc.p_x > b->br_loc.p_x) return 1;
    }
    else
    {
	if (a->br_loc.p_y < b->br_loc.p_y) return -1;
	if (a->br_loc.p_y > b->br_loc.p_y) return 1;
    }
    return 0;
}

/*
 *-------------------------------------------------------------------------
 *
 * MergeSorted --
 *
 *	Helper routine for MergeSortBreaks() (below).  Merge sort
 *	merging routine.
 *
 *-------------------------------------------------------------------------
 */

Breakpoint *
MergeSorted(
    Breakpoint *a,
    Breakpoint *b,
    int xsort)
{
    Breakpoint head;
    Breakpoint *tail = &head;

    head.br_next = NULL;

    while (a != NULL && b != NULL)
    {
	if (BreakCompare(a, b, xsort) <= 0)
	{
	    tail->br_next = a;
	    a = a->br_next;
	}
	else
	{
	    tail->br_next = b;
	    b = b->br_next;
	}
	tail = tail->br_next;
    }
    tail->br_next = (a != NULL) ? a : b;

    return head.br_next;
}

/*
 *-------------------------------------------------------------------------
 *
 * SplitList --
 *
 *	Helper routine for MergeSortBreaks() (below).  Merge sort
 *	splitting routine.
 *
 * Results:
 *	None.
 *
 *-------------------------------------------------------------------------
 */

void
SplitList(
    Breakpoint *source,
    Breakpoint **front,
    Breakpoint **back)
{
    Breakpoint *slow;
    Breakpoint *fast;

    if (source == NULL || source->br_next == NULL)
    {
	*front = source;
	*back = NULL;
	return;
    }

    slow = source;
    fast = source->br_next;

    while (fast != NULL)
    {
	fast = fast->br_next;

	if (fast != NULL)
	{
	    slow = slow->br_next;
	    fast = fast->br_next;
	}
    }

    *front = source;
    *back = slow->br_next;
    slow->br_next = NULL;
}

/*
 *-------------------------------------------------------------------------
 *
 * MergeSortBreaks --
 *
 *	See "ResSortBreaks" below.  Alternative to bubble sort for long
 *	linked lists.
 *
 * Results:
 *	Pointer to a sorted breakpoint list.
 *
 * Side effects:
 *	The breakpoints are sorted.
 *
 *-------------------------------------------------------------------------
 */

Breakpoint *
MergeSortBreaks(Breakpoint *list, int xsort)
{
    Breakpoint *a, *b;

    if (list == NULL || list->br_next == NULL)
	return list;

    SplitList(list, &a, &b);

    a = MergeSortBreaks(a, xsort);
    b = MergeSortBreaks(b, xsort);

    return MergeSorted(a, b, xsort);
}

/*
 *-------------------------------------------------------------------------
 *
 * ResSortBreaks --
 *
 *	Sort breakpoints, either in the X direction (if "xsort" is TRUE)
 *	or in the Y direction (if "xsort" is FALSE).  For short lists
 *	(< 16 elements), a simple bubble sort is used.  For larger lists,
 *	a merge sort is used.  Most resistor networks are short, but
 *	power/ground networks can be huge and cause a performance
 *	bottleneck. 
 *
 * Results:
 *	Return the length of the list (maximum truncated at 16) so that
 *	the calling routine can determine if this is a long or a short
 *	linked list and treat it accordingly.
 *
 *-------------------------------------------------------------------------
 */

int
ResSortBreaks(masterlist, xsort)
    Breakpoint	**masterlist;
    int		xsort;
{
    Breakpoint	*p1, *p2, *p3, *p4;
    bool	changed;
    int		count = 0;

    for (p1 = *masterlist; p1; p1 = p1->br_next)
    {
	count++;
	if (count > 16)
	{
	    *masterlist = MergeSortBreaks(*masterlist, xsort);
	    return count;
	}
    }

    /* Simple bubble sort */

    changed = TRUE;
    while (changed == TRUE)
    {
	changed = FALSE;
	p1 = NULL;
	p2 = *masterlist;
	p3 = p2->br_next;
	while (p3 != NULL)
	{
	    if ((xsort == TRUE  && p2->br_loc.p_x > p3->br_loc.p_x) ||
	           (xsort == FALSE && p2->br_loc.p_y > p3->br_loc.p_y))
	    {
		changed = TRUE;
		if (p1 == NULL)
		{
		    *masterlist = p3;
		}
		else
		{
		    p1->br_next = p3;
		}
		p2->br_next = p3->br_next;
		p3->br_next = p2;
		p4 = p2;
		p2 = p3;
		p3 = p4;
	    }
	    else
	    {
	        p1 = p2;
	        p2 = p3;
	       	p3 = p3->br_next;
	    }
	}
    }
    return count;
}

