Thursday, October 13, 2011

Persisting a GridSplitter

Hi All,

If you are using WPF then you probably use the Grid container and if you are using that then at times you surely need the assistance of the GridSplitter. The GridSplitter is a sub element of the Grid and it allows the user to conveniently resize the grid columns or rows. Those of you who worked with the GridSplitter know that it is quite challenging to work with correctly.

I will start with a small example. In my application I need a vertical splitter between two buttons (conveniently named Left and Right). The initial size of the Left button should be twice the size of the Right button. Here is the XAML:

  1. <Grid>
  2.     <Grid.ColumnDefinitions>
  3.         <ColumnDefinition Width="2*"></ColumnDefinition>
  4.         <ColumnDefinition Width="Auto"></ColumnDefinition>
  5.         <ColumnDefinition Width="*"></ColumnDefinition>
  6.     </Grid.ColumnDefinitions>
  7.     <GridSplitter Width="5" Background="Red" VerticalAlignment="Stretch" HorizontalAlignment="Center" Grid.Column="1"></GridSplitter>
  8.     <Button Grid.Column="0">Left</Button>
  9.     <Button Grid.Column="2">Right</Button>
  10. </Grid>

And this is the result:

p2

I am using a technique where the GridSplitter sits in its own column. I find this approach better since then you don’t need to think how it should be position within the column or within the XAML file.

The problem with the GridSplitter becomes apparent when you try to use fixed sizes in the grid column width (the same applies for grid row height but I will continue the discussion with the grid columns). What if we want the left column to start with a fixed size of 5cm on the screen. The logical thing to do would be to set the width of the first column to 5cm. If you do that and run the application everything would seem normal until you start dragging the GridSplitter. Try dragging it to the right… way right… past the window border right… now let go and try to drag it back. That’s right. The GridSplitter is gone! I read somewhere on the Internet that the grid splitter does exactly what I told it to do. If you believe that then try to do the same with the right column and dragging the GridSplitter left. The phenomenon here is even stranger.

  1. <Grid>
  2.      <Grid>
  3.          <Grid.ColumnDefinitions>
  4.              <ColumnDefinition Width="*" ></ColumnDefinition>
  5.              <ColumnDefinition Width="Auto"></ColumnDefinition>
  6.              <ColumnDefinition Width="5cm" ></ColumnDefinition>
  7.          </Grid.ColumnDefinitions>
  8.  
  9.          <GridSplitter Width="5" Background="Red" VerticalAlignment="Stretch"
  10.     HorizontalAlignment="Center" Grid.Column="1"></GridSplitter>
  11.          <Button Grid.Column="0">Left</Button>
  12.          <Button Grid.Column="2" >Right</Button>
  13.      </Grid>
  14.  </Grid>

Don’t do that… Its crazy!

The point I am trying to make here is that the GridSplitter is best used when the widths of the column are star based. You can have some control using the MinWidth and MaxWidth properties applied on the columns, but sometimes this behavior is not the desired one.

Now for the main challenge. I want my application to restore the state of the GridSplitter position next time it is run. For example if I move the GridSplitter such that only the Right button is visible and close the application. When I start the application I expect only the Right button to be visible. Actually doing this is quite simple. I add x:Name attributes to the grid columns and handle the DragCompleted event of the GridSplitter. In the handler I serialize the width properties of both columns into a file. The problem here is that the Width is not a simple double value but a struct (GridLength). Fortunately, the framework provides us with a small helper class to serialize and deserialize this struct called GridLengthConverter. The serialization code looks like this:

  1. Assembly assembly = Assembly.GetExecutingAssembly();
  2. String directory = System.IO.Path.GetDirectoryName(assembly.Location);
  3. using (StreamWriter writer = new StreamWriter(Path.Combine(directory, "width.txt")))
  4. {
  5.   GridLengthConverter converter = new GridLengthConverter();
  6.   writer.WriteLine(converter.ConvertToString(LeftColumn.Width));
  7.   writer.WriteLine(converter.ConvertToString(RightColumn.Width));
  8. }

