rtnode.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: RTNode.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.database.topology;

import com.sun.electric.database.geometry.DBMath;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.variable.EditWindow_;
import com.sun.electric.tool.Job;

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

/**
 * The RTNode class implements R-Trees.
 * R-trees come from this paper: Guttman, Antonin, "R-Trees: A Dynamic Index Structure for Spatial Searching",
 * ACM SIGMOD, 14:2, 47-57, June 1984.
 * <P>
 * R-trees are height-balanced trees in which all leaves are at the same depth and contain RTBounds objects
 * (generally Geometric objects NodeInst and ArcInst). Entries higher in the tree store boundary information
 * that tightly encloses the leaves below. All nodes hold from M to 2M entries, where M is 4.
 * The bounding boxes of two entries may overlap, which allows arbitrary structures to be represented.
 * A search for a point or an area is a simple recursive walk through the tree to collect appropriate leaf nodes.
 * Insertion and deletion, however, are more complex operations.  The figure below illustrates how R-Trees work:
 * <P>
 * <CENTER><IMG SRC="doc-files/Geometric-1.gif"></CENTER>
 */
public class RTNode
{
/** lower bound on R-tree node size */			private static final int MINRTNODESIZE = 4;
/** upper bound on R-tree node size */			private static final int MAXRTNODESIZE = (MINRTNODESIZE*2);

	/** bounds of this node and its children */	private Rectangle2D bounds;
	/** number of children */					private int total;
	/** children */								private Object [] pointers;
	/** nonzero if children are terminal */		private boolean flag;
	/** parent node */							private RTNode parent;

	private RTNode()
	{
		pointers = new Object[MAXRTNODESIZE];
		bounds = new Rectangle2D.Double();
	}

	/** Method to get the number of children of this RTNode. */
	public int getTotal() { return total; }
	/** Method to set the number of children of this RTNode. */
	private void setTotal(int total) { this.total = total; }

	/** Method to get the parent of this RTNode. */
	private RTNode getParent() { return parent; }
	/** Method to set the parent of this RTNode. */
	private void setParent(RTNode parent) { this.parent = parent; }

	/** Method to get the number of children of this RTNode. */
	public Object getChild(int index) { return pointers[index]; }
	/** Method to set the number of children of this RTNode. */
	private void setChild(int index, Object obj) { this.pointers[index] = obj; }

	/** Method to get the leaf/branch flag of this RTNode. */
	public boolean getFlag() { return flag; }
	/** Method to set the leaf/branch flag of this RTNode. */
	private void setFlag(boolean flag) { this.flag = flag; }

	/** Method to get the bounds of this RTNode. */
	private Rectangle2D getBounds() { return bounds; }
	/** Method to set the bounds of this RTNode. */
	private void setBounds(Rectangle2D bounds) { this.bounds.setRect(bounds); }
	/** Method to extend the bounds of this RTNode by "bounds". */
	private void unionBounds(Rectangle2D bounds) { Rectangle2D.union(this.bounds, bounds, this.bounds); }

	/**
	 * Method to create the top-level R-Tree structure for a new Cell.
	 * @return an RTNode object that is empty.
	 */
	public static RTNode makeTopLevel()
	{
		RTNode top = new RTNode();
		top.total = 0;
		top.flag = true;
		top.parent = null;
		return top;
	}

	/**
	 * Method to link this RTBounds into the R-tree of its parent Cell.
	 * This is static, because it may modify the root node, and so it must
	 * take a root node and possibly return a different one.
	 * @param env the environment of this operation (for messages).
     * @param root root of the RTree.
     * @param geom RTBounds to link.
     * @return new root of RTree.
	 */
	public static RTNode linkGeom(Object env, RTNode root, RTBounds geom)
	{
		// find the bottom-level branch (a RTNode with leafs) that would expand least by adding this RTBounds
		if (root == null) return null;
        RTNode rtn = root;
		for(;;)
		{
			// if R-tree node contains primitives, exit loop
			if (rtn.getFlag()) break;

			// find sub-node that would expand the least
			double bestExpand = 0;
			int bestSubNode = 0;
			for(int i=0; i<rtn.getTotal(); i++)
			{
				// get bounds and area of sub-node
				RTNode subrtn = (RTNode)rtn.getChild(i);
				Rectangle2D bounds = subrtn.getBounds();
				double area = bounds.getWidth() * bounds.getHeight();

				// get area of sub-node with new element
				Rectangle2D newUnion = new Rectangle2D.Double();
				Rectangle2D.union(geom.getBounds(), bounds, newUnion);
				double newArea = newUnion.getWidth() * newUnion.getHeight();

				// accumulate the least expansion
				double expand = newArea - area;

				// remember the child that expands the least
				if (i != 0 && expand > bestExpand) continue;
				bestExpand = expand;
				bestSubNode = i;
			}

			// recurse down to sub-node that expanded least
			rtn = (RTNode)rtn.getChild(bestSubNode);
		}

		// add this geometry element to the correct leaf R-tree node
		return rtn.addToRTNode(geom, env, root);
	}

