Mixins and Traits in C# 3.0

Hi there!

Since C# 3.0 it’s possible to create extension methods. You can regard an extension method as a method that you can add to a class, without even touching it. This might come in handy when you are using an API and have no direct access to the class code. If you wish to do some very important stuff with a certain class but can’t modify the code; extension methods to the rescue!

Suppose I want all my string to be able to shout. “Hello world” is cool, but “HELLO WORLD” is understood by grandma. So we just create a new ShoutableString object and let that inherit from String. We add the Shout method to the class et voila, we can shout.  You might run into some problems when you have other methods and/or classes that return a regular String. You just cast them et voila, you can shout!

Yeah, no. Extension methods you say?

Have you ever used a Tools.cs class or something? A few static utility methods that just *do* stuff to input and return it? Well, extension methods to the rescue. Suppose I want to make my string shoutable:

All you do is create a static class (e.g. “ExtraStringMethods“) and insert the methods you want there:

static class ExpressionMethods
{
    public static string Shout(this string input)
    {
        return input.ToUpper();
    }
}

Well great you say, another utility class. No, not really. Notice the this string” in the input part of the Shout method. This let’s the compiler know that your string objects now have access to this method, just like it would be any other instance method! At compile-time the compiler translates this code to a call to a static method. However, you don’t really care because it’s just sitting there in your intellisense.

In a class, far far away we want to use this stuff. How?  Simple, just import/use using ExpressionMethods; and you will have the methods at your disposal!

    class Program
    {
        static void Main(string[] args)
        {
            var regular = "hello world";
            var shouted = regular.Shout(); //Shouted now equals "HELLO WORLD"
        }
    }

Yeah sure. Cool. What if I want two objects to use the same mixin? It’s not fair I can only use it one type 😦

Marker interfaces! When you DO have access to the class sources you can do a nifty little thing. Suppose I have a User object somewhere, and some other very important objects.
I want all of these methods to be able to write to the console (e.g. log a message for debugging purposes). Well, give them a mixin! But how?

First we use a marker interface (you have read it, didn’t you?) ILog. This just “tags” our classes as loggers.

 interface ILog {}

Tagging our classes is as simple as this:

    class User : ILog
    {

        //This user should be able to log
    }
    class VeryImportantObject : ILog
    {
        //This object should be able to log as well
    }

Awesome, now we have two classes that implement Ilog, but actually don’t do anything special. Now, back to our extension methods.  How do we create a method that works for both these classes? Simple! Remember the this string from last time? We just put ILog there now.

    static class LoggerMethod
    {
        public static void LogMsg(this ILog obj, string msg)
        {
            Console.WriteLine(msg);
        }
    }

Note that the obj parameter is actually a reference to the object you called the method on. So you have access to it’s public members!

So what can we do now? Well we can log stuff really.

        static void Main(string[] args)
        {
            var u = new User();
            u.LogMsg("User doing some important stuff!");

            var io = new VeryImportantObject();
            io.LogMsg("Very imporant object getting moved around!");
        }

Quick note(s):

I have played around with multiple methods with the same name but in other extension methods. This throws:

Error    1    The call is ambiguous between the following methods or properties: ‘LoggerMethod.LogMsg(Mixins_Extension_Methods.ILog, string)’ and ‘BetterLoggerMethod.LogMsg(ILogBetter, string)’   Program.cs    82    13    Mixins Extension Methods

So be careful when implementing multiple mixins!

Also, you can add state to these mixins as well. That’s why I call them mixins instead of traits. However, I personally find the approach a bit cumbersome.
You can simply add static private properties to your Mixin static class (e.g. LoggerMethod) and create getters and setters for them in that same class.

All source code can ben found on BitBucket!

Have fun!

Advertisements

Pattern Matching Algorithms

Hi there!

I’ve implemented some pattern matching algorithms in C#. They were part of a course I took at the university I study at. They are therefore hardly optimized for real life usage. They do represent the conceptual idea of the algorithms.

The algorithms I implemented are Knuth-Morris-Pratt, Quicksearch and the brute force method.

Brute force method

The brute force method is quite simple. We align our pattern with the text and every time we have a mismatch we shift our pattern one step to the right. This is very bad performance wise. Worst case we will match every letter of our text with every letter of our pattern, which equals to 0(np*nt). Imagine this for a text of 1m characters and pattern of 100.000 characters. This method is good enough for very small text and patterns but as you’ll see, the complexity of other algorithms is hardly bigger. The code is quite straight forward and given below.