and the deserialization code is therefore like this:

  1. Assembly assembly = Assembly.GetExecutingAssembly();
  2. String directory = System.IO.Path.GetDirectoryName(assembly.Location);
  3. if (File.Exists(Path.Combine(directory, "width.txt")))
  4. {
  5.   using (StreamReader reader = new StreamReader(Path.Combine(directory, "width.txt")))
  6.   {
  7.     GridLengthConverter converter = new GridLengthConverter();
  8.     LeftColumn.Width = (GridLength)converter.ConvertFromString(reader.ReadLine());
  9.     RightColumn.Width = (GridLength)converter.ConvertFromString(reader.ReadLine());
  10.   }
  11. }

(it is run after InitializeComponents).

The important thing to notice here is that you must serialize both column width because they are relative to each other.

That’s it for today. Thank you for reading.

Boris.

Tuesday, September 27, 2011

Writing an Extensible Application – Part 2: Extensibility by Reflection

 

Hi,

This time I will present a very primitive (yet somehow effective) extensibility method: Extensibility by Reflection. This method is good when you don’t want to over complicate things and all you need is a simple way to extend some specific types. This method is based on the Reflection mechanism of .Net (as the name suggests).

Let’s make a short recap of the previous post. I have made a small application that simulates balls within an enclosed rectangular area. Each ball has three “properties”: The Collider, the Mover, and the Drawer. The UI allows the user to select each of the aforementioned properties from a list and create a ball using these properties. The most important thing I did was to design the application in an extensible way. The main application uses all the data through interfaces which are defined in an external DLL (BallsInterfaces.dll).

I have created an additional project which represents the extensibility client (a dll your user would write). For coherence, I have moved all the basic types to that dll and now all of our colliders, drawers, and movers will be loaded through extensibility. I changed the build target path of the new project to be inside <Main project dir>/Extensibility. In the main project I have added the following key to the application settings:

  1. <appSettings>
  2.   <add key="ExtensibilityPath" value="Extensibility"/>
  3. </appSettings>

From this point things are quite simple. All we have to do is to load all the DLLs from the defined path and in each such DLL find and instanciate any class that inherits from ICollider, IMover, or IDrawer interfaces. The following code does just that:

  1. private void LoadExtensibility()
  2. {
  3.   Assembly applicationAssembly =  Assembly.GetAssembly(GetType());
  4.   string extensibilityPath = System.IO.Path.Combine(System.IO.Path.GetDirectoryName(applicationAssembly.Location), ConfigurationManager.AppSettings["ExtensibilityPath"]);
  5.   string[] dllFiles = System.IO.Directory.GetFiles(extensibilityPath, "*.dll");
  6.   foreach (string fileName in dllFiles)
  7.   {
  8.     Assembly currentAssembly =  Assembly.LoadFile(fileName);
  9.     Type[] innerTypes = currentAssembly.GetTypes();
  10.     foreach (Type t in innerTypes)
  11.     {
  12.       if (t.IsClass && t.IsPublic)
  13.       {
  14.         if (t.GetInterfaces().Contains(typeof(ICollider)))
  15.         {
  16.           Colliders.Add(new StrategyAdapter(t));
  17.         }
  18.  
  19.         if (t.GetInterfaces().Contains(typeof(IMover)))
  20.         {
  21.           Movers.Add(new StrategyAdapter(t));
  22.         }
  23.  
  24.  
  25.         if (t.GetInterfaces().Contains(typeof(IDrawer)))
  26.         {
  27.           Drawers.Add(new StrategyAdapter(t));
  28.         }
  29.  
  30.       }
  31.     }
  32.   }
  33. }

