rtnode.java

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

			for(int i=1; i<getTotal(); i++) setChild(i, null);
			setTotal(1);
			if (!getFlag()) ((RTNode)obj).setParent(this);
			Rectangle2D oldBounds = getBBox(0);
			setBounds(oldBounds);
			double oldArea = oldBounds.getWidth() * oldBounds.getHeight();

			// cluster the rest of the nodes
			for(;;)
			{
				// search for a cluster about each new node
				int bestNewNode = -1, bestOldNode = -1;
				double bestNewExpand = 0, bestOldExpand = 0;
				for(int i=0; i<temp.getTotal(); i++)
				{
					obj = temp.getChild(i);
					if (obj == null) continue;
					bounds = temp.getBBox(i);

					Rectangle2D newUnion = new Rectangle2D.Double();
					Rectangle2D oldUnion = new Rectangle2D.Double();
					Rectangle2D.union(newBounds, bounds, newUnion);
					Rectangle2D.union(oldBounds, bounds, oldUnion);
					double newAreaPlus = newUnion.getWidth() * newUnion.getHeight();
					double oldAreaPlus = oldUnion.getWidth() * oldUnion.getHeight();

					// remember the child that expands the new node the least
					if (bestNewNode < 0 || newAreaPlus-newArea < bestNewExpand)
					{
						bestNewExpand = newAreaPlus-newArea;
						bestNewNode = i;
					}

					// remember the child that expands the old node the least
					if (bestOldNode < 0 || oldAreaPlus-oldArea < bestOldExpand)
					{
						bestOldExpand = oldAreaPlus-oldArea;
						bestOldNode = i;
					}
				}

				// if there were no nodes added, all have been clustered
				if (bestNewNode == -1 && bestOldNode == -1) break;

				// if both selected the same object, select another "old node"
				if (bestNewNode == bestOldNode)
				{
					bestOldNode = -1;
					for(int i=0; i<temp.getTotal(); i++)
					{
						if (i == bestNewNode) continue;
						obj = temp.getChild(i);
						if (obj == null) continue;
						bounds = temp.getBBox(i);

						Rectangle2D oldUnion = new Rectangle2D.Double();
						Rectangle2D.union(oldBounds, bounds, oldUnion);
						double oldAreaPlus = oldUnion.getWidth() * oldUnion.getHeight();

						// remember the child that expands the old node the least
						if (bestOldNode < 0 || oldAreaPlus-oldArea < bestOldExpand)
						{
							bestOldExpand = oldAreaPlus-oldArea;
							bestOldNode = i;
						}
					}
				}

				// add to the proper "old node" to the old node cluster
				if (bestOldNode != -1)
				{
					// add this node to "rtn"
					obj = temp.getChild(bestOldNode);
					temp.setChild(bestOldNode, null);
					int curPos = getTotal();
					setChild(curPos, obj);
					setTotal(curPos+1);
					if (!getFlag()) ((RTNode)obj).setParent(this);
					unionBounds(getBBox(curPos));
					oldBounds = getBounds();
					oldArea = oldBounds.getWidth() * oldBounds.getHeight();
				}

				// add to proper "new node" to the new node cluster
				if (bestNewNode != -1)
				{
					// add this node to "newrtn"
					obj = temp.getChild(bestNewNode);
					temp.setChild(bestNewNode, null);
					int curPos = newrtn.getTotal();
					newrtn.setChild(curPos, obj);
					newrtn.setTotal(curPos+1);
					if (!newrtn.getFlag()) ((RTNode)obj).setParent(newrtn);
					newrtn.unionBounds(newrtn.getBBox(curPos));
					newBounds = newrtn.getBounds();
					newArea = newBounds.getWidth() * newBounds.getHeight();
				}
			}

			// sensibility check
			if (temp.getTotal() != getTotal() + newrtn.getTotal())
				System.out.println("R-trees: " + temp.getTotal() + " nodes split to " +
					getTotal()+ " and " + newrtn.getTotal() + "!");

			// now recursively insert this new element up the tree
			if (getParent() == null)
			{
				// at top of tree: create a new level
                assert root == this;
				RTNode newroot = new RTNode();
				newroot.setTotal(2);
				newroot.setChild(0, this);
				newroot.setChild(1, newrtn);
				newroot.setFlag(false);
				newroot.setParent(null);
				setParent(newroot);
				newrtn.setParent(newroot);
				newroot.figBounds();
                root = newroot;
			} else
			{
				// first recompute bounding box of R-tree nodes up the tree
				for(RTNode r = getParent(); r != null; r = r.getParent()) r.figBounds();

				// now add the new node up the tree
				root = getParent().addToRTNode(newrtn, env, root);
			}
		}

		// now add "rtnInsert" to the R-tree node
		int curPos = getTotal();
		setChild(curPos, rtnInsert);
		setTotal(curPos+1);

		// compute the new bounds
		Rectangle2D bounds = getBBox(curPos);
		if (getTotal() == 1 && getParent() == null)
		{
			// special case when adding the first node in a cell
			setBounds(bounds);
			return root;
		}

		// recursively update node sizes
		RTNode climb = this;
		for(;;)
		{
			climb.unionBounds(bounds);
			if (climb.getParent() == null) break;
			climb = climb.getParent();
		}

		// now check the RTree