Code:


        public static int BruteForce(string text, string pattern)
        {
            var nt = text.Length;
            var np = pattern.Length;

            var it = 0;
            var ip = 0;

            while (it < (nt - np))             {                 if (ip > (np - 1))
                {
                    return it;
                }
                if (it > (nt - np))
                {
                    return -1;
                }
                if (text[it + ip] == pattern[ip])
                {
                    ip++;
                }
                else
                {
                    it++;
                    ip = 0;
                }
            }
            return -1;
        }

Knuth Morris Pratt

This algorithm is rather difficult to explain in a simple blog post. So bear with me as I try. The algorithm fully depends on the sigma-function. This function will return the largest prefix of the pattern, that is also a suffix of the part of the pattern that we have already matched. This is quite crucial to understand. Take a look at the image below.

KMP

As you can see we have mismatch at the character ‘x’ and ‘a’. Using the bruteforce method we would just shift our pattern one step to the right. So the first ‘a’ would align with the second ‘b’ of our text. What KMP will do, is calculate the sigmafunction. You can see in the image, a suffix of the last ‘a’ in our pattern is ‘ab’ for example. ‘aab’ is one too but you’ll get it in a minute. This ‘ab’ is also a prefix of our pattern. Meaning, if we shift our pattern just the length of that pre- and suffix, we don’t have to match those characters anymore. Because we know for certain that all the characters before our mismatch matched. So we will shift the pattern as you can see in the image. And this is the idea behind the sigma function. Once you got it, it’s a very simple algorithm.

The code:

        private static int[] SigmaTable(string pattern)
        {
            //We will calculate the longest prefix of 0->ip that is also a prefix of the pattern

            var np = pattern.Length;
            var sigmatable = new int[np];

            var ip = 2;
            var k = 0;

            while (true)
            {
                if (ip >= np)  //We have shifted out of our pattern, we are done.
                    break;
                if (pattern[k] == pattern[ip - 1])//Our prefix extends
                {
                    sigmatable[ip] = (k + 1);
                    ip++;
                    k++;
                    continue;
                }
                if (k > 0)//We have a mismatch, so we need to see if we have a smaller prefix that we can use
                          //We already calculated this, so just get it.
                {
                    k = sigmatable[ip];
                    continue;
                }
                //We have a mismatch, but K = 0, so we dont have a prefix.
                sigmatable[ip] = 0;
                ip++;
            }
            sigmatable[np - 1] = k;
            sigmatable[0] = -1;
            return sigmatable;
        }

The actual algorithm

 public static int Kmp(string text, string pattern)
        {
            var nt = text.Length;
            var np = pattern.Length;
            var sigmatable = SigmaTable(pattern);

            var it = 0;
            var ip = 0;

            //We will keep looping, untill
            //-->We have found a match (ip > (np -1)
            //--> We have shifted out of our text, not found (it > (nt -np))
            //We have match, step forward in the pattern!
            //We have a mismatch, jump back as much as the sigmatable tells us.

            while (true)
            {
                if (ip > (np - 1))
                {
                    return it;
                }
                if (it > (nt - np))
                {
                    return -1;
                }
                if (text[it + ip] == pattern[ip])
                {
                    ip++;
                    continue;
                }
                it = (it + (ip - sigmatable[ip]));
                ip = ip > 0 ? sigmatable[ip] : 0;
            }
        }

Quick Search

This is my personal favorite for two reasons: 1) it’s fast and 2) it’s everything but difficult!

This algorithm too, will do some preprocessing, although not as difficult to explain as KMP. What we will do is, for every character in the pattern, store the left most location in the pattern. E.g “abcabcd” will have 1 for a, 2 for b, 3 for c and 7 for d. Now, when we have a mismatch, what we will do is take the first character that comes after the entire pattern in the text. So in our picture above, we would take ‘y’. We then check to see if this character exists in our pattern. If it does not, we don’t even have to try matching, we skip it entirely, i.e shift the beginning of our pattern past that character (see the performance?). If it does exist, we shift our pattern the value of our table to the right and start matching from scratch.
We don’t know if our first characters will match, but we do know there is going to match one. The performance boost this algorithm gets is from the parts where we can skip characters that don’t exist in our pattern.

The code:

        private static ShiftTable ComputeShiftTable(string pattern)
        {
            //We will just calculate the position of every character in the pattern. We then store the most right location.

            int[] shift_table;

            int minAscii = pattern[0];
            int maxAscii = minAscii;

            var idx = 0;
            //First we calculate the lowest and highest ascii value to create our array
            while (idx < pattern.Length)
            {
                minAscii = Math.Min(minAscii, pattern[idx]);
                maxAscii = Math.Max(maxAscii, pattern[idx]);
                idx++;
            }

            shift_table = new int[maxAscii - minAscii + 1];

            //Loop over the table and store our patternlength in it. (If we dont find the character, we have to shift the entire pattern!).
            for (int i = 0; i < shift_table.Length; i++)
                shift_table[i] = pattern.Length + 1;

            //Loop over the pattern again. For every char we update it's position in the array.
            //This way, we always have the leftmost character in the array.
            idx = 0;
            while (idx < pattern.Length)
            {                 
                 int currentascii = pattern[idx];                 
                 shift_table[currentascii - minAscii] = pattern.Length - idx;                 
                 idx++;             
            }             
            return new ShiftTable(shift_table, maxAscii, minAscii, pattern.Length);         
} 