A few things worth mentioning:

  1. I have added three ObservableCollections named – Colliders, Movers, and Drawers and hooked them up with the ComboBoxes in the application.
  2. Each observable collection contains an adapter class (StrategyAdapter) which mitigates the extensible type with the instance creation. It also provides the Name property for display within the ComboBoxes. The StrategyAdapter code is as follows:
  1. public class StrategyAdapter
  2.   {
  3.     
  4.     protected Type _innerItemType;
  5.     public string Name
  6.     {
  7.       get
  8.       {
  9.         if (_innerItemType != null)
  10.         {
  11.           return _innerItemType.Name;
  12.         }
  13.         return "Null";
  14.  
  15.       }
  16.       
  17.     }
  18.     public StrategyAdapter(Type itemType)
  19.     {
  20.       _innerItemType = itemType;
  21.     }
  22.  
  23.     public T CreateInstance<T>() where T:class
  24.     {
  25.       return Activator.CreateInstance(_innerItemType) as T;
  26.     }
  27.   }

And from this code you may infer that the ball creation code becomes:

  1. Ball ball = new Ball(SelectedMover.CreateInstance<IMover>(), SelectedCollider.CreateInstance<ICollider>(), SelectedDrawer.CreateInstance<IDrawer>(), _environment);

To extend this example I have added three new implementations of the extensibility interfaces:

  1. The Parabolic Mover – It moves the ball as if there was gravity (i.e. with acceleration).
  2. The Blinker Drawer – It creates a slightly bigger red ball that slowly disappears and then instantly reappears.
  3. The Stopper Collider – It stops the other ball on the spot after collision.

As usual, you can download the sources from my SkyDrive -

I want to take this opportunity to say שנה טובה וחג שמח to all my Jewish friends. Nice and fun 国庆节 to all my Chinese friends, rest and spend time with your families. Happy Friday to all my Pastafarian friends (since every Friday is a holyday!).

Thanks for reading,

Boris.

Friday, September 16, 2011

Yet Another Blog Post About Windows 8 – YABPAW8

 [Edit: You can find a more in depth information on Shasha Goldshtein blog who actually attends the convention. See the links on the right.]

Hi All,
Well, this is somewhat unexpected but even I cannot ignore the recent arrival of Windows 8 preview. Microsoft has created so much hype and rumors about their new OS that even I had to go against my rule – “Never come near Microsoft beta products” – and check it out. Before this release there were many speculations about which direction Microsoft is going to take. Most of those were based on a 4 minute video and various presentation shown in conventions (and a certain leaked build that could be found on the torrents). I heard ludicrous things like “Microsoft has rewritten the entire OS in JS and HTML 5” and somewhat worrying assumptions that .Net will no longer be supported. From looking at the preview version of Windows 8, the vast majority of these rumors and speculations is not at all close to reality.
Here is a summary of my very brief experience with Windows 8. Note that I might missed important things so you can always mention them in the comments.


Installation
The installation was quite simple. I installed Windows 7 on another machine just a couple of days ago and I must say that the Windows 8 installation is much shorter and doesn’t require restarts. Nevertheless, it looks exactly like the installation of Windows 7 (at least until the post installation steps). At the beginning the installation asked if I want to upgrade my existing installation which was interesting since I was installing on a clean machine. In the post installation I was asked to enter my Live ID and after I did everything was connected and my Windows user was my Live ID. I think it is safe to guess that in the real version they will have a way to create a regular user and connect to domains (at least for the Enterprise versions).


The new UI
Once you log on to the new Windows you are immediately thrown into the new Metro UI.p1


