Critical Development

Language design, framework development, UI design, robotics and more.

Archive for March, 2008

A Workaround for Poor Formatting and Copy-Paste Behavior of Code on the Web

Posted by Dan Vanderboom on March 22, 2008

I bought BlogJet for publishing my blog articles, and have struggled with it (sometimes for hours) to get the formatting right, or as close to it as possible.  Sometimes I can paste code in it from Visual Studio (to get the color-coding perfect), and other times the color or indentations won’t transfer.  Invariably the way it looks when published doesn’t represent the way it looks in the editor itself.

Maybe BlogJet just sucks and there is a better option!  With this idea in mind, I downloaded and started using Microsoft Live Writer, which is free and part of Microsoft Live Services.  At first I was very happy with it, but soon I realized that it had many of the same problems as BlogJet.  What are they doing, copying each others’ bugs?!

So I’m on the lookout for an exceptional blog publishing software package.  I’d like to manage categories through it (add, edit, remove), maybe read comments, or at least be able to have an accurate and reliable WYSIWYG experience.  If you know of any, drop me a line.  I’m willing to pay a premium price for a good thick-client article authoring environment.

In the meantime, I’ve discovered that I can usually get around the source code problem by copying the code first into Microsoft Word, and then copying it from Word and pasting into the blog software.  No extra lines, indentation, or color problems so far have occurred with this technique.  Why does this work?  I have no idea.

Also, if you’re copying code from a webpage such as my blog, and pasting it directly into Visual Studio (or the Macro editor), you’ll notice blank lines between lines of code.  If you care, the same trick of copying to Word, and copying from Word to Visual Studio, will steer you around this annoyance.

Posted in Visual Studio | 3 Comments »

Visual Studio Macro: Locate Item in Solution Explorer on Demand

Posted by Dan Vanderboom on March 21, 2008

[ For an updated macro that works best with VS2008 and VS2010, see the followup article. ]

By default, Visual Studio’s Solution Explorer will update its selected item based on the currently active document.  This is occassionally useful when exploring unfamiliar code, but it’s annoying when it’s always on, bouncing around as you navigate through larger solutions.

Do you want to disable project item tracking?

 

Go to Tools—>Options, expand Projects and Solutions, select General, and then uncheck the box next to Track Active Item in Solution Explorer.

But what if you’re looking at a document, and you want to know where in Solution Explorer it’s located?  Unfortunately, you would have to go back into Tools—>Options, …, turn that option back on, locate the project item, and then turn it back off again.

This is very inconvenient.  What would be ideal is a button or hot key that would jump to that item in Solution Explorer just once, on demand.  “Where’s the corresponding project item for this document?  Find it and then don’t track after that.”

After about two hours of messing around with the VS SDK, trying to read the documentation, finding out that this particular option isn’t available for manipulation through automation, and resolving to figure out another way to do it, I finally accomplished this goal and I’m happy to share the macro that I created.

Don’t know how to create a macro?

 

Adding a macro is easy.  First open the Macro Explorer.  Press Alt-F8, or if you’ve remapped your keys, go to Tools—>Macros—>Macro Explorer.  You’ll probably have a project in there called MyMacros.  If not, right-click on Macros and select New Macro Project…  A window pops up, and you can enter a project name.  Once you have selected or created a macro project, right click on the project name and select New module…  I named mine Utilities.  Right click on the module name and select Edit.  You should now see a VB code editor window.

Copy the following code into the editor and press Ctrl-S to save it.

Imports System
Imports EnvDTE
Imports EnvDTE80
Imports EnvDTE90

Public Module Utilities
    Public Sub TrackProjectItem()
        Dim solution As Solution2 = DTE.Solution
        If Not solution.IsOpen OrElse DTE.ActiveDocument Is Nothing Then Return

        solution.FindProjectItem(DTE.ActiveDocument.FullName).ExpandView()

        Dim FileName As String = DTE.ActiveDocument.FullName

        Dim SolutionExplorerPath As String
        Dim items As EnvDTE.UIHierarchyItems = DTE.ToolWindows.SolutionExplorer.UIHierarchyItems
        Dim item As Object = FindItem(items, FileName, SolutionExplorerPath)

        If item Is Nothing Then
            MsgBox("Couldn't find the item in Solution Explorer.")
            Return
        End If

        DTE.Windows.Item(Constants.vsWindowKindSolutionExplorer).Activate()
        DTE.ActiveWindow.Object.GetItem(SolutionExplorerPath).Select(vsUISelectionType.vsUISelectionTypeSelect)
    End Sub

    Public Function FindItem(ByVal Children As UIHierarchyItems, ByVal FileName As String, ByRef SolutionExplorerPath As String) As Object
        For Each CurrentItem As UIHierarchyItem In Children
            Dim TypeName As String = Microsoft.VisualBasic.Information.TypeName(CurrentItem.Object)
            If TypeName = "ProjectItem" Then
                Dim projectitem As EnvDTE.ProjectItem = CType(CurrentItem.Object, EnvDTE.ProjectItem)
                Dim i As Integer = 1
                While i <= projectitem.FileCount
                    If projectitem.FileNames(i) = FileName Then
                        SolutionExplorerPath = CurrentItem.Name
                        Return CurrentItem
                    End If
                    i = i + 1
                End While
            End If

            Dim ChildItem As UIHierarchyItem = FindItem(CurrentItem.UIHierarchyItems, FileName, SolutionExplorerPath)
            If Not ChildItem Is Nothing Then
                SolutionExplorerPath = CurrentItem.Name + "\" + SolutionExplorerPath
                Return ChildItem
            End If
        Next
    End Function
