verticalroute.java

The ElectricTM VLSI Design System is an open-source Electronic Design Automation (EDA) system that c

/* -*- tab-width: 4 -*-
 *
 * Electric(tm) VLSI Design System
 *
 * File: VerticalRoute.java
 *
 * Copyright (c) 2003 Sun Microsystems and Static Free Software
 *
 * Electric(tm) is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Electric(tm) is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Electric(tm); see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, Mass 02111-1307, USA.
 */

package com.sun.electric.tool.routing;

import com.sun.electric.technology.ArcProto;
import com.sun.electric.database.prototype.PortProto;
import com.sun.electric.database.prototype.NodeProto;
import com.sun.electric.database.variable.ElectricObject;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.geometry.Dimension2D;
import com.sun.electric.database.geometry.PolyMerge;
import com.sun.electric.technology.PrimitiveNode;
import com.sun.electric.technology.PrimitivePort;
import com.sun.electric.technology.Technology;
import com.sun.electric.technology.technologies.Generic;
import com.sun.electric.tool.user.User;

import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;

/**
 * Class to route vertically (in Z direction) between two RouteElements.
 * The class is used as following:
 * <p>After creating the object, call specifyRoute() to find a way to connect
 * between startRE and endRE RouteElement objects.  At this point you may wish to
 * use the information about the specified route before actually building the route.
 * Right now the only useful information that is exported is the start and end ArcProtos
 * used, if not already specified.
 * <p>Once satisfied with the specification, call buildRoute() to create all
 * the RouteElements that determine exactly what the route will look like. Note
 * that this does not actually create any objects, it just creates a Route, which
 * can then be used to create Electric database objects.
 * <p>There are two forms of build route, the first tries to figure out everything
 * for you (contact sizes, arc angles), and connects to startRE and endRE if given.
 * The second just creates RouteElements from the specification, and you need to give
 * it the contact size and arc angle, and it does not connect to startRE or endRE.
 */
public class VerticalRoute {
    /** start of the vertical route */          private PortProto startPort;
    /** end of the vertical route */            private PortProto endPort;
    /** list of arcs and nodes to make route */ private SpecifiedRoute specifiedRoute;
    /** list of all valid specified routes */   private List<SpecifiedRoute> allSpecifiedRoutes;
    /** first arc (from startRE) */             private ArcProto startArc;
    /** last arct (to endRE) */                 private ArcProto endArc;

    /** the possible start arcs */              private ArcProto [] startArcs;
    /** the possible end arcs */                private ArcProto [] endArcs;
    /** if route specification succeeded */     private boolean specificationSucceeded;

    private int searchNumber;
    private static final int SEARCHLIMIT = 3000;
    private static final boolean DEBUG = false;
    private static final boolean DEBUGSEARCH = false;
    private static final boolean DEBUGTERSE = false;

    private static class SpecifiedRoute extends ArrayList<Object> {
        ArcProto startArc;
        ArcProto endArc;

        void printRoute() {
            for (int k=0; k<size(); k++) {
                System.out.println("   "+k+": "+get(k));
            }
        }
    }

    /**
     * Private constructor. Any of start/endPort, or start/endArc may be null, however
     * startArcs and endArcs must not be null.  They are the possible arcs to connect between
     * startPort/Arc and endPort/Arc.
     * @param startPort the start port of the route
     * @param endPort the end port of the route
     * @param startArc the start arc of the route
     * @param endArc the end arc of the route
     * @param startArcs the possible starting arcs
     * @param endArcs the possible ending arcs
     */
    private VerticalRoute(PortProto startPort, PortProto endPort, ArcProto startArc, ArcProto endArc,
                          ArcProto [] startArcs, ArcProto [] endArcs) {
        this.startPort = startPort;
        this.endPort = endPort;
        // special case: if port is a universal port, limit arc lists, otherwise
        // searching entire space for best connection will take forever
        if (DEBUGTERSE) {
            System.out.println("Searching for way to connect "+startPort.getBasePort().getParent()+
                    " and "+endPort.getBasePort().getParent());
        }
        if ((startPort.getBasePort().getParent() == Generic.tech().universalPinNode &&
            endPort.getBasePort().getParent() == Generic.tech().universalPinNode) ||
            (startPort.getBasePort().getParent() == Generic.tech().invisiblePinNode &&
            endPort.getBasePort().getParent() == Generic.tech().invisiblePinNode)) {
            startArc = endArc = User.getUserTool().getCurrentArcProto();
            startArcs = endArcs = new ArcProto [] { startArc };
        }
        this.startArc = startArc;
        this.endArc = endArc;
        this.startArcs = copyArcArray(startArcs);
        this.endArcs = copyArcArray(endArcs);
        specifiedRoute = null;
        allSpecifiedRoutes = null;
        specificationSucceeded = false;
    }
    