//		checkRTree(0, env);
        return root;
	}

	/**
	 * Method to remove entry "ind" from this R-tree node in cell "cell"
	 */
	private RTNode removeRTNode(int ind, Object env, RTNode root)
	{
		// delete entry from this R-tree node
		int j = 0;
		for(int i=0; i<getTotal(); i++)
			if (i != ind) setChild(j++, getChild(i));
		setTotal(j);

		// see if node is now too small
		if (getTotal() < MINRTNODESIZE)
		{
			// if recursed to top, shorten R-tree
			RTNode prtn = getParent();
			if (prtn == null)
			{
				// if tree has no hierarchy, allow short node
				if (getFlag())
				{
					// compute correct bounds of the top node
					figBounds();
					return root;
				}

				// save all top-level entries
				RTNode temp = new RTNode();
				temp.setTotal(getTotal());
				temp.setFlag(true);
				for(int i=0; i<getTotal(); i++)
					temp.setChild(i, getChild(i));

				// erase top level
				setTotal(0);
				setFlag(true);

				// reinsert all data
				for(int i=0; i<temp.getTotal(); i++)
                    root = ((RTNode)temp.getChild(i)).reInsert(env, root);
				return root;
			}

			// node has too few entries, must delete it and reinsert members
			int found = -1;
			for(int i=0; i<prtn.getTotal(); i++)
				if (prtn.getChild(i) == this) { found = i;   break; }
			if (found < 0) System.out.println("R-trees: cannot find entry in parent");

			// remove this entry from its parent
			root = prtn.removeRTNode(found, env, root);

			// reinsert the entries
			return reInsert(env, root);
		}

		// recompute bounding box of this R-tree node and all up the tree
		RTNode climb = this;
		for(;;)
		{
			climb.figBounds();
			if (climb.getParent() == null) break;
			climb = climb.getParent();
		}
        return root;
	}

	/**
	 * Method to reinsert the tree of nodes below this RTNode into cell "cell".
	 */
	private RTNode reInsert(Object env, RTNode root)
	{
		if (getFlag())
		{
			for(int i=0; i<getTotal(); i++)
                root = linkGeom(env, root, (RTBounds)getChild(i));
		} else
		{
			for(int i=0; i<getTotal(); i++)
				root = ((RTNode)getChild(i)).reInsert(env, root);
		}
        return root;
	}

	/**
	 * Method to find the location of geometry module "geom" in the R-tree
	 * below this.  The subnode that contains this module is placed in "subrtn"
	 * and the index in that subnode is placed in "subind".  The method returns
	 * null if it is unable to find the geometry module.
	 */
	private Object [] findGeom(RTBounds geom)
	{
		// if R-tree node contains primitives, search for direct hit
		if (getFlag())
		{
			for(int i=0; i<getTotal(); i++)
			{
				if (getChild(i) == geom)
				{
					Object [] retObj = new Object[2];
					retObj[0] = this;
					retObj[1] = new Integer(i);
					return retObj;
				}
			}
			return null;
		}

		// recurse on all sub-nodes that would contain this geometry module
		Rectangle2D geomBounds = geom.getBounds();
		for(int i=0; i<getTotal(); i++)
		{
			// get bounds and area of sub-node
			Rectangle2D bounds = getBBox(i);

			if (bounds.getMaxX() < geomBounds.getMinX()-DBMath.getEpsilon()) continue;
			if (bounds.getMinX() > geomBounds.getMaxX()+DBMath.getEpsilon()) continue;
			if (bounds.getMaxY() < geomBounds.getMinY()-DBMath.getEpsilon()) continue;
			if (bounds.getMinY() > geomBounds.getMaxY()+DBMath.getEpsilon()) continue;
			Object [] subRet = ((RTNode)getChild(i)).findGeom(geom);
			if (subRet != null) return subRet;
		}
		return null;
	}

	/**
	 * Method to find the location of geometry module "geom" anywhere in the R-tree
	 * at "rtn".  The subnode that contains this module is placed in "subrtn"
	 * and the index in that subnode is placed in "subind".  The method returns
	 * false if it is unable to find the geometry module.
	 */
	private Object [] findGeomAnywhere(RTBounds geom)
	{
		// if R-tree node contains primitives, search for direct hit
		if (getFlag())
		{
			for(int i=0; i<getTotal(); i++)
			{
				if (getChild(i) == geom)
				{
					Object [] retVal = new Object[2];
					retVal[0] = this;
					retVal[1] = new Integer(i);
					return retVal;
				}
			}
			return null;
		}

		// recurse on all sub-nodes
		for(int i=0; i<getTotal(); i++)
		{
			Object [] retVal = ((RTNode)getChild(i)).findGeomAnywhere(geom);
			if (retVal != null) return retVal;
		}
		return null;
	}

	/**
	 * Class to search a given area of a Cell.
	 * This class acts like an Iterator, returning RTBounds objects that are inside the selected area.
	 * <P>
	 * For example, here is the code to search cell "myCell" in the area "bounds" (in database coordinates):
	 * <P>
	 * <PRE>
	 * for(RTNode.Search sea = <B>new RTNode.Search(bounds, cell)</B>; sea.hasNext(); )
	 * {
	 *     Geometric geom = (Geometric)sea.next();
	 *     if (geom instanceof NodeInst)
	 *     {
	 *         NodeInst ni = (NodeInst)geom;
	 *         // process NodeInst ni in the selected area
	 *     } else
	 *     {
	 *         ArcInst ai = (ArcInst)geom;
	 *         // process ArcInst ai in the selected area
	 *     }
	 * }
	 * </PRE>
	 */
	public static class Search implements Iterator<RTBounds>
	{
		/** maximum depth of search */			private static final int MAXDEPTH = 100;

		/** current depth of search */			private int depth;
		/** RTNode stack of search */			private RTNode [] rtn;
		/** index stack of search */			private int [] position;
		/** desired search bounds */			private Rectangle2D searchBounds;
		/** the next object to return */		private RTBounds nextObj;
        /** includes objects on the search area edges */ private boolean includeEdges;

        public Search(Rectangle2D bounds, RTNode root, boolean includeEdges)
		{
			this.depth = 0;
			this.rtn = new RTNode[MAXDEPTH];
			this.position = new int[MAXDEPTH];
			this.rtn[0] = root;
			this.searchBounds = new Rectangle2D.Double();
			this.searchBounds.setRect(bounds);
            this.includeEdges = includeEdges;
			this.nextObj = null;
		}

		/**
		 * Method to return the next object in the bounds of the search.
		 * @return the next object found.  Returns null when all objects have been reported.
		 */
		private RTBounds nextObject()
		{
			for(;;)
			{
				RTNode rtnode = rtn[depth];
				int i = position[depth]++;
				if (i < rtnode.getTotal())
				{
					Rectangle2D nodeBounds = rtnode.getBBox(i);
                    if (includeEdges)
                    {
                        if (nodeBounds.getMaxX() < searchBounds.getMinX()) continue;
                        if (nodeBounds.getMinX() > searchBounds.getMaxX()) continue;
                        if (nodeBounds.getMaxY() < searchBounds.getMinY()) continue;
                        if (nodeBounds.getMinY() > searchBounds.getMaxY()) continue;
                    }
                    else
                    {
                        if (nodeBounds.getMaxX() <= searchBounds.getMinX()) continue;
                        if (nodeBounds.getMinX() >= searchBounds.getMaxX()) continue;
                        if (nodeBounds.getMaxY() <= searchBounds.getMinY()) continue;
                        if (nodeBounds.getMinY() >= searchBounds.getMaxY()) continue;
                    }
					if (rtnode.getFlag()) return((RTBounds)rtnode.getChild(i));

					// look down the hierarchy
					if (depth >= MAXDEPTH-1)
					{
						System.out.println("R-trees: search too deep");
						continue;
					}
					depth++;
					rtn[depth] = (RTNode)rtnode.getChild(i);
					position[depth] = 0;
				} else
				{
					// pop up the hierarchy
					if (depth == 0) break;
					depth--;
				}
			}
			return null;
		}

		public boolean hasNext()
		{
			if (nextObj == null)
			{
				nextObj = nextObject();
			}
			return nextObj != null;
		}

		public RTBounds next()
		{
			if (nextObj != null)
			{
				RTBounds ret = nextObj;
				nextObj = null;
				return ret;
			}
			return nextObject();
		}

		public void remove() { throw new UnsupportedOperationException("Search.remove()"); };
	}
}