End Module

 

Now let’s hook it up to a keyboard hot key to make it super fast to access.  If you open Tools—>Options, expand Environment, select Keyboard, and in the text box labeled Show commands containing, type part of the macro name, such as TrackProjectItem.  You’ll see your new macro in the list highlighted.  In the dropdown control labeled Use new shortcut in, select Text Editor.  Click on the box that says Press shortcut keys, and press a key combination.  I chose Alt-T (for Track), which was available in that context to my surprise.

Try it out.  Open up a few code or XML windows.  Make one of those windows active and press your hot key.  The item in Solution Explorer that corresponds to the current document window will activate.

 

Tags: , , ,

Posted in Invention-A-Day, Visual Studio, Visual Studio Extensibility | 47 Comments »

Tree<T>: Implementing a Non-Binary Tree in C#

Posted by Dan Vanderboom on March 15, 2008

[Updated 8/14/2014] The source code for this library can be found here at GitHub. Also check out my blog post announcing it.

[This is the first article in a series of intelligent data structures, which is continued here with KeyedList.]

I’ve always thought it was odd that the .NET Framework never shipped with a Tree or Tree class in its collection namespaces.  Most of the other classic data structures are there: List, Dictionary, Stack, Queue, and so on.  Where then is Tree?  I have no idea, but finding myself in need of one, I decided to build one, and in doing so realized that it was a little trickier than I first imagined it would be.  Certainly it isn’t difficult to get some kind of tree working, even without support for generics, but building one that is truly intuitive to use was a real challenge.  In this article I will share what I came up with, and will illustrate the thought process behind each of the design decisions that I made as a study in object-oriented design and the use of some cool C# language features like generics constraints.

First, what is a tree data structure and what is it used for?  A tree is, in layman’s terms, a collection of nodes (items) that are connected to each other in such a way that no cycles (circular relationships) are allowed.  Examples abound in organization charts, family trees, biological taxonomies, and so forth.  Trees are incredibly useful structures because they allow us to represent hierarchies and to compose complex structures out of basic parts and simple relationships.  In the world of programming specifically, this provides a mechanism for extensibility across many domains, and a container to assist us in searching, sorting, compressing, and otherwise processing data in efficient and sophisticated ways.  Trees are also a natural fit for use in the composite design pattern, where a group of objects can be treated (or processed) like a single object.

Just as it’s possible to implement recursive algorithms non-recursively, it’s also possible to create non-hierarchical data structures to store data that would more logically be stored in a tree.  In these cases, your code is typically much more clear when organized in a tree, leading to greater maintainability and refactorability.  Recursion itself, while not exceptionally common in every day programming tasks, plays a more important role in some interesting ways with trees and traversal patterns.  Traversal is the term used to describe how nodes in a tree are visited.  Later I’ll demonstrate some tree traversal techniques that you can use.

Binary vs. Non-Binary Trees

What are binary trees, and why the focus on non-binary trees?  Binary trees are a special kind of tree in which each node can only have two children, often referred to as left and right child nodes.  These special trees are very useful for sophisticated searching, sorting, and other algorithms.  However, trees that allow any number of children seem to abound in more general, every-day programming scenarios, as you’ll see from examples below.  In a follow-up article, I’ll demonstrate how you can create a BinaryTree class that inherits from Tree and applies the necessary restrictions and some useful abstractions.  Below (figure 1) is a binary tree, which I present here to contrast with the non-binary trees that we’ll be covering in detail.

BinaryTree

Figure 1. A generic binary tree.

For more information on implementing and using binary trees, see this article which is part of a larger series on data structures.

Examples of Non-Binary Trees

A simple example of a non-binary tree is the file system in any modern operating system.  The diagram below (figure 2) illustrates a small part of the structure of the Windows file system.  Folders can be nested inside other folders as deeply as needed, providing the ability to compose a complex organizational structure for storing files.  The traversal path—from the root to some other node—can be represented by a canonical resource descriptor such as C:\Windows\system32.

FileSystemTree

Figure 2. The file system is a tree structure of folders containing other folders.

This hierarchical structure can be represented and visualized in different ways, though the underlying relationships are the same.  The screenshot below (figure 3) is of Windows Explorer on my development computer.  The control is the common TreeView, which supplies a way in this case for users to explore and interact with the tree data structure of the file system.

FileSystemTreeView

Figure 3. A tree view control in Windows Explorer provides access to a hierarchy of nested folders.

Another example is the organization of controls in a form (for Windows Forms) or in a window (for WPF).  The next diagram (figure 4) depicts the relationship of controls containing child controls, which may in turn contain their own children, and so on.

AppWindowTree2

Figure 4. A user interface is composed of a tree of controls that contain other controls.

