The blog of dlaa.me

Last week I posted the code for VirtualFileDataObject, an easy-to-use implementation of virtual files for .NET and WPF. This code implements the standard IDataObject COM interface for drag-and-drop and clipboard operations and is specifically targeted at scenarios where an application wants to allow the user to drag an element to a folder and create a file (or files) dynamically on the drop/paste. The standard .NET APIs for drag-and-drop don't support this scenario, so VirtualFileDataObject ended up being a custom implementation of the System.Runtime.InteropServices.ComTypes.IDataObject interface. Fortunately, the specifics aren't too difficult, and a series of posts by Raymond Chen paved the way (in native code).

 

If you read my previous post, you may recall there was an issue with the last scenario of the sample: the application became unresponsive while data for the virtual file was downloading from the web. While this unresponsiveness won't be a noticeable for scenarios involving local data, scenarios that create large files or hit the network are at risk. Well, it's time to find a solution!

And we don't have to look far: the answer is found in the MSDN documentation for Transferring Shell Objects with Drag-and-Drop and the Clipboard under the heading Using IAsyncOperation. As you might expect, we're not the first to notice this behavior; the IAsyncOperation interface exists to solve this very problem. So it seems like things ought to be easy - let's just define the interface, implement its five methods (none of which are very complicated), and watch as the sample application stays responsive during the time-consuming download...

FAIL.

 

Okay, so that didn't work out quite how we wanted it to. Maybe we defined the interface incorrectly? Maybe we implemented it incorrectly? Or maybe Windows just doesn't support this scenario??

No, no, and no. We've done everything right - it's the platform that has betrayed us. :( Specifically, the DragDrop.DoDragDrop method does something sneaky under the covers: it wraps our respectable System.Runtime.InteropServices.ComTypes.IDataObject instance in a System.Windows.DataObject wrapper. Because this wrapper object doesn't implement or forward IAsyncOperation, it's as if the interface doesn't exist!

Aside: I have the fortune of working with some of the people who wrote this code in the first place, and I asked why this extra level of indirection was necessary. The answer is that it probably isn't - or at least nobody remembers why it's there or why it couldn't be removed now. So the good news is they'll be looking at changing this behavior in a future release of WPF. The bad news is that the change probably won't happen in time for the upcoming WPF 4 release.

Be that as it may, it looks like we're going to need to call the COM DoDragDrop function directly. Fortunately, there's not much that happens between WPF's DragDrop.DoDragDrop and COM's DoDragDrop, so there's not much we have to duplicate. That said, we do need to define the IDropSource interface and write a custom DropSource implementation of its two methods. The nice thing is that both methods are pretty simple and straightforward, so our custom implementation can be private. (And for simplicity's sake, we're not going to bother raising DragDrop's (Preview)GiveFeedbackEvent or (Preview)QueryContinueDragEvent events.)

Because we've been careful to define the VirtualFileDataObject.DoDragDrop replacement method with the same signature as the DoDragDrop method it's replacing, updating the sample to use it is trivial. So run the sample again, and - BAM - no more unresponsive window during the transfer! (For real, this time.) You can switch to the window, resize it, drag it, etc. all during the creation of the virtual file.

 

But now we've got a bit of a dilemma: if things are happening asynchronously, how can we tell when they're done? The answer lies with the StartOperation and EndOperation methods of the IAsyncOperation interface. Per the interface contact, these methods are called at the beginning/end of the asynchronous operation. So if we just add another constructor to the VirtualFileDataObject class, we can wire things up in the obvious manner:

 /// <summary>
 /// Initializes a new instance of the VirtualFileDataObject class.
 /// </summary>
 /// <param name="startAction">Optional action to run at the start of the data transfer.</param>
 /// <param name="endAction">Optional action to run at the end of the data transfer.</param>
 public VirtualFileDataObject(Action startAction, Action endAction)

Well, almost... The catch is that while VirtualFileDataObject now supports asynchronous mode, there's no guarantee that the drop target will use it. Additionally, the developer may have specifically set the VirtualFileDataObject.IsAsynchronous property to false to disable asynchronous mode. And when you're in synchronous mode, there aren't any handy begin/end notifications to rely on...

So I've added support to VirtualFileDataObject for calling the begin/end actions in synchronous mode based on some semi-educated guesses. In my testing, the notifications during synchronous mode behave as identically as possible to those in asynchronous mode. Granted, in some scenarios startAction may run a little earlier in synchronous mode than it would have for asynchronous mode - but as far as the typical developer is concerned, VirtualFileDataObject offers the same handy behavior for both modes!

 

Let's celebrate by updating the sample to show a simple busy indicator during the download:

Code-wise, once we've updated the call to DoDragDrop:

VirtualFileDataObject.DoDragDrop(dragSource, virtualFileDataObject, DragDropEffects.Copy);

Everything else stays the same except for the constructor:

var virtualFileDataObject = new VirtualFileDataObject(
    // BeginInvoke ensures UI operations happen on the right thread
    () => Dispatcher.BeginInvoke((Action)(() => BusyScreen.Visibility = Visibility.Visible)),
    () => Dispatcher.BeginInvoke((Action)(() => BusyScreen.Visibility = Visibility.Collapsed)));

The BusyScreen variable above corresponds to a new element in the sample application that provides the simple "Busy..." UI shown above. In real life, we'd probably use MVVM and a bool IsBusy property on our data model to trigger this, but for a sample application, toggling Visibility works fine. Because all the hard work is done by the VirtualFileDataObject class [you're welcome! :) ], the application remains unencumbered by complex logic for anything related to the management of virtual files.

Which is the way it should be!

 

[Click here to download the complete code for VirtualFileDataObject and the sample application.]

 

PS - I have one more post planned on this topic demonstrating something I haven't touched on yet to help applications coordinate better with the shell. Stay tuned...

Have you ever used one of those programs that lets you drag a UI widget, drop it in a folder, and - poof - a file that didn't exist magically appears? Me, too - it's cool! But how does it work? Are they really deferring the work of creating that file until it's needed and then creating the file during the drag-and-drop operation? Yes they are - and now you can, too!

If I have seen a little further it is by standing on the shoulders of Giants.- Sir Isaac Newton

Everything you ever needed to know about drag-and-drop in Windows can probably be found in the MSDN documentation for Transferring Shell Objects with Drag-and-Drop and the Clipboard. That documentation is a great resource for specific questions, but because it covers so many topics, it's not necessarily the best way to get an overview. For that, we turn to Raymond Chen's blog - specifically, a series he did called "What a drag" in March of last year. Raymond's example uses native code exclusively, but don't let that scare you away - his presentation and explanations are always engaging! Please take a moment to read (or at least skim) the following articles, or else the rest of this post might not make much sense:

• What a drag: Dragging text
• What a drag: Dragging a Uniform Resource Locator (URL)
• What a drag: Dragging a Uniform Resource Locator (URL) and text
• What a drag: Dragging a virtual file (HGLOBAL edition)
• What a drag: Dragging a virtual file (IStream edition)
• What a drag: Dragging a virtual file (IStorage edition)
• You can drag multiple virtual objects, you know