The algorithm

         
public static int QuickSearch(string text, string pattern)         {             
       var nt = text.Length;             
       var np = pattern.Length;             
       var shift = ComputeShiftTable(pattern);             
       var it = 0;            
       var ip = 0;             
       while (true)             {                 
                if (ip > (np - 1))//We shifted out of our pattern, found!
                {
                    return it;
                }
                if (it > (nt - np))//We reached the end of our text with our pattern, not found!
                {
                    return -1;
                }
                if (text[it + ip] == pattern[ip])//We have a match, continue.
                {
                    ip++;
                    continue;
                }
                //We didnt have match, get the first character next to our pattern, and calculate the shift back.
                var ct = text[(it + np)%nt];

                it = (it + shift.Shift(ct));
                ip = 0;
            }
        }

That’s it!

Christophe,

Basic Sorting Algorithms

Hi,

I’m studying for my master’s degree at the moment and in my spare time I rebuilt some of the basic sorting algorithms I learned. There are many more, but I wrote a few of them to gain some insight and because it’s fun :). The algorithms are far from optimized for real-life usage, but the mechanics are correct.

I built the following algorithms:

  • Bubble sort
  • Insertion sort
  • Merge sort
  • Quicksort
  • Quicksort with median 3
  • Randomized Quicksort

All the algorithms are built in such a way that they can sort any object type. To make this possible I used delegates to pass to the algorithms so they can extract the properties of the object that you need to sort on. To show how it works I’ve added a testing solution. It’s a simple console application that sorts arrays of given size and times how long it takes the algorithm to finish.

The source code can be found on Github, or in the downloads (top navigation bar).

If you have any questions, comments are open! 🙂

,Christophe

Notify Icon C#

Hi there,

I’ve been building an application that shows that little yellow balloon in the right corner (your system tray). I just wanted to share how I accomplished it.

notify

1. First of all you need to instantiate an object NotifyIcon

You can give NotifyIcon an icon that shows in the system tray by adding any .ico file to a Resource file in your project. You can then reference this resource file. An other important property of the object is the .Visible property. This tells the icon.. if it’s visible in the system tray. You also might want to add a handler to the .DoubleClick. I’ve done this to show a dialog to change settings of the little program in question.

_notifyIcon = new NotifyIcon { 
              Icon = Mail_Checker.Resources.Icons.mail, 
              Visible = false 
                             };
_notifyIcon.DoubleClick += ToggleSettingsDialog;


//The handler
private void ToggleSettingsDialog(object e, EventArgs ea)
{
    if (WindowState == WindowState.Minimized)
    {
        this.Show();
        this.WindowState = WindowState.Normal;
        _notifyIcon.Visible = false;
    }
    else
    {
        this.WindowState = WindowState.Minimized;
        this.Hide();
        _notifyIcon.Visible = true;
    }
}

2. Adding a right-click menu

To add a right-click menu to a notifyicon you have to create two objects. A MenuItem and a ContextMenu.

The contextmenu is the actual menu itself, and every option in that menu has to be added manually. So first, let’s create a quit-item for the menu.

//Initialize quit-option in menu 
_menuItemQuit = new MenuItem
                {
                    Index = 0,
                    Text = "Quit"
                };
_menuItemQuit.Click += MenuItemQuitClick;

Next, we want to add that to the (not yet created) contextmenu so let’s do that now. As you can see, you need to cast the menuitem to an array, since the contextmenu usually takes more than 1 menu item.

//Configure contextmenu for notifyicon
_notifyIconContextMenu = new System.Windows.Forms.ContextMenu();
_notifyIconContextMenu.MenuItems.AddRange(
                                         new[] { _menuItemQuit }
                                         );

And at last add that contextmenu to your notifyicon:

_notifyIcon.ContextMenu = _notifyIconContextMenu;

Now, to show a balloontip during runtime it’s as simple as calling ShowBalloonTip. The parameters below are the time-out (time it will display), the title, the message itself and the icon it shoud be given.

_notifyIcon.Visible = true;
_notifyIcon.ShowBalloonTip
    (5000, "Mail Checker", "Check your inbox, sir!", ToolTipIcon.Info);

Source code for the little program I built can be found on Github. Mail Notifier C# @ Github