This is also manifested through a user interface with the Document Outline window in Visual Studio, which is very useful for selecting deeply nested controls, or container controls that are otherwise difficult to select in the forms designer itself.  This is shown in figure 5, where you can clearly see the different levels of all controls.

DocumentOutline

Figure 5. The document outline window in Visual Studio for a Windows Forms screen.

Defining the Basic Components

There is a lot of formal terminology in graph theory to contend with, but for our purposes, we only really need to be concerned with a few basic terms.

  • Tree – This refers to a collection of nodes connected by parent-child relationships in a hierarchical structure.
  • Parent – A node one level up from the current node.
  • Child – A node one level down from the current node.
  • Node – One item in a tree with an optional parent and zero or more children.
  • Root Node – A special node with no parent.  A tree can have only one root node.
  • Subtree – A section of a larger tree including the non-root node of a larger tree, plus all of its children.

That’s not so bad, is it?  In designing a reusable tree data structure, it’s important to establish a consistent and sensible pattern for semantics.  In fact, coming up with good names for the components of our data structure may be the most difficult part.  With poor identifiers, even simple structures can be confusing to those using it.

Begin with the End in Mind

I began with a quasi-test-driven development approach.  I asked myself how I’d like the end result to look when consuming the new data structure.  I knew from the start that a tree data structure that didn’t use generics wasn’t going to be very useful.  Imagine this code:

Tree ObjectTree;

What is the type of each node in the tree?  If I’m going to use this in different scenarios, the only answer is to make it an object, so that I could store whatever I liked in my tree, but this would require a lot of casting and a lack of type checking at compile type.  So instead, using generics, I could define something like this:

Tree <string> StringTree;

This is much better, and leads to two more steps that we’ll need to take conceptually.  The first one is that I will definitely want a tree of nodes for custom types in my software’s problem domain, perhaps Customer or MobileDevice objects.  Like strings, these objects are (for our purposes here) simply dumb containers of data in the sense that they are unaware of the tree structure in which they reside.  If we take this one level further, and consider custom types that are aware of their place within the tree (and can therefore particpate in much richer ways to compose hierarchical algorithms), we’ll need to consider how to make that awareness happen.  I will explain this in more detail later in this article.

public class Tree : TreeNode

{

    public Tree() { }

    public Tree(T RootValue)

    {

        Value = RootValue;

    }

}

This definition of Tree is really a matter of semantics and syntax preference.  I’m creating an alias for the TreeNode type, claiming that a Tree is a node itself—the root node in a Tree, by convention.  I call this a synonym type.  Here’s a very simple example of its use:

Tree<string> root = new Tree<string>();

root.Value = “zero”;

int d0 = zero.Depth;

TreeNode<string> one = zero.Children.Add(“one”);

int d1 = one.Depth;

TreeNode<string> twoa = one.Children.Add(“two-a”);

TreeNode<string> twob = one.Children.Add(“two-b”);

TreeNode<string> twoc = one.Children.Add(“two-c”);

string twocstr = twoc.Value;

int

d2 = two.Depth;

You can tell a few things by looking at this code:

  • The root node is defined as a Tree, but is manipulated like the other TreeNodes because it inherits from TreeNode.
  • Each node’s value is stored in a property called Value, which has a type of T (using generics).
  • A Depth property indicates how deeply in the tree the node is nested (the root has a depth of 0).
  • The Add method in the Children TreeNode collection returns a TreeNode object, making it easier to create a new node and get a handle to it in the same statement.

Connecting Nodes to Their Parents & Children

The intelligence needed to make a Tree work resides in two classes: TreeNode and TreeNodeList.  I could have used a standard collection type for TreeNodeList, but each TreeNode links to both Parent and Children nodes, which are two fundamentally different relationships; and I wanted parent and child nodes to connect and disconnect automatically behind-the-scenes—if you add a child to X, that child’s Parent property should automatically be set to X, and vice versa.  That requires hooking into the Add method in a custom collection class to manage those relationships.  TreeNodeList therefore looks like this:

public class TreeNodeList : List<TreeNode>

{

    public TreeNode Parent;

    public TreeNodeList(TreeNode Parent)

    {

        this.Parent = Parent;

    }

    public new TreeNode Add(TreeNode Node)

    {

        base.Add(Node);

        Node.Parent = Parent;

        return Node;

    }

    public TreeNode Add(T Value)

    {

        return Add(new TreeNode(Value));

    }

    public override string ToString()

    {

        return “Count=” + Count.ToString();

    }

}

The ToString override is very important for making your debugging sessions more manageable.  Without this kind of assistance, especially when troubleshooting recursive, hierarchical algorithms, you may go crazy digging through the debugger’s own tree view control to find what you’re looking for.

The Tree Node

The TreeNode itself gets a little tricky.  If you update the Parent property because a node is going to be moved to another part of the tree, for example, you want to make sure that it gets removed from the Parent’s list of Children, and you also want to add it as a child to the new Parent.  If the Parent was null, or is being set to null, then only one of those operations (remove or add) is necessary.

Here are the primary structural and payload-containing portions of this early version of the TreeNode class:

public class TreeNode : IDisposable

{

    private TreeNode _Parent;

    public TreeNode Parent

