/* -*- tab-width: 4 -*- * * Electric(tm) VLSI Design System * * File: Topology.java * Written by: Dmitry Nadezhin, Sun Microsystems. * * Copyright (c) 2006 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.database.topology;import com.sun.electric.database.CellRevision;import com.sun.electric.database.ImmutableArcInst;import com.sun.electric.database.geometry.Poly;import com.sun.electric.database.hierarchy.Cell;import com.sun.electric.database.hierarchy.EDatabase;import com.sun.electric.database.id.CellId;import com.sun.electric.database.text.ImmutableArrayList;import com.sun.electric.database.text.Name;import com.sun.electric.database.text.TextUtils;import com.sun.electric.technology.BoundsBuilder;import java.awt.geom.Rectangle2D;import java.util.ArrayList;import java.util.Arrays;import java.util.Iterator;/** * A class to manage nodes and arcs of a Cell. */public class Topology {    /** Owner cell of this Topology. */                             final Cell cell;    /** A maximal suffix of temporary arc name. */                  private int maxArcSuffix = -1;    /** Chronological list of ArcInst in this Cell. */              private final ArrayList<ArcInst> chronArcs = new ArrayList<ArcInst>();    /** A list of ArcInsts in this Cell. */							private final ArrayList<ArcInst> arcs = new ArrayList<ArcInst>();    /** True if arc bounds are valid. */                            boolean validArcBounds;	/** The geometric data structure. */							private RTNode rTree = RTNode.makeTopLevel();    /** True of RTree matches node/arc sizes */                     private boolean rTreeFresh;    /** Creates a new instance of Topology */    public Topology(Cell cell, boolean loadBackup) {        this.cell = cell;        if (loadBackup)            updateArcs(cell.backup().cellRevision);    }	/****************************** ARCS ******************************/	/**	 * Method to return an Iterator over all ArcInst objects in this Cell.	 * @return an Iterator over all ArcInst objects in this Cell.	 */	public synchronized Iterator<ArcInst> getArcs()	{        ArrayList<ArcInst> arcsCopy = new ArrayList<ArcInst>(arcs);		return arcsCopy.iterator();	}	/**	 * Method to return the number of ArcInst objects in this Cell.	 * @return the number of ArcInst objects in this Cell.	 */	public int getNumArcs()	{		return arcs.size();	}	/**	 * Method to return the ArcInst at specified position.	 * @param arcIndex specified position of ArcInst.	 * @return the ArcInst at specified position..	 */	public final ArcInst getArc(int arcIndex)	{		return arcs.get(arcIndex);	}	/**	 * Method to return the ArcInst by its chronological index.	 * @param arcId chronological index of ArcInst.	 * @return the ArcInst with specified chronological index.	 */	public ArcInst getArcById(int arcId)	{		return arcId < chronArcs.size() ? chronArcs.get(arcId) : null;	}    public int[] getArcIndexByArcIdMap() {        int[] arcIndexByArcIdMap = new int[chronArcs.size()];        Arrays.fill(arcIndexByArcIdMap, -1);        for (int arcIndex = 0; arcIndex < getNumArcs(); arcIndex++) {            int arcId = getArc(arcIndex).getArcId();            assert arcIndexByArcIdMap[arcId] == -1;            arcIndexByArcIdMap[arcId] = arcIndex;        }        return arcIndexByArcIdMap;    }	/**	 * Method to find a named ArcInst on this Cell.	 * @param name the name of the ArcInst.	 * @return the ArcInst.  Returns null if none with that name are found.	 */	public ArcInst findArc(String name)	{		int arcIndex = searchArc(name, 0);		if (arcIndex >= 0) return arcs.get(arcIndex);		arcIndex = - arcIndex - 1;		if (arcIndex < arcs.size())		{			ArcInst ai = arcs.get(arcIndex);			if (ai.getName().equals(name)) return ai;		}		return null;	}	/**	 * Method to add a new ArcInst to the cell.	 * @param ai the ArcInst to be included in the cell.	 */	void addArc(ArcInst ai)	{        cell.setTopologyModified();        validArcBounds = false;        unfreshRTree();		int arcIndex = searchArc(ai);		assert arcIndex < 0;		arcIndex = - arcIndex - 1;		arcs.add(arcIndex, ai);        int arcId = ai.getArcId();        while (chronArcs.size() <= arcId) chronArcs.add(null);        assert chronArcs.get(arcId) == null;        chronArcs.set(arcId, ai);        // update maximal arc name suffux temporary name		if (ai.isUsernamed()) return;		Name name = ai.getNameKey();        assert name.getBasename() == ImmutableArcInst.BASENAME;        maxArcSuffix = Math.max(maxArcSuffix, name.getNumSuffix());        cell.setDirty();	}	/**	 * Method to return unique autoname for ArcInst in this cell.	 * @return a unique autoname for ArcInst in this cell.	 */	Name getArcAutoname()	{        if (maxArcSuffix < Integer.MAX_VALUE)            return ImmutableArcInst.BASENAME.findSuffixed(++maxArcSuffix);        for (int i = 0;; i++) {            Name name = ImmutableArcInst.BASENAME.findSuffixed(i);            if (!hasTempArcName(name)) return name;        }	}	/**	 * Method check if ArcInst with specified temporary name key exists in a cell.	 * @param name specified temorary name key.	 */	boolean hasTempArcName(Name name)	{		return name.isTempname() && findArc(name.toString()) != null;	}	/**	 * Method to remove an ArcInst from the cell.	 * @param ai the ArcInst to be removed from the cell.	 */	void removeArc(ArcInst ai)	{		cell.checkChanging();        cell.setTopologyModified();        unfreshRTree();		assert ai.isLinked();		int arcIndex = searchArc(ai);		ArcInst removedAi = arcs.remove(arcIndex);		assert removedAi == ai;        int arcId = ai.getArcId();        assert chronArcs.get(arcId) == ai;        chronArcs.set(arcId, null);        cell.setDirty();	}    public ImmutableArcInst[] backupArcs(ImmutableArrayList<ImmutableArcInst> oldArcs) {        ImmutableArcInst[] newArcs = new ImmutableArcInst[arcs.size()];        boolean changed = arcs.size() != oldArcs.size();        for (int i = 0; i < arcs.size(); i++) {            ArcInst ai = arcs.get(i);            ImmutableArcInst d = ai.getD();            changed = changed || oldArcs.get(i) != d;            newArcs[i] = d;        }        return changed ? newArcs : null;    }    public void updateArcs(CellRevision newRevision) {        validArcBounds = false;        arcs.clear();        maxArcSuffix = -1;        for (int i = 0; i < newRevision.arcs.size(); i++) {            ImmutableArcInst d = newRevision.arcs.get(i);            while (d.arcId >= chronArcs.size()) chronArcs.add(null);            ArcInst ai = chronArcs.get(d.arcId);            PortInst headPi = cell.getPortInst(d.headNodeId, d.headPortId);            PortInst tailPi = cell.getPortInst(d.tailNodeId, d.tailPortId);            if (ai != null && (/*!full ||*/ ai.getHeadPortInst() == headPi && ai.getTailPortInst() == tailPi)) {                ai.setDInUndo(d);            } else {                ai = new ArcInst(this, d, headPi, tailPi);                chronArcs.set(d.arcId, ai);            }            arcs.add(ai);            if (!ai.isUsernamed()) {                Name name = ai.getNameKey();                assert name.getBasename() == ImmutableArcInst.BASENAME;                maxArcSuffix = Math.max(maxArcSuffix, name.getNumSuffix());            }        }        int arcCount = 0;        for (int i = 0; i < chronArcs.size(); i++) {            ArcInst ai = chronArcs.get(i);            if (ai == null) continue;            int arcIndex = searchArc(ai);            if (arcIndex < 0 || arcIndex >= arcs.size() || ai != arcs.get(arcIndex)) {                chronArcs.set(i, null);                continue;            }            arcCount++;        }        assert arcCount == arcs.size();    }    /**     * Low-level routine.     */    public void computeArcBounds() {        if (!cell.getDatabase().canComputeBounds())            return;        int[] intCoords = new int[4];        BoundsBuilder b = new BoundsBuilder(cell);        for (int arcIndex = 0; arcIndex < arcs.size(); arcIndex++) {            ArcInst ai = arcs.get(arcIndex);            ai.computeBounds(b, intCoords);        }        validArcBounds = true;    }    private int searchArc(ArcInst ai) {        return searchArc(ai.getName(), ai.getArcId());    }    /**     * Searches the arcs for the specified (name,arcId) using the binary     * search algorithm.     * @param name the name to be searched.	 * @param arcId the arcId index to be searched.     * @return index of the search name, if it is contained in the arcs;     *	       otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The     *	       <i>insertion point</i> is defined as the point at which the     *	       ArcInst would be inserted into the list: the index of the first     *	       element greater than the name, or <tt>arcs.size()</tt>, if all     *	       elements in the list are less than the specified name.  Note     *	       that this guarantees that the return value will be &gt;= 0 if     *	       and only if the ArcInst is found.     */	private int searchArc(String name, int arcId)	{		int low = 0;		int high = arcs.size()-1;        int pick = high; // initially try the last postition		while (low <= high) {			ArcInst ai = arcs.get(pick);			int cmp = TextUtils.STRING_NUMBER_ORDER.compare(ai.getName(), name);			if (cmp == 0) cmp = ai.getArcId() - arcId;			if (cmp < 0)				low = pick + 1;			else if (cmp > 0)				high = pick - 1;			else				return pick; // ArcInst found			pick = (low + high) >> 1; // try in a middle		}		return -(low + 1);  // ArcInst not found.    }//    void setArcsModified() {//        cell.checkChanging();//        cell.setTopologyModified();//    }	/****************************** GRAPHICS ******************************/    /**	 * Method to return an interator over all RTBounds objects in a given area of this Cell that allows     * to ignore elements touching the area.     * Note that Geometric objects implement RTBounds, so for database searches, the iterator     * returns Geometrics (NodeInsts and ArcInsts).	 * @param bounds the specified area to search.     * @param includeEdges true if RTBounds objects along edges are considered in.	 * @return an iterator over all of the RTBounds objects in that area.	 */    public Iterator<RTBounds> searchIterator(Rectangle2D bounds, boolean includeEdges) {        return new RTNode.Search(bounds, getRTree(), includeEdges);    }    public void unfreshRTree() {        rTreeFresh = false;    }	/**	 * Method to R-Tree of this Cell.	 * The R-Tree organizes all of the Geometric objects spatially for quick search.	 * @return R-Tree of this Cell.	 */    public RTNode getRTree() {        if (rTreeFresh) return rTree;        EDatabase database = cell.getDatabase();        if (database.canComputeBounds()) {            rebuildRTree();            rTreeFresh = true;//        } else {//            Snapshot snapshotBefore = database.getFreshSnapshot();//            rebuildRTree();//            rTreeFresh = snapshotBefore != null && database.getFreshSnapshot() == snapshotBefore;        }        return rTree;    }    public void rebuildRTree() {//        long startTime = System.currentTimeMillis();        if (!validArcBounds)            computeArcBounds();        CellId cellId = cell.getId();        RTNode root = RTNode.makeTopLevel();        for (Iterator<NodeInst> it = cell.getNodes(); it.hasNext(); ) {            NodeInst ni = it.next();            root = RTNode.linkGeom(cellId, root, ni);        }        for (Iterator<ArcInst> it = cell.getArcs(); it.hasNext(); ) {            ArcInst ai = it.next();            root = RTNode.linkGeom(cellId, root, ai);        }        root.checkRTree(0, cellId);        rTree = root;        rTreeFresh = true;//        long stopTime = System.currentTimeMillis();//        if (Job.getDebug()) System.out.println("Rebuilding R-Tree in " + this + " took " + (stopTime - startTime) + " msec");    }    /**     * Method to check invariants in this Cell.     * @exception AssertionError if invariants are not valid     */    public void check() {        // check arcs        ArcInst prevAi = null;        Poly.Builder polyBuilder = Poly.newGridBuilder();        for(int arcIndex = 0; arcIndex < arcs.size(); arcIndex++) {            ArcInst ai = arcs.get(arcIndex);            ImmutableArcInst a = ai.getD();            assert ai.getParent() == cell;            assert chronArcs.get(a.arcId) == ai;            if (prevAi != null) {                int cmp = TextUtils.STRING_NUMBER_ORDER.compare(prevAi.getName(), ai.getName());                assert cmp <= 0;                if (cmp == 0)                    assert prevAi.getArcId() < a.arcId;            }            assert ai.getHeadPortInst() == cell.getPortInst(a.headNodeId, a.headPortId);            assert ai.getTailPortInst() == cell.getPortInst(a.tailNodeId, a.tailPortId);            ai.check(polyBuilder);            prevAi = ai;        }        for (int arcId = 0; arcId < chronArcs.size(); arcId++) {            ArcInst ai = chronArcs.get(arcId);            if (ai == null) continue;            assert ai.getArcId() == arcId;            int arcIndex = searchArc(ai);            assert ai == arcs.get(arcIndex);        }        if (rTreeFresh)            rTree.checkRTree(0, cell.getId());    }}