As you know, a treeview control is very useful for viewing hierarchical information. Each node in a tree can have its own parent/child relationships.

Some of these trees can be extremely large, and can thus be prohibitively expensive to calculate completely.

Windows Explorer comes to mind. Outlook Mailbox folders. The game of chess.

Here’s a hypothesis: The tree of possible chess games is finite:

·        There’s a finite number of chess pieces on a board at any time.

·        At any given board position each piece has a finite number of moves

·        A draw is the result of 3 repeated positions

·        A draw is the result of 50 moves without a pawn move or capture

So, we could enumerate the tree to have a node representing each possible board position. The parent is the prior move. The children are the positions resulting from the possible moves from that position.

We can calculate the average fanout (average number of children per node, or moves from a position) of the tree. From the starting position, each pawn can move 2 possible squares and each knight can move 2. That’s 8 pawns* 2 + 2 knights * 2 = 18 possible positions after the 1st move. Let’s call it 20 moves per position.

The number of moves in a chess game (White, then Black, then White is 3 moves) is usually way less than 100 until checkmate, resignation, or draw. Let’s call it 100.

Thus we have about 20 ^ 100 moves. Let’s calculate the power of 10, or the number of zeros.

From my slide rule days (remember those? Before the calculator!) I remember memorizing the base 10 logarithm of the integers from 1-10.

Of course, this is pretty trivial for some numbers:

N    Log10(N)    Notes

1             0             Trivial: 10^0 = 1

2             .3010     Gotta remember it: 10^.3010 = 2

3             .4771     Remember it

4             .6020     Just twice Log10(2)

5             .6990     ez to remember

6             .7782     Just Log10(2) + Log10(3)

7             .8451     kinda harder to remember

8             .9031     3 Log10(2)

9             .9542     2 Log10(3)

10           1             not so hard: 10^1 = 1J

So it really  comes down to remembering the primes  >1 and < 10 = 2,3,5,7 which is only 4 numbers! Remembering these 4 numbers allows a huge range of order of magnitude (power of 10) calculations.

Getting back to our problem, we want to know x where 10^x = 20^100.

From the laws of logarithms and the table,

x = Log10(20^100) = 100 * (Log10(4*5)) = 100 * (log10(4) + log10(5)) = 100 * (2 * .3010 + .6990) = 100 * (.1301) = 130

Thus 20^ 100 = 10 ^ 130  (Go ahead: try it on a calculator!)

(See the Shannon number indicating that the number is roughly 10^120 )

This number is way more than a googol and way more than the number of electrons in the universe! And is thus effectively impractical to compute.

In any case, getting back to our little TreeView sample

Start VS 2010 File->New->Project->VB->WPF Application. Replace the Mainwindow.Xaml.vb with the code below.

Make sure that the xmlns in the inline XML in the code matches the project and namespace name. I chose “WpfApplication1” for both the project and the namespace for my sample.

Hit F5 to run the code.

Note the time it takes for the Title of the window to indicate the total number of nodes before the treeview is visible. Thus calculating the tree seems faster than rendering it.

Try moving around the tree, and hovering the mouse over an expanded item to see the MouseOver event trigger change the colors.

The code shows the inheritance hierarchies of a few classes in the WPF namespace, and can be completely calculated in a few seconds, resulting in about 3600 nodes.

Try commenting out the assignment of the ItemContainerStyle in the MyTreeViewItem constructor to see how styles propagate.

When you bring up Windows Explorer (Windows Key + E),  you can see a tree representation of the files on your disk. Obviously, the designers of that treeview wanted to make it appear quickly, so only the top level nodes are shown (perhaps a few dozen) rather than calculating the entire tree (perhaps millions of nodes).

Creating child nodes dynamically only upon request, (the user chooses a particular child from perhaps dozens and clicks to expand it) is a great technique.

Dynamically create huge tooltips in WPF TreeView and ListView

Returning data from a recursive method

Remove double spaces from pasted code samples in blog

<Code>

Imports System.Reflection

Class MainWindow

Private Sub Window_Loaded(ByVal sender As System.Object, ByVal e As System.Windows.RoutedEventArgs) Handles MyBase.Loaded

Try

Me.Width = 800

Me.Height = 800

Dim treeview = New MyTreeView

Me.Content = treeview

Dim asm = Assembly.GetAssembly(GetType(TreeView)) ' PresentationFramework

For Each typ In asm.GetExportedTypes

FillData(treeview, typ)

Next

Me.Title = String.Format("Num items = {0}   Asm = {1}", MyTreeViewItem._nTotItems, asm.FullName)

Catch ex As Exception

Me.Content = ex.ToString

End Try

End Sub

Public Sub FillData(ByVal itemsControl As ItemsControl, ByVal typ As Type)

Dim childItem = New MyTreeViewItem With {.Header = String.Format("{0}", typ.Name)}

