com.sun.electric.database.topology
Class RTNode

java.lang.Object
  extended by com.sun.electric.database.topology.RTNode

public class RTNode
extends java.lang.Object

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.

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:


Nested Class Summary
static class RTNode.Search
          Class to search a given area of a Cell.
 
Method Summary
 void checkRTree(int level, java.lang.Object env)
          Method to check the validity of an RTree node.
 java.lang.Object getChild(int index)
          Method to get the number of children of this RTNode.
 boolean getFlag()
          Method to get the leaf/branch flag of this RTNode.
 int getTotal()
          Method to get the number of children of this RTNode.
static RTNode linkGeom(java.lang.Object env, RTNode root, RTBounds geom)
          Method to link this RTBounds into the R-tree of its parent Cell.
static RTNode makeTopLevel()
          Method to create the top-level R-Tree structure for a new Cell.
 void printRTree(int indent)
          Debugging method to print this R-Tree.
static RTNode unLinkGeom(java.lang.Object env, RTNode root, RTBounds geom)
          Method to remove this geometry from the R-tree its parent cell.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

getTotal

public int getTotal()
Method to get the number of children of this RTNode.


getChild

public java.lang.Object getChild(int index)
Method to get the number of children of this RTNode.


getFlag

public boolean getFlag()
Method to get the leaf/branch flag of this RTNode.


makeTopLevel

public static RTNode makeTopLevel()
Method to create the top-level R-Tree structure for a new Cell.

Returns:
an RTNode object that is empty.

linkGeom

public static RTNode linkGeom(java.lang.Object env,
                              RTNode root,
                              RTBounds geom)
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.

Parameters:
env - the environment of this operation (for messages).
root - root of the RTree.
geom - RTBounds to link.
Returns:
new root of RTree.

unLinkGeom

public static RTNode unLinkGeom(java.lang.Object env,
                                RTNode root,
                                RTBounds geom)
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.

Parameters:
env - the environment of this operation (for messages).
root - root of the RTree.
geom - RTBounds to unlink.
Returns:
new root of RTree.

printRTree

public void printRTree(int indent)
Debugging method to print this R-Tree.

Parameters:
indent - the level of the tree, for proper indentation.

checkRTree

public void checkRTree(int level,
                       java.lang.Object env)
Method to check the validity of an RTree node.

Parameters:
level - the level of the node in the tree (for error reporting purposes).
env - the environment in which this node resides.