A lousy tutorial to C# drag and drop

Drag and drop is a neat way to allow the user the "transfer" data into a winform control. Here's how to enable drag and drop in a windows form in C#:

1. Create your source and target controls. In this case we're using 2 ListViews where the one on the right (called listView1) is the source of the drag and the one on the left (called listView2) is target of the drop. However note that the source of the drag can even be from the windows explorer by drag dropping a file into the control.

2. Set the AllowDrop property of the control which will receive the drop to true.

3. Set up an event in the control which will be dragged from, that senses that a drag has been initiated, such as the ItemDrag event or the DragLeave event and call the DoDragDrop method. The DoDragDrop method is to be passed the data to be transferred (the object you want the receiving control to get).

4. Set up the DragOver event in the control which will be dropped on, to check if the data being dragged over can be accepted and change the cursor to an invalid cursor picture if not. You can check the type of the data being dragged by using the GetDataPresent method.

5. Set up the DragDrop event in the control which will be dropped on, to actually do something with the data once it has been dropped. This event will only fire if the DragOver event did not set Effect to None.

And there you have it. A lousy tutorial. However, here's something worth mentioning:

If you are transferring an object which could be one of several types and you want to view the object as its base type, then this will not work, as the GetData method will just return null if you pass it a base class for a type. The only was I found to get around this was by created a proxy object which will contain the object of interest casted as its base class, and then what you receive the proxy object in the receiving control you just get the object of interest from it. Like so:

Generic Genetic Algorithms

I have finally finished my C# generic genetic algorithm library which is based on my university thesis "A Generic Genetic Algorithm using Phenotype Building Functions" (http://www.scribd.com/doc/48697452/A-Generic-Genetic-Algorithm-using-Phenotype-Building-Functions). You can find it at http://code.google.com/p/genericga/. The wiki page explains how to use it.

Typocalypse

Lately me and my friend Andreas Grech (http://blog.dreasgrech.com/) developed jointly a Microsoft XNA game in just under a sleepless and coffee ridden 24 hours called Typocalypse which is a game where you have to type the words under zombies before they reach you.

My involvement in the game was in using my previous two blog posts, the biasing function for gradually increasing the difficulty of the game by gradually biasing the randomly chosen words to prefer longer words as the score increases and the trie for determining which zombies have a word which has a prefix that matches the currently typed text. I was also responsible for handling keyboard events, displaying the words under the zombies and sound effects which I created orally.

To give credit where credit is due, the background music was taken from the Amiga game The Great Giana Sisters, the pictures including the background image where found from google images and we couldn't be bothered with looking for them again and the library which enabled capturing of keyboard input was taken from here which was developed by George Mamaladze.

The game is open source and you can download and use the source code if you wish, but keep in mind that this was developed in under 24 sleepless hours so at some point coding started getting messy.

Link to the game is http://code.google.com/p/typocalypse/downloads/list.

Enjoy :)

C# Trie

*Update* I have developed a new an improved version of this data structure which you can find here.

For anyone interested, I have also written a Java Trie here.

In a recent project I have ventured into, I had to develop a set of classes in C# for a simple trie which are now released as open source (http://code.google.com/p/typocalypse/source/browse/#hg/Trie). This blog post shall describe how it works and how to use it.

Introduction to tries

Simple tries are a data structure for mapping strings to values such that it enables you to efficiently retrieve all the values whose key strings have a particular prefix. This works by storing all the strings in a tree where each node is a prefix to a number of strings and each edge is a character to append to the prefix in the parent node. The root node is the empty string which is a prefix to all strings.

As you traverse a path from the root downwards, you follow the edges which lead to prefixes of the string you are trying to match. Eventually if such a string exists, a node will be pointing to the value mapped by the string. By traversing the descendants of a particular node, you can retrieve all the stored strings which have that prefix in common and their corresponding value.

Here's a diagram example from wikipedia:
http://upload.wikimedia.org/wikipedia/commons/b/be/Trie_example.svg

Implemented trie

The implemented trie supports adding, removing and character-by-character prefix searching of string-value pairs.

The way it works is by keeping a reference in each node to a value object such that if the reference is null then the node does not point to a value object and hence the prefix is not a complete string. The type of the values is generic, any referencable type is allowed. Each node points to its children via a Dictionary object which maps characters to nodes, thereby allowing a fast search by following the characters.

The following is a description of each class:

TrieNode

This is a non-public class which represents the nodes of the trie, that is, the prefixes. However in this implementation, the prefix itself is not stored, only the last character of the prefix called the Key is stored in order to know which character was followed to access this node. It also stores the value (generic type), a pointer to the parent node and a dictionary which maps characters to children nodes. If this node terminates a string then it's value field points to an object, otherwise it is null.

PrefixMatcher

This is a non-public class which is dedicated to allow the user to search the trie for a particular string or strings with a particular prefix. It was designed for enabling the user to search for the values of said strings on a character by character basis rather than providing the whole string immediately so that it can be used to search for user input as the user types in the query. This requires the maintenance of a state so that it is known which prefix has been entered thus far as well as which node that prefix is found in so as to enable an efficient search. For this reason the search feature was kept in a class of its own. Each time the trie is modified with the removal of a string, the current search is cancelled and must be redone from first character so as to avoid the user from searching non-existent strings.

IPrefixMatcher

This is a public interface which abstracts the methods of the PrefixMatcher class so that the user is provided with an abstraction rather than a concrete class in order to search.

Trie

This is the main class which provides the features of the trie data structure. Searching is done through the public property "Matcher" which returns an instance of IPrefixMatcher. When a string is removed, the current search is cleared so as to avoid the user from searching non-existent strings.

Examples

Here is an example of how to use the implemented trie:

//Create trie
Trie < string > trie = new Trie < string > ();

//Add some key-value pairs to the trie
trie.Put("James", "112");
trie.Put("Jake", "222");
trie.Put("Fred", "326");

//Search the trie
trie.Matcher.NextMatch('J'); //Prefix thus far: "J"
trie.Matcher.GetPrefixMatches(); //[112, 222]
trie.Matcher.IsExactMatch(); //false
trie.Matcher.NextMatch('a');
trie.Matcher.NextMatch('m'); //Prefix thus far: "Jam"
trie.Matcher.GetPrefixMatches(); //[112]
trie.Matcher.NextMatch('e');
trie.Matcher.NextMatch('s'); //Prefix thus far: "James"
trie.Matcher.IsExactMatch(); //true
trie.Matcher.GetExactMatch(); //112

//Remove a string-value pair
trie.Remove("James");

Link to classes

http://code.google.com/p/typocalypse/source/browse/#hg/Trie