Chris Miceli

New DAAP Release!

Now that Windows 10 has launched, I felt that it was time to update the awful Windows 8 DAAP application. The Windows 8 version was a fast port of the much better phone version, but with worse UI. For the Windows 10 version, I decided to put a little bit more effort to emulate the Groove music application that ships as part of the OS. Here are some stills from the new Windows 10 version. Let me know what you think in the comments below.

The initial setup wizard

Albums

All songs

Search results

New features include:

Search support
Change server support
Windows 10 support
Refreshed look and feel

Web Optimization {version} pattern in bundles

While creating a website using Web Optimization to handle bundling, I became curious as to what the {version} pattern matched. I couldn't find documentation for this besides what it outlined here:

The bundling framework follows several common conventions such as:
•Selecting “.min” file for release when “FileX.min.js” and “FileX.js” exist. 
•Selecting the non “.min” version for debug.
•Ignoring “-vsdoc” files (such as jquery-1.7.1-vsdoc.js), which are used only by IntelliSense.

Digging into the source code here, I was able to find exactly what {version} matches, the C# regex @"(\d+(\s*\.\s*\d+){1,3})(-[a-z][0-9a-z-]*)?". This means it matches:

1 or more digits followed by
   0 or more whitespace followed by
   the '.' character followed by
   0 or more whitespace followed by
   1 or more digits followed by
the preceding group at least 1 times but no more than 3 times optionally followed  by
   the '-' character followed by
   any a-z character followed by
   0 or more a-z characters or numbers

Example matches would be:

1.23.23-a9
1.23.23
2.34
2.2-min
2

I hope that helps clears things up for some people.

Base32 Decoding in JavaScript

When working on the Google Authenticator web page, I realized that I needed to base32 decode the secret given from Google to get to the raw bytes. For those unaware, Base32 encoding is a mechanism to represent arbitrary binary data (1s and 0s) into an alphanumeric representation that is more convenient for transport (typing, etc.). Base32 encoding is exactly like hexadecimal or octal, where binary data is represented using different characters (0-9, A-F in hex, 0-7 in octal) except Base32 encoding uses even more alphanumeric characters (2-7, A-Z) to reduce the space required to represent the same number of bits. Looking around I couldn't find a well tested implementation of this, so I decided to write my own. I used this opportunity to explore unit testing a JavaScript method using QUnit. Let's start with gathering the test cases. The RFC has some test vectors, so obviously those will be included:

test("Test Vectors", function () {
    // Base32Decode should correctly decode the test vectors from the RFC
    strictEqual(Base32Decode("").length, 0, "Base32Decode should return an empty array for the empty string");
    ok(compareUint8ArrayToString(Base32Decode("MY======"), "f"), "Base32Decode should return 'f' for 'MY======'");
    ok(compareUint8ArrayToString(Base32Decode("MZXQ===="), "fo"), "Base32Decode should return 'f' for 'MZXQ===='");
    ok(compareUint8ArrayToString(Base32Decode("MZXW6YQ="), "foob"), "Base32Decode should return 'foob' for 'MZXW6YQ='");
    ok(compareUint8ArrayToString(Base32Decode("MZXW6YTB"), "fooba"), "Base32Decode should return 'fooba' for 'MZXW6YTB'");
    ok(compareUint8ArrayToString(Base32Decode("MZXW6YTBOI======"), "foobar"), "Base32Decode should return 'foobar' for 'MZXW6YTBOI======'");
});

Obviously these tests won't pass until we have a working Base32 decoder. The decoder is fairly straight-forward for inputs that don't have padding (i.e., the number of bytes are multiples of 40). In that case, you simple map the bits per the RFC:

|__A__|__B__|__C__|__D__|__E__|__F__|__G__|__H__|__I__|__J__|__K__|__L__|__M__|__N__|__O__|__P__|__Q__|__R__|__S__|__T__|__U__|__V__|__W__|__X__|__Y__|__Z__|__2__|__3__|__4__|__5__|__6__|__7__|

|00000|00001|00010|00011|00100|00101|00110|00111|01000|01001|01010|01011|01100|01101|01110|01111|10000|10001|10010|10011|10100|10101|10110|10111|11000|11001|11010|11011|11100|11101|11110|11111

The RFC goes into detail about what cases are possible with padding, etc. but I'll leave that as an exercise to the reader. I could have made the code smaller, but I wanted to be clear and follow the RFC as closely as possible. Here is the implementation:

var Base32Decode = function (base32EncodedString) {
    /// Decodes a base32 encoded string into a Uin8Array, note padding is not supported
    /// The base32 encoded string to be decoded
    /// The Unit8Array representation of the data that was encoded in base32EncodedString
    if (!base32EncodedString && base32EncodedString !== "") {
        throw "base32EncodedString cannot be null or undefined";
    }

    if (base32EncodedString.length * 5 % 8 !== 0) {
        throw "base32EncodedString is not of the proper length. Please verify padding.";
    }

    base32EncodedString = base32EncodedString.toLowerCase();
    var alphabet = "abcdefghijklmnopqrstuvwxyz234567";
    var returnArray = new Array(base32EncodedString.length * 5 / 8);

    var currentByte = 0;
    var bitsRemaining = 8;
    var mask = 0;
    var arrayIndex = 0;

    for (var count = 0; count < base32EncodedString.length; count++) {
        var currentIndexValue = alphabet.indexOf(base32EncodedString[count]);
        if (-1 === currentIndexValue) {
            if ("=" === base32EncodedString[count]) {
                var paddingCount = 0;
                for (count = count; count < base32EncodedString.length; count++) {
                    if ("=" !== base32EncodedString[count]) {
                        throw "Invalid '=' in encoded string";
                    } else {
                        paddingCount++;
                    }
                }

                switch (paddingCount) {
                    case 6:
                        returnArray = returnArray.slice(0, returnArray.length - 4);
                        break;
                    case 4:
                        returnArray = returnArray.slice(0, returnArray.length - 3);
                        break;
                    case 3:
                        returnArray = returnArray.slice(0, returnArray.length - 2);
                        break;
                    case 1:
                        returnArray = returnArray.slice(0, returnArray.length - 1);
                        break;
                    default:
                        throw "Incorrect padding";
                }
            } else {
                throw "base32EncodedString contains invalid characters or invalid padding.";
            }
        } else {
            if (bitsRemaining > 5) {
                mask = currentIndexValue << (bitsRemaining - 5);
                currentByte = currentByte | mask;
                bitsRemaining -= 5;
            } else {
                mask = currentIndexValue >> (5 - bitsRemaining);
                currentByte = currentByte | mask;
                returnArray[arrayIndex++] = currentByte;
                currentByte = currentIndexValue << (3 + bitsRemaining);
                bitsRemaining += 3;
            }
        }
    }

    return new Uint8Array(returnArray);
};

I've added more tests around padding and other specifics you can find at the source below, but enjoy a live demo converting base32 encoded strings to hexadecimal:

You can find the source for both the tests and the actual decode on github here: Base32Decode in JavaScript.
Also, if you'd like, you can run the tests directly from your browser via this link.

Google Authenticator in HTML5 with WebCrypto

I was poking around the web cryptography API and noticed how powerful it was. It even includes the ability to perform HMAC-SHA1 via the sign method. That is all you need to create TOTP one time passwords. I've done some work in the past on TOTP and knew that it is the backing algorithm for Google's two factor authentication.

Here is the main method that generates the token given the secret, which is base32 encoded. I wrote this in Microsoft's TypeScript, since I think it is great and definitely eased development. For those unfamiliar with Typescript, it is a superset of normal JavaScript so it should be pretty easy to read regardless.

function GenerateToken(base32EncodedSecret: string, callback: (number) => void): void {
    if (!msCrypto) {
        throw "MsCrypto not found";
    }

    // Google by default puts spaces in the secret, so strip them out.
    base32EncodedSecret = base32EncodedSecret.replace(/\s/g, "");

    // This method decodes the secret to bytes, the code is excluded here.
    var keyData: Uint8Array = GoogleAuthenticator.Base32Decode(base32EncodedSecret);
    var time: number = Math.floor(Date.now() / 30000);
    var data: Uint8Array = GoogleAuthenticator.NumericToUint8Array(time);

    // We need to create a key that the subtle object can actualy do work with
    var importKeyOp: KeyOperation = msCrypto.subtle.importKey("raw", keyData, { name: "HMAC", hash: "SHA-1" }, false, ["sign"]);

    importKeyOp.onerror = function (e) {
        console.log("error event handler fired.");
        callback(-1);
    }

    importKeyOp.oncomplete = function (e) {
        var key: Key = e.target.result;
        // HMAC the secret with the time
        var signkey = msCrypto.subtle.sign({ name: "HMAC", hash: "SHA-1" }, key, data);

        signkey.onerror = function (evt) {
            console.error("onerror event handler fired.");
            callback(-1);
        };

        signkey.oncomplete = function (evt) {
            // Now that we have the hash, we need to perform the HOTP specific byte selection
            // (called dynamic truncation in the RFC)
            var signature: ArrayBuffer = evt.target.result;

            if (signature) {
                var signatureArray: Uint8Array = new Uint8Array(signature);
                var offset: number = signatureArray[signatureArray.length - 1] & 0xf;
                var binary: number = ((signatureArray[offset] & 0x7f) << 24) |
                    ((signatureArray[offset + 1] & 0xff) << 16) |
                    ((signatureArray[offset + 2] & 0xff) << 8) |
                    (signatureArray[offset + 3] & 0xff);
                callback(binary % 1000000);

            } else {
                console.error("Sign with HMAC - SHA-1: FAIL");
                callback(-1);
            }
        };
    };
}

Setup Process

Token

For those of you who are worried about how this changes the multi-factor part of multi-factor auth, you should worry not. The demo page below saves the secret in the localStorage, which is device specific. So having the secret is an indicator that you have the device. This satisfies the "something you have" factor of multi-factor authentication. Currently only Internet Explorer 11 supports some form of the msCrypto object so if you want to check out the demo, you'll need to download that.

Demo page

Where is it 5 o'clock?

In 2003 Alan Jackson and Jimmy Buffett released the song It's Five O'clock Somewhere. It went on to spend 8 weeks at number one on the Billboard Hot Country Songs. It also reached number 17 on the US Hot 100, making it a huge crossover hit.

This poses the question, where is it 5 o'clock exactly at this moment and what is going on in that area? My brother created a website http://wheresitfiveoclock.com based off of publically available material to determine where in the world it is 5 o'clock by using time zones and day light savings calculations. Sources include:

I decided to create a windows phone application based off of the website http://wheresitfiveoclock.com/. This app shows you where it is currently 5 o'clock with the weather information. Hopefully, this app leads you to travel more and see more of the world. Leisure is important to your health so say it with us: It's 5 o'clock somewhere.

Main view

Live tile support

DAAP Media Player for Windows 8

DAAP, the digital audio access protocol that is commonly used by NAS devices to deliver personal music shares to your devices, is now available in Windows 8 Store! Now you can stream your music while using all of your Windows applications. The current release is available in German, English, Spanish, French, Italian, Japanese, Korean, Portuguese, Russian, and Simplified and Traditional Chinese.
Please leave any concerns or issues in the comments below.

Download here: http://apps.microsoft.com/windows/en-us/app/62bf2213-e46f-426d-962e-e317ddfd4722

Initial setup process.

List of albums.

Playing a song.

Coalescable Timers in Typescript

Not too many people may be familiar with the concept of coalescable timers, but they an be very useful for a power conscious application without hard real time requirements. Coalesce literally means "to grow together". In the case of timers, this means that multiple timers are allowed to be combined into one. This is usually done to reduce the number of times a computer is woken from a low power state to perform some action. This can be incredibly useful with mobile processors where power is very critical. As more and more applications move towards web applications to reduce re-implementing code in multiple mobile SDKs, it becomes necessary to introduce an implementation of coalescable timers into JavaScript, the client side logic language of modern web applications.

The idea is that when creating a timer, a tolerance value is specified that states how much variability is allowed in the timer. The tolerance allows timers with similar values to "grow together" into one timer. Examine the following example:

Timer 1: Trigger every 1 minutes with tolerance of 10 seconds
Timer 2: Trigger every 50 seconds with tolerance of 10 seconds

Coalesced Timer: Trigger every 60 seconds

Now becomes time to describe an algorithm for implementing coalescable timers. The goal is to minimize the number of times a timer is triggered. When a new timer is created, examine the existing timers, if any of the existing coalesced timers satisfy the requirements, add the new timer to the existing ones. If no existing coalesced timer handles the requirements specified, then create a new coalesced timer. Below is an implementation in TypeScript, which compiles down to basic JavaScript:

// Module containing all logic for coalescable timers
module Coalescable {
    // Variable holding all coalesced timers that are aggregating the individual timers
    var timers: CoalescedTimer[] = new CoalescedTimer[];

    export function SetCoalescableTimeout(expression: any, msec: number, tolerance: number): void {
        // Search existing coalesced timers for timers that can accomodate this request
        for (var index: number = 0; index < timers.length; index++) {
            var coalescedTimer: CoalescedTimer = timers[index];
            if (msec - tolerance < coalescedTimer.msec &&
                msec + tolerance > coalescedTimer.msec) {
                coalescedTimer.Timers.push(expression);
                return;
            }
        }

        // Create a new coalesced timer since none can accomodate this request
        var coalescedTimer: CoalescedTimer = new CoalescedTimer(msec)
        coalescedTimer.Timers.push(expression);
        timers.push(coalescedTimer);
    }

    class CoalescedTimer {
        constructor(public msec: number) {
            setInterval(function () => {
                for (var index: number = 0; index < this.Timers.length; index++) {
                    new Function(this.Timers[index])();
                }
            }, msec);
        }

        public Timers: any[] = new any[];
    }
}

Coalescable.SetCoalescableTimeout("alert('1')", 5000, 10); // Will create a new coalesced timer since none exist.
Coalescable.SetCoalescableTimeout("alert('2')", 6000, 2000); // Will be coalesced into the existing timer to run every 5000ms.

Obviously this is a first implementation. Many improvements could be made, such as minimizing distance from threshold when more than one coalesced timer exists to service a new timer request. There are also a few other interesting scenarios. Say creating a new timer means that a new coalesced timer will be created. In this case, it may make sense to move an existing timer to this new coalesced timer to reduce the difference from the requested interval and the coalesced interval. Also, cancelling or clearing a timeout should be supported.

A good abstract by Microsoft on coalescable timers: http://go.microsoft.com/fwlink/p/?linkid=246618

DAAP Media Player released on Windows Phone!

Today marks the general availability of the first version of DAAP Media Player for Windows Phone! As some of you may know, DAAP, digital audio access protocol, is a protocol initially developed by Apple for sharing audio across computers through iTunes. A while ago, my brother and I released an Android implementation of the DAAP protocol, but now is the time for Windows Phone. As with all platforms, it pays to have the implementation be a native application that takes full advantage of the platforms features.

We have taken the opportunity to do some optimizations that we have been wanting to do to the Android application but did not do initially. First and foremost, songs are cached in a local database after initially being fetched. This is opposite to Android where all songs are downloaded every time the application is launched. This can be a major benefit for libraries with a large amount of songs. Also, the Windows Phone platform has a great mechanism for playing songs independently of the application. This means that you can do any other tasks while listening to your music with no interruptions. You can change songs, play/pause, etc. from the volume button just as if DAAP Media Player was your local media application (even from the lock screen!).

The pricing is roughly $2 with a trial ad-supported version supported. You can find the application in the store by searching DAAP or installing from the Windows Phone Store website: DAAP Media Player.

HOTP on Windows Phone 8!

Recently I have been working on porting the existing Android one time password application to Windows Phone 8. Well the efforts have come to fruition. Now you can use your Windows Phone Device to create HOTP tokens for your authentication purposes. Below are some teaser screenshots:

Let me know any comments on the application below. You can download the application from the Windows Store here: http://www.windowsphone.com/en-us/store/app/hotp/ad7aad9e-294f-4731-9a5f-994a9cbaed13

Emulating Windows 8 Tilt Effect

When you click on a tile from the start screen on Windows 8, there is a nice effect where the tile "tilts" backwards towards the pointer or touch location. See below for an example:

Taken from IEBlog

The tilt direction appears be to based on the mouse or touch location. The image above was taken when the click was towards the right side of the live tile. The regions of the image that dictate the direction of the tilt is dictated roughly by the below guidelines:

Regions that determine direction of tilt.

The center region simply causes the tile to be depressed as an HTML button or other similar icon. The first step towards emulating this behavior is to determine the direction of the tilt. Once the direction is chose, we must apply the correct CSS3 3D transform to the tile.

Let's first define our points of interest relative to our object, which will be defined by its top-left coordinate (left, top) with width width and height height.
1. Center defined by rectangle:
(left+(width/2)-(.1*left), top+(height/2)-(.1*top)) width .2*width height .2*height.
2. Descending line defined by point (left, top) and slope (-height / width):
y - top = (-height / width) * (x - left)
3. Ascending line defined by point (left, top+height) and slope (heigh,width):
y - (top + height) = (height / width) * (x - left)

Now that we've defined our points of interest, we can take the incoming click and determine which direction the tilt is. The below code will install an event handler for the mouse down event for ever element with class "tilt".

        $(".tilt").each(function () {
            $(this).mousedown(function (event) {
                // Does the click reside in the center of the object 
                if (event.pageX > $(this).offset().left + ($(this).outerWidth() / 2) - (0.1 * $(this).outerWidth()) &&
                        event.pageX < $(this).offset().left + ($(this).outerWidth() / 2) + (0.1 * $(this).outerWidth()) &&
                        event.pageY > $(this).offset().top + ($(this).outerHeight() / 2) - (0.1 * $(this).outerHeight()) &&
                        event.pageY < $(this).offset().top + ($(this).outerHeight() / 2) + (0.1 * $(this).outerHeight())) {
                    $(this).css("transform", "perspective(500px) translateZ(-15px)");
                } else {
                    var slope = $(this).outerHeight() / $(this).outerWidth(),
                        descendingY = (slope * (event.pageX - $(this).offset().left)) + $(this).offset().top,
                        ascendingY = (-slope * (event.pageX - $(this).offset().left)) + $(this).offset().top + $(this).outerHeight();

                    if (event.pageY < descendingY) {
                        if (event.pageY < ascendingY) {
                            // top region
                            $(this).css("transform", "perspective(500px) rotateX(8deg)");
                        } else {
                            // right region
                            $(this).css("transform", "perspective(500px) rotateY(8deg)");
                        }
                    } else {
                        if (event.pageY > ascendingY) {
                            // bottom region
                            $(this).css("transform", "perspective(500px) rotateX(-8deg)");
                        } else {
                            // left region
                            $(this).css("transform", "perspective(500px) rotateY(-8deg)");
                        }
                    }
                }
            });

            $(this).mouseup(function (event) {
                $(this).css("transform", "");
            });
        });

Here is a below working example. Click the image to see the tilt effect:

Let me know if you find any particular issues with any browsers or have any comments below. I also should plug the useful tools used to help with this code:

Tool to see visually what different CSS3 3D transformation do: http://ie.microsoft.com/testdrive/Graphics/hands-on-css3/hands-on_3d-transforms.htm
IE blog talking about new support for CSS3: http://blogs.msdn.com/b/ie/archive/2012/02/02/css3-3d-transforms-in-ie10.aspx

Non-negative matrix factorization

In line with my previous post, I would like to take a look at using a technique called Nonnegative matrix factorization for creating an unsupervised learning classifier. The idea is given a matrix with no negative entries, factor the matrix into two other matrices such that their product is approximately equal to the original matrix. Assuming such a factorization exists, we can extract information from the resulting matrices that help describe the dependencies of the entries in the original matrix. By knowing the dependencies, we can see what elements are related to each other, and group them accordingly. Let's do an example by hand first with A, a 4x2 matrix :

Suppose we discover two matrices W and H such that W*H approximately equal to A:

W = [0.29291    1.85124;
     1.94600    0.26850;
     2.53183    3.97099;
     2.82474    5.82223];

H = [0.97449    0.44915;
     0.38599    0.46911];

W*H = [1.0000    1.0000;
       2.0000    1.0000;
       4.0000    3.0000;
       5.0000    4.0000];

What do the values in W and H say about the data in A? Let's examine just row 3 in W*H:

2.53183 * 0.97449 + 3.97099 * 0.38599 % = 4.0000
2.53183 * 0.44915 + 3.97099 * 0.46911 % = 3.0000

We notice that 3.97099 from row 3 of W is greater than 2.53183 of the same row. This means that row 3 in the result of W*H will be more heavily influenced by the second row of H ([0.83599 0.46911]). By looking at which column is greater in W, we can divide the data into two groups, one group more influenced by the first row of H (row 2 of A), and another group more influenced on the second row of H (rows 1, 3, & 4 of A). Using this logic, we can treat H as a sort of basis for the entries in W. Using this understanding of the matrices W and H, we can say that W defines which group an entry in A belongs where H defines the basis of the entire group. By controlling the dimensions of W and H, we can chose how many groups we want the factorization to create.

There has been much research into algorithms that actually can find the nonnegative matrix factorization of a matrix, but I will show just one of the most basic and earliest ones originating with Lee and Seung. Essentially the algorithm begins with an initial guess of W and H and then iteratively updates them using a rule proven not to increase the error of the approximation of A. Here is an Octave/Matlab implementation:

function [W, H] = nnmf(A, k)
%nnmf factorizes matrix A into to matrices W, H such that W*H ~= A
% A must be non negative
% k is used to define the dimensions of W and H
m = size(A, 1); % # of rows in A
n = size(A, 2); % # of cols in A
W = rand(m, k);
H = rand(k, n);

for i = 1:1500
   % update rule proven to not increase the 
   % error of the approximation
   % when cost = (1/2) * sum(sum((A - W*H) .^ 2));
   W = W .* (A * H') ./ (W*H*H' + 10^-9);
   H = H .* (W' * A) ./ (W'*W*H + 10^-9);
end
end

Using this algorithm, we can now create a classifier based on nonnegative matrix factorization. We start with a set of points and then decide how many groups we want to classify the data into. When then supply this information into the algorithm to get a factorization.

X = [1 1;
     2 1;
     4 3;
     5 4];
[W H] = nnmf(X, 2)

W =
   1.12234   0.19811
   0.31776   1.80444
   2.56244   2.20065
   3.68479   2.39876

H =
   0.71766   0.81862
   0.98200   0.41003

Now to better see the classification, we can create a matrix Wn, such that the 1 entry in each row is the maximum column from W for that row. This will indicate which group a data entry belongs.

So given the original 4 data points, we have classified them into two groups. Similarly to k-means clustering, this algorithm can be used to group extremely complex groups of data, such as web results, documents, spam, etc. Please comment if I can explain more clearly or missed any crucial information.

k-means clustering

k-means clustering is a technique used to categorize some data points into k distinct groups. This is an example of an unsupervised learning classifier where an algorithm refines an initial guess without training data to determine the groupings. Usually the "similarity" of two different data entries is based off some idea of a difference or distance to other data points. Graphically, the goal of k-means clustering can be easily demonstrated by plotting points and grouping them by colorization:

The algorithm works off of the ideas of centroids, which represent the "center" of the clusters of data (represented by circles in the illustration). The algorithm's inputs are the data and an initial guess at the k different centroids, usually chosen at randomly. Next the algorithm takes each data point and computes which cluster the point is closest to, and thus assigns that data point to that particular cluster. Now that every point is assigned to one of the initial guessed at clusters, the new centroids (center of all the points assigned to each cluster) are calculated. Now that there are new centroids, the cluster assignment may have change, so the algorithm goes back and recalculates the distances. This process is repeated until the clusters no longer change.

Since this algorithm may fail to find the "best" clustering assignment due to a poor initial guess, the algorithm is usually run with multiple different initial guesses. The next step would be to determine which clustering assignment was "best" using some heuristics or other mechanisms.

I have implemented the algorithm in Octave, a software package with capabilities similar to Matlab. The implementation works on any dimensionality data, allowing greater flexibility than just classifying dyads.

% Our data points, in this case 2d points, but could be in any dimension
% Each row represents a data point, each column represents a dimension
X = [1 1; 2 1; 4 3; 5 4];

% Our initial guess at the centroids, in this case the first two data points
centroids = [1 1; 2 1];

% Make a function call to my k-means clustering function
[centroids, clusterAssignment] = kMeansCluster(X, centroids);

The bulk of the work is done in the function kMeansCluster. The function works by first calculating which clusters each data point belongs to, and then updating the centroids accordingly. The function then repeats until the cluster assignment fails to change. The function takes advantage of the trivial function distance I wrote, which just calculates the distances between two points using Euclidean distance, but could be any "distance" mechanism appropriate for your data collection.

function [centroids, clusters] = kMeansCluster(X, initialCentroids)
%KMEANSCLUSTER assign clusters to the data from X based on 
% euclidian distance

% initialize centroids to the initial guess
centroids = initialCentroids;
k = size(centroids, 1); % number of clusters
m = size(X, 1);         % number of data points
% assign clusters to something random so that the 
% first cluster calculation is not coincidentally the same
% causing the the algorithm to end prematurely
clusters = rand(m, k);  

while 1
   % calculate the new cluster assignment based on the centroids
   % For each row which represents each data point
   % Each columns will be 0 except the column representing 
   % the cluster this point belongs to which will be 1
   newClusters = zeros(m, k);
   for i = 1:m
      % Calculate distance to each centroid
      distances = zeros(1, k);
      for j = 1:k
         distances(j) = distance(X(i, :), centroids(j, :));
      end

      % determine which centroid is closed to this data point
      [temp, index] = min(distances);

      % Set 0 for every cluster for this data point
      newClusters(i, :) = zeros(1, length(newClusters(i, :)));

      % Set 1 for the closest cluster
      newClusters(i, index) = 1;
   end

   % update centroids based on new cluster assignments
   for i = 1:k
      total = zeros(1, size(X, 2));
      count = 0;
      for j = 1:m
         if newClusters(j, i) == 1
            total += X(j, :);
            count++;
         end
      end

      if count == 0
         % prevent divide by zero
         centroids(i, :) = zeros(1, size(X, 2));
      else
         % calculate the average point
         centroids(i, :) = total / count;
      end
   end

   if newClusters == clusters
      % if this is the same as the last cluster, we are done
      break;
   else
      % We have a different cluster assignment, keep iterating
      clusters = newClusters;
   end
end
end

Running of this program will appropriately determine the clusters and output the centroids too:

% Initial data
%
% 5....x
% 4.....
% 3...x.
% 2.....
% 1xx...
% |12345
X = 
    1    1
    2    1
    4    3
    5    3

initialGuess = 
    1    1
    2    1

% [centroids, clusterAssignemnt] = kMeansCluster(X, centroids);
centroids = 
    1.5000   1.0000
    4.5000   3.5000

clusterAssignment = 
    1    0
    1    0
    0    1
    0    1

k-means clustering can be used for many things that may not be obvious based on the visual. For example, we could define a spam classifier algorithm. The 2 clusters would be spam and not spam, the data points would represent email characteristics (possibly with normalization, such as:

contains wrist watch offers
from someone in address book
...

When we run the classifier on some mail sample, the algorithm will output 2 clusters. Some other method will have to be used to determine which cluster is spam and which cluster is not spam. This algorithm will probably not be as good as Bayesian spam filtering and is heavily dependent on what characteristics you pick, but it does demonstrate k-means clustering's capabilities.

I hope my example k-means clustering algorithm explanation was helpful. Please post any questions in the comments.

Source code released under public domain where available.
External reference

A .Net Trie in C# implementing IDictionary

Recently I decided to write a straight forward solver for a popular word game similar to Boggle. The obvious data structure for such a game is the Trie. When searching the .Net library for such a data structure, I could not find one that suited my needs. Also looking over the internet did not yield the result I desired. I decided to implement my own Trie for this application.

Before we can start implementing the Trie, we need to understand the data structure at a fundamental level. Though often thought of as a neat way to store strings in memory, the structure is much more than that. A Trie is an associative array mapping sets of keys to values. This differs from most associative arrays that map keys to values. In many uses of a Trie, the keys are strings and the values are unused. Even in this configuration a Trie's internal structure yields very useful properties such as finding all sets of keys that share the same prefix. This was the property that I needed for my word game solver, but if we are implementing the structure, we should do it correctly. I decided that a Trie can be mapped to the interface of IDictionary with at least one added method to look up entries that share the same prefix.

Seperating these Trie specific methods into a seperate interface yields:

    /// <summary>
    /// Interface for a data structure that implements a Trie.
    /// </summary>
    /// <typeparam name="TKey">Type of the Key to store. Note each entry in the Trie has multiple Keys represented by an IEnumerable.</typeparam>
    /// <typeparam name="TValue">Type of the Value to store. This type must have a public parameterless constructor.</typeparam>
    public interface ITrie<TKey, TValue> : IDictionary<IEnumerable<TKey>, TValue>
    {
        /// <summary>
        /// Find all KeyValuePairs whose keys have the prefix specified by keys
        /// </summary>
        /// <param name="keys">Keys that all results must begin with</param>
        /// <returns>Collection of KeyValuePairs whose Keys property begins with the supplied keys prefix</returns>
        ICollection<KeyValuePair<IEnumerable<TKey>, TValue>> Suffixes(IEnumerable<TKey> keys);
    }

Notice that I abstracted out the concept of sets of keys from the interface. This cleans up many methods, while still making the user aware via method signatures that entries in the associative array are represented by sets of keys and not keys. Here is what the interface becomes for a Trie implementing ITrie:

    /// <summary>
    /// Implementation of the ITrie interface, representing a collection of keys of keys and values.
    /// </summary>
    /// <typeparam name="TKey">Type of the Key to store. Note each entry in the Trie has multiple Keys represented by an IEnumerable.</typeparam>
    /// <typeparam name="TValue">Type of the Value to store. This type must have a public parameterless constructor.</typeparam>
    public class Trie<TKey, TValue> : ITrie<TKey, TValue> where TValue : new()
    {
        /// <summary>
        /// Initializes a new instance of the Trie class.
        /// </summary>
        public Trie()
        {
            this.root = new Node<TKey, TValue>();
            this.keys = new List<IEnumerable<TKey>>();
            this.values = new List<TValue>();
        }

        #region ICollectionProperties
        /// <summary>
        /// Gets the number of elements contained in the ICollection.
        /// </summary>
        public int Count;

        /// <summary>
        /// Gets a value indicating whether the ICollection is read-only.
        /// </summary>
        public bool IsReadOnly;
        #endregion

        #region IDictionaryProperties
        /// <summary>
        /// Gets an ICollection containing the keys of the IDictionary.
        /// </summary>
        public ICollection<IEnumerable<TKey>> Keys;

        /// <summary>
        /// Gets an ICollection containing the values in the IDictionary.
        /// </summary>
        public ICollection<TValue> Values;
        #endregion

        #region IDictionaryIndexers
        /// <summary>
        /// Gets or sets the element with the specified key.
        /// </summary>
        /// <param name="keys">The key of the element to get or set.</param>
        /// <returns>The element with the specified key.</returns>
        public TValue this[IEnumerable<TKey> keys];
        #endregion

        #region ICollectionMethods
        /// <summary>
        /// Adds an item to the ICollection.
        /// </summary>
        /// <param name="item">The object to add to the ICollection.</param>
        public void Add(KeyValuePair<IEnumerable<TKey>, TValue> item);

        /// <summary>
        /// Removes all items from the ICollection.
        /// </summary>
        public void Clear();

        /// <summary>
        /// Determines whether the ICollection contains a specific value.
        /// </summary>
        /// <param name="item">The object to locate in the ICollection.</param>
        /// <returns>true if item is found in the ICollection; otherwise, false.</returns>
        public bool Contains(KeyValuePair<IEnumerable<TKey>, TValue> item);

        /// <summary>
        /// Copies the elements of the ICollection to an Array, starting at a particular Array index. 
        /// </summary>
        /// <param name="array">The one-dimensional Array that is the destination of the elements copied from ICollection. The Array must have zero-based indexing.</param>
        /// <param name="arrayIndex">The zero-based index in array at which copying begins.</param>
        public void CopyTo(KeyValuePair<IEnumerable<TKey>, TValue>[] array, int arrayIndex);

        /// <summary>
        /// Removes the first occurrence of a specific object from the ICollection. 
        /// </summary>
        /// <param name="item">The object to remove from the ICollection.</param>
        /// <returns>true if item was successfully removed from the ICollection; otherwise, false. This method also returns false if item is not found in the original ICollection.</returns>
        public bool Remove(KeyValuePair<IEnumerable<TKey>, TValue> item);
        #endregion

        #region IDictionaryMethods
        /// <summary>
        /// Adds an element with the provided key and value to the IDictionary.
        /// </summary>
        /// <param name="keys">The object to use as the key of the element to add.</param>
        /// <param name="value">The object to use as the value of the element to add.</param>
        public void Add(IEnumerable<TKey> keys, TValue value);
        
        /// <summary>
        /// Determines whether the IDictionary contains an element with the specified key.
        /// </summary>
        /// <param name="keys">The key to locate in the Dictionary.</param>
        /// <returns>true if the IDictionary contains an element with the key; otherwise, false.</returns>
        public bool ContainsKey(IEnumerable<TKey> keys);

        /// <summary>
        /// Removes the element with the specified key from the IDictionary.
        /// </summary>
        /// <param name="keys">The key of the element to remove.</param>
        /// <returns>true if the element is successfully removed; otherwise, false. This method also returns false if key was not found in the original IDictionary.</returns>
        public bool Remove(IEnumerable<TKey> keys);

        /// <summary>
        /// Gets the value associated with the specified key.
        /// </summary>
        /// <param name="keys">The key whose value to get.</param>
        /// <param name="value">When this method returns, the value associated with the specified key, if the key is found; otherwise, the default value for the type of the value parameter. This parameter is passed uninitialized.</param>
        /// <returns>true if the object that implements IDictionary contains an element with the specified key; otherwise, false.</returns>
        public bool TryGetValue(IEnumerable<TKey> keys, out TValue value);
        #endregion

        #region ITrieMethods
        /// <summary>
        /// Find all KeyValuePairs whose keys have the prefix specified by keys
        /// </summary>
        /// <param name="keys">Keys that all results must begin with</param>
        /// <returns>Collection of KeyValuePairs whose Keys property begins with the supplied keys prefix</returns>
        public ICollection<KeyValuePair<IEnumerable<TKey>, TValue>> Suffixes(IEnumerable<TKey> keys);
        #endregion

        #region IEnumerableMethods
        /// <summary>
        /// Returns an enumerator that iterates through the collection. 
        /// </summary>
        /// <returns>A IEnumerator that can be used to iterate through the collection.</returns>
        public IEnumerator<KeyValuePair<IEnumerable<TKey>, TValue>> GetEnumerator();

        /// <summary>
        /// Returns an enumerator that iterates through a collection.
        /// </summary>
        /// <returns>An IEnumerator object that can be used to iterate through the collection.</returns>
        IEnumerator IEnumerable.GetEnumerator();
        #endregion
}

This makes a nice Trie that is useful not only for simple word game solvers, but also complex associate array uses. For an example use, we can use the word game. Say we are given the prefix "do" and told to determine whether for a given list of words, if there are any words that begin with this prefix. We could use linq, but this is inefficient as we have to do a string comparison on every word in the word list:

words.Where(word => word.StartsWith("do")).Any();

A Trie on the otherhand can simply navigate to a certain node of the prefix tree, and enumerate all decendents. If there are no decendents, then we know there are not any words that start with the given set of keys:

words.Suffixes("do").Count == 0;

I've zipped the library and made availble under the lenient public domain license where available. Please comment on my implementation in the comments! I definitely know we can improve the enumerator to have a smaller memory footprint.

Trie - A C# implementation implementing to IDictionary

Implementing Generators/Yield in Languages Without Support

As a follow up to my previous post, I intent to go into detail how generators are actually implemented in a language. The way I intend to do this is to actually implement the generator paradigm without using language provided tools such as keywords. The first step to this process is actually understanding what is happening when you use the yield keyword. Perhaps an simple walk through will be illustrative.

A function that wishes to use a generator will iterate over that generator. To the function using the generator, the generator acts more like a data structure that implements the enumerable (iterable) interface than a function at all. The generator function cannot be called except by iterating over it. This is the proper way to think of a generator, a data structure. If you are only using a generator, than this is all you need to know. Implementing a generator requires a little more detail. Let's examine a the most basic generator, one that counts down. This example uses, C#, but the syntax is only slightly different than other languages such as python.

public IEnumerable<int> count(int start, int end)
{
   int counter = end;
   while (counter <= end)
   {
      yield return counter;
      counter++;
   }
}

I used a while loop here intentionally so the control flow is obvious. Up until the yield statement, everything is normal. So what is happening at "yield return counter"? The function execution stops and returns the variable counter for each "call" happening indirectly through the iterator. So what happens the next time the iterator issues a call to this function? Well, the execution picks up at counter++! But what is the value of counter? The special yield return statement is saving the entire state of the generator(local variables, instruction pointer, and any other state information), allowing the generator to be resumed exactly where it left off. I'll get to that other information later. To wrap up the basic, right before yielding a value, save the state of the generator. Upon entering the generator again, restore the saved state and jump to where we left off.

Let's examine another example. This time we will be looking at a recursive implementation of our count generator. I'm going to be intentionally avoiding the use of foreach to bring out the enumerator (iterator).

public IEnumerable<int> count(int start, int end)
{
   yield return start;
   if (start != end)
   {
      // foreach (int result in count(start + 1, end))
      // {
      //    yield return result;
      // }
      IEnumerator<int> enumerator = count(start + 1, end).GetEnumerator();
      while (false != enumerator.MoveNext())
      {
         yield return enumerator.Current;
      }
   }
}

This generator does the same thing, just in a recursive fashion. The first yield is exactly as the one previously examined. Things get slightly more difficult to keep track when the recursion begins, but the same exact process is followed. The enumerator is saved as part of the state of the count generator. When returning, the iterator is restored and so the generator continues as expected.

If C# allowed us to directly recur on the generator itself instead of iterating over the results as shown below:

public IEnumerable<int> count(int start, int end)
{
   yield return start;
   if (start != end)
   {
      // Will not compile
      yield return count(start + 1, end);
   }
}

then the state would have to include the call stack of the recursion produced by the generator. By explicitly restricting yield to return the enumerated base type (int), we are prevented from this operation because count returns an enumerable type. This makes implementing generators manually easier. We don't have to worry about recursion at all.

So now we get to implementing a generator. The basic ideas have been captured above. We need to save locals upon yielding, restore state upon calling, and allow enumeration. Since we generators are essentially data structures, we are going to have our desired operation (count) be a member function of a class that extends from a Generator class. Then your program can call foreach on this data type. Let's shown the Generator class first.

class Generator<T, State, RetType>

   : IEnumerable<RetType> where T : GeneratorIterator<State, RetType>, new()
{
   public Generator(State initialState)
   {
      this.initialState = initialState;
   }

   private State initialState;

   #region IEnumerable
   public IEnumerator<RetType> GetEnumerator()
   {
      GeneratorIterator<State, RetType> yieldedFunction = new T();
      yieldedFunction.Initialize(initialState);
      return yieldedFunction;
   }

   IEnumerator IEnumerable.GetEnumerator()
   {
      return this.GetEnumerator();
   }
   #endregion
}

public abstract class GeneratorIterator<State, RetType> : IEnumerator<RetType>
{
   public void Initialize(State initialState)
   {
      this.initialState = initialState;
      this.currentState = initialState;
   }

   public RetType YieldReturn(State state, RetType result)
   {
      // Save state before returning
      this.currentState = state;
      return result;
   }

   private State initialState;

   private State currentState;

   private RetType nextResult;

   public abstract RetType function(State currentState);

   #region IEnumerator
   public RetType Current
   {
      get
      {
         return this.nextResult;
      }
   }

   object IEnumerator.Current
   {
      get
      {
         return this.Current;
      }
   }

   public void Reset()
   {
      // Set the state back and invalid nextResult
      this.Initialize(this.initialState);
      this.nextResult = default(RetType);
   }

   public bool MoveNext()
   {
      this.nextResult = this.function(this.currentState);
      return this.currentState != null;
   }

   public void Dispose() { }
   #endregion
}

Let's examine what this class is doing. It is taking a class that is expected to override a member called function. This will be the function that is expected to be using the YieldReturn method provided by this class. Most of the code is setting up the enumerator. The enumerator takes care of calling the function when appropriate. The real magic that enables this class to be a generator is the currentState variable. This is where the function's state is saved. Whenever the function is needed, the function is passed the current state that was saved by YieldReturn. The function is responsible for using the state to produce the expected results.

To actually use the state, we are going to have functions that resemble finite state machines more than traditional functions. This is due to limitations of the C# compiler to allow us to jump to exactly where we need to. Below is a version of the first non recursive count and the appropriate state class representing all locals.

class Count : GeneratorIterator<CountState, int>
{
   public override int function(CountState currentState)
   {
      if (currentState.stateIndex == 0)
      {
         currentState.counter = currentState.start;
         currentState.stateIndex = 1;
         // Proceed to state 1
      }

      if (currentState.stateIndex == 1)
      {
         while (currentState.counter <= currentState.end)
         {
            // Set the next state
            currentState.stateIndex = 2;
            // yield return
            return YieldReturn(currentState, currentState.counter);
         }

         // Signal no more to yield, normally accomplished by reaching end of the function
         return YieldReturn(null, default(int));
      }

      if (currentState.stateIndex == 2)
      {
         currentState.counter = currentState.counter + 1;
         currentState.stateIndex = 1;
         // Use recursion to jump to state already passed
         return function(currentState);
      }
      
      // Can only get here if an invalid stateIndex was given
      throw new Exception("Unreachable");
   }
}

class CountState
{
   public int stateIndex;
   public int start;
   public int end;
   public int counter;
}

The stateIndex variable of the CountState class is used to determine where in the code path we left off. The function has no locals to avoid having variables no properly restored when upon reentry. To use this generator, we simply instantiate the wrapper and then the class behaves as all enumerator types do.

CountState initialState = new CountState
{
   start = 0,
   end = 5,
   stateIndex = 0
};

Generator<Count, CountState, int> generator = new Generator<Count, CountState, int>(initialState);
foreach (int result in generator)
{
   Console.WriteLine(result);
}

To illustrate that recursion is supported, I am translated the recursive count above to an appropriate finite state machine. You can try for yourself, but you can observe that there is no need to save a call stack to support recursion in your generators.

class RecursiveCount : GeneratorIterator<RecursiveCountState, int>
{
   public override int function(RecursiveCountState currentState)
   {
      if (currentState.stateIndex == 0)
      {
         currentState.stateIndex = 1;
         return YieldReturn(currentState, currentState.start);
      }

      if (currentState.stateIndex == 1)
      {
         if (currentState.start == currentState.end)
         {
            // We are done, signal no more results in this generator
            currentState.stateIndex = 3;
         }
         else
         {
            /// repeat
            currentState.recursiveCall = new Generator<RecursiveCount, RecursiveCountState, int>(
               new RecursiveCountState
                  {
                     start = currentState.start + 1,
                     end = currentState.end,
                     stateIndex = 0
                  }).GetEnumerator();
            // Go to state 2
            currentState.stateIndex = 2;
         }
      }

      if (currentState.stateIndex == 2)
      {
         while (false != currentState.recursiveCall.MoveNext())
         {
            return YieldReturn(currentState, currentState.recursiveCall.Current);
         }

         // We are done, signal no more results in this generator
         currentState.stateIndex = 3;
      }

      if (currentState.stateIndex == 3)
      {
         return YieldReturn(null, default(int));
      }

      throw new Exception("Unreachable");
   }
}

class RecursiveCountState
{
   public int stateIndex;
   public int start;
   public int end;
   public IEnumerator<int> recursiveCall;
}

I hope that this has been informative of the inner workings of generators and the yield statement. Please comment below with any questions.

Yield statement in C#

My great friend recently did on his wonderful blog covered in a recent post the basics of generators in Python. To further my own knowledge about generators, especially in the language I use most at work, I decided to port his permutation function to C#, yield statement and all.

To basically reiterate what my friend stated, the yield statement allows a function's state to be saved. For functions that are designed to generate a set of data to be iterated over this is great. Instead of computing the entire list and storing the results in memory, the function is able to pick up where it left off and generate the next element of the set when requested. Here is an example with a function that generates permutations.

   private static IEnumerable<string> Permutations(string input)
   {
      List<string> result = new List<string>();
      if (string.IsNullOrEmpty(input))
      {
         yield return string.Empty;
      }
      else
      {
         for (int i = 0; i < input.Count(); i++)
         {
            foreach (string permutation in Permutations(input.Substring(0, i) + input.Substring(i + 1)))
            {   
               yield return input[i] + permutation;
            }
         }
      }
   }

If you iterate over this function, you will notice that the entire list is never generated entirely in memory. The syntax would be something along the lines of:

   foreach (string permutation in Permutations("vegetable"))
      {
         System.Console.WriteLine(permutation);
      }

Thanks to my friend for helping me understand this topic and bring attention to features of a language I use every day.

Time Lapse

Recently, I set up my server with a copy of Yawcam on my home server. The initial plan was to experiment with using a webcam for security purposes, but found myself a little creeped out. I decided to turn the camera away from the door and out to the window. I set the software to take a picture every 10 seconds for a full day. You can see the results on Vimeo.

Formatting Lilypond Sheet Music for the Kindle

Tired of fumbling around with my collection of sheet music looking for a certain piece, I thought it would be great to have some sheet music on my third generation kindle (now called the Kindle Keyboard). I have always been a fan of the open source program Lilypond. Lilypond is a TeX-like system where sheet music is written to a text file and then compiled into the desired output.
Since Lilypond is similar to Tex, Lilypond files have incredible control of the output. No exception is adjusting paper dimensions, only a simple command is required:

\paper {
   paper-height = H\mm
   paper-width = W\mm
}

where H is the desired height in millimeters and W is the desired width in millimeters of the output paper. Since the kindle was a "fit-to-width" option for PDFs, the first step is to figure out the aspect ratio of the display. Once we have the aspect ratio, then we can configure the scaling to make the actual output legible from a reasonable distance. At first I thought that this would be easy. The Kindle has a resolution of 600x800, or an aspect ratio of 3:4 (the screen is taller than it is wide). However, when creating sheet music of this ratio and the display mode of the Kindle set to "fit-to-width", the pages spanned multiple virtual pages. This meant that the music was cut off between virtual pages. This makes playing the music impossible. From here I decided to figure out the ratio by creating a bunch of files of varying ratios and testing the output.

It turns out that the Kindle is doing a little fudging on the display and allows a range of display ratios that will appear as one virtual page. From what I observe, any ratio between .57-.61. I tried many variations and it also seems there is some other logic going on in the "fit-to-width" option and determining when to page, but this is a decent rule of thumb to work with. Now that we have a few aspect ratios to work with, I wanted to figure out some nice paper size in absolute terms such that Lilypond will output notes about the same size as normal sheet music.

At first I tried 100mm x 59mm. As you can see, the notes were extremely large and didn't allow many notes to displayed at once. This would making paging an annoying operation while trying to play the music.

Next I doubled everything. I found 200mm x 122mm appears nice.

Compared to actual sheet music, the font is a little small, but completely usable. If you want a bigger font and don't mind paging frequently, I tried the in the between, 150mm x 80mm.

This is the closest to actual size, but fine tuning could be done.

It is worth noting that while doing this, the "fudge" factor I mentioned earlier, or variability in determining the aspect ratio of the virtual page the Kindle will chose to display, is frustrating. These values I found through trial and error by generating many sheet music files, and looking at all of them.

Custom HTML "Widgets" for ASP.NET MVC3

I was experimenting with ASP.NET MVC3 and found myself in need of some HTML outputted by the Razor engine that would need to be used many times. I wanted to follow the DRY (Don't Repeat Yourself) principle by having the HTML appear in one spot and allow me to use it many times. Ideally I wanted something like the builtin HTML "widgets".

   @Html.DropDownList("DropDownID", Model.Items)

The way I accomplished this was extension methods. Extension methods are an interesting way to add functionality to a class without inheritence. There are drawbacks, such as not being able to access protected members of the base class, but for some cases this is ok.

I decided to use extension methods to add a method to the class that corresponded to the @Html object in the Razor engine. I found out that this class was the HtmlHelper class in the System.Web.Mvc namespace. By extending the HtmlHelper class via extension methods, I was able to achieve my goal of adding a custom widget.

namespace MvcHtml
{
   using System.Web.Mvc;

   public static class ExtensionHtml
   {
      public static MvcHtmlString CustomWidget(this HtmlHelper htmlHelper, string property)
      {
         TagBuilder tagBuilder = new TagBuilder("div");
         tagBuilder.SetInnerText(property);
         return new MvcHtmlString(tagBuilder.ToString());
      }
   }
}

After this little bit of work, we are ready to use the custom widget in our view template just as traditional widgets provided for us.

   @Html.CustomWidget("SampleProperty")

I hope this helps people understand how Razor is producing HTML from these view files!

Combining the Decorator Pattern with the Template Method Pattern

Design patterns are exactly that, patterns of design. These patterns have been determined to appear frequently throughout software development. These patterns appear so often that they have become well documented and given names. I cannot recommend more highly the book Design Patterns by the "Gang of Four" as a resource on the topic of patterns. Recently I came across the need to combine to of the most common patterns, the decorator pattern and the template method pattern. I needed multiple implementation of a class to simultaneously coexist, the template method pattern, and I also needed to be able to decorate these classes, the decorator pattern. I noticed that while combining these two patterns, the decorator class behaves just as another class that implements the template method.

/* The template method */
interface AbstractClass
{
   void Method();
}

/* One implementation */
class ConcreteClass1 : AbstractClass
{
   public void Method()
   {
      System.Console.WriteLine("   ConcreteClass1");
   }
}

/* Second implementation */
class ConcreteClass2 : AbstractClass
{
   public void Method()
   {
      System.Console.WriteLine("   ConcreteClass2");
   }
}

/* Now comes the decorator, which feels just like any other implementation */
abstract class AbstractClassDecorator : AbstractClass
{
   public AbstractClassDecorator(AbstractClass abstractClass)
   {
      this.abstractClass = abstractClass;
   }

   public virtual void Method()
   {
      this.abstractClass.Method();
   }

   protected AbstractClass abstractClass;
}

Now it becomes time to implement the decorators. The nice thing about the decorator pattern is that it allows you to add decorators simply by extending a class. Here I have two decorators.

class ConcreteDecoratedAbstractClass1 : AbstractClassDecorator
{
   public ConcreteDecoratedAbstractClass1(AbstractClass abstractClass)
      : base(abstractClass)
   {
   }

   public override void Method()
   {
      this.abstractClass.Method();
      System.Console.WriteLine("   Decorator1");
   }
}

class ConcreteDecoratedAbstractClass2 : AbstractClassDecorator
{
   public ConcreteDecoratedAbstractClass2(AbstractClass abstractClass)
      : base(abstractClass)
   {
   }

   public override void Method()
   {
      this.abstractClass.Method();
      System.Console.WriteLine("   Decorator2");
   }
}

And now that the patterns are in place, all we have to do is simply use them. Because of the decoration and template pattern, we are able to create many possibilities to execute the "same" method. We can decorate or not decorate with any of the decorators, and we have multiple implementations of each method.

class Program
{
   static void Main(string[] args)
   {
      AbstractClass concrete1 = new ConcreteClass1();
      AbstractClass concrete2 = new ConcreteClass2();
      ConcreteDecoratedAbstractClass1 decorated1Concrete1 = new ConcreteDecoratedAbstractClass1(concrete1);
      ConcreteDecoratedAbstractClass1 decorated1Concrete2 = new ConcreteDecoratedAbstractClass1(concrete2);
      ConcreteDecoratedAbstractClass2 decorated2Concrete1 = new ConcreteDecoratedAbstractClass2(concrete1);
      ConcreteDecoratedAbstractClass2 decorated2Concrete2 = new ConcreteDecoratedAbstractClass2(concrete2);
      ConcreteDecoratedAbstractClass2 decorated21Concrete1 = new ConcreteDecoratedAbstractClass2(decorated1Concrete1);
      /* Et cetra */

      System.Console.WriteLine("Implementaiton 1");
      concrete1.Method();

      System.Console.WriteLine("Implementation 2");
      concrete2.Method();

      System.Console.WriteLine("Implementation 1 decorated by decorator 1");
      decorated1Concrete1.Method();

      System.Console.WriteLine("Implementation 2 decorated by decorator 1");
      decorated1Concrete2.Method();

      System.Console.WriteLine("Implementation 1 decorated by decorator 2");
      decorated2Concrete1.Method();

      System.Console.WriteLine("Implementation 2 decorated by decorator 2");
      decorated2Concrete2.Method();

      System.Console.WriteLine("Implementation 1 decorated by decorator 1 and decorator 2");
      decorated21Concrete1.Method();
}

This program outputs

Implementaiton 1
   ConcreteClass1
Implementation 2
   ConcreteClass2
Implementation 1 decorated by decorator 1
   ConcreteClass1
   Decorator1
Implementation 2 decorated by decorator 1
   ConcreteClass2
   Decorator1
Implementation 1 decorated by decorator 2
   ConcreteClass1
   Decorator2
Implementation 2 decorated by decorator 2
   ConcreteClass2
   Decorator2
Implementation 1 decorated by decorator 1 and decorator 2
   ConcreteClass1
   Decorator1
   Decorator2

I hope that this was informative in demonstrating the power of patterns and how they can be combined for even greater utility. Please feel free to comment below.

Scrobbler support in DAAP

A popular feature request for DAAP has been Last.fm's Scrobbler support. Scrobbling is a mechanism that allows Last.fm to know what songs you listen to on your personal devices, such as iPods, computer, or your Android device. This allows Last.fm to personalize which songs to suggest more quickly than normal. Big thanks to my brother Michael for implementing this.

The feature is pretty straight forward. First, a Scrobbling application must be installed on your device. For this version, Scrobbling has been tested with scrobbledroid and A Simple Last.fm Scrobbler. Next, navigating to the preferences via Menu -> Preferences from the Servers screen presents an option to enable this feature. From now on, your music listening will be relayed to your Scrobbling application which in turn relays that to your Last.fm account! No interaction required.

You can download DAAP via the android market by

The Android Market Application
Scanning the tag