It looks and feels very nice and it is easy to find and activate each application. Although there was one thing that bothered me. It seems that it wasn’t designed for a mouse control because you cannot drag it left and right (I hope this will be added in the release). Instead you can use a small scrollbar on the bottom of the screen or the mouse wheel to scroll. As you can see in the screenshot, Metro style applications may use the new Tiles API while other application get a default tile that shows the application name and title. I tried to run some Metro applications and found nothing really special about them. They run on full screen without windows and have a common menu style that is similar to Windows Phone and can be activated by a right-click. There was one annoying thing that I experienced. It seems that Microsoft designed the applications for tablets or something because for the hell of me I couldn’t find an “Exit” button anywhere! Eventually I had to close each application using the Task Manager since Alt+F4 didn’t close them either (and trust me I know how to exit VIOpen-mouthed smile). Good thing that Windows button works during these applications and you can easily go back to the desktop.


p2


The Old UI
The nice surprise comes when you click the Desktop tile (or Windows button or Windows + D that still works). You are flung into the familiar Windows desktop (using a strange Skew effect from the 90’s which, I hope, can be somehow modified) and there you can see some subtle changes that I feel will make working with Windows somewhat simpler. As published, the Ribbon has spread into the Windows Explorer and all the important functions were externalized. This makes work somewhat simpler since you don’t need to rely on the context menus or the hidden main menu so much.
p3
There is still a strange Start button which, when clicked, throws you back into the Metro UI. Sometimes it shows this (see screenshot) ugly black menu and huge time display when you hover over it (sometimes it shows the very important tooltip “Start”).
An even nicer surprise was the new Task Manager (which I had to use quite a lot, see previous section) which has a brand new UI that shows all the important information in a nice colorful way. You can now easily see all the significant counters and have easy access to the Performance UI (which was hidden in Windows 7) and the graphs. Other than that the UI felt unchanged from Windows 7 in both the look and feel and the behavior.

Visual Studio Express (Preview Edition)
I tried out the new Visual Studio (a.k.a. vNext) and didn’t find any surprises there (although this is the Express version and I didn’t want to install the Ultimate version, yet). It looks exactly like VS2010 with no apparent significant changes. I think the most important change is that they finally cleaned out the default toolbars and left only the most important commands there. Other than that, from what I could find from my short experience with vNext, the major changes are:
  • Moved the Quick Access window (Control+3 in VS2010) to a static toolbar item.
  • Renamed Solution Navigator to Solution Explorer (I think the original Solution Explorer was removed).
  • Removed Quick Find.
(And no, they didn’t fix the most annoying bug ever where you can’t “Find In Files” if the editor is not open!)
In the short time I tested vNext I tried to create a small Metro application in WPF. Couldn’t see anything new here. There were some strange things (a project that has no references but still compiles with no problems) but everything seems to work as I am used to. By the way, I couldn’t find an “Exit” button on the default template of the Metro application either. Which makes me believe that there is some key I can click to close the applications.


Conclusion
From my very brief experience with the new Windows 8 I can say that there are quite many new things and concepts but it is certainly not a revolution. The Metro UI looks promising for the average user but it seems to target mostly tablets and not regular PCs that still use keyboard and mouse to interact with the interface. Once you go back to the Desktop the experience is not much different than Windows 7 except for the many UX improvements and additions. As a developer I didn’t find anything interesting in vNext but I checked only this Express Preview version and there are probably some surprises hiding inside (at least I hope so). I am looking forward to see what Microsoft has in its sleeve for the release.

Have a nice day,
Boris.

P.S.
This blog post was written on my Windows 7 PC.

Saturday, September 10, 2011

Writing an Extensible Application - Part 1

Hi All,


In the next posts I will try to examine some simple ways to make your application extensible. Most of the applications we use in our daily life have some form of extensibility. For example the Visual Studio has add ins, extensions, packages and other forms of extensibility which allow you integrate your own functionality to an existing application. For the purpose of our discussion I will define extensibility of an application simply as adding new application functionality without having to recompile any part of the application.

I will demonstrate briefly several simple ways to make your application extensible. To this end I have prepared a demo project (in fact, this post will discuss only this demo project).

The Balls Simulation