Okay, so we know what we want to do and now we know how it's supposed to work! The first thing to consider is whether the WPF platform supports the virtual file scenario. And unfortunately, it doesn't seem to. :( Specifically, the DataObject class is where we'd expect to find such support, but the closest it has is SetFileDropList. And while that sounds promising, it's really just a list of strings with paths to existing files. Recall that the DragDrop.DoDragDrop method is synchronous (i.e., does not return until the drag-and-drop operation is complete), and the obvious consequence is that creating a virtual file on the fly isn't practical with this API. Specifically, the bits already need to exist on disk by the time the user starts the drag operation - but you don't know what data they're going to drag until they start! It's a classic Catch-22...

The natural next step is to consider whether subclassing DataObject would help - but it's sealed, so that's a pretty quick dead end.

Move on to consider whether the System.Windows.IDataObject interface used by DataObject would be useful. But it seems not; it's pretty much the same API as DataObject which we've already dismissed.

So that leaves us looking at the System.Runtime.InteropServices.ComTypes.IDataObject interface which is a simple managed representation of the actual IDataObject COM interface that the shell uses directly. Clearly, anything is possible at this point, so if we can just channel our inner Raymond, we ought to be in business!

 

The good news is that I've already done this for you. I've even written a simple WPF application to show how everything fits together:

 

[Click here to download the complete code for VirtualFileDataObject and the sample application.]

 

What I've done is write a custom IDataObject class called VirtualFileDataObject that does all the hard work for you. All you need to do is provide the relevant data, and your users will be dragging-and-dropping virtual files in no time. And what's really neat is that writing the code to support drag-and-drop automatically gives complete support for the clipboard because the Clipboard.SetDataObject method uses the same IDataObject interface!

Let's look at the sample scenarios to understand how VirtualFileDataObject is used:

 

Text only

var virtualFileDataObject = new VirtualFileDataObject();

// Provide simple text (in the form of a NULL-terminated ANSI string)
virtualFileDataObject.SetData(
    (short)(DataFormats.GetDataFormat(DataFormats.Text).Id),
    Encoding.Default.GetBytes("This is some sample text\0"));

DoDragDropOrClipboardSetDataObject(e.ChangedButton, Text, virtualFileDataObject);

This is the simplest possible scenario - just to show off that simple things stay simple with VirtualFileDataObject. Here's the signature for the SetData method used above:

/// <summary>
/// Provides data for the specified data format (HGLOBAL).
/// </summary>
/// <param name="dataFormat">Data format.</param>
/// <param name="data">Sequence of data.</param>
public void SetData(short dataFormat, IEnumerable<byte> data)

Note that it operates in "HGLOBAL mode" where all the data is provided at the time of the call. Note also that it doesn't know anything about what the data is, so it's up to the caller to make sure it's in the right format. Specifically, the right format for DataFormats.Text is a NULL-terminated ANSI string, so that's what the sample passes in.

Aside: The DoDragDropOrClipboardSetDataObject method used above is a simple helper method for the test application - it calls DragDrop.DoDragDrop or Clipboard.SetDataObject depending on what the user did. It's not very exciting, so I won't be showing it (or the VirtualFileDataObject constructor) in the following examples.

 

Text and URL

// Provide simple text and a URL in priority order
// (both in the form of a NULL-terminated ANSI string)
virtualFileDataObject.SetData(
    (short)(DataFormats.GetDataFormat(CFSTR_INETURLA).Id),
    Encoding.Default.GetBytes("http://blogs.msdn.com/delay/\0"));
virtualFileDataObject.SetData(
    (short)(DataFormats.GetDataFormat(DataFormats.Text).Id),
    Encoding.Default.GetBytes("http://blogs.msdn.com/delay/\0"));

Another simple example based on Raymond's discussion of drag-and-drop into Internet Explorer. For our purposes, this example demonstrates that you can set multiple data formats and that formats other than those exposed by WPF's DataFormats enumeration are easy to deal with. Per the guidelines, supported formats are provided in order by priority, with higher priority formats coming first.

 

Virtual file

// Provide a virtual file (generated on demand) containing the letters 'a'-'z'
virtualFileDataObject.SetData(new VirtualFileDataObject.FileDescriptor[]
{
    new VirtualFileDataObject.FileDescriptor
    {
        Name = "Alphabet.txt",
        Length = 26,
        ChangeTimeUtc = DateTime.Now.AddDays(-1),
        StreamContents = stream =>
            {
                var contents = Enumerable.Range('a', 26).Select(i => (byte)i).ToArray();
                stream.Write(contents, 0, contents.Length);
            }
    },
});

At last, something juicy! This example creates a virtual file named Alphabet.txt that's 26 bytes long and appears to have been written exactly one day ago. The contents of this file aren't generated until they're actually required by the drop target, so there's no wasted effort if the user doesn't start the drag, aborts it, or whatever. When the file's contents are eventually needed, VirtualFileDataObject calls the user-provided Action (not necessarily a lambda expression, though I've used one here for conciseness) and passes it a write-only Stream instance for writing the data. The user code writes to this stream as much or as little as necessary, then returns control to VirtualFileDataObject in order to complete the operation.

The file that gets created when you drop/paste this item into a folder looks just like you'd expect. And because VirtualFileDataObject supports the length and change time fields, Windows has all the information it needs to help the user resolve possible conflicts:

Here's the relevant SetData method (note that you can provide an arbitrary number of FileDescriptor instances, so you can create as many virtual files as you want):

/// <summary>
/// Provides data for the specified data format (FILEGROUPDESCRIPTOR/FILEDESCRIPTOR)
/// </summary>
/// <param name="fileDescriptors">Collection of virtual files.</param>
public void SetData(IEnumerable<FileDescriptor> fileDescriptors)

It makes use of another SetData method that's handy for dealing with "ISTREAM mode":

/// <summary>
/// Provides data for the specified data format and index (ISTREAM).
/// </summary>
/// <param name="dataFormat">Data format.</param>
/// <param name="index">Index of data.</param>
/// <param name="streamData">Action generating the data.</param>
/// <remarks>
/// Uses Stream instead of IEnumerable(T) because Stream is more likely
/// to be natural for the expected scenarios.
/// </remarks>
public void SetData(short dataFormat, int index, Action<Stream> streamData)

And accepts data in the following form:

/// <summary>
/// Class representing a virtual file for use by drag/drop or the clipboard.
/// </summary>
public class FileDescriptor
{
    /// <summary>
    /// Gets or sets the name of the file.
    /// </summary>
    public string Name { get; set; }

    /// <summary>
    /// Gets or sets the (optional) length of the file.
    /// </summary>
    public UInt64? Length { get; set; }

    /// <summary>
    /// Gets or sets the (optional) change time of the file.
    /// </summary>
    public DateTime? ChangeTimeUtc { get; set; }

    /// <summary>
    /// Gets or sets an Action that returns the contents of the file.
    /// </summary>
    public Action<Stream> StreamContents { get; set; }
}

 

Text, URL, and a virtual file!

// Provide a virtual file (downloaded on demand), its URL, and descriptive text
virtualFileDataObject.SetData(new VirtualFileDataObject.FileDescriptor[]
{
    new VirtualFileDataObject.FileDescriptor
    {
        Name = "DelaysBlog.xml",
        StreamContents = stream =>
            {
                using(var webClient = new WebClient())
                {
                    var data = webClient.DownloadData("http://blogs.msdn.com/delay/rss.xml");
                    stream.Write(data, 0, data.Length);
                }
            }
    },
});
virtualFileDataObject.SetData(
    (short)(DataFormats.GetDataFormat(CFSTR_INETURLA).Id),
    Encoding.Default.GetBytes("http://blogs.msdn.com/delay/rss.xml\0"));
virtualFileDataObject.SetData(
    (short)(DataFormats.GetDataFormat(DataFormats.Text).Id),
    Encoding.Default.GetBytes("[The RSS feed for Delay's Blog]\0"));

Finally, here's a sample that pulls everything together in a nice, fancy package with a bow on top. The text is an informative snippet, the URL is a link to an RSS feed, and the virtual file is the dynamically downloaded content of that RSS feed! Way cool - it's like there's this big file sitting around that the user can drop anywhere they want - except that it only really exists on the web and it's always up to date whenever you drop it somewhere!

As you can see, the VirtualFileDataObject class makes the whole scenario really easy and approachable - even if you're not an expert on shell interoperability. It's pretty snazzy, I'd say. :)

 

There's just one small problem...

If you tried the drag-and-drop version of the last sample above on a machine with a slow network connection, you probably noticed that the sample application became unresponsive as soon as you dropped the virtual file and didn't recover until the download completed. This is a natural consequence of the DoDragDrop method being synchronous and getting called from the UI thread (like it should be). In most scenarios, you probably won't notice this problem because generating the file's data is practically instantaneous. But when there's a delay, unresponsiveness is a possibility. The good news is that there's an official technique for solving this problem. The bad news is that it doesn't work for WPF apps. The good news is that I can show you how to make it work anyway.

But that's a topic for another blog post - one that I'll write in a week or so... :)

I tend to write pretty long blog post titles.

There, I said it.

That's the first step, right? Admitting the problem? Except I don't usually think it's a problem... :) Nobody's going to type post URLs, anyway - long ones are really only an issue in one scenario: Twitter. And there are already plenty of solutions for URL shortening, so why does the world need another one?

It probably doesn't. But I wanted one anyway. In particular, I wanted something ridiculously simple to manage that I had complete control over and that didn't depend on how my web site host configured their server. I wanted to be sure I could use human-readable aliases and never need to worry about namespace collisions (a problem with existing services because all the good names have been taken). Besides, I don't see the point in relying on someone else (or some other web site) to do something I can do for myself pretty easily.

 

So as long as I'm writing my own URL shortener, I might as well give it a special power or something, right? Well, one thing that seemed pretty useful (to me and you) was an easy way to list all the supported aliases. Therefore, when you navigate to the root of the redirect namespace on my web site, that's just what you'll get:

 

Now, when I want to point to a blog or sample of mine, instead of linking to it like this:

http://blogs.msdn.com/delay/archive/2009/07/19/my-new-home-page-enhanced-updated-collection-of-great-silverlight-wpf-data-visualization-resources.aspx

I can link to it like this:

http://cesso.org/r/DVLinks

What's more, because these redirects are of the 302/Found variety, I can update where they go when new content becomes available without having to change any existing content. This is something I've wanted for my links post(s) ever since I posted the first version! Problem solved: from now on, the DVLinks alias will always take you to my most recent post of Data Visualization links.

Some of the aliases above use MixedCase and some use ALLCAPS - there's actually meaning behind that. When I create an alias I intend to be widely useful and expect to use more than once, I'll use mixed case like I did with DVLinks. But when I'm creating an alias just so I can post it to Twitter, I'll use all caps like I did for TWITTER. This way, it's easy to browse my list of aliases and pick out the particularly interesting ones.

 

Here's the complete code for the IHttpModule-based URL shortener I wrote last night. It's standard ASP.NET and doesn't use any .NET 3.5 features, so it should work fine on pretty much any ASP.NET server.

public class UrlShortener : IHttpModule
{
    /// <summary>
    /// The prefix (directory/namespace) for all redirect requests.
    /// </summary>
    private const string RedirectPrefix = "~/r/";

    /// <summary>
    /// Maintains a mapping from alias to Uri for all redirect entries.
    /// </summary>
    private IDictionary<string, Uri> _aliases =
         new SortedDictionary<string, Uri>(StringComparer.OrdinalIgnoreCase);

    /// <summary>
    /// Initializes the IHttpModule instance.
    /// </summary>
    /// <param name="context">HttpApplication instance.</param>
    public void Init(HttpApplication context)
    {
        // Populate the alias mappings
        AddAlias("ChartBuilder", "https://dlaa.me/Samples/ChartBuilder/");
        AddAlias("DVLinks",      "http://blogs.msdn.com/delay/archive/2009/07/19/my-new-home-page-enhanced-updated-collection-of-great-silverlight-wpf-data-visualization-resources.aspx");
        AddAlias("SLHash",       "https://dlaa.me/Samples/ComputeFileHashes/");
        AddAlias("TWITTER",      "http://blogs.msdn.com/delay/archive/2009/10/13/if-all-my-friends-jumped-off-a-bridge-apparently-i-would-too-just-created-a-twitter-account-davidans.aspx");

        context.BeginRequest += new EventHandler(HttpApplication_BeginRequest);
    }

    /// <summary>
    /// Adds an alias/Uri pair and validates it.
    /// </summary>
    /// <param name="alias">Alias to add.</param>
    /// <param name="uri">Uri to associate with the alias.</param>
    private void AddAlias(string alias, string uri)
    {
        // Validate the URI when adding it
        _aliases.Add(alias, new Uri(uri, UriKind.Absolute));
    }

    /// <summary>
    /// Handles the HttpApplication's BeginRequest event.
    /// </summary>
    /// <param name="source">HttpApplication source.</param>
    /// <param name="e">Event arguments.</param>
    private void HttpApplication_BeginRequest(object source, EventArgs e)
    {
        // Check if the request is a redirect attempt
        HttpApplication context = (HttpApplication)source;
        string requestPath = context.Request.AppRelativeCurrentExecutionFilePath;
        if (requestPath.StartsWith(RedirectPrefix, StringComparison.OrdinalIgnoreCase))
        {
            // Extract the alias
            string alias = requestPath.Substring(RedirectPrefix.Length);
            if (_aliases.ContainsKey(alias))
            {
                // Known alias; redirect the user there
                context.Response.Redirect(_aliases[alias].ToString());
            }
            else
            {
                // Invalid alias; write a simple list of all known aliases
                using (HtmlTextWriter writer = new HtmlTextWriter(context.Response.Output, ""))
                {
                    writer.RenderBeginTag(HtmlTextWriterTag.Html);
                    writer.RenderBeginTag(HtmlTextWriterTag.Head);
                    writer.RenderBeginTag(HtmlTextWriterTag.Title);
                    writer.Write("Supported Aliases");
                    writer.RenderEndTag();
                    writer.RenderEndTag();
                    writer.RenderBeginTag(HtmlTextWriterTag.Body);
                    foreach (string key in _aliases.Keys)
                    {
                        writer.AddAttribute(HtmlTextWriterAttribute.Href, _aliases[key].ToString());
                        writer.RenderBeginTag(HtmlTextWriterTag.A);
                        writer.Write(key);
                        writer.RenderEndTag();
                        writer.WriteBreak();
                        writer.WriteLine();
                    }
                    writer.RenderEndTag();
                    writer.RenderEndTag();
                }
                context.Response.End();
            }
        }
    }

    /// <summary>
    /// Disposes of resources.
    /// </summary>
    public void Dispose()
    {
    }
}

To enable this URL shortener for IIS 7, just save the code above to a .CS file, put that file in the App_Code directory at the root of your web site, and register it in web.config with something like the following:

<?xml version="1.0"?>
<configuration>
    <system.webServer>
        <modules>
            <add name="UrlShortener" type="UrlShortener"/>
        </modules>
    </system.webServer>
</configuration>

(For IIS 6, you'll need to change system.webServer to system.web and modules to httpModules - otherwise it's just the same.)

The default power settings for Windows are set up so a computer will go to sleep after 15 to 30 minutes of inactivity (i.e., no mouse or keyboard input). This is great because a computer that's not being used doesn't need to be running at full power. By letting an idle machine enter sleep mode, the user benefits from a significant reduction in electricity use, heat generation, component wear, etc.. And because sleep mode preserves the state of everything in memory, it's quick to enter, quick to exit, and doesn't affect the user's work-flow. All the same applications continue running, windows stay open and where they were, etc.. So sleep mode is a Good Thing and I'm a fan.

However, sometimes a computer is busy even though someone isn't actively using the mouse and keyboard; common examples include playing a movie, burning a DVD, streaming music, etc.. In these cases, you don't want the machine to go to sleep because you're using it - even though you're not actually using it! So most media players and disc burners tell Windows not to go to sleep while they're running. In fact, there's a dedicated API for exactly this purpose: the SetThreadExecutionState Win32 Function.

But what about those times when the computer is busy doing something and the relevant program doesn't suppress the default sleep behavior? For example, it might be downloading a large file, re-encoding a music collection, backing up the hard drive, or hashing the entire contents of the disk. You don't want the machine to go to sleep for now, but are otherwise happy with the default sleep behavior. Unfortunately, the easiest way I know of to temporarily suppress sleeping is to go to Control Panel, open the Power Options page, change the power plan settings, commit them - and then remember to undo everything once the task is finished. It's not hard; but it's kind of annoying...

 

So here's a better way:

Insomnia is a simple WPF application that calls the SetThreadExecutionState API to disable sleep mode for as long as it's running. (Note that the display can still power off during this time - it's just sleep for the computer that's blocked.) Closing the Insomnia window immediately restores whatever sleep mode was in effect before it was run. It couldn't be easier!

 

[Click here to download the Insomnia application along with its complete source code.]

 

Notes:

• Insomnia basically boils down to a single function call - but to a function that's a Win32 API and is not part of the .NET Framework. This is where a very powerful feature saves the day: Platform Invoke. For those who aren't familiar with it, P/Invoke (as it's called) lets a managed application call into the APIs exposed by a native DLL. All it takes is a dash of the DllImport attribute and a little bit of translation from the Win32 types to their managed counterparts. The MSDN documentation goes into lots of detail here, and I encourage interested parties to go there.
• One popular resource for P/Invoke assistance is PInvoke.net, where you can find managed definitions for hundreds of native APIs. But I usually just end up creating my own - if nothing else, it's a good learning exercise. :)
• The Insomnia window has its Topmost property set to True so it's always visible and people will be less likely to accidentally leave their computers sleep-less. Other than taking up a small bit of screen space and memory, Insomnia consumes no system resources, so it won't get in the way of whatever else is running.
• It is considered polite to leave things the way you found them, so Insomnia makes an extra call to SetThreadExecutionState when it's closed in order to restore things to how they were. However, this is really more for show than anything else, because the execution state is clearly per-thread and Insomnia's thread is about to die anyway.
• I did a quick web search for similar tools before I wrote Insomnia and there are a few out there. Most of what I found was for Linux and Mac for some reason, but I'm sure Insomnia isn't the first of its kind for Windows. However, that doesn't stop it from being a nice introduction to P/Invoke - and besides, I'm always happier running my own code! :)

 

Finally, here's the implementation:

public partial class Window1 : Window
{
    private uint m_previousExecutionState;

    public Window1()
    {
        InitializeComponent();

        // Set new state to prevent system sleep (note: still allows screen saver)
        m_previousExecutionState = NativeMethods.SetThreadExecutionState(
            NativeMethods.ES_CONTINUOUS | NativeMethods.ES_SYSTEM_REQUIRED);
        if (0 == m_previousExecutionState)
        {
            MessageBox.Show("Call to SetThreadExecutionState failed unexpectedly.",
                Title, MessageBoxButton.OK, MessageBoxImage.Error);
            // No way to recover; fail gracefully
            Close();
        }
    }

    protected override void OnClosed(System.EventArgs e)
    {
        base.OnClosed(e);

        // Restore previous state
        if (0 == NativeMethods.SetThreadExecutionState(m_previousExecutionState))
        {
            // No way to recover; already exiting
        }
    }

    private void Hyperlink_RequestNavigate(object sender, RequestNavigateEventArgs e)
    {
        // Start an instance of the NavigateUri (in a browser window)
        Process.Start(((Hyperlink)sender).NavigateUri.ToString());
    }
}

internal static class NativeMethods
{
    // Import SetThreadExecutionState Win32 API and necessary flags
    [DllImport("kernel32.dll")]
    public static extern uint SetThreadExecutionState(uint esFlags);
    public const uint ES_CONTINUOUS = 0x80000000;
    public const uint ES_SYSTEM_REQUIRED = 0x00000001;
}

As part of a personal project, I had a scenario where I expected to be doing large HTTP uploads (ex: PUT) over a slow network connection. The typical user experience here is to show a progress bar, and that's exactly what I wanted to do. So I wrote some code to start the upload and then write to the resulting NetworkStream in small chunks, updating the progress bar UI after each chunk was sent. In theory (and my test harness), this approach worked perfectly; in practice, it did not...

What I saw instead was that the progress bar would quickly go from 0% to 100% - then the application would stall for a long time before completing the upload. Which is not a good user experience, I'm afraid. I'll show what I did wrong in a bit, but first let's take a step back to look at the sample application I've written for this post.

 

The core of the sample app is a simple HttpListener that logs a message whenever it begins an operation, reads an uploaded byte, and finishes reading a request:

// Create a simple HTTP listener
using (var listener = new HttpListener())
{
    listener.Prefixes.Add(_uri);
    listener.Start();

    // ...

    // Trivially handle each action's incoming request
    for (int i = 0; i < actions.Length; i++)
    {
        var context = listener.GetContext();
        var request = context.Request;
        Log('S', "Got " + request.HttpMethod + " request");
        using (var stream = request.InputStream)
        {
            while (-1 != stream.ReadByte())
            {
                Log('S', "Read request byte");
            }
            Log('S', "Request complete");
        }
        context.Response.Close();
    }
}

Aside: The code is straightforward, but it's important to note that HttpListener is only able to start listening when run with Administrator privileges (otherwise it throws "HttpListenerException: Access is denied"). So if you're going to try the sample yourself, please remember to run it from an elevated Visual Studio or Command Prompt instance.

 

With our test harness in place, let's start with the simplest possible code to upload some data:

/// <summary>
/// Test action that uses WebClient's UploadData to do the PUT.
/// </summary>
private static void PutWithWebClient()
{
    using (var client = new WebClient())
    {
        Log('C', "Start WebClient.UploadData");
        client.UploadData(_uri, "PUT", _data);
        Log('C', "End WebClient.UploadData");
    }
}

Here's the resulting output from the Client and Server pieces):

09:27:07.72 <C> Start WebClient.UploadData
09:27:07.76 <S> Got PUT request
09:27:07.76 <S> Read request byte
09:27:07.76 <S> Read request byte
09:27:07.76 <S> Read request byte
09:27:07.76 <S> Read request byte
09:27:07.76 <S> Read request byte
09:27:07.76 <S> Request complete
09:27:07.76 <C> End WebClient.UploadData

The WebClient's UploadData method offers a super-simple way of performing an upload that's a great choice when it works for your scenario. However, all the upload data must be passed as a parameter to the method call, and that's not always desirable (especially for large amounts of data like I was dealing with). Furthermore, it's all sent to the server in arbitrarily large chunks, so our attempt at frequent progress updates isn't likely to work out very well. And while there's the OnUploadProgressChanged event for getting status information about an upload, WebClient doesn't offer the granular level of control that's often nice to have.

 

So WebClient is a great entry-level API for uploading - but if you're looking for more control, you probably want to upgrade to HttpWebRequest:

/// <summary>
/// Test action that uses a normal HttpWebRequest to do the PUT.
/// </summary>
private static void PutWithNormalHttpWebRequest()
{
    var request = (HttpWebRequest)(WebRequest.Create(_uri));
    request.Method = "PUT";
    Log('C', "Start normal HttpWebRequest");
    using (var stream = request.GetRequestStream())
    {
        foreach (var b in _data)
        {
            Thread.Sleep(1000);
            Log('C', "Writing byte");
            stream.WriteByte(b);
        }
    }
    Log('C', "End normal HttpWebRequest");
    ((IDisposable)(request.GetResponse())).Dispose();
}

Aside from the Sleep call I've added to simulate client-side processing delays, this is quite similar to the code I wrote for my original scenario. Here's the output:

09:27:08.78 <C> Start normal HttpWebRequest
09:27:09.79 <C> Writing byte
09:27:10.81 <C> Writing byte
09:27:11.82 <C> Writing byte
09:27:12.83 <C> Writing byte
09:27:13.85 <C> Writing byte
09:27:13.85 <C> End normal HttpWebRequest
09:27:13.85 <S> Got PUT request
09:27:13.85 <S> Read request byte
09:27:13.85 <S> Read request byte
09:27:13.85 <S> Read request byte
09:27:13.85 <S> Read request byte
09:27:13.85 <S> Read request byte
09:27:13.85 <S> Request complete

Although I've foreshadowed this unsatisfactory result, maybe you can try to act a little surprised that it didn't work the way we wanted... :) The data bytes got written at 1 second intervals over the span of 5 seconds to simulate a gradual upload from the client - but on the server side it all arrived at the same time after the client was completely finished making its request. This is exactly the behavior I was seeing in my application, so it's nice that we've managed to reproduce the problem.