	/**
	 * Method to remove this geometry from the R-tree its parent cell.
	 * This is static, because it may modify the root node, and so it must
	 * take a root node and possibly return a different one.
	 * @param env the environment of this operation (for messages).
     * @param root root of the RTree.
     * @param geom RTBounds to unlink.
     * @return new root of RTree.
	 */
	public static RTNode unLinkGeom(Object env, RTNode root, RTBounds geom)
	{
		// find this node in the tree
		RTNode whichRTN = null;
		int whichInd = 0;
		if (root == null) return null;
		Object[] result = root.findGeom(geom);
		if (result != null)
		{
			whichRTN = (RTNode)result[0];
			whichInd = ((Integer)result[1]).intValue();
		} else
		{
			result = root.findGeomAnywhere(geom);
//			if (result == null)
//			{
//				System.out.println("Internal error: " + cell + " cannot find " + geom + " in R-Tree...Rebuilding R-Tree");
//                root = makeTopLevel();
//				for(Iterator<ArcInst> it = cell.getArcs(); it.hasNext(); )
//					root = linkGeom(env, root, (RTBounds)it.next());
//				for(Iterator<NodeInst> it = cell.getNodes(); it.hasNext(); )
//					root = linkGeom(env, root, (RTBounds)it.next());
//				return root;
//			}
			whichRTN = (RTNode)result[0];
			whichInd = ((Integer)result[1]).intValue();
			System.out.println("Internal warning: " + geom + " not in proper R-Tree location in " + env);
		}

		// delete geom from this R-tree node
		return whichRTN.removeRTNode(whichInd, env, root);
	}

	private static int branchCount;

	/**
	 * Debugging method to print this R-Tree.
	 * @param indent the level of the tree, for proper indentation.
	 */
	public void printRTree(int indent)
	{
		if (indent == 0) branchCount = 0;

		StringBuffer line = new StringBuffer();
		for(int i=0; i<indent; i++) line.append(" ");
		line.append("RTNode");
		if (flag)
		{
			branchCount++;
			line.append(" NUMBER " + branchCount);
		}
		line.append(" X(" + bounds.getMinX() + "-" + bounds.getMaxX() + ") Y(" + bounds.getMinY() + "-" + bounds.getMaxY() + ") has " +
			total + " children:");
		System.out.println(line);

		for(int j=0; j<total; j++)
		{
			if (flag)
			{
				line = new StringBuffer();
				for(int i=0; i<indent+3; i++) line.append(" ");
				RTBounds child = (RTBounds)getChild(j);
				Rectangle2D childBounds = child.getBounds();
				line.append("Child X(" + childBounds.getMinX() + "-" + childBounds.getMaxX() + ") Y(" +
					childBounds.getMinY() + "-" + childBounds.getMaxY() + ") is " + child);
				System.out.println(line);
			} else
			{
				((RTNode)getChild(j)).printRTree(indent+3);
			}
		}
	}

	/**
	 * Debugging method to display this R-Tree.
	 * @param cell the Cell in which to show the R-Tree.
	 */
	public void displayRTree(Cell cell)
	{
		EditWindow_ wnd = Job.getUserInterface().getCurrentEditWindow_();
		wnd.clearHighlighting();
		displaySubRTree(cell);
		wnd.finishedHighlighting();
	}

	private void displaySubRTree(Cell cell)
	{
		EditWindow_ wnd = Job.getUserInterface().getCurrentEditWindow_();
		for(int j=0; j<getTotal(); j++)
		{
			if (getFlag())
			{
				RTBounds child = (RTBounds)getChild(j);
				Rectangle2D childBounds = child.getBounds();
				wnd.addHighlightArea(childBounds, cell);
			} else
			{
				RTNode child = (RTNode)getChild(j);
				child.displaySubRTree(cell);
			}
		}
	}

	/**
	 * Method to return the number of leaf entries in this RTree.
	 * @return the number of leaf entries in this RTree.
	 */
	public int tallyRTree()
	{
		int total = 0;
		if (getFlag()) total += getTotal(); else
		{
			for(int j=0; j<getTotal(); j++)
			{
				RTNode child = (RTNode)getChild(j);
				total += child.tallyRTree();
			}
		}
		return total;
	}