If typ.BaseType IsNot Nothing Then

FillData(childItem, typ.BaseType) ' recur

'childItem.IsExpanded = True  ' expand the node: takes more time!

End If

'For Each mem In typ.GetMembers

'Next

End Sub

End Class

Public Class MyTreeView

Inherits TreeView

Friend Shared myStyle As Windows.Style

Sub New()

'"Segoe UI" "Consolas" "Tahoma" "Calibri" "Lucida Console" "Lucida Sans Typewriter" "MS Gothic" "MS Mincho" "David" "Modern No. 20"

Dim _FontName = "Segoe UI"

Dim _FontSize = "8"

Dim _Foreground = "Blue"

Dim _Background = "AntiqueWhite"

' http://msdn.microsoft.com/en-us/library/aa358802(v=VS.85).aspx

'Public Text_Colors() As String = {"AliceBlue", "AntiqueWhite", "Aqua", "Aquamarine", "Azure", "Beige", "Bisque", "Black", "BlanchedAlmond",

'"Blue", "BlueViolet", "Brown", "BurlyWood", "CadetBlue", "Chartreuse", "Chocolate", "Coral", "CornflowerBlue", "Cornsilk", "Crimson", "Cyan",

'"DarkBlue", "DarkCyan", "DarkGoldenrod", "DarkGray", "DarkGreen", "DarkKhaki", "DarkMagenta", "DarkOliveGreen", "DarkOrange", "DarkOrchid", "DarkRed",

'"DarkSalmon", "DarkSeaGreen", "DarkSlateBlue", "DarkSlateGray", "DarkTurquoise", "DarkViolet", "DeepPink", "DeepSkyBlue", "DimGray", "DodgerBlue", "Firebrick",

'"FloralWhite", "ForestGreen", "Fuchsia", "Gainsboro", "GhostWhite", "Gold", "Goldenrod", "Gray", "Green", "GreenYellow", "Honeydew", "HotPink", "IndianRed", "Indigo",

'"Ivory", "Khaki", "Lavender", "LavenderBlush", "LawnGreen", "LemonChiffon", "LightBlue", "LightCoral", "LightCyan", "LightGoldenrodYellow", "LightGray", "LightGreen",

'"LightPink", "LightSalmon", "LightSeaGreen", "LightSkyBlue", "LightSlateGray", "LightSteelBlue", "LightYellow", "Lime", "LimeGreen", "Linen", "Magenta", "Maroon",

'"MediumAquamarine", "MediumBlue", "MediumOrchid", "MediumPurple", "MediumSeaGreen", "MediumSlateBlue", "MediumSpringGreen", "MediumTurquoise", "MediumVioletRed",

'"MidnightBlue", "MintCream", "MistyRose", "Moccasin", "NavajoWhite", "Navy", "OldLace", "Olive", "OliveDrab", "Orange", "OrangeRed", "Orchid", "PaleGoldenrod",

'"PaleGreen", "PaleTurquoise", "PaleVioletRed", "PapayaWhip", "PeachPuff", "Peru", "Pink", "Plum", "PowderBlue", "Purple", "Red", "RosyBrown", "RoyalBlue", "SaddleBrown",

'"Salmon", "SandyBrown", "SeaGreen", "SeaShell", "Sienna", "Silver", "SkyBlue", "SlateBlue", "SlateGray", "Snow", "SpringGreen", "SteelBlue", "Tan", "Teal", "Thistle",

'"Tomato", "Transparent", "Turquoise", "Violet", "Wheat", "White", "WhiteSmoke", "Yellow", "YellowGreen"}

'Note: make sure the 3rd xmlns has the right namespace and assembly name

Dim XAMLtvItemStyle = _

<Style

xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"

xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"

xmlns:l="clr-namespace:WpfApplication1;assembly=WpfApplication1"

TargetType="{x:Type TypeName=l:MyTreeViewItem}">

<Setter Property="FontFamily" Value=<%= _FontName %>/>

<Setter Property="FontSize" Value=<%= _FontSize.ToString + "pt" %>/>

<Setter Property="Foreground" Value=<%= _Foreground %>/>

<Setter Property="Background" Value=<%= _Background %>/>

<Style.Triggers>

<Trigger Property="IsMouseOver" Value="True">

<Setter Property="Foreground" Value="DarkRed"/>

<Setter Property="Background" Value="LightGray"/>

</Trigger>

</Style.Triggers>

</Style>

' examine the Style properties at a breakpoint

Me.ItemContainerStyle = myStyle

' here we can create a new contextmenu which will be accessible from every node

End Sub

End Class

Public Class MyTreeViewItem

Inherits TreeViewItem

Friend Shared _nTotItems As Integer

Sub New()

Me.ItemContainerStyle = MyTreeView.myStyle ' try commenting this line out and expanding nodes

_nTotItems += 1

End Sub

End Class

</Code>