But what in the world is going on here? Why is that data sitting around on the client for so long?

 

The answer lies in the documentation for the AllowWriteStreamBuffering property (default value: True):

Remarks
When AllowWriteStreamBuffering is true, the data is buffered in memory so it is ready to be resent in the event of redirections or authentication requests.

Notes to Implementers:
Setting AllowWriteStreamBuffering to true might cause performance problems when uploading large datasets because the data buffer could use all available memory.

In trying to save me from the hassle of redirects and authentication requests, HttpWebRequest has broken my cool streaming scenario. :( Fortunately, it's easy to fix - just set the property to False, right?

Wrong; that'll get you one of these:

ProtocolViolationException: When performing a write operation with AllowWriteStreamBuffering set to false, you must either set ContentLength to a non-negative number or set SendChunked to true.

Okay, so we need to set one more property before we're done. Fortunately, the choice was easy for me - my target server didn't support chunked transfer encoding, so choosing to set ContentLength was a no-brainer. The only catch is that you need to know how much data you're going to upload before you start - but that's probably true most of the time anyway! And I think ContentLength is a better choice in general, because the average web server is more likely to support it than chunked encoding.

 

Making the highlighted changes below gives the streaming upload behavior we've been working toward:

/// <summary>
/// Test action that uses an unbuffered HttpWebRequest to do the PUT.
/// </summary>
private static void PutWithUnbufferedHttpWebRequest()
{
    var request = (HttpWebRequest)(WebRequest.Create(_uri));
    request.Method = "PUT";
    // Disable AllowWriteStreamBuffering allows the request bytes to send immediately
    request.AllowWriteStreamBuffering = false;
    // Doing nothing else will result in "ProtocolViolationException: When performing
    // a write operation with AllowWriteStreamBuffering set to false, you must either
    // set ContentLength to a non-negative number or set SendChunked to true.
    // The most widely supported approach is to set the ContentLength property
    request.ContentLength = _data.Length;
    Log('C', "Start unbuffered HttpWebRequest");
    using (var stream = request.GetRequestStream())
    {
        foreach (var b in _data)
        {
            Thread.Sleep(1000);
            Log('C', "Writing byte");
            stream.WriteByte(b);
        }
    }
    Log('C', "End unbuffered HttpWebRequest");
    ((IDisposable)(request.GetResponse())).Dispose();
}

Here's the proof - note how each byte gets uploaded to the server as soon as it's written:

09:27:14.86 <C> Start unbuffered HttpWebRequest
09:27:14.86 <S> Got PUT request
09:27:15.88 <C> Writing byte
09:27:15.88 <S> Read request byte
09:27:16.89 <C> Writing byte
09:27:16.89 <S> Read request byte
09:27:17.90 <C> Writing byte
09:27:17.90 <S> Read request byte
09:27:18.92 <C> Writing byte
09:27:18.92 <S> Read request byte
09:27:19.93 <C> Writing byte
09:27:19.93 <C> End unbuffered HttpWebRequest
09:27:19.93 <S> Read request byte
09:27:19.93 <S> Request complete

 

Like many things in life, it's easy once you know the answer! :) So if you find yourself wondering why your streaming uploads aren't so streaming, have a look at the AllowWriteStreamBuffering property and see if maybe that's the cause of your problems.

 

[Please click here to download a sample application demonstrating everything shown here.]

I posted the source code for a Silverlight implementation of the HTML 5 <canvas> API yesterday and some readers have been pretty interested in the concept/implementation. Thanks for all your comments and feedback!

Earlier today, kind user Fabien Ménager left a comment reporting an unhandled exception in the sample app and was generous enough to follow up by sending me the text of the exception. And as soon as I saw it, I knew the problem - both because of what it said and because of the language it was in!

Here, you give it a try:

System.FormatException: Le format de la chaîne d'entrée est incorrect.

Here's a hint: the operating system's culture settings for France (and many other countries) use a ',' for the decimal separator instead of '.' (as is used in the United States). For example, while Pi would be written as "3.14" with the US culture settings, it would be written as "3,14" with French culture settings. And while Html5Canvas doesn't accept any user input, it does parse some of the JavaScript input that makes up the script... Specifically, my sample application includes the following line:

context.fillStyle = "rgba(255, 127, 39, 0.8)";

The <canvas> specification allows for strings to be assigned to the fillStyle property, so it's necessary for Html5Canvas to parse that string. And it was the "0.8" alpha value that was the problem here. Attempting to parse that value with the user's culture settings will fail for a culture that uses ',' as the decimal separator. This is actually a common problem for text formats that are meant to be used in multiple cultures - and the typical solution is to require that the text always be written for some form of invariant culture (which typically adheres to the US's conventions). Therefore, the trivial fix was to parse that value according to the invariant culture (i.e., always use '.' as the decimal separator) instead of using the default parsing behavior which honors the user's settings.

Aside: The default behavior is nearly always what you want... except for very rarely when it's not... like this time! :)

Of course, if I'd reviewed the project's code analysis warnings a few days ago, I would have found this issue earlier. And while I usually do that for all my sample code, I skipped it this time because it was proof-of-concept code and because I knew the "Naming" analysis rules threw lots of warnings for the official <canvas> API (mainly because JavaScript tends to follow different conventions than .NET). So as punishment for my misdeed, I went ahead and fixed (or suppressed) all of the non-"Naming" code analysis warnings in the project!

To be clear, there is no functional change because of this - but now the code is just a little bit cleaner. :)

 

[Please click here to download the updated source code to Html5Canvas and its sample application.]

 

And while I was at it, I decided to post the sample application in runnable form just in case there were some people who wanted to watch the Hypotrochoid draw itself, but didn't want to compile the sample themselves.

 

[Click here or on the image below to run the sample application in your browser.]

 

It has been great to see all the interest in this project over the past couple of days - thanks very much for everyone's support, feedback, and kind words!!

Background

There's been some buzz about the upcoming HTML 5 standard over the past few months. In particular, there are a couple of new features that people are looking forward to. One of them is the new <canvas> element which introduces a 2D drawing API offering a pretty rich set of functionality. If you've worked with HTML much, you can probably imagine some of the things that become possible with this. In fact, those are probably some of the same things that Flash and Silverlight are being used for today! So some people have gone as far as to suggest HTML 5 could eliminate the need for Flash and Silverlight...

I didn't know much about the <canvas> element and I wanted to understand the situation better, so I did some research. The specification for <canvas> is available from two sources: the W3C and the WHATWG. (The two groups are working together, so the spec is the same on both sites.) The API is comprised of something close to 100 interfaces, properties, and methods and offers an immediate mode programming model that's superficially similar to the Windows GDI API. At a very high level, the following concepts are defined (though Philip Taylor did some investigation a while back which suggested that no browser offered complete support):

• Paths and shapes (move/line/curve/arc/clipping/etc.)
• Strokes and fills (using solid colors/gradients/images/etc.)
• Images
• Context save/restore
• Transformations (scale/rotate/translate/etc.)
• Compositing (alpha/blending/etc.)
• Text (font/alignment/measure/etc.)
• Pixel-level manipulation
• Shadows

There's a variety of stuff there - and as I read through the list, I was struck by how much of it is natively supported by Silverlight. Pretty much all of it, in fact! :) So I thought it might be a fun and interesting learning experience to try implementing the HTML 5 <canvas> specification in Silverlight! What better way to understand the capabilities of <canvas> than to implement them, right?

So I went off and started coding... I didn't set out to support everything and I didn't set out to write the most efficient code (in fact, some of what's there is decidedly inefficient!) - I just set out to implement enough of the specification to run some sample apps and see how hard it was.

And it turns out to have been pretty easy! Thanks to Silverlight's HTML Bridge, I had no trouble creating a Silverlight object that looks just like a <canvas> to JavaScript code running on a web page. So similar, in fact, that I'm able to run some pretty cool sample applications on my own <canvas> simply by tweaking the HTML to instantiate a Silverlight <canvas> instead of the browser's <canvas>. And as a nice side effect, Internet Explorer "magically" gains support for the <canvas> tag!

Aside: Yes, I know I'm not the first person to add <canvas> support to IE. :)

 

Samples

I started off easy by working my way through the Mozilla Developer Center's Canvas tutorial and implementing missing features until each of the samples loaded and rendered successfully. Here are three of my favorite samples as rendered by Html5Canvas, my custom <canvas> implementation:

 

Aside: It's important to note that I did NOT change the JavaScript of these (or any other) samples - I just tweaked the HTML host page to load my <canvas> implementation. My goal was API- and feature-level parity; a Silverlight implementation of <canvas> that was "plug-compatible" with the existing offerings.

 

After that, I knew I just had to run Ben Joffe's Canvascape "3D Walker" because it bears a striking resemblance to one of the games I played when I was younger:

 

Aside: Be sure to look for the "Silverlight" context menu item I've included in the image above and in the next few screen shots to prove there's no trickery going on. :)

 

Next up was Bill Mill's Canvas Tutorial - and another shout-out to hours of misspent youth:

 

For something completely different, I got Bjoern Lindberg's Blob Sallad running:

 

Then it was on to Ryan Alexander's Chrome Canopy fractal zoomer (despite the note, it runs okay-ish in IE8 with my Silverlight <canvas>):

 

Finally, I wanted to see how the 9elements HTML5 Canvas Experiment ran:

 

Whew, What a rush - those apps are really cool! :)

 

