Patent ID: 7096444

Claim:
A computer implemented method for representing a layout of a programmable device as a tree structure to be searched by a computer program for determining a configuration of components within a selected area of the layout, the method comprising: representing a main portion of the device layout as a root node on the tree structure; assigning faux cell units to represent an area of the main portion occupied by a non-uniform layout unit straddling across multiple sub-areas of the main portion; representing each sub-area of the main portion as a branch node of the main portion root; dividing each sub-area further into equally sized lower level sub-areas until each of the lower level sub-areas corresponds to a layout unit of the device layout or a faux cell unit; representing each of the sub-areas corresponding to a layout unit or a faux cell unit as a leaf node on the tree structure; relating leaf nodes related to the faux cell units to the non-uniform straddling layout unit; and selecting one of the faux cell units to return results of a search rectangle overlapping the one or more of the faux cell units.