    /**
     * Create new VerticalRoute object to route between startRE and endRE
     * @param startPort the start port of the route
     * @param endPort the end port of the route
     */
    public static VerticalRoute newRoute(PortProto startPort, PortProto endPort) {
        ArcProto [] startArcs = startPort.getBasePort().getConnections();
        ArcProto [] endArcs = endPort.getBasePort().getConnections();
        // special case for universal pins
        if (startPort.getBasePort().getParent() == Generic.tech().universalPinNode ||
            startPort.getBasePort().getParent() == Generic.tech().invisiblePinNode)
            startArcs = endArcs;
        if (endPort.getBasePort().getParent() == Generic.tech().universalPinNode ||
            endPort.getBasePort().getParent() == Generic.tech().invisiblePinNode)
            endArcs = startArcs;
        if ((startPort.getBasePort().getParent() == Generic.tech().universalPinNode ||
             startPort.getBasePort().getParent() == Generic.tech().invisiblePinNode) &&
            (endPort.getBasePort().getParent() == Generic.tech().universalPinNode ||
             endPort.getBasePort().getParent() == Generic.tech().invisiblePinNode))
            startArcs = endArcs = new ArcProto[] {User.getUserTool().getCurrentArcProto()};
        VerticalRoute vr = new VerticalRoute(startPort, endPort, null, null, startArcs, endArcs);
        vr.specificationSucceeded = vr.specifyRoute();
        return vr;
    }

    /**
     * Create new VerticalRoute object to route between startRE and endArc
     * @param startPort the start port of the route
     * @param endArc and arc the end of the route will be able to connect to
     */
    public static VerticalRoute newRoute(PortProto startPort, ArcProto endArc) {
        ArcProto [] startArcs = startPort.getBasePort().getConnections();
        ArcProto [] endArcs = {endArc};
        // special case for universal pins
        if (startPort.getBasePort().getParent() == Generic.tech().universalPinNode)
            startArcs = endArcs;
        VerticalRoute vr = new VerticalRoute(startPort, null, null, endArc, startArcs, endArcs);
        vr.specificationSucceeded = vr.specifyRoute();
        return vr;
    }

    /**
     * Get the arc used to start the vertical route from startRE
     * @return the start arc, or null if route could not be found or not created
     */
    public ArcProto getStartArc() { return startArc; }

    /**
     * Get the arc used to end the vertical route to endRE
     * @return the end arc, or null if route could not be found or not created
     */
    public ArcProto getEndArc() { return endArc; }

    /**
     * See if specification succeeded and VerticalRoute contains a valid specification
     * @return true if succeeded, false otherwise.
     */
    public boolean isSpecificationSucceeded() { return specificationSucceeded; }

    // we need to copy the array, because we want to modify it
    private ArcProto [] copyArcArray(ArcProto [] arcs)
    {
        ArcProto [] copy = new ArcProto[arcs.length];

        // see if there are nongeneric arcs
        boolean allGeneric = true;
        for(int i=0; i<arcs.length; i++)
        	if (arcs[i].getTechnology() != Generic.tech()) allGeneric = false;

        for (int i=0; i<arcs.length; i++)
        {
            ArcProto arc = arcs[i];
            // get rid of arcs we won't route with
            if (!allGeneric && arc.getTechnology() == Generic.tech() && User.getUserTool().getCurrentArcProto() != arc) arc = null;
            if (arc != null && arc.isNotUsed()) arc = null;
            copy[i] = arc;
        }
        return copy;
    }

    /**
     * Specify a Route between startRE and endRE
     * @return true if a route was found, false otherwise
     */
    private boolean specifyRoute() {

        if (endArcs == null || startArcs == null) {
            System.out.println("VerticalRoute: invalid start or end point");
            return false;
        }

        return specifyRoute(startArcs, endArcs);
    }

    /**
     * Builds a Route using the specification from specifyRoute(). It connects
     * this route up to startRE and endRE if they were specified.
     * Note that this may create non-orthogonal
     * arcs if startRE and endRE are not orthogonal to location.  Also,
     * startRE and endRE must have valid ports (i.e. are existingPortInst or newNode
     * types) if they are non-null. This method automatically determines the contact size, and the
     * angle of all the zero length arcs.
     * @param route the route to append with the new RouteElements
     * @param cell the cell in which to create the vertical route
     * @param location where to create the route (database units)
     * @param stayInside a polygonal area in which the new arc must reside (if not null).
     */
    public void buildRoute(Route route, Cell cell, RouteElementPort startRE, RouteElementPort endRE,
                           Point2D startLoc, Point2D endLoc, Point2D location, PolyMerge stayInside) {
        buildRoute(route, cell, startRE, endRE, startLoc, endLoc, location, stayInside, null);
    }