But I still wanted a sample I could include with the source code download, so I also wrote a little app to exercise most of the APIs supported by Html5Canvas (thanks to Mozilla for the Hypotrochoid animation inspiration and Wikipedia for the equation). Here it is on IE:

 

And wouldn't it be nice to see how Html5Canvas compares to a "real" <canvas> implementation? Sure, here's my sample running on Firefox:

 

Details

So how does it actually work? Well, I'm obviously not modifying the browser itself, so redefining the actual <canvas> tag isn't an option. Instead, I've written a simple Html5Canvas.js file which gets referenced at the top of the HTML page:

<script type="text/javascript" src="Html5Canvas.js"></script>

Among other things, it defines the handy function InsertCanvasObject(id, width, height, action) function which can be used to insert a Silverlight <canvas> thusly:

<script type="text/javascript">
    InsertCanvasObject("mycanvas", 200, 200, onCanvasLoad);
</script>

That code inserts a Silverlight object running Html5Canvas.xap that looks just like the <canvas> tag would have. Yep, it's that easy!

And it brings up an important difference between Html5Canvas and a real <canvas>: Html5Canvas can be used only after the Silverlight object has loaded - whereas <canvas> is usable as soon as the body/window has loaded (which happens sooner). This distinction is important to keep in mind if you're converting an existing page, because it requires moving the initialization call from onload to the action parameter of InsertCanvasObject. Believe it or not, that's really the only big "gotcha"!