	/**
	 * Method to check the validity of an RTree node.
	 * @param level the level of the node in the tree (for error reporting purposes).
	 * @param env the environment in which this node resides.
	 */
	public void checkRTree(int level, Object env)
	{
		Rectangle2D localBounds = new Rectangle2D.Double();
		if (total == 0)
		{
			localBounds.setRect(0, 0, 0, 0);
		} else
		{
			localBounds.setRect(getBBox(0));
			for(int i=1; i<total; i++)
				Rectangle2D.union(localBounds, getBBox(i), localBounds);
		}
		if (!localBounds.equals(bounds))
		{
			if (Math.abs(localBounds.getMinX() - bounds.getMinX()) >= DBMath.getEpsilon() ||
				Math.abs(localBounds.getMinY() - bounds.getMinY()) >= DBMath.getEpsilon() ||
				Math.abs(localBounds.getWidth() - bounds.getWidth()) >= DBMath.getEpsilon() ||
				Math.abs(localBounds.getHeight() - bounds.getHeight()) >= DBMath.getEpsilon())
			{
				System.out.println("Tree of "+env+" at level "+level+" has bounds "+localBounds+" but stored bounds are "+bounds);
				for(int i=0; i<total; i++)
					System.out.println("  ---Child "+i+" is "+ getBBox(i));
			}
		}

		if (!flag)
		{
			for(int j=0; j<total; j++)
			{
				((RTNode)getChild(j)).checkRTree(level+1, env);
			}
		}
	}

	/**
	 * Method to get the bounding box of child "child" of this R-tree node.
	 */
	private Rectangle2D getBBox(int child)
	{
		if (flag)
		{
			RTBounds geom = (RTBounds)pointers[child];
			// @TODO: GVG if pointers is null (bad file read in), we get an exception
			return geom.getBounds();
		}
		RTNode subrtn = (RTNode)pointers[child];
		return subrtn.getBounds();
	}


	/**
	 * Method to recompute the bounds of this R-tree node.
	 */
	private void figBounds()
	{
		if (total == 0)
		{
			bounds.setRect(0, 0, 0, 0);
			return;
		}
		bounds.setRect(getBBox(0));
		for(int i=1; i<total; i++)
			unionBounds(getBBox(i));
	}

	/**
	 * Method to add object "rtnInsert" to this R-tree node, which is in cell "cell".  Method may have to
	 * split the node and recurse up the tree
	 */
	private RTNode addToRTNode(Object rtnInsert, Object env, RTNode root)
	{
		// see if there is room in the R-tree node
		if (getTotal() >= MAXRTNODESIZE)
		{
			// no room: copy list to temp one
			RTNode temp = new RTNode();
			temp.setTotal(getTotal());
			temp.setFlag(getFlag());
			for(int i=0; i<getTotal(); i++)
				temp.setChild(i, getChild(i));

			// find the element farthest from new object
			Rectangle2D bounds;
			if (rtnInsert instanceof RTBounds)
			{
				RTBounds geom = (RTBounds)rtnInsert;
				bounds = geom.getBounds();
			} else
			{
				RTNode subrtn = (RTNode)rtnInsert;
				bounds = subrtn.getBounds();
			}
			Point2D thisCenter = new Point2D.Double(bounds.getCenterX(), bounds.getCenterY());
			double newDist = 0;
			int newN = 0;
			for(int i=0; i<temp.getTotal(); i++)
			{
				Rectangle2D thisv = temp.getBBox(i);
				double dist = thisCenter.distance(thisv.getCenterX(), thisv.getCenterY());
				if (dist >= newDist)
				{
					newDist = dist;
					newN = i;
				}
			}

			// now find element farthest from "newN"
			bounds = temp.getBBox(newN);
			thisCenter = new Point2D.Double(bounds.getCenterX(), bounds.getCenterY());
			double oldDist = 0;
			int oldN = 0;
			if (oldN == newN) oldN++;
			for(int i=0; i<temp.getTotal(); i++)
			{
				if (i == newN) continue;
				Rectangle2D thisv = temp.getBBox(i);
				double dist = thisCenter.distance(thisv.getCenterX(), thisv.getCenterY());
				if (dist >= oldDist)
				{
					oldDist = dist;
					oldN = i;
				}
			}

			// allocate a new R-tree node
			RTNode newrtn = new RTNode();
			newrtn.setFlag(getFlag());
			newrtn.setParent(getParent());

			// put the first seed element into the new RTree
			Object obj = temp.getChild(newN);
			temp.setChild(newN, null);
			newrtn.setChild(0, obj);
			newrtn.setTotal(1);
			if (!newrtn.getFlag()) ((RTNode)obj).setParent(newrtn);
			Rectangle2D newBounds = newrtn.getBBox(0);
			newrtn.setBounds(newBounds);
			double newArea = newBounds.getWidth() * newBounds.getHeight();

			// initialize the old R-tree node and put in the other seed element
			obj = temp.getChild(oldN);
			temp.setChild(oldN, null);
			setChild(0, obj);