    /**
     * Builds a Route using the specification from specifyRoute(). It connects
     * this route up to startRE and endRE if they were specified.
     * Note that this may create non-orthogonal
     * arcs if startRE and endRE are not orthogonal to location.  Also,
     * startRE and endRE must have valid ports (i.e. are existingPortInst or newNode
     * types) if they are non-null. This method automatically determines the contact size, and the
     * angle of all the zero length arcs.
     * @param route the route to append with the new RouteElements
     * @param cell the cell in which to create the vertical route
     * @param location where to create the route (database units)
     * @param stayInside a polygonal area in which the new arc must reside (if not null).
     */
    public void buildRoute(Route route, Cell cell, RouteElementPort startRE, RouteElementPort endRE,
                           Point2D startLoc, Point2D endLoc, Point2D location, PolyMerge stayInside, Rectangle2D contactArea) {

        if (specifiedRoute == null) {
            System.out.println("Error: Trying to build VerticalRoute without a call to specifyRoute() first");
            return;
        }
        if (specifiedRoute.size() == 0) return;

        if (startRE != null) if (!route.contains(startRE)) route.add(startRE);
        if (endRE != null) if (!route.contains(endRE)) route.add(endRE);

        // set angle by start arc if it is vertical, otherwise angle is zero
        int startArcAngle = 0;
        int endArcAngle = 0;
        if (startRE != null) {
//            if (startRE.getLocation().getX() == location.getX() &&
//                startRE.getLocation().getY() != location.getY()) arcAngle = 900;
            if (startLoc.getX() == location.getX() &&
                startLoc.getY() != location.getY()) startArcAngle = 900;
            if (startLoc.getX() == location.getX() &&
                startLoc.getY() == location.getY()) startArcAngle = startRE.getConnectingArcAngle(specifiedRoute.startArc);
        }
        if (endRE != null) {
//            if (startRE.getLocation().getX() == location.getX() &&
//                startRE.getLocation().getY() != location.getY()) arcAngle = 900;
            if (endLoc.getX() == location.getX() &&
                endLoc.getY() != location.getY()) endArcAngle = 900;
            if (endLoc.getX() == location.getX() &&
                endLoc.getY() == location.getY()) endArcAngle = endRE.getConnectingArcAngle(specifiedRoute.endArc);
        }

        // create Route, using default contact size
        Route vertRoute = buildRoute(cell, location, new Dimension2D.Double(-1,-1), startArcAngle, stayInside);

        // remove startRE and endRE if they are bisect arc pins and at same location,
        // otherwise, connect them to start and end of vertical route
        double startArcWidth = 0;
        double endArcWidth = 0;
        if (startRE != null) {
            Router.ArcWidth aw = new Router.ArcWidth(startArcAngle);
            aw.findArcWidthToUse(startRE, startArc);
            //startArcWidth = Router.getArcWidthToUse(startRE, startArc);
            startArcWidth = aw.getWidth();

            if (route.replacePin(startRE, vertRoute.getStart(), stayInside)) {
                route.remove(startRE);
                if (route.getStart() == startRE) route.setStart(vertRoute.getStart());
            } else {
                RouteElementArc arc1 = RouteElementArc.newArc(cell, startArc, startArcWidth, startRE, vertRoute.getStart(),
                        startLoc, location, null, null, null, startArc.isExtended(), startArc.isExtended(), stayInside);
                arc1.setArcAngle(startArcAngle);
                route.add(arc1);
            }
        }
        if (endRE != null) {
            Router.ArcWidth aw = new Router.ArcWidth(endArcAngle);
            aw.findArcWidthToUse(endRE, endArc);
            //endArcWidth = Router.getArcWidthToUse(endRE, endArc);
            endArcWidth = aw.getWidth();

            if (route.replacePin(endRE, vertRoute.getEnd(), stayInside)) {
                route.remove(endRE);
                if (route.getEnd() == endRE) route.setEnd(vertRoute.getEnd());
            } else {
                RouteElementArc arc2 = RouteElementArc.newArc(cell, endArc, endArcWidth, endRE, vertRoute.getEnd(),