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.

 

See also

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)}

 

        itemsControl.Items.Add(childItem)

 

        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

        '    itemsControl.Items.Add(New MyTreeViewItem With {.Header = mem.Name})

        '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>

 

        myStyle = CType(Windows.Markup.XamlReader.Load(XAMLtvItemStyle.CreateReader), Windows.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

        'Me.ContextMenu = New ContextMenu

        'Me.ContextMenu.AddMnuItem("_DumpChildren To Notepad", "Dump expanded children to notepad", AddressOf on_ctxMenuItemBase)

        'Me.ContextMenu.AddMnuItem("_Expand SubTree", "Expand tree branch from here: warning: try small branches first!", AddressOf on_ctxMenuItemBase)

 

    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>