    {

        get { return _Parent; }

        set

        {

            if (value == _Parent)

            {

                return;

            }

            if (_Parent != null)

            {

                _Parent.Children.Remove(this);

            }

            if (value != null && !value.Children.Contains(this))

            {

                value.Children.Add(this);

            }

            _Parent = value;

        }

    }

    public TreeNode Root

    {

        get

        {

            //return (Parent == null) ? this : Parent.Root;

            TreeNode node = this;

            while (node.Parent != null)

            {

                node = node.Parent;

            }

            return node;

        }

    }

    private TreeNodeList _Children;

    public TreeNodeList Children

    {

        get { return _Children; }

        private set { _Children = value; }

    }

    private T _Value;

    public T Value

    {

        get { return _Value; }

        set

        {

            _Value = value;

            if (_Value != null && _Value is ITreeNodeAware)

            {

                (_Value as ITreeNodeAware).Node = this;

            }

        }

    }

}

There are two ways we could find the Root node.  The commented line shows a succinct way to walk the tree (recursively) toward successive parents until Parent is null.  The actual implementation being used shows another way, using a simple while loop.  I prefer this because in the event of debugging, it’s easy to step through a loop, and a little more difficult to jump through the same property on multiple, perhaps many, different instances of TreeNode.  I follow the same pattern for the Depth property (below).

A tree structure isn’t very useful, however, unless it can carry some kind of payload.  You want to build a tree of something, and it’s handy that we can use generics to tell the compiler that we want a Tree of strings (Tree), for example.  That’s what the Value property is for, and why its type is the generic type parameter T.

To instantiate and initialize TreeNodes, you’ll need some constructors.  Here are two of them I defined:

public TreeNode(T Value)

{

    this.Value = Value;

    Parent = null;

    Children = new TreeNodeList(this);

}

 

public TreeNode(T Value, TreeNode Parent)

{

    this.Value = Value;

    this.Parent = Parent;

    Children = new TreeNodeList(this);

}

The Tree Node Payload’s Awareness of its Place in the Tree

You probably noticed in the last section that the Value object is checked to see if it implements the ITreeNodeAware interface.  This is an optional extensibility mechanism for custom classes that need to be aware of the tree so that payload objects can read or manipulate it in some way.  In developing a data binding framework for Windows Forms that allows you to bind control properties to paths (“PurchaseOrder.Customer.Name”) instead of specific objects (PurchaseOrder.Customer, “Name”), as ASP.NET and WPF data binding works, I needed this ability and came to the conclusion that this would be a useful feature in general.  Later in the article, I will magically transform the TreeNode and TreeNodeList classes in such a way that both this interface and the Value property become unnecessary.

Until then, here’s how the interface looks with an example class that uses it.

public interface ITreeNodeAware

{

    TreeNode Node { get; set; }

}

public class Task : ITreeNodeAware<Task>

{

    public bool Complete = false;

    private TreeNode<Task> _Node;

    public TreeNode<Task> Node

    {

        get { return _Node; }

        set

        {

            _Node = value;

            // do something when the Node changes

            // if non-null, maybe we can do some setup

        }

    }

    // recursive

    public void MarkComplete()

    {

        // mark all children, and their children, etc., complete

        foreach (TreeNode<Task> ChildTreeNode in Node.Children)

        {

            ChildTreeNode.Value.MarkComplete();

        }

        // now that all decendents are complete, mark this task complete

        Complete = true;

    }

}

Using the ITreeNodeAware interface means we have another step to make in our implementation, and adds some complexity to its use in terms of discoverability and implementation of the interface by consumers of the Tree structure in creating custom payload classes.  By doing this, however, our Task objects will get injected with a Node property value when added to a Tree of Tasks.  So the payload object will point to the node via the Node property, and the Node will point to payload object via its Value property.  This is a lot of logic for such a simple relationship, but as we’ll see later, there is an elegant way around all of this.

Including Structure Helper Members

There are some common measurements of aspects of the tree’s nodes, as well as operations that you will typically want to perform on a tree or subtree, such as initialization, systematic traversal, pruning and grafting, disposal, and determination of depth, some of which I will discuss here.

Here is a property to determine your current nesting depth, which can be useful while debugging:

public int Depth

{

    get

    {

        //return (Parent == null ? -1 : Parent.Depth) + 1;

        int depth = 0;

        TreeNode node = this;

        while (node.Parent != null)

        {

            node = node.Parent;

            depth++;

        }

        return depth;

    }

}

Because the payload objects (referenced by the Value property) may require disposing, the tree nodes (and therefore the tree as a whole) is IDisposable.  Different trees of objects may require being disposed in different orders, so I’ve created a TreeTraversalType, a DisposeTraversal property of this type to specify the order, and have implemented the Dispose method that takes this into consideration.

public enum TreeTraversalType

{

    TopDown,

    BottomUp

}

private TreeTraversalType _DisposeTraversal = TreeTraversalType.BottomUp;

public TreeTraversalType DisposeTraversal

{

    get { return _DisposeTraversal; }

    set { _DisposeTraversal = value; }

}

Here is one way to implement IDisposable that includes a property indicating whether a node has been disposed, invokes a Disposing event, and traverses the tree according to the value of DisposeTraversal.

private bool _IsDisposed;

public bool IsDisposed

{

    get { return _IsDisposed; }

}

