Next: Elastic Window Operations Up: Data Structures and Algorithms Previous: Elastic Windows Data Structures

## Window Hierarchy

The Elastic Windows algorithms use a modified ordered k-ary tree data structure with three types of nodes to manipulate hierarchically nested windows. Each node in the tree structure corresponds to a visible window or an invisible grouping of windows. At each level of the tree, space is partitioned either horizontally or vertically in an alternating order. Children of a node are ordered either left to right (horizontal) or bottom to top (vertical) depending on the partitioning. The ordering among the children nodes determines the stacking order within their parents' space. A pointer, called TreeRoot, is kept to the root of this tree structure pointing to the current top-level window.

There are three types of nodes in the tree data structure as follows:

• H-node: Visible non-leaf hierarchy window, nesting at least another child window
• G-Node: Invisible non-leaf group window to skip partitioning order, nesting at least another child window
• L-Node: Visible leaf window with no children windows, displaying content view on its associated object

An example hierarchical window layout and its corresponding tree structure is shown in Figure . Here, node A is the root window, which has two children: node X and D. Node X is a G-Node with no visible borders, which has two children nodes B and C, vertically stacked. Thus, by the use of a G-Node, in practice, window A has three children, two of them stacked vertically, one horizontally.

At each node the following information is kept about its associated window:

• WindowType: Boolean to indicate that the node is horizontal (TRUE) or vertical (FALSE)
• ID: Window identification number
• OID: Identification number of the associated object
• Index: Index number for the stacking order
• H: Boolean to indicate that the node is an H-Node
• G: Boolean to indicate that the node is a G-Node
• Level: Depth of the window counting only H-Nodes to the root
• NumberOfChildren: Number of children nodes
• ChildrenArray: Array of pointers to the children nodes
• Position: Array of cut locations for children nodes
• Parent: Pointer to the parent node
• XMin, XMax, YMin, YMax: Coordinates of the window

This data structure resembles the adaptive k-d-tree with multiple cuts. Instead of marking nodes with cut directions, alternating cut directions (horizontal and vertical) are assumed and G-Nodes are introduced that allow to skip levels which also simplifies most of the algorithms. It uses data-based partitioning that suits more the dynamic nature of the layout. Layout changes do not result in node reorganizations. The representation of the rectangle data is area-based to make better use of the space-filling layout strategy by storing only the cut points. The hierarchy relationship is coded into the data structure simply by indicating such nodes as H-Nodes.

Next: Elastic Window Operations Up: Data Structures and Algorithms Previous: Elastic Windows Data Structures

Eser Kandogan
Sun Sep 13 18:34:46 EDT 1998

Web Accessibility