All for .net, .net for all!

LearnVSXNow! Part #35 - Working with Hierarchies Part 2 - Internal Structure of Hierarchies

In the previous part of this mini-series I gave an overview of the IVsHierarchy interface. My statement was that the hierarchy abstraction provided by IVsHierarchy is very different from the one we get used to in connection with tree views.

IVsHierarchy represents a collection of nodes forming a hierarchy. The hierarchy has a distinguished node called root node and each node can have a shortcut to another hierarchy. Each node has a collection of properties, a few defining the internal structure of the hierarchy and potentially unlimited number of arbitrary properties that can be accessed and interpreted in the context where the hierarchy is used.

In this article I treat the internal structure of the hierarchy and explain some important details that are fundamental to understand how hierarchies work.

The Tree View Approach

The TreeView control is one of the most widely used in applications with graphical UI. Many developers use it frequently for Windows Forms, ASP.NET and WPF applications. The internal structure of a TreeView instance is quite simple from the developer’s point of view. The tree has zero, one or more root nodes and each node can have child nodes recursively. When working with a concrete node instance, we can directly access its children through an enumeration. The following figure shows how we see a tree:

The tree on the left has eight nodes and each node has a collection of child nodes indicated in the table on the right side. When the developer works with Node1, it can access its Nodes container and enumerate child nodes. In this meaning each node in the tree is a nested hierarchy composed from other nested hierarchies.

The TreeView control works with the concept of tree nodes where the lion’s share of the behavior is delegated to these tree nodes. A tree node knows its parent node and keeps an inventory of its child nodes. It has simple operations to add or remove a child, change the properties of the node.

IVsHierarchy Approach

IVsHierarchy provides a more generic abstraction of a tree than the TreeView control and assumes a different type of behavior to provide the functionality required for representing a hierarchy. In the following points I summarize the essential elements of the IVsHierarchy approach.

—  No explicit operations for adding or removing nodes. In the previous part I enumerated the interface methods of IVsHierarchy. We could see there are no explicit operations to add a node to a hierarchy or to remove it! It is an interesting question, how can we extend or reduce the hierarchy without these operations? Do not worry in a later post I will answer this question.

—  The hierarchy is self-organizing. Each node has limited explicit information about its context. They know the following explicit structural information about themselves:

—  IVsHierarchy instance managing the collection of hierarchy nodes

—  Their own VSITEMID

—  The VSITEMID of their parent node within the hierarchy

—  The VSITEMID of their first child node within the hierarchy

—  The VSITEMID of their next sibling node within the hierarchy

—  Distinction between physical and visual representation. The hierarchy has a physical structure (how the hierarchy nodes are “chained” together to form a tree) and a visual structure (how they are displayed) that may be different from the physical structure. The visual structure can change the order of children for a hierarchy item or even hide nodes (or a complete subtree formed by a set of nodes). To achieve this behavior each node has some more structural information beside the aforementioned ones:

—  The VSITEMID of their first visible child node within the hierarchy

—  The VSITEMID of their next visible sibling node within the hierarchy

—  Shortcuts to other hierarchies. We can assign zero or one shortcut to a hierarchy items pointing to the root node of another hierarchy. Only zero or one shortcut is allowed to refer the root node of the other hierarchy. A root node of the hierarchy keeps more structural information about itself than a non-root node:

—  The IVsHierarchy instance representing the parent hierarchy that has a node with shortcut to this root node.

—  The VSITEMID of the node in the parent hierarchy that has the shortcut of this root node.

I suppose, you are going to be lost shortly in the forest of IVsHierarchy and VSITEMID instances, so I show you a few concrete examples to understand how nodes are organized into a hierarchy.

Hierarchies Organized By Structural Properties

To make it easier to imagine how the structural properties form the hierarchy, let’s see a figure summarizing these properties:

We can take these structural properties into account as pointers that link together nodes within a hierarchy or between hierarchies. The solid arrows in this figure represent links within the owning hierarchy of Node while dashed arrows illustrate inter-hierarchy relationships. The latest one is used to access the parent hierarchy node (the shortcutting node) from a root node of a nested (shortcut) hierarchy.

All the VSITEMID-typed structural properties are used to represent the hierarchy of nodes by allowing traversal from parent to child nodes and from one sibling to another. Let’s assume we have the following nodes illustrated as a tree:

In this tree Node3 and Node5 represent invisible nodes. The physical layout of tree (including hidden nodes) can be represented by the structural properties in the following way:

The names of structural properties are abbreviated:

—  P: Parent

—  FC: FirstChild

—  NS: NextSibling

For the sake of clarity I omitted all the links representing structural properties with “NIL” values. For example, the FirstChild property of Node6 is NIL, because Node6 does not have a child.

The visual layout of the tree represents only the visible nodes and uses the FirstVisibleChild and NextVisibleSibling structural properties in the following way:

Here I used the FVS abbreviation for FirstVisibleChild and NVS for NextVisibleSibling.

Although in the figures I illustrated the structural properties with links, actually they are not physical pointers but VSITEMIDs identifying the target node in the hierarchy. As you may recall from the previous article, VSITEMIDs are 32-bit unsigned integers created by the shell. For the sake of simplicity let’s assume that each node has a VSITEMID that equals with its index. Node1 has VSITEMID with a value of 1, Node7 with the value of 7 and so on. The root node always has its ID with the value of VSITEMID_ROOT (or simply ROOT). From this perspective we can describe our hierarchy with a table that lists the structural property values for each node:

I suppose, it is easy to understand how this table works. For example, the NVS column for Node2 says that the next visible sibling of Node2 is Node4.

Shortcuts to Hierarchies

Visual Studio represents projects in a solution with nested (shortcut) hierarchies. We also can have nested hierarchies. For example, the simple tree with eight nodes we used in the examples above can be composed from two hierarchies as illustrated here:

The two hierarchies here are the one with the root Node0 and the other with root Node1. In the first hierarchy we have a node with a shortcut to Node1. This node definitely belongs to the Node0 hierarchy and has its own VSITEMID within that hierarchy. I call it NodeX. When the hierarchy is visualized, we do not see NodeX, we see only Node1. Visually we cannot decide if Node1 is a part of the Node0 hierarchy or belongs to a separate one.

There is no structural property that would tell whether a node has a shortcut or not. The IVsHierarchy provides the GetNestedHierarchy method to check this fact. As we saw before, a node has properties to check its parent hierarchy and the VSITEMID of the node in the parent hierarchy having the shortcut.

Where we are?

The IVsHierarchy approach is very different from the one developers perceive when using TreeView controls. A hierarchy contains a collection of hierarchy items. Relations between items (parent, children, and siblings) are defined through so-called structural properties. These properties are links to other nodes and use the appropriate VSITEMID to address the target node.

Till this time we have not seen any code yet. In the next blog, I will dive into the details of hierarchy traversal and we are going to write code.

Posted Oct 09 2008, 10:43 AM by inovak
Filed under: ,


Munir Husseini wrote re: LearnVSXNow! Part #35 - Working with Hierarchies Part 2 - Internal Structure of Hierarchies
on Sat, Oct 9 2010 23:34

Great articles! They really clarified things for me. Thanks a lot.

About IVsHierarchy Structure for VSPackage Development « ????????????????????? wrote About IVsHierarchy Structure for VSPackage Development « ?????????????????????
on Fri, Apr 22 2011 11:04

Pingback from  About IVsHierarchy Structure for VSPackage Development « ?????????????????????

rimonabantexcellence site title wrote rimonabantexcellence site title
on Wed, Jul 17 2013 6:15

Pingback from  rimonabantexcellence site title