public void Dispose()

{

    CheckDisposed();

    OnDisposing();

    // clean up contained objects (in Value property)

    if (Value is IDisposable)

    {

        if (DisposeTraversal == TreeTraversalType.BottomUp)

        {

            foreach (TreeNode node in Children)

            {

                node.Dispose();

            }

        }

        (Value as IDisposable).Dispose();

        if (DisposeTraversal == TreeTraversalType.TopDown)

        {

            foreach (TreeNode node in Children)

            {

                node.Dispose();

            }

        }

    }

    _IsDisposed = true;

}

public event EventHandler Disposing;

protected void OnDisposing()

{

    if (Disposing != null)

    {

        Disposing(this, EventArgs.Empty);

    }

}

public void CheckDisposed()

{

    if (IsDisposed)

    {

        throw new ObjectDisposedException(GetType().Name);

    }

}

I overrode ToString in the TreeNodeList class above to display the count of children.  I do the same thing for TreeNode, which as I mentioned earlier aids a great deal in debugging.

public override string ToString()

{

    string Description = string.Empty;

    if (Value != null)

    {

        Description = “[“ + Value.ToString() + “] “;

    }

    return Description + “Depth=” + Depth.ToString() + “, Children=”

      + Children.Count.ToString();

}

Notice how the Value property, if it’s set, gets included in the ToString value.  If you’re looking at a TreeNode in the watch window, you’ll appreciate that your Value object can be represented without having to drill into anything.  You can see at a glance what the payload is, how deep it is in the tree, and how many child nodes it has.

The Role of Generics in Representing Payloads

I have already supplied enough logic and sample code for a fully functioning tree data structure for use in the .NET Framework, which incidentally was developed in a Compact Framework project and will therefore work in any .NET environment.  That being said, there are some syntactical inconveniences with the approach mentioned so far.  Consider the Tree example above in a scenario where we want to access a parent node’s payload from a current node:

TreeNode<Task> CurrentTaskNode = /* get current task node */;

bool IsComplete = CurrentTaskNode.Parent.Value.Complete;

Note that Parent doesn’t return our object of type T, but instead gives us a TreeNode; and our CurrentTaskNode object is also a node object and not a task object.  When we think about trees in theory, especially visually in the form of diagrams, the parent of a node is another node, meaning that parent and child are the same type of thing.  In our simple implementation so far, however, the parent of a task is not another task, but rather a task-tree-node, which is not the same thing.

If we start from a Task object instead of a TreeNode, the syntax is worse:

Task CurrentTask = /* get current task */;

bool IsComplete = CurrentTask.Node.Parent.Value.Complete;

Notice how each time we access Node or Value, we’re weaving in and out between types.  So we must manipulate this data structure and its payload all the while with explicit deference to the type disparity and dualism, and a careful naming of variables is important to avoid confusion between types (CurrentTaskNode vs. CurrentTask).  When I first had this realization, it occurred to me why a Tree data type may have been missing from the original .NET Framework.  I doubt very much that all the brilliant developers working on the base class libraries didn’t think to include such a useful structure, but perhaps the obvious implementations that came to mind seemed confusing and problematic for real-world use.

Fortunately, we now have capabilities in the CLR as of 2.0—and corresponding language features—that enable us to solve this problem elegantly.  I’m referring to generics, and more specifically, to generic constraints.

The simplifying idea is that by creating a payload class that inherits from TreeNode, and applying a simple generic constraint to get around some casting problems that would normally prevent us from compiling, we can make our final syntax look like this:

Task MakeDinner = new Task();

Task PrepareIngredients = MakeDinner.Children.Add(new Task());

Task CookMeal = MakeDinner.Children.Add(new Task());

Task PreheatOven = CookMeal.Children.Add(new Task());

Task BakeAt350 = CookMeal.Children.Add(new Task());

Task Cleanup = MakeDinner.Children.Add(new Task());

bool IsAllDone = BakeAt350.Parent.Parent.Complete;

Notice that in the final statement, we don’t have to navigate from BakeAt350 to some different type object through a Node property, and that we can go directly from Parent to the Complete property.  This is because our Task class is defined like this now:

public class Task : TreeNode<Task>

{

    public bool Complete = false;

 

    // recursive

    public void MarkComplete()

    {

        // mark all children, and their children, etc., complete

        foreach (Task Child in Children)

        {

            Child.MarkComplete();

        }

 

        // now that all decendents are complete, mark this task complete

        Complete = true;

    }

}

It’s been compressed!  The Node property is no longer necessary (since the task is-a node, instead of being contained-by a node), and therefore the ITreeNodeAware interface can also be dispensed with.  The MarkComplete method is different, too: we simply write Child.MarkComplete instead of Child.Value.MarkComplete, and we can loop through a collection of Task objects with the Children property directly, instead of going through a set of TreeNode objects in some external Node object.

In our consuming code above, we didn’t even have to mention the Tree or TreeNode type, but if we did declare a variable that way (for the sake of clarity), it would simply be a synonym of Task.  It would look like this:

Tree<Task> MakeDinner = new Tree<Task>();

We could use TreeNode as well; it makes no difference.  Task = Tree = TreeNode.

To make all of this magic happen, we need to define TreeNode with a generics constraint.