Aside: While I could think of a few ways to avoid exposing this difference to the developer, none of them were general enough to apply universally.

Other minor differences between Html5Canvas and <canvas> are that Silverlight doesn't natively support the relevant repeat modes used by createPattern to tile images (though I could implement them without much difficulty), Silverlight doesn't support the GIF image format for use with drawImage (also easily worked around), and the conventional technique of JavaScript feature-detection by writing if (canvas.toDataURL) { ... } doesn't work because Silverlight's HTML Bridge doesn't allow a method to be treated like a property (I could work around this, too, but the extra level of indirection was unnecessarily confusing for a sample app).

Finally, let me reiterate that I did not attempt to implement the complete <canvas> specification. Instead, I implemented just enough to support the first 5 (of 6 total) Mozilla sample pages as well as the handful of applications shown above. Specifically, I've implemented everything that's not in italics in the feature list at the beginning of this post. Thinking about what it would take to add the stuff that's not implemented: text and pixel-level manipulation are both directly supported by Silverlight and should be pretty easy. Shadows seem like a natural fit for Silverlight's pixel shader support (though I haven't played around with it yet). All that's left is layer compositing, which does worry me just a little... I haven't thought about it much, but this seems like another job for WriteableBitmap, perhaps.

 

[Please click here to download the complete source code to Html5Canvas and the sample application shown above.]

Be sure to set the Html5Canvas.Web project as the active project and run the TestPage.html within it to see the sample application.

 

Summary

Html5Canvas was a fun project that definitely accomplished its goal of bringing me up to speed on HTML 5's <canvas> element! The implementation proved to be fairly straightforward, though there were a couple of challenging bits that ended up being good learning opportunities. :) The code I'm sharing here is intended to be a proof-of-concept and is not optimized for performance. However, if there's interest in making broader use of Html5Canvas, I have some ideas that should really improve things...

I hope folks find this all as interesting as I did - and maybe next time you want to add browser features, you'll use Silverlight, too! ;)

Problem

I spent some time in my last post explaining how Silverlight/WPF Charting takes advantage of an ordered multi-dictionary to improve the performance of various scenarios. I wrote about Charting's use of a custom binary tree implementation and outlined some limitations of that algorithm and our particular implementation of it. In this post, I'm going to explain how we're addressing those limitations for the next release of Charting and share the general purpose code we're using to do it!

The fundamental problem with our current BinaryTree implementation is that offers no guarantee of balance, and can devolve into linear performance even when dealing with fairly typical data. And this isn't an implementation problem - it's an algorithmic one: if you want balancing behavior, you should really use a data structure that balances. (Duh...) One of the most popular data structures for implementing a balanced binary tree is the red-black tree. Red-black trees get their name from the colors they assign to their nodes - which they use to perform various "rotations" on the tree in order to maintain a set of invariants that guarantee the tree remains more-or-less balanced. (I'm not going to go into more detail here; the Wikipedia article is a great resource for learning more.) The "problem" with red-black trees is that they're notoriously tricky to implement correctly - especially the remove scenarios. There are a lot of special cases to deal with, and things can get messy pretty quickly...

Solution

Which is why I was so excited to read about Robert Sedgewick's research paper on "left-leaning red-black trees". (If you want something a little more colorful than a research paper, here's a presentation on the same topic.) Basically, Dr. Sedgewick took advantage of a correspondence between red-black trees and 2-3-4 trees to introduce a constraint (that red nodes must be "left-leaning") which significantly simplifies the overall implementation. This new algorithm sounded perfect for our purposes, and I spent a few bus rides developing a C# implementation of left-leaning red-black trees based on the published research.

But wait! Charting needs an ordered multi-dictionary whereas red-black trees implement a standard dictionary - what gives? Well, do you remember the trick I wrote about in my binary tree post where I figured out that I could turn a standard dictionary into an ordered multi-dictionary by adding a value comparison into the mix? Good, because I've done exactly the same thing here. :)

But this time it's even a little bit better! Instead of storing "identical" nodes next "beside" each other (which is not as easy in a red-black tree), I realized that I could collapse all duplicate nodes into the same node by adding a Sibling count to the Node structure. This makes duplicate nodes really easy to deal with because the standard add and remove code stays exactly the same until the very end when it checks for siblings.

But wait - there's more. :) Because it was so easy to implement the ordered multi-dictionary Charting needed, I decided to make my LeftLeaningRedBlackTree implementation both an ordered multi-dictionary and a normal dictionary! You can choose which one you want by passing in either key+value comparison functions to the constructor (to create an ordered multi-dictionary) or just a key comparison function (to create a standard dictionary). All the class's properties and methods work exactly the same in both modes, so switching between them is easy! (To make it even easier, I've added two trivial helper methods to simplify the standard dictionary scenarios: Remove(key) and GetValueForKey(key).)

Performance

Okay, so this is all well and good, but the real question is whether LeftLeaningRedBlackTree runs faster than BinaryTree or not. Well, if you looked at the graph above comparing the elapsed time (vertical axis) of the two solutions for different node counts (horizontal axis), then you already know the answer. LeftLeaningRedBlackTree is a clear win for the tested scenario (which was sequential adds, a bunch of min/max search operations, then sequential removes - typical Charting behavior). Okay, so once you've decided that LeftLeaningRedBlackTree is a win when node counts start getting large, the next question is how the two implementations compare for low node counts. Because the scale of the previous graph is large and could be obscuring some detail in the low range, let's specifically measure the performance for small numbers of nodes:

And there you have it: BinaryTree beats LeftLeaningRedBlackTree when the node count is close to 20. Which isn't very surprising when you think about it - for small numbers of nodes, the unbalance of BinaryTree is not yet significant enough to outweigh the overhead that LeftLeaningRedBlackTree incurs from its balancing process. But does this particular region of performance inversion really matter? Not so much - the range where BinaryTree wins is very small, the difference in timings is small, and the impact of sorting on performance at those node counts is basically insignificant. So the next version of Charting doesn't bother trying to pick the best sorting algorithm for different scenarios - it uses LeftLeaningRedBlackTree for everything. And you'll be glad it does when your node count starts growing! :)

Aside: There is a scenario where BinaryTree beats LeftLeaningRedBlackTree even at large node counts. Specifically, if the original data is already completely random, then BinaryTree naturally ends up nicely balanced as a direct consequence of that randomness - and it didn't need to spend any cycles making itself that way! LeftLeaningRedBlackTree doesn't know the data is random and spends cycles balancing itself unnecessarily. However, this performance delta between the algorithms doesn't diverge like in the charts above - LeftLeaningRedBlackTree has a consistent ~35% overhead across the board. It's been said that you never get something for nothing - and this overhead is just part of the cost of having guaranteed balancing behavior across all inputs.

Testing

Okay, so it's faster - but is it correct? Yes, I'm prepared to suggest that it is - and I happen to have a set of automated test cases to back my claim up! :) The tests I've written pick a random number of elements across randomly sized key and value spaces, add all these random pairs to the tree, make sure everything's behaving correctly, and then remove them all in random order. After each add or remove, the complete state of the entire tree is checked against a separate algorithm. And all the while LeftLeaningRedBlackTree is running its own internal code to ensure the invariants of a left-leaning red-black tree are maintained at all times.

I call this whole thing a "scenario". I've found that 100% code coverage is achieved after running just 1 or 2 scenarios; 40 scenarios is all it takes to exercise the set of problematic corner cases I've seen. Well, the automated tests run 1000 scenarios - 250 known scenarios against a normal dictionary, 250 known scenarios against an ordered multi-dictionary, 250 random ones on a normal dictionary, and 250 random ones on an ordered multi-dictionary. Whew!

Of course, no code is ever perfect - but I'm pretty happy with the level of coverage here and optimistic that it's helped squash the bugs that matter.

API

You might expect LeftLeaningRedBlackTree to implement IDictionary<TKey, TValue> - but it doesn't. However, it does have an API that strongly resembles that interface, so it should look pretty familiar. For example, Add looks exactly the same and the single-parameter form of Remove (for normal dictionary mode) is exactly the same as well. Ordered multi-dictionary mode necessitates a two-parameter form of Remove, but it's just what you'd expect. Clear and Count (via IDictionary's base class ICollection<T>) are identical as well.

