Saturday, August 20, 2011

Opening a WPF window from a C++ application.

Hello All,

I was recently requested to show a WPF UI from legacy C++ code. I thought that this is a quite common task and that I would be able to find ample resources about it on the internet but I found only general guidance with lots of missing details that assume you are a C++ developer wanting to use WPF while I am a WPF developer wanting to reuse legacy C++ code. I hope this short guide will help my readers to accomplish this quite simple task.


My implementation is generic and contains three parts:
  1. The C++ COM interface.
  2. The WPF application (i.e. the client).
  3. The C++ application (i.e. the host).
The goal: Open a simple dialog that will show "Hello World" in a WPF window from my C++ application. To achieve this goal I will be using COM interoperability (but don't worry, if you have no clue in COM you can still use this method. I will explain the parts that you need).

Creating the COM interface
Fire up your Visual Studio (I will be using Visual Studio 2010 Ultimate) and create a new ATL Project (Other languages, C++ category). A wizard will pop up just press Finish.
You will see two projects were created, one with the name you selected (I selected TheInterface so I will run with this name) and the other with the name you selected and PS suffix.
  • Delete the project with the PS suffix (in my case TheInterfacePS).
  • Delete the Generated Files folder from your project.
  • Delete ReadMe.txt (unless you really like it).
  • In the Header Files folder leave only Resource.h,  StdAfx.h and dllmain.h (delete the rest).
  • Open TheInterface.cpp file (if you selected a different name it will be <your name>.cpp) and add the line:
         #include "TheInterface_i.c"
      right after the line:
      #include "TheInterface_i.h"
      but before the line:
      #include "dllmain.h"


Build the project. At this point the build should pass.
Your solution will look something like this.
Now we will define our COM interface. Open the idl file (TheInterface.idl). You will see the library that was defined for you by the wizard. We will add our interface to that library. The syntax is simple and similar to C#. In square braces you define something like attributes and then the interface itself. Each COM interface must be assigned a GUID. Inside the library definition (in the block surrounded by the curly braces add the following definition (at the end)



   [
        uuid(20F0BD1B-4B00-4a1f-B600-420631C40CD8),
helpstring("IShowDialog Interface"),
    ]
Note that you shouldn't use the GUID from my example! 
To create a new GUID use the Create GUID tool found in the Tools menu of Visual Studio. In the Create GUID tool select registry format (4) and copy the GUID. Don't forget to remove the curly braces after you paste it.
Create GUID tool.


(The helpstring is not mandatory but it will show in several places that will help you later)


Now for the interface itself:

    interface IShowDialog : IUnknown
{
     [id(1),helpstring("Show the dialog")] HRESULT ShowDialog([in]BSTR bstrCaption);
    };




The IUnknown is the base interface of COM interfaces so we inherit from it. We create one method and give it the id of 1 (the helpstring is again not mandatory. Our method returns HRESULT, is called ShowDialog and accepts one parameter of type BSTR (which in the string type of COM). 
Your idl file should look something like this:

import "oaidl.idl";
import "ocidl.idl";
 
[
	uuid(DB9255B8-4D42-42D2-8C81-6734E52EEDB3),
	version(1.0),
]
library TheInterfaceLib
{
	importlib("stdole2.tlb");
	
	[
      uuid(73756BB5-41B1-4383-B899-B4EB4AE0A38A),
	  helpstring("IShowDialog Interface"),
    ]
    interface IShowDialog : IUnknown
	{
     [id(1),helpstring("Show the dialog")] HRESULT ShowDialog([in]BSTR bstrCaption);
    };
 
};

Now open the properties of your project and go to the MIDL-> Output category. There are two items to notice here:
  1. Header file - This is the file you will use in your C++ project to use the interface definition.
  2. Type library - This is the file we are going to use for our C# project.
The next and final thing to do is to create an interop dll that we can easily use in our C# project. Open the properties of your project again and go to Build Events -> Post-build events. Edit the Command line and write there:
tlbimp.exe $(IntDir)TheInterface.tlb /namespace:MyNamespace /out:"$(IntDir)Interop.TheInterface.dll"
The tlbimp tool (comes with Visual Studio) and it will transform your tlb file into a dll you can reference in your C# project. One thing to notice is the namespace parameter where you define your namespace (as in any .NET dll).
Now we have all the needed tools to communicate between the C++ and the C# projects so lets create them.
Creating the C# project
Add to your project a C# WPF Application (I call it TheDialog). First we create a class that will implement the interface we declared earlier. First I reference the interop dll we created ealier - Interop.TheInterface.dll and create a class called DialogShower that will show the dialog.
At this point we remember that we will create this class from the C++ application and therefore we must mark it with some attributes to make it visible by COM. The attributes are:
  1. [ComVisible(true)] - So that the class will be registered to COM.
  2. [Guid("48CCE666-E6C4-464C-94D3-83148A88A6D5")] - Because every COM objects needs a GUID.
  3. [ClassInterface(ClassInterfaceType.None)] - Means we are implementing our own interface.
  4. [ProgId("WPFMessageDialog")] - This is the "secret keyword" we can use to create this object in C++ code (you will see later).
In my class I will simply show the default window that will contain a label with the provided message (note that the interface implementation contains a string parameter converted from BSTR).
Since the project is an application you can run it for a small test.
Creating the C++ project
Now for the last part, creating the C++ project. We add a C++ Win32 Console application to our solution called TheApplication. In the wizard click next and then select ATL checkbox (in "Add common header files for:").
In your main file you must add include to TheInterface_i.h file created in the first part and to comutil.h which comes by default.
The code in my main method is:
	USES_CONVERSION;  //Needed to convert from regular "" strings to BSTR
	CComPtr<IShowDialog> dialog;
	if (CoInitializeEx(NULL,COINIT_APARTMENTTHREADED) != S_OK)	 //Needed to use any COM call in your application
		return -1;
 
    HRESULT res = dialog.CoCreateInstance(L"WPFMessageWindow", NULL, CLSCTX_INPROC_SERVER); //Create the instance of our object through COM
	if (FAILED(res))
		return -1;	
	BSTR message = SysAllocString(L"Hello World"); //Convert a regular string to BSTR (COM string)
	dialog->ShowDialog(message); // Show the dialog
	SysFreeString(message); // Free the created string
	CoUninitialize(); //Uninitialized COM
	return 0;
Comments are in the body.
And the result is:

A few needed things to make things work correctly:
  • You must have access to the TheInterface_i.h file from the main C++ application. I suggest configuring the MIDL section of that project to produce this file to some global location.
  • The same applies for the Interop.TheInterface.dll file. You might want to build it to some global bin dir.
  • Note that the WPF dll contains a COM object therefore you must register it within any system that will run your application. You cannot use regsvr32 to do that. Instead you must run the following command in the post build events of the WPF application: 
%windir%\Microsoft.NET\Framework\v4.0.30319\RegAsm.exe "$(TargetDir)$(TargetFileName)" /regfile:"$(TargetDir)$(TargetFileName).reg"
This will register the dll on your local machine and create a registry file 
that you will have to run on the deployment machine.
  • The exe file of the application and the dll/exe of the WPF dialog assembly must be in the same directory otherwise the COM object will not be created.
That's it for today. I hope you enjoyed the post. 
You can find all the related files on my SkyDrive here.
Thanks for reading,
Boris.

Saturday, August 6, 2011

A philosophical view on interview questions using BFS and DFS traversals

Hello All,

Today I want to talk about computer science riddles versus computer science problems especially during job interviews. I will start by saying I hate CS riddles, I don't understand why someone would give them in an interview and what it would show about both the interviewer and the interviewee. On the other hand I love CS problems which made me wonder what is the difference between the two. I thought long and hard about this question and decided that the main difference is that a CS riddle is usually solved using a very specific, usually unorthodox method which in many times is not directly related to the topic (or general area) of the question. On the other hand a CS problem can be solved in many ways which usually derive from well known practices in CS.


Anyway... My story starts one day when I wondered into the kitchen at work seeking a cup of tea. I saw one of my group mates interviewing some guy. At this point he left the room to let the interviewee deal with the question alone so I took the opportunity to ask what was the question. He said that he asked the interviewee to print a binary tree using a BFS traversal. This is after he already solved the same question using the DFS traversal. I responded that this is a nice warm-up question since the two methods differ only by the words Stack (for DFS) and Queue (for BFS) and other than that the algorithm is exactly the same. He said that the interviewee solved the DFS traversal using recursion so he may have to think. 
At this point I could leave the kitchen and concentrate on drinking my tea but I thought to myself... What is the difference between the recursive DFS and BFS methods?


Thinking further I realized that it is not that simple to implement a recursive BFS method because essentially the recursion uses a Stack while BFS uses a queue which are the opposite.
For the sake of this exercise I assume that a recursive method cannot use any loops of any kind and all the traversal must be done using the recursion.


I implemented a small tree class as follows:

  public class TreeNode
  {
    public int Data
    {
      get;
      set;
    }
 
    public TreeNode Left
    { getset; }
 
    public TreeNode Right
    { getset; }
 
    public TreeNode(int data)
    {
      Data = data;
    }
  }
 
  public class Tree
  {
    public TreeNode Root
    {
      get;
      set;
    }

First I will present the iterative DFS and BFS methods (just to prove my point that they differ in only that one word)
   internal void PrintDfs()
    {
      Console.Out.WriteLine("Printing tree using iterative DFS algorithm");
      Stack<TreeNode> nodes = new Stack<TreeNode>();
      nodes.Push(Root);
      while (nodes.Count > 0)
      {
        TreeNode tempNode = nodes.Pop();
        Console.Out.Write(string.Format("{0},", tempNode.Data));
        if (tempNode.Right != null)
          nodes.Push(tempNode.Right);
        if (tempNode.Left != null)
          nodes.Push(tempNode.Left);
      }
      Console.Out.WriteLine();
    }
 
    internal void PrintBfs()
    {
      Console.Out.WriteLine("Printing tree using iterative BFS algorithm");
      Queue<TreeNode> nodes = new Queue<TreeNode>();
      nodes.Enqueue(Root);
      while (nodes.Count > 0)
      {
        TreeNode tempNode = nodes.Dequeue();
        Console.Out.Write(string.Format("{0},", tempNode.Data));
        if (tempNode.Left != null)
          nodes.Enqueue(tempNode.Left);
        if (tempNode.Right != null)
          nodes.Enqueue(tempNode.Right);
      }
      Console.Out.WriteLine();
      
    }
Implementing DFS using recursion is trivial:
    private void PrintDfsRecursiveInternal(TreeNode node)
    {
        Console.Out.Write(string.Format("{0},", node.Data));
        if (node.Left != null)
          PrintDfsRecursiveInternal(node.Left);
        if (node.Right != null)
          PrintDfsRecursiveInternal(node.Right);
    }
 
    internal void PrintDfsRecursive()
    {
      Console.Out.WriteLine("Printing tree using recursive DFS algorithm");
      PrintDfsRecursiveInternal(Root);
      Console.Out.WriteLine();
    }
Now what about implementing BFS using recursion. Well, I read a bit online and I tend to believe that it is impossible to do it in O(1) extra space therefore I will show a solution with O(n) extra space. Before I present my solution I would like to note a solution I found online here:
BFS(Q)
{
  if (|Q| > 0)
     v <- Dequeue(Q)
     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}

There is something very bad in this solution (and in fact all other solution I saw). Because the recursive call is at the end of the method the recursion level is O(n) while the recursion level of the DFS algorithm is only O(log(n)). Considering the fact that opening a stack frame is somewhat expensive, this makes a major difference.


My solution uses the regular DFS traversal but ignores the nodes from the DFS order and calculated the nodes from the BFS order passed by the queue to the recursive method.
 internal void PrintBfsRecursive()
    {
      Console.Out.WriteLine("Printing tree using recursive BFS algorithm");
      Queue<TreeNode> queue = new Queue<TreeNode>();
      queue.Enqueue(Root);
      PrintBfsRecursiveInternal(queue, Root);
      Console.Out.WriteLine();
    }
 
    private void PrintBfsRecursiveInternal(Queue<TreeNode> queue, TreeNode node)
    {
      if (queue.Count > 0)
      {
        TreeNode tempNode = queue.Dequeue();
        Console.Out.Write(string.Format("{0},", tempNode.Data));
        if (tempNode.Left != null)
          queue.Enqueue(tempNode.Left);
        if (tempNode.Right != null)
          queue.Enqueue(tempNode.Right);
      }
 
      if (node.Left != null)
        PrintBfsRecursiveInternal(queue,node.Left);
      if (node.Right != null)
        PrintBfsRecursiveInternal(queue, node.Right);
    }
As you can see I used the DFS traversal only as a counter for the iterative BFS algorithm but this saves me the exponential increase in stack size.

In any case, if you are interested in CS problems (not riddles) I suggest checking out this site: Project Euler (if you want to collaborate with me on this please email me)

Thanks for reading,
Boris.