public class TreeNode : IDisposable where T : TreeNode

This tells the compiler that T must inherit from TreeNode, and therefore variables of type T are safe to manipulate as tree nodes.  TreeNodeList requires the same constraint:

public class TreeNodeList : List<TreeNode> where T : TreeNode

This breaks us out of a restrictive pattern where normally a custom collection class is unable to richly manipulate the objects within it (unless the collection is instantiated directly from consumer code, which is not the case in this pattern).  But because the collection class knows that all of its items will derive from TreeNode, it can manipulate them as tree nodes with no problem.

There is a price to pay for this convenience, however, which is that the tree is restricted to types that inherit from TreeNode.  This means that a Tree is no longer possible.  You will have to decide how you will likely use trees in your development to determine whether to design something like this into it.  If you want this cleaner syntax but still need trees of primitive and other non-TreeNode-derived types, you can create a distinct SimpleTree for this purpose.  It may even be possible for Tree to inherit from SimpleTree, hiding the Value property (with a private shadow method shown below) and adding the generic constraint.

Cleaning Up

Now that the basic functionality is in place, I decided to split the Tree class into two.  SimpleTree represents a simple tree data structure that can contain as its Value any object; and ComplexTree, which uses the generic constraint described above and supports more complex hierarchical algorithms and tree-aware nodes.  I really like the simplicity of the Tree name, but along with the need to support both simple and complex scenarios, there are two more reasons for this name-change decision.

First, in the System.Windows.Forms namespace, there is already a TreeNode class that corresponds to the TreeView control.  If I had designed that control, I probably would have named it VisualTree and its node VisualTreeNode to distinguish it from a logical node, but as it is, dealing with two different TreeNode classes, even in different namespaces, could be confusing and messy.  Second, the new Task Parallel Library (TPL) contains an implementation of a binary tree called Tree, which is a rather short-sighted name considering that all useful trees are not binary trees, as I’ve demonstrated in this article; BinaryTree would have been a much more appropriate name.  Hopefully by the time TPL is released, this identifier will be updated to reflect this.

Conclusion

Elegant implementations of tree data structures in .NET Framework, though problematic in the past, are finally possible with the introduction of generics and generic constraints.  With some careful syntax planning for consuming code, as well as experimentation with different language constructs, I hope I have shed some light on how these kinds of problems can be approached and solved.

In future articles, I will be exploring some techniques and specific uses for hierarchical algorithms.  Some of the very problems that appear too difficult to solve without a background in mathmatics can be much more easily understood and mastered by using tree data structures and associated visualization techniques.

[This is the first article in a series of intelligent data structures, which is continued here with KeyedList.]

Posted in Algorithms, Data Structures, Object Oriented Design, Problem Modeling, Software Architecture | 119 Comments »

Compact Framework Controls (Part 1): Creating Custom Controls and Designers

Posted by Dan Vanderboom on March 14, 2008

I’ve been having a lot of fun learning how to create rich design-time experiences for custom controls in Compact Framework for the past few days.  It’s been frustrating, and the documentation is hard to find unless you’re already familiar with the metaphors and know the buzzwords.  While this first article won’t be completely comprehensive, I will continue to write about this topic until I have covered all of the bases necessary for you to create professional, polished controls and design-time experiences suitable for commercial use or sale.

I’m going to assume you have at least some experience in creating custom controls, at least for desktop applications.  Creating custom controls for Compact Framework applications is another story, however.  Not because of any particular constraints of memory of screen real estate, but because the typical method for attaching metadata to specify design-time behavior is different.  There are some other subtleties and oddness as well that are specific to the Compact Framework.

In the full .NET Framework, we have many attributes at our disposal to specify design-time behavior; most of these can be found in System.ComponentModel.  We have access to a lot of these for mobile device applications, but because they’re not included in the Compact Framework, we need another way to associate them with our control classes and their members.  This is done through something called the “design-time attributes file”, which has an extension of .xtma.

There are two ways to add this file.  The method that people typically suggest is to add a class diagram to your project (right-click on your project in Solution Explorer, and select View Class Diagram), select an item in the diagram, edit the Custom Attributes property in the property grid (see screenshot below), click on the ellipsis (…) to open a pop-up window, and then enter an attribute such as DesktopCompatible(true).

Custom Attributes in properties

When you click the OK button, a new file will be added to your project called DesignTimeAttributes.xtma, and this file will open in Visual Studio.

This is quite a round-about way to create the file in my opinion, and it presumes that you know a valid attribute to add right from the beginning.  I personally don’t use the class diagrams, and I think it’s easier just to add the .xtma file directly, by right-clicking on your project in Solution Explorer, Add—New Item, and selecting Design-Time Attribute File.  Editing your attributes directly in this XML file instead of the pop-up window in the class designer has the benefit of providing you with some Intellisense (which it gets from the associated XSD file).

I get a little disappointed when I see people list only the most common attributes that I already know about, and then fail to mention the rest of the attributes that are supported in Compact Framework, and since the list isn’t unmanagable—and easily determined from Intellisense—I will list most of them that are supported .xtma file here, and in a future artile will provide the remaining ones.