However, things start to diverge a bit after that. Instead of ICollection<T> properties for Keys and Values (which may be unnecessarily costly to compute if the caller only needed a few of the elements), there are IEnumerable<T> methods GetKeys and GetValuesForAllKeys. It's the same idea, but more efficient thanks to being sequence-based! The array accessor (this[T]) is deliberately absent because it doesn't make much sense for the ordered multi-dictionary mode - I'd rather things be more explicit via Add or GetValueForKey/GetValuesForKey. The latter of those last two methods works in both modes; the first is available as a simplification for normal dictionary mode (and throws KeyNotFoundException for consistency with IDictionary implementations). ContainsKey and TryGetValue are both absent - and trivial to add if you want them. As for the rest of the IDictionary<T>/ICollection<T>/IEnumerable<T>/IEnumerable properties and methods, they either don't make sense on an ordered multi-dictionary or are easy enough to add. And finally, the API is rounded out by the MinimumKey and MaximumKey properties - specifically implemented for efficiency because Charting makes such heavy use of them.

In case that was all just a confusing jumble of class names and interfaces, here's what it looks like in code:

/// <summary>
/// Implements a left-leaning red-black tree.
/// </summary>
/// <remarks>
/// Based on the research paper "Left-leaning Red-Black Trees"
/// by Robert Sedgewick. More information available at:
/// http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
/// http://www.cs.princeton.edu/~rs/talks/LLRB/08Penn.pdf
/// </remarks>
/// <typeparam name="TKey">Type of keys.</typeparam>
/// <typeparam name="TValue">Type of values.</typeparam>
public class LeftLeaningRedBlackTree<TKey, TValue>
{
    /// <summary>
    /// Initializes a new instance of the LeftLeaningRedBlackTree class implementing a normal dictionary.
    /// </summary>
    /// <param name="keyComparison">The key comparison function.</param>
    public LeftLeaningRedBlackTree(Comparison<TKey> keyComparison)

    /// <summary>
    /// Initializes a new instance of the LeftLeaningRedBlackTree class implementing an ordered multi-dictionary.
    /// </summary>
    /// <param name="keyComparison">The key comparison function.</param>
    /// <param name="valueComparison">The value comparison function.</param>
    public LeftLeaningRedBlackTree(Comparison<TKey> keyComparison, Comparison<TValue> valueComparison)

    /// <summary>
    /// Adds a key/value pair to the tree.
    /// </summary>
    /// <param name="key">Key to add.</param>
    /// <param name="value">Value to add.</param>
    public void Add(TKey key, TValue value)

    /// <summary>
    /// Removes a key (and its associated value) from a normal (non-multi) dictionary.
    /// </summary>
    /// <param name="key">Key to remove.</param>
    /// <returns>True if key present and removed.</returns>
    public bool Remove(TKey key)

    /// <summary>
    /// Removes a key/value pair from the tree.
    /// </summary>
    /// <param name="key">Key to remove.</param>
    /// <param name="value">Value to remove.</param>
    /// <returns>True if key/value present and removed.</returns>
    public bool Remove(TKey key, TValue value)

    /// <summary>
    /// Removes all nodes in the tree.
    /// </summary>
    public void Clear()

    /// <summary>
    /// Gets a sorted list of keys in the tree.
    /// </summary>
    /// <returns>Sorted list of keys.</returns>
    public IEnumerable<TKey> GetKeys()

    /// <summary>
    /// Gets the value associated with the specified key in a normal (non-multi) dictionary.
    /// </summary>
    /// <param name="key">Specified key.</param>
    /// <returns>Value associated with the specified key.</returns>
    public TValue GetValueForKey(TKey key)

    /// <summary>
    /// Gets a sequence of the values associated with the specified key.
    /// </summary>
    /// <param name="key">Specified key.</param>
    /// <returns>Sequence of values.</returns>
    public IEnumerable<TValue> GetValuesForKey(TKey key)

    /// <summary>
    /// Gets a sequence of all the values in the tree.
    /// </summary>
    /// <returns>Sequence of all values.</returns>
    public IEnumerable<TValue> GetValuesForAllKeys()

    /// <summary>
    /// Gets the count of key/value pairs in the tree.
    /// </summary>
    public int Count

    /// <summary>
    /// Gets the minimum key in the tree.
    /// </summary>
    public TKey MinimumKey

    /// <summary>
    /// Gets the maximum key in the tree.
    /// </summary>
    public TKey MaximumKey
}

Debugging

At this point, I'm reasonably confident that LeftLeaningRedBlackTree behaves correctly - but that wasn't always the case! :) Three particular debugging aids served me well and I'd like to call them out (Note: to enable the bottom two debugging aids, you need to uncomment the line #define DEBUGGING at the top of LeftLeaningRedBlackTree.cs):

• The first is a standard .NET technique, but one many people don't seem to be familiar with: DebuggerDisplayAttribute. Specifically, this attribute improves the debugging experience by turning the visual representation of a node from {LeftLeaningRedBlackTree<int,int>.Node} into Key=4, Value=15, Siblings=0. Granted, it's the same information you'd get by expanding to display the node's properties, but it's automatically used in the Autos and Watch windows as well as by tooltips! What's more, this is easy to enable for any class - just provide a customized format string like this: "Key={Key}, Value={Value}, Siblings={Siblings}".

• Both LeftLeaningRedBlackTree and its private Node class expose a string property that returns an HTML representation of the tree/node and its children. Here's what it looks like when viewed with Visual Studio's built-in "HTML Visualizer" for strings:

  

  More than just a cool trick, the HtmlDocument and HtmlFragment properties are an invaluable resource for visualizing the many rotations/manipulations of the tree as it balances itself. After you've stared at this kind of stuff for a while, you start to develop a sense of what looks wrong - and this visualization makes finding algorithmic problems quite a bit easier than if the in-memory representation of the tree was all you had!

• When enabled for debugging, the AssertInvariants method gets called at the end of every method that manipulates the tree. The purpose of this method is to ensure the basic requirements of a left-leaning red-black tree are maintained - specifically, it Asserts that the following conditions are true every time it's called:
  • Root node is black
  • Every path from the root to leaf nodes contains the same number of black nodes
  • Left node is less
  • Right node is greater
  • Both children of a red node are black
  • Nodes are always left-leaning
  • No consecutive red nodes

Summary

LeftLeaningRedBlackTree has been a fun project and I'm glad to be able to leverage it to help make significant improvements to Charting's performance for some very real customer scenarios. I'd like to extend my thanks to Dr. Sedgewick for his research in this area and express my hope that others will be able to take advantage of LeftLeaningRedBlackTree to improve the performance of their own applications. As always, if you run into any problems, please let me know - any errors here are my fault, not anyone else's! :)

 

[Please click here to download the source code for LeftLeaningRedBlackTree, its test application, unit tests, and the comparison project.]

Jafar was teasing me about his F# solution to Eric Lippert's comma quibbling problem, and I decided to retaliate. :) One of the things I didn't like about the five-or-so solutions I'd seen [including Jafar's :P ] was that they were doing a bunch of work to detect special cases on every pass through the loop. That seemed silly to me because there are really only two special cases and they only come into play at the very end of the operation.

So I threw together the following method which has a fairly efficient inner loop which saves the special cases for the end. I also made it generic so it'll take an input stream of any type - then defer to StringBuilder (or the object itself!) for proper formatting. Oh, and the code is both compact and commented. :)

The downside - and it's a big one - is that the input stream is enumerated three times instead of just one. :(

Oh well, when you're out for a quick bit of revenge you can't accomplish everything... :)

/// <summary>
/// Solve comma quibbling posed by Eric Lippert at:
/// http://blogs.msdn.com/ericlippert/archive/2009/04/15/comma-quibbling.aspx.
/// </summary>
/// <typeparam name="T">Type of input.</typeparam>
/// <param name="input">Stream of input elements (ex: string).</param>
/// <returns>Quibbled string.</returns>
/// <remarks>
/// Good points:
/// * Generic type support (StringBuilder formats for output)
/// * Special-case logic is not run every time through the loop
/// Bad points:
/// * Input stream is traversed three times :(
/// </remarks>
private static string CommaQuibbling<T>(IEnumerable<T> input)
{
    // Capture stream
    var a = input.GetEnumerator();
    var b = input.Skip(1).GetEnumerator();
    var c = input.Skip(2).GetEnumerator();
    // Prefix the result
    var sb = new StringBuilder("{");
    // Process the "normal" leading elements
    while (c.MoveNext() && b.MoveNext() && a.MoveNext())
    {
        sb.Append(a.Current).Append(", ");
    }
    // Process the non-Oxford comma scenario
    if (b.MoveNext() && a.MoveNext())
    {
        sb.Append(a.Current).Append(" and ");
    }
    // Process the remaining element
    if (a.MoveNext())
    {
        sb.Append(a.Current);
    }
    // Postfix the result and return it
    return sb.Append("}").ToString();
}

I occasionally find myself on a particular network that's separated from the rest of the Internet by a firewall. The administrators of this network are kind enough to provide both HTTP and SOCKS 4a proxy servers, so it's generally quite easy to get access to the Internet in spite of the firewall. Unfortunately, a couple of the programs I use from time to time support only the SOCKS 5 protocol which is not backwards compatible with the SOCKS 4a protocol...

Well, after bumping into this problem again recently, I checked the SOCKS specifications on Wikipedia and decided it would be pretty straightforward to write a SOCKS 5 proxy server that forwarded all its traffic to a SOCKS 4a proxy server to do the real work. There's just not that much to a proxy server - especially when you're only interested in supporting TCP/IP streams and aren't hoping for production-quality code. :)

So I dashed off a program called Socks5to4a that does exactly what I envisioned. I just run it on my machine, tell it how to connect to the network's SOCKS 4a server, and point my SOCKS 5 applications at localhost. The programs all think they're talking to a real SOCKS 5 server and the network's SOCKS 4a server thinks it's talking to a real SOCKS 4a client - and they're almost right!

With Socks5to4a, things couldn't be simpler - here's what it looks like in action:

D:\T>Socks5to4a myproxy 1080 fallback.example.com
0: Listening on localhost:1080 with fall-back to fallback.example.com...
1: Accepted connection.
1: Reading client request...
1: Client requests fallback.example.com:1234.
1: Connecting to proxy...
1: Connected.
1: Forwarding request...
1: Connected.
1: Sending response...
1: Proxying data...
2: Accepted connection.
2: Reading client request...
2: Client requests fallback.example.com:1234.
2: Connecting to proxy...
2: Connected.
2: Forwarding request...
2: Connected.
2: Sending response...
2: Proxying data...
3: Accepted connection.
3: Reading client request...
3: Client requests 192.168.1.6:2345.
3: Connecting to proxy...
3: Connected.
3: Forwarding request...
3: Connect failed.
3: Retrying with fallback.example.com:2345...
3: Connected.
3: Sending response...
3: Proxying data...
3: Connection closed.
1: Connection closed.
2: Connection closed.

If you paid close attention to the above trace, you probably noticed the "fall-back" behavior. What's going on is that one of the applications I use connects to a server that misreports its public IP address - so subsequent attempts to connect to that IP fail. What I did is add a bit of smarts to Socks5to4a so I can specify an optional fall-back server when I run it; and then any connection failures are automatically (and seamlessly) retried using the fall-back server. Because the fall-back server is used only when necessary, this kludge stays out of the way until it's needed. At which point it's elegant and icky at the same time... :)

Socks5to4a is something I wrote to solve a specific problem I was having - but if it's interesting to you, please go ahead and have a look or give it a try. However, please remember that I specifically did not set out to create the world's best or fastest SOCKS 5 server - the code I wrote works well enough for my scenarios, but may need a bit of tweaking for yours.

[Click here to download the Socks5to4a application along with its complete source code.]

Happy proxying!