verticalroute.java

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

                        endLoc, location, null, null, null, endArc.isExtended(), endArc.isExtended(), stayInside);
                arc2.setArcAngle(endArcAngle);
                route.add(arc2);
            }
        } else {
            if (route.getEnd() == null) {
                // both endRE and end of route are null, use end of vertical route
                route.setEnd(vertRoute.getEnd());
            }
        }

        // resize contacts to right size, and add to route
        Dimension2D size;
        if (contactArea != null) {
            size = new Dimension2D.Double(contactArea.getWidth(), contactArea.getHeight());
        } else {
            //size = Router.getContactSize(vertRoute.getStart(), vertRoute.getEnd());
            double width = 0, height = 0;
            if (startArcAngle == 900 && startArcWidth > width) width = startArcWidth;
            if (startArcAngle == 0 && startArcWidth > height) height = startArcWidth;
            if (endArcAngle == 900 && endArcWidth > width) width = endArcWidth;
            if (endArcAngle == 0 && endArcWidth > height) height = endArcWidth;            
            size = new Dimension2D.Double(width, height);
        }
        for (RouteElement re : vertRoute) {
            if (re instanceof RouteElementPort)
                ((RouteElementPort)re).setNodeSize(size);
            if (!route.contains(re)) route.add(re);
        }
    }

    /**
     * Builds a Route using the specification from specifyRoute(), but without
     * connecting to startRE and endRE.  The start of the returned Route can connect
     * to startRE, and the end of the returned Route can connect to endRE.
     * The caller must handle the final connections.
     * @param cell the Cell in which to create the route
     * @param location where in the database the vertical route is to be created
     * @param contactSize the size of contacts
     * @param arcAngle angle of zero length arcs created between contacts (usually zero)
     * @param stayInside a polygonal area in which the new arc must reside (if not null).
     * @return a Route whose start can connect to startRE and whose end
     * can connect to endRE. Returns null if no specification for the route exists.
     */
    public Route buildRoute(Cell cell, Point2D location, Dimension2D contactSize, int arcAngle, PolyMerge stayInside) {
        if (specifiedRoute == null) {
            System.out.println("Error: Trying to build VerticalRoute without a call to specifyRoute() first");
            return null;
        }
        Route route = new Route();
        if (specifiedRoute.size() == 0) return route;
        if (DEBUG) {
            System.out.println("Building route: ");
            for (Object obj : specifiedRoute) {
                System.out.println("  "+obj);
            }
        }

        // pull off the first object, which will be a port, and create contact from that
        PrimitivePort pp = (PrimitivePort)specifiedRoute.remove(0);
        RouteElementPort node = RouteElementPort.newNode(cell, pp.getParent(), pp,
                location, contactSize.getWidth(), contactSize.getHeight());
        route.add(node);
        route.setStart(node);
        route.setEnd(node);

        // now iterate through rest of list and create arc,port route element pairs
        for (Iterator<Object> it = specifiedRoute.iterator(); it.hasNext(); ) {
            ArcProto ap = (ArcProto)it.next();
            PrimitivePort port = (PrimitivePort)it.next();

            // create node
            RouteElementPort newNode = RouteElementPort.newNode(cell, port.getParent(), port,
                    location, contactSize.getWidth(), contactSize.getHeight());
            route.add(newNode);
            route.setEnd(newNode);

            // create arc
            double arcWidth = Router.getArcWidthToUse(node, ap);
            RouteElementArc arc = RouteElementArc.newArc(cell, ap, arcWidth, node, newNode, location, location,
            	null, null, null, ap.isExtended(), ap.isExtended(), stayInside);
            arc.setArcAngle(arcAngle);
            route.add(arc);

            node = newNode;
        }

        return route;
    }

    /**
     * Specify the route
     */
    private boolean specifyRoute(ArcProto [] startArcs, ArcProto [] endArcs) {

        specifiedRoute = new SpecifiedRoute();
        allSpecifiedRoutes = new ArrayList<SpecifiedRoute>();
        this.startArc = null;
        this.endArc = null;

        // try to find a way to connect, do exhaustive search
        for (int i=0; i<startArcs.length; i++) {
            for (int j=0; j<endArcs.length; j++) {
                ArcProto startArc = startArcs[i];
                ArcProto endArc = endArcs[j];
                if (startArc == null || endArc == null) continue;

                specifiedRoute.clear();
                specifiedRoute.startArc = startArc;
                specifiedRoute.endArc = endArc;
                searchNumber = 0;
                if (DEBUGSEARCH || DEBUGTERSE) System.out.println("** Start search startArc="+startArc+", endArc="+endArc);
                findConnectingPorts(startArc, endArc, new StringBuffer());
                if (DEBUGSEARCH || DEBUGTERSE) System.out.println("   Search reached searchNumber "+searchNumber);
            }
        }

        if (allSpecifiedRoutes.size() == 0) return false;           // nothing found

        // choose shortest route
        specifiedRoute = allSpecifiedRoutes.get(0);
        List<SpecifiedRoute> zeroLengthRoutes = new ArrayList<SpecifiedRoute>();
        for (int i=0; i<allSpecifiedRoutes.size(); i++) {
            SpecifiedRoute r = allSpecifiedRoutes.get(i);
            if (r.size() < specifiedRoute.size()) specifiedRoute = r;
            if (r.size() == 0) zeroLengthRoutes.add(r);
        }
        // if multiple ways to connect that use only one wire, choose
        // the one that uses the current wire, if any.
        if (zeroLengthRoutes.size() > 0) {
            for (SpecifiedRoute r : zeroLengthRoutes) {
                if (r.startArc == User.getUserTool().getCurrentArcProto())
                    specifiedRoute = r;
            }
        }

        allSpecifiedRoutes.clear();
        startArc = specifiedRoute.startArc;
        endArc = specifiedRoute.endArc;
        if (DEBUGSEARCH || DEBUGTERSE) {
            System.out.println("*** Using Best Route: ");
            specifiedRoute.printRoute();
        }

        return true;
    }

    /**
     * Recursive method to create a specification list of ports and arcs
     * that connect startArc to endArc.  The list will be odd in length
     * (or zero if startArc and endArc are the same). It will consist
     * of a PortProto, and zero or more ArcProto,PortProto pairs in that order.
     * The first PortProto will be able to connect to the initial startArc,
     * and the last PortProto will be able to connect to the final endArc.
     * <p>PortProtos used are Ports from the current technology whose parents
     * (NodeProtos) have the function of CONTACT.
     * @param startArc connect from this arc
     * @param endArc connect to this arc
     * @param ds spacing for debug messages, if enabled
     */
    private void findConnectingPorts(ArcProto startArc, ArcProto endArc, StringBuffer ds) {

        // throw away route if it's longer than shortest good route
        if (specifiedRoute.size() > getShortestRouteLength())
            return;

        if (startArc == endArc) {
            saveRoute(specifiedRoute);
            if (DEBUGTERSE) System.out.println("  --Found good route of length "+specifiedRoute.size());
            return;    // don't need anything to connect between them
        }

        ds.append("  ");
        if (searchNumber > SEARCHLIMIT) { return; }
        if (searchNumber == SEARCHLIMIT) {
            System.out.println("Search limit reached in VerticalRoute");
            searchNumber++;
            return;
        }
        searchNumber++;
        Technology tech = startArc.getTechnology();

        // see if we can find a port in the current technology
        // that will connect the two arcs
		for (Iterator<PrimitiveNode> nodesIt = tech.getNodes(); nodesIt.hasNext(); ) {
			PrimitiveNode pn = nodesIt.next();
            // ignore anything that is noy CONTACT
            if (pn.getFunction() != PrimitiveNode.Function.CONTACT) continue;
            if (pn.isNotUsed()) continue;

			for (Iterator<PortProto> portsIt = pn.getPorts(); portsIt.hasNext(); ) {
				PrimitivePort pp = (PrimitivePort)portsIt.next();
				if (DEBUGSEARCH) System.out.println(ds+"Checking if "+pp+" connects between "+startArc+" and "+endArc);
				if (pp.connectsTo(startArc) && pp.connectsTo(endArc)) {
					specifiedRoute.add(pp);
					saveRoute(specifiedRoute);
					return;                                // this connects between both arcs
				}
			}
		}

        // try all contact ports as an intermediate
		for (Iterator<PrimitiveNode> nodesIt = tech.getNodes(); nodesIt.hasNext(); ) {
			PrimitiveNode pn = nodesIt.next();
            // ignore anything that is noy CONTACT
            if (pn.getFunction() != PrimitiveNode.Function.CONTACT) continue;
            if (pn.isNotUsed()) continue;

			for (Iterator<PortProto> portsIt = pn.getPorts(); portsIt.hasNext(); ) {
				PrimitivePort pp = (PrimitivePort)portsIt.next();
				if (DEBUGSEARCH) System.out.println(ds+"Checking if "+pp+" (parent is "+pp.getParent()+") connects to "+startArc);
				if (pp.connectsTo(startArc)) {
					if (pp == startPort) continue;                       // ignore start port
					if (pp == endPort) continue;                         // ignore end port
					if (specifiedRoute.contains(pp)) continue;          // ignore ones we've already hit
					// add to list
					int prePortSize = specifiedRoute.size();
					specifiedRoute.add(pp);

					// now try to connect through all arcs that can connect to the found pp
					int preArcSize = specifiedRoute.size();
					ArcProto [] arcs = pp.getConnections();
					for (int i=0; i<arcs.length; i++) {
						ArcProto tryarc = arcs[i];
						if (tryarc == Generic.tech().universal_arc) continue;
						if (tryarc == Generic.tech().invisible_arc) continue;
						if (tryarc == Generic.tech().unrouted_arc) continue;
						if (tryarc.isNotUsed()) continue;
						if (tryarc == startArc) continue;           // already connecting through startArc
						if (tryarc == this.startArc) continue;      // original arc connecting from
						if (specifiedRoute.contains(tryarc)) continue;       // already used this arc
                        // if it is not the first specific route, then avoid to come back to the startPin
//                        if (specifiedRoute.size() > 0)
//                        {
//                            boolean notSameStart = false;
//                            for (Iterator<PrimitivePort> itP = tryarc.findPinProto().getPrimitivePorts(); itP.hasNext();)
//                            {
//                                PrimitivePort p = itP.next();
//                                if (p == startPort)
//                                {
//                                    notSameStart = true; // passing for the same port, avoiding loops
//                                }
//                            }
//                            if (notSameStart)
//                                continue;
//                        }
                        specifiedRoute.add(tryarc);
						if (DEBUGSEARCH) System.out.println(ds+"...found intermediate node "+pp+" through "+startArc+" to "+tryarc);
						// recurse
						findConnectingPorts(tryarc, endArc, ds);

						// remove added arcs and port and continue search
						while (specifiedRoute.size() > preArcSize) {
							specifiedRoute.remove(specifiedRoute.size()-1);
						}
					}

					// that port didn't get us anywhere, clear list back to last good point
					while (specifiedRoute.size() > prePortSize) {
						specifiedRoute.remove(specifiedRoute.size()-1);
					}
				}
			}
		}

        if (DEBUGSEARCH) System.out.println(ds+"--- Bad path ---");
        return;               // no valid path to endpp found
    }

    /**
     * Save a successful route
     * @param route the route to save
     */
    private void saveRoute(SpecifiedRoute route) {
        // create copy and store it
        if (DEBUGSEARCH) {
            System.out.println("** Found Route for: startArc="+route.startArc+", endArc="+route.endArc);
            route.printRoute();
        }
        int shortestLength = getShortestRouteLength();
        if (route.size() > shortestLength) {
            // ignore it
            return;
        }
        SpecifiedRoute loggedRoute = new SpecifiedRoute();
        loggedRoute.startArc = route.startArc;
        loggedRoute.endArc = route.endArc;
        loggedRoute.addAll(route);
        allSpecifiedRoutes.add(loggedRoute);
        boolean trim = true;
        while (trim) {
            // remove shorter routes
            Iterator<SpecifiedRoute> it = null;
            for (it = allSpecifiedRoutes.iterator(); it.hasNext(); ) {
                SpecifiedRoute r = it.next();
                if (r.size() > shortestLength) {
                    allSpecifiedRoutes.remove(r);
                    break;
                }
            }
            if (!it.hasNext()) {
                trim = false;           // done trimming
            }
        }
    }

    /**
     * Get the length of the shortest route.
     */
    private int getShortestRouteLength() {
        // Because all routes should be of the
        // shortest length, just return the length of the first route
        if (allSpecifiedRoutes.size() == 0) return Integer.MAX_VALUE;
        SpecifiedRoute r = allSpecifiedRoutes.get(0);
        return r.size();
    }
}