Here’s a screenshot showing the full list of tags that you can use at the class level.  Most of them are attributes, while some of them like Event, Method, and Property allow you to specify specific members of the class so that you can apply attributes to just those members.

 Xtma attributes

This is what they mean:

  • ApplyDeviceDefaults – I couldn’t find any mention of this in the normal area of MSDN that enumerates all of the classes, but I did find it explained well in this MSDN article.
  • ComplexBindingProperties – For complex data binding, of course.
  • DefaultBindingProperty – This is for simple data binding.
  • DefaultEvent – The default event for Button is Click.  When you double-click on a control in the designer, Visual Studio switches to the code behind file and will automatically generate this event’s handler for you.  Very handy.
  • DefaultProperty – When you select a control in the designer, this is the property in the properties window that gets focus first.  For the Label control, this is the Caption property.
  • Description – The description text appears in the properties window below the grid of property names and values, and can provide useful information about the meaning of a property or event.
  • Designer – The Designer attribute is one of the primary gateways for providing rich design-time experiences for your controls.  Creating custom designers and associating your controls with them is a tricky business, and one I intend to explore in depth in this and future articles.  Because MSDN documentation in this area is rather sparse, I’ve begun contributing to the community content on the MSDN pages, and you’ll see the help I’ve added at the very bottom of the page if you follow the link for this item.
  • DesignerSerializer – Located in System.ComponentModel.Design.Serialization, a DesignerSerializer is used to provide a custom way of serializing your control to code in the designer partial class file.  I haven’t had a need yet to use this, but if someone can think of a real-world scenario that requires it, I will be happy to explore the subject further and write about it.
  • DesignTimeVisible – Indicates whether a control can be shown on a designer, and is supposedly ignored by “components with a UI presense”, whatever that means.  A little more usefully, MSDN states that it is useful when you have a control that accepts child components, such as the TreeView whose node items “should not appear in the component tray because they are drawn by the TreeView control”.  This will require some more exploration.
  • DesktopCompatible – This is the first design-time attribute I became familiar with in working with Compact Framework controls.  If you have a control that makes P/Invoke calls, Visual Studio is uncertain whether they’re device specific OS calls, and to be safe, it doesn’t execute your control’s code, which means your control can’t render itself even on the designer surface.  You get a message telling you that it’s unsafe.  To get around this, and presuming that it is indeed safe to run your control’s code on the desktop (I’ll explain more about this later, or you can read this article by XinYan), just add a DesktopCompatible attribute to the control class, and you’ll be back in business.  I’m not sure where this attribute is located; it’s not a desktop attribute, so it’s not in the full .NET Framework’s System.dll, and a search through Reflector didn’t locate it, so I’ll have to keep looking.  But it’s there, and it works.
  • Docking – Specifies the default docking behavior for controls.  This is located in System.Windows.Forms.
  • Editor – If you need a more powerful experience for editing complex properties within the properties window itself, this attribute will allow you to hook into one.  I’ll be covering over custom editors in detail.
  • ImmutableObject – Specifies that an object has no subproperties capable of being edited, per MSDN documentation.  Not sure what the benefits of that would be: perhaps to hide all properties for a class without having to hide each one separately?
  • InitializationEvent – This is used to support auto data-binding (by Visual Studio wizards I’m guessing), so it knows which event to hook into when generating the data-binding code.
  • LookupBindingProperties
  • RootDesignerSerializer – I’m not sure what this was for originally, but according to bug report, this attribute is both deprecated and broken.
  • Supported – Explained in this blog as part of Platform Verification Task.  Located in Microsoft.CompactFramework.Build.Tasks.  You can use this attribute to indicate that a class or member is not supported for the specific platform.
  • SuppressFiltering – Located in Microsoft.CompactFramework.Build.Tasks.
  • ToolboxBitmap – This simply specifies the bitmap that will be displayed in the toolbox.  Located in System.Drawing.
  • TypeConverter – Specifies the TypeConverter class used for a property.  TypeConverters are an important aspect of the design-time experience and merit further explanation.
  • Browsable – This determines whether a property or event will be displayed in the properties window, and is typically used to hide properties or events that must be public for some reason but aren’t meant to be manipulated during design time.
  • Category – If you set this to an existing category name, your property or event will appear in there; if you create your own category name, a new category will appear in the properties window.

There are a few more that are specific to properties, events, and methods, but this will give us a good start.  I’ll cover the remainder in future articles.

That seems like a lot at first glance, but chances are that you’ll only need a handful at any given time.  With a little exploration and practice (and guidance from myself and others whose blogs and other resources I’ll share), you could soon be a master of rich, no-compromise custom control development for Compact Framework applications.  I believe this is a worthy cause, for one because there is a scarcity of good third-party controls, especially when compared to the abundance that we have for the desktop world of .NET development; but also because I have personally struggled with Compact Framework development and have always thought it would be nice to have a step-by-step series of tutorial to follow for creating custom controls.  I’ve found many useful and helpful articles, but nothing that really brings it all together in a clear manner.

Here is an example .xtma file for a new user control I created that has Category and Description attributes on a property I created called HighlightForeColor:

XTMA

The magic happens when you build your custom control project.  Visual Studio builds not only your control project in its runtime form, but also generates another assembly with .asmmeta.dll after your own target assembly name.

Build output

If you use Reflector to disassemble it, you will see that this is a design-time component that contains all of your classes and their members with real attributes attached.  Strangely, it does not contain any code, and parameters have no names.  The purpose is simply to be a carrier of attributes.  This is a screen shot from Reflector, showing the attached attributes:

Reflector

I’m puzzled by this implementation detail.  Attributes are so insignificant in size, being just metadata tags.  If Microsoft had just included them in the Compact Framework, it seems they could have avoided the requirement for this second, oddly-empty assembly (and there is a third, for custom designers and editors, as you’ll see later).  Unless there’s something else to it that I’m missing…

[This article is part of a series that continues in this article.]

Posted in Compact Framework, Custom Controls, User Interface Design, Visual Studio, Windows Forms, Windows Mobile | 10 Comments »

Listing Storage Card Paths in Compact Framework

Posted by Dan Vanderboom on March 10, 2008

Getting a list of storage card paths on a Windows CE or Windows Mobile device from Compact Framework is a lot more complicated than it should be.  After finding references to FindFirstFlashCard and FindNextFlashCard, which require interop calls, I found this helpful MSDN article which talks about a way of obtaining storage card folder names without using interop. 

However, there are a few problems with it.  First, attrStorageCard is not defined.  If you’re interested in that technique, use this:

FileAttributes attrStorageCard = FileAttributes.Directory | FileAttributes.Temporary;

Second, with the device that I’m working on (made by DAP), that method returned not only the storage card, but also a DiskOnChip folder (fair enough), and a folder called Network, which I can only guess is some kind network-mapped directory.  I didn’t want to include this Network folder and then have to create some kind of exclusion rule for it, so I decided to take the interop route and try FindFirstFlashCard using code from this website.

I didn’t have any luck there either, unfortunately, because the DAP device I’m working with doesn’t have the required note_prj.dll file.  Foo.

Eventually I stumbled across a registry setting at HKEY_LOCAL_MACHINE\System\StorageManager\Profiles\MMC\Folder, which is set to “Storage Card” for my device.  I really dislike using the registry for this, and I’m hoping it will work for other manufacturer’s devices.  Because it’s a Microsoft area of the registry, I’m fairly confident this will be the case.  I was informed that the DAP device I’m developing for likes to randomly change its storage card path to “Storage Card2”, so I’ll have to check that this registry setting is updated when that happens.

I’m going to say a little prayer to the Compact Framework dieties to add some better managed support for accessing common device functionality like storage cards.  CF really is a great platform, but the learning curve is still pretty painful after all this time.

I wonder how Google’s Android API exposes things like this…

Posted in Compact Framework, Windows Mobile | 3 Comments »

Windows Forms Data Binding: Language-Level Support Needed

Posted by Dan Vanderboom on March 6, 2008

I’ve been busy building an MVC framework for the past few weeks, and one of the aspects of this framework I want to make as transparent as possible is data binding.  I want to use automatic data binding between a control property in the view and a property in the controller.  This is much more difficult than it needs to be.  Because my controller inherits from a base class, it has access to a helper method to raise the PropertyChanged event in the INotifyPropertyChanged interface, which makes things a tad easier.

LastNameProperty

Here is what that helper method looks like:

SetProperty

Even with a code snippet to generate the property (with the call to SetProperty), I don’t like it.  For one or two properties, it’s not too bad, but when you have dozens of properties that need to notify another object of changes—multiplied by dozens of controllers and views, it creates code bloat.  The string “LastName”, lacking strong typing, is also less than perfect.

What I really want is to combine automatic properties (a new feature in C# 3.0) with a new language keyword like “notify” that would hook the SetProperty logic into the setter.  Like this:

public notify string LastName { get; set; }

The same keyword for collection types, producing slightly different notification effects, would be nice as well, so I wouldn’t have to use BindingList<T> specifically.

public notify List<Customer> Customers { get; set; }

But alas, I’ll have to do it the hard way.  I’ve been considering using an aspect weaver to stitch in this logic in a post-build task.  It would work, but the notifications wouldn’t be fired during debugging, and that’s just not acceptable.

Data binding is extremely important, and WPF has—from what I’ve seen so far—done a great job implementing it.  For those of us stuck in Windows Forms (I develop applications for Windows Mobile devices primarily), some other alternatives are long overdue.

I’ve been able to mimic a small part of the capabilities of WPF data binding, specifically support for binding paths such as “Controller.Computer.ProcessorName”.  In Windows Forms data binding, if you change which object Controller.Computer points to, your user interface control will continue to reference the old Computer object’s ProcessorName property.  Not so good!  Using data binding paths, if you point Controller.Computer to a new Computer object, the UI control does an automatic rebinding to the new object’s ProcessorName property.  I then set the control’s Tag property to tell it the name of the control property and the name of the property to bind it to, like this: “Text=Controller.Customer.LastName”.  There have been a number of road blocks to making it work smoothly (such as dealing with null values, and null parent objects), but it does in fact work, is smooth and fast, and supports complex as well as simple data binding.

In a future blog post, I’ll describe the general design and hopefully also share some code.

Posted in Compact Framework, Data Binding, Invention-A-Day, Object Oriented Design, User Interface Design, Windows Forms | Leave a Comment »