The demo project might be familiar to some of my readers since I take it from the new employee training program of my previous job. The application contains a rectangular area called "field". The user adds entities to that field called "balls" and they move inside the field. The balls may collide with each other during the movement within the field and they have to react accordingly. The balls may also collide with the walls and react accordingly.

A screenshot from my demo application
The most important part of writing an extensible application is to decide how the user will be able to extend it. In the case of my application the user will be able to extend the ball behavior using three aspects:

  • Movement - Determines how the ball is going to move around the field.
  • Drawing - Determines how the ball is going to be drawn on the filed.
  • Collision - Determines how the ball will react to a collision with another ball.
Now that I decided that these three items are my extensibility points I need to decide on the design of the application. I chose to implement it using the strategy design pattern. Each of the three elements mentioned above will have a strategy object which will be assigned to a ball. (The ball will be composed of the three element.) Now that this is decided I can define a dll that will be given to the extension writers, clients, which will contain the required interfaces. You don't want to give your clients a bulky dll that will contain all the classes and the logic but a thin layer which will not confuse them but will allow to write a complete extension set.

The interfaces I defined are:
  1. public interface IMover
  2. {
  3.   void Tick(IBall ball);
  4.   void Initialize(IBall ball);
  5.   void AtWalls(IBall ball, HashSet<WallType> wallTypes);
  6. }
 
  1. public interface IColider
  2. {
  3.   void AfterCollision(IBall ball, IBall other);
  4.   void BeforeCollision(IBall ball, IBall other);
  5.   void Collision(IBall ball, IBall other);
  6. }
 
  1. public interface IDrawer
  2. {
  3.   void Tick(IBall ball);
  4.   void Initialize(IBall ball);
  5. }
 
At this point I want to dedicate a short passage on coding games. The basic design of a game contains a game timer that paces the game. The game timer activates as fast as possible but sometimes it is limited to a specific frame rate - FPS (Frames Per Second). Each time the timer activates is called a game "tick". In each tick the game manager iterates on all the entities within the game (called "sprites") and calls a method that updates their inner parameters. Then the game manager iterates on all the sprites again and draws them on the screen.

As you can see I am using a 3 method collision handling. This method will not cover all the collision cases but it is good enough for many basic games including this demo application. The rules are simple: When two balls collide then the three collision methods are called one by one on each ball with an alternating order (see the code snippet next). On the BeforeCollision method the current ball can gather and data it needs from the other ball but it is not allowed to change its own data. On the Collision method the ball may change any of its parameters based on the data collected in the BeforeCollision method. On the AfterCollision method each ball may set any parameters on the other ball but not on itself.


Putting every thing mention above into code, results in the following Tick method of the timer:





  1. #region Handle Movement
  2. foreach (Ball ball in _balls)
  3. {
  4.   ball.Move();
  5.  
  6.   HashSet<WallType> hitWalls = new HashSet<WallType>();
  7.  
  8.   if (ball.Left <= 0)
  9.     hitWalls.Add(WallType.Left);
  10.  
  11.   if (ball.Top <= 0)
  12.     hitWalls.Add(WallType.Top);
  13.  
  14.   if (ball.Right >= MainCanvas.ActualWidth)
  15.     hitWalls.Add(WallType.Right);
  16.  
  17.   if (ball.Bottom >= MainCanvas.ActualHeight)
  18.     hitWalls.Add(WallType.Bottom);
  19.  
  20.   if (hitWalls.Count > 0)
  21.     ball.AtWalls(hitWalls);
  22. }
  23.  
  24. #endregion
  25.  
  26. #region Handle Collision
  27. for (int i = 0; i < _balls.Count; i++)
  28. {
  29.   for (int j = i + 1; j < _balls.Count; j++)
  30.   {
  31.     if (IsColliding(_balls[i], _balls[j]))
  32.     {
  33.       _balls[i].BeforeCollision(_balls[j]);
  34.       _balls[j].BeforeCollision(_balls[i]);
  35.       _balls[i].Collision(_balls[j]);
  36.       _balls[j].Collision(_balls[i]);
  37.       _balls[i].AfterCollision(_balls[j]);
  38.       _balls[j].AfterCollision(_balls[i]);
  39.     }
  40.   }
  41. }
  42. #endregion


(Note that in this first version the Drawer is not used but you will see it in play in the next post)


The main object of the game is the Ball class. It is exposed to the client as an interface and the client may interact with this class through the interface. All the Ball logic is managed within the class itself, feel free to browse the code there after downloading the demo application.


The application UI is quite simple. The field is on the left side. On the right side there are three combo boxes which will allow you to select the relevant strategy objects and a create button that generates a ball with the selected strategy objects. Both the Mover and the Drawer have Initialize methods that are called once the ball is created to allow the client position and draw the ball for the first time. Note that for this initial stage of the application the combo boxes are not used (since there is no extensibility yet) and the create button creates a small blue ball that just moves around and bounces off walls and other balls.


I encourage you to try out the code to get the feel of it before diving into the extensibility part in the next posts.


You can download the code from my SkyDrive here:


 


Thank you for reading,


Boris.


 


P.S.


Thanks to David Elentok you can see that the formatting is improved a little. I hope to improve it even more in future posts.

Friday, September 9, 2011

Writing an Extensible Application - Part 1

Hi All,


In the next posts I will try to examine some simple ways to make your application extensible. Most of the applications we use in our daily life have some form of extensibility. For example the Visual Studio has add ins, extensions, packages and other forms of extensibility which allow you integrate your own functionality to an existing application. For the purpose of our discussion I will define extensibility of an application simply as adding new application functionality without having to recompile any part of the application.


I will demonstrate briefly several simple ways to make your application extensible. To this end I have prepared a demo project (in fact, this post will discuss only this demo project).


The Balls Simulation


The demo project might be familiar to some of my readers since I take it from the new employee training program of my previous job. The application contains a rectangular area called "field". The user adds entities to that field called "balls" and they move inside the field. The balls may collide with each other during the movement within the field and they have to react accordingly. The balls may also collide with the walls and react accordingly.
A screenshot from my demo application
The most important part of writing an extensible application is to decide how the user will be able to extend it. In the case of my application the user will be able to extend the ball behavior using three aspects:


  • Movement - Determins how the ball is going to move around the field.
  • Drawing - Determins how the ball is going to be drawn on the filed.
  • Collision - Determines how the ball will react to a collision with another ball.
Now that I decided that these three items are my extensibility points I need to decide on the design of the application. I chose to implement it using the strategy design pattern. Each of the three elements mentioned above will have a strategy object which will be assigned to a ball. (The ball will be composed of the three element.) Now that this is decided I can define a dll that will be given to the extension writers, clients, which will contain the required interfaces. You don't want to give your clients a bulky dll that will contain all the classes and the logic but a thin layer which will not confuse them but will allow to write a complete extension set.

The interfaces I defined are:

  public interface IMover
  {
    void Tick(IBall ball);
    void Initialize(IBall ball);
    void AtWalls(IBall ball, HashSet<WallType> wallTypes);
  }
  public interface IDrawer
  {
    void Tick(IBall ball);
    void Initialize(IBall ball);
  }

  public interface IColider
  {
    void AfterCollision(IBall ball, IBall other);
    void BeforeCollision(IBall ball, IBall other);
    void Collision(IBall ball, IBall other);
  }
At this point I want to dedicate a short passage on coding games. The basic design of a game contains a game timer that paces the game. The game timer activates as fast as possible but sometimes it is limited to a specific frame rate - FPS (Frames Per Second). Each time the timer activates is called a game "tick". In each tick the game manager iterates on all the entities within the game (called "sprites") and calls a method that updates their inner parameters. Then the game manager iterates on all the sprites again and draws them on the screen.

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.