Rhino Mocks moving to the AAA syntax

Having looked at how I should write my unit tests, I've started to move to the AAA syntax (Arrange, Act, Assert). I found it quite hard (me being stupid) to find a before and after example - so here's my before and after...

// Art of unit testing (7.3.1 naming unit tests)
  //  name of method being tested _ scenario being tested _ the expected behaviour
  //  MethodUnderTest_Scenario_Behaviour
  [TestMethod]
  public void CreateParser_WellKnownDataset_PostsNodesToReciever()
  {
   MockRepository mocks = new MockRepository();
   IParsedReceiver receiver = mocks.StrictMock<IParsedReceiver>();

   using (mocks.Record())
   {
    receiver.AcceptNode(null);
    LastCall.IgnoreArguments().Repeat.Times(14);
   }

   Parser parser = Manager.CreateParser(receiver, @"..\..\ParseData\OsmTestData.xml");

   mocks.VerifyAll();
  }

and using the 3.5 Arrange, Act, Assert approach:

// Art of unit testing (7.3.1 naming unit tests)
  //  name of method being tested _ scenario being tested _ the expected behaviour
  //  MethodUnderTest_Scenario_Behaviour
  [TestMethod]
  public void CreateParser_WellKnownDataset_PostsNodesToReciever_AsStub()
  {
   // arrange
   IParsedReceiver receiver = MockRepository.GenerateStub<IParsedReceiver>();

   // act
   Parser parser = Manager.CreateParser(receiver, @"..\..\ParseData\OsmTestData.xml");
   
   // assert
   receiver.AssertWasCalled(c => c.AcceptNode(null), options => options.Repeat.Times(14).IgnoreArguments());
  }

which has the nice side effect of being less code as well!

Image scaling and GCD (greatest common divisor)

Whilst embedding an image in a wiki page I found it was too big (wide) and therefore caused lots of layout issues. The obvious solution to this was to scale the image (by editing the HTML and adding a style attribute style="width:80%;") unfortunately this caused the image (a diagram) to be unreadable - due to image artefacts.

After looking at the image properties, I saw the cause of problem - its dimensions (865 x 596). As there is no common divisor of these two numbers there is now way to scale it down without one of the dimensions being rounded - for example at a scale of ½ the dimensions become (432.5 x 298). And you can't have half a pixel...

So I suspect (intuitively rather than by proof) that images scale best if they have a GCD (greatest common divisor), a quick port of the binary GCD from wikipedia in C#:

        static uint gcd(uint u, uint v)
        {
            int shift;

            /* GCD(0,x) := x */
            if (u == 0 || v == 0)
                return u | v;

            /* Let shift := lg K, where K is the greatest power of 2
               dividing both u and v. */
            for (shift = 0; ((u | v) & 1) == 0; ++shift)
            {
                u >>= 1;
                v >>= 1;
            }

            while ((u & 1) == 0)
                u >>= 1;

            /* From here on, u is always odd. */
            do
            {
                while ((v & 1) == 0)  /* Loop X */
                    v >>= 1;

                /* Now u and v are both odd, so diff(u, v) is even.
                   Let u = min(u, v), v = diff(u, v)/2. */
                if (u < v)
                {
                    v -= u;
                }
                else
                {
                    uint diff = u - v;
                    u = v;
                    v = diff;
                }
                v >>= 1;
            } while (v != 0);

            return u << shift;
        }

Port of code from wikipedia

How the silverlight tag cloud works, including source code

The TagCloud Silverlight application allows a user to see a visual representation of an RSS feed. It shows a visualization of the labels used within a feed, using size to indicate frequency and closeness to other tags showing frequency of co-occurrence.

This means that tags that occur often together (for example “Silverlight” and “Xaml”) will tend to appear next to each other, whilst tags that don’t occur together in the feed (for example “Silverlight” and “Credit Crunch”) will tend to be far apart.

Colour is also used to group the tag cloud, with the most frequently occurring tags taking a colour, and co-occurring tags inheriting that colour. This visually groups the cloud by colour as well.

Mouse-Over a tag shows lines to all other tags that it has occurred with, and clicking presents a popup menu of posts that mention that tag. Clicking on an item in the menu navigates to that post.

You can also click and drag a tag for fun, and watch all the other tags chase it..

Model

• Cloud: the model of a RSS feed, separating the model from the UI. Processes an RSS feed and create subordinate Post and Tag with relationships. The cloud class is more of a management class that delegates most of the work to the Tag class.
  
• Post: very simple class that represents a post/entry in an RSS feed. Used to allow navigation back to a particular post.
  
• Tag: represents a tag (label/syndicationItem) in an RSS feed. Holds frequency count of how many times it has co-occurred with other tags. Has a SeekHarmony function that does the majority of the application “ah!” factor.
  

Approach

The application builds an internal model of the RSS feeds, critically in terms of tags and their co-occurrences. It then follows a simulation approach, where it tries to position each tag such that it is near tags it has co-occurred with, and far from tags it has not.

The algorithm for doing this does not pay attention to the overall cloud shape, but acts as an emergent system – the application of the simple harmony seeking behaviour between tags creating a global balance (generally a circle)

Code structure

Four parts

• JavaScript library to make embedding the application less error prone
  
• A server based proxy for getting RSS feeds to avoid cross domain issues
  
• A silverlight library for math functions (mostly polar calculations and some extension methiods)
  
• TagCloud silverlight application, with App and Page classes and three supporting classes (Cloud, Post and Tag)
  

Lifecycle

The silverlight application is embedded in a HTML page which passes a number of parameters via JavaScript to the Silverlight object creation code. The Silverlight application reads these settings and downloads the RSS feed via a server side proxy (to avoid cross-domain issues). The code then build an internal model of the RSS feed, with co-occurrence information about tags. On a timer basis the code then moves each tag such that it is nearer tags it co-occurred with, and further from ones it has not occurred with. Over time an order emerges which shows how the tags relate – tags that are nearer co-occur more.

Embedding the control in the page

For my blog I use JavaScript to embed the silverlight control

<div id='feCloud' style='text-align: center;'/>  
 <script src='http://www.figmentengine.com/tagCloud/feCloudv1.2.js' type='text/javascript'/>  
 <script type='text/javascript'>  
  var feCloudElementId = 'feCloud';  
  var feCloudFeedAddress = 'http://feedproxy.google.com/FigmentEngine';  
  var feCloudNavigateFormat = 'http://blog.figmentengine.com/search/label/{0}';  
  var feCloudSize = 400;  
  feTagCloudLoad(feCloudElementId, feCloudFeedAddress, feCloudNavigateFormat, feCloudSize, feCloudSize);  
 </script> 

 

The function in the feCloudv1.2.js is a wrapper for the Silverlight.js createObject call:

function feTagCloudLoad(elementId, feed, navigateFormat, width, height)
{
  var params = "";

  if (feed != null)
    params += "feedAddress=" + feed + ", ";
  if (navigateFormat != null)
    params += "navigateFormat=" + navigateFormat + ", ";

  var slWidth = 350;
  if (width)
   slWidth = width;
  params += "width=" + slWidth + ", "; 

  var slHeight = 350;
  if (height)
   slHeight = height;

  var container = document.getElementById(elementId);
  var cloudControl = document.createElement('object');
  
  cloudControl.setAttribute('data', 'data:application/x-silverlight-2,');
  cloudControl.setAttribute('type', 'application/x-silverlight-2');
  cloudControl.setAttribute('id', 'feCloudControl');
  container.appendChild(cloudControl);

  var host = "http://www.figmentengine.com/";
  var source = host + "tagCloud/TagCloudV1.2.xap";
  var parentElement = container;
  var callbackId = "feCloud";
  var properties = { width: slWidth, height: slHeight, version: "2.0.31005.0", enableHtmlAccess: "true" };
  var events = { };
  var initParams = params;
  Silverlight.createObject(source, parentElement,
   callbackId, properties, events, initParams);
}

I’ve put in bold the section that deals with passing the feed information via initParams. I also set enabledHtmlAccess to allow the Silverlight code to navigate the browser using HtmlPage.Window.Navigate.

Application startup

Reads the settings specified in the embedding JavaScript, most importantly the address of the RSS feed and how to navigate to page. It creates an instance of the Page and asks it to populate the TagCloud based on the feed address information.

Populating the cloud

Obtain the RSS feed: Due to issues in making requests to websites that the silverlight does not originate from I use the technique outlined at Franksworld (when your silverlight app needs to get data from another server that does not contain a crossdomain.xml then it proxies the call via the server)

http://franksworld.com/blog/archive/2008/04/15/10903.aspx

protected void Page_Load(object sender, EventArgs e)
    {
        // Load the URI from the Query String
        string sourceUriString = Request.QueryString["Uri"];

        try
        {
            // Clear the output buffer
            Response.Clear();

            // Make new WebClient 
            WebClient webClientRequest = new WebClient();

            // Download data from URI
            byte[] requestByteArray = webClientRequest.DownloadData(sourceUriString);

            // Match the Mime Types
            string contentType = webClientRequest.ResponseHeaders["Content-type"].ToString();
            Response.ContentType = contentType;

            // Copy the Streams
            int requestByteArrayLength = requestByteArray.GetLength(0);
            Response.OutputStream.Write(requestByteArray, 0, requestByteArrayLength);
            Response.OutputStream.Close();

            // Exit the Page
            // see http://support.microsoft.com/kb/312629
            //Response.End();
            HttpContext.Current.ApplicationInstance.CompleteRequest();

        }
        catch(Exception ex)
        {
            // 5xx errors mean server error
            Response.StatusCode = 501;
            Response.StatusDescription = "Error encountered. Details: " + ex.Message;
        }
    }

Conversion of the RSS into the internal object model ignores most of the information in the feed, concentrating on posts, tags and co-occurrence.

Initializing the UI

At start-up the code creates a pool of connecter lines (to reduce the need to create them dynamically). It also create TextBlocks to represent each tag. It then start the timer to repeatedly move the tags around (seeking harmony)

Seeking Harmony

The code only works at a tag level, relying on emergent behaviour to get the UI effect. For each tag we do the following:

• Each tag calculates how near it should be to all the other tags based on frequency of co-occurrence.
  
• It then uses a polar conversion to work out the vector it would need to move in to get to this position.
  
• We add up all these vectors for the tag, which gives us a vector that if it applied would be the ideal location for it.
  
• We then down-scale the vector:
  

1. So tags don’t jump massive distances
   
2. Tags can react to where all the other tags have moved to on the next cycle 
   

Source code
Source code available as a zip

Tag cloud seeking harmony

I'm about to release the code for the tag cloud - here's a teaser of the code that each tag runs to seek harmony:

  internal void SeekHarmony(IEnumerable<Tag> valueCollection, double SIZE)
  {
   double maxOccurance = OccuredCount + 0.1d;

   // how we scale the whole cloud, 4 would be exactly the size of the area
   // 3 would be slightlight larger and 5 would be smaller
   const double ATTRACTION_SCALE = Math.PI;
   // how much tags that have not cooccurred repel each other
   // ϕ (golden ratio) gives us a nice aesthic
   const double REPEL_RATIO = 1.618d;
   // how much tags that cooccurred attract each other
   // it must be greater than the repel rate or everything
   // will fly away from each other
   const double ATTRACT_RATIO = Math.E;

   // assume we don't need to be moved
   Point offset = new Point(0, 0);

   // work out where the best place in 2d space to be
   // would be given where all the other tags are
   foreach (Tag otherTag in valueCollection)
   {
    // ignore ourself
    if (otherTag == this)
     continue;

    // work out vector bewteen us and the other tag
    Polar vector = Trigonometry.CartesianToPolar(this.Point, otherTag.Point);

    // how far apart?
    double distance = vector.Magnitude;

    // how much they repel by default
    double desiredDistance = maxOccurance * REPEL_RATIO;
    // did we co-occur with the other tag?
    int cooccurred = this[otherTag];
    if (cooccurred != 0)
     // we want to closer to the other tag based on frequency
     desiredDistance /= (cooccurred * (ATTRACTION_SCALE / ATTRACT_RATIO));

    // scale the distance based on the play area and how important
    // the other tag is compared to all the tags we co-occurred with
    distance = SIZE * (desiredDistance / (ATTRACTION_SCALE * maxOccurance));
    distance = (vector.Magnitude - distance); // towards not away

    // work out what vector needs to be applied to our
    // current position to move us closer
    Polar desiredVector = new Polar(vector.Direction, distance);
    Point offsetPoint = Trigonometry.PolarToCartesian(desiredVector);

    // accumlate all the proposed changes
    offset.X += offsetPoint.X;
    offset.Y -= offsetPoint.Y;
   }

   // update our new position, (scaled to fit within play area)
   // and also scaled to allow gradual movement
   double rateOfChange = SIZE / ATTRACTION_SCALE;
   point.X += offset.X / rateOfChange;
   point.Y += offset.Y / rateOfChange;
  }

hopefully I will post all the code and zip file tomorrow..

Waiting for multiple threads

Nice post on implementing a lock with timeout.

Though the code has two areas I would consider enhancing:
1) use WaitHandle.WaitAll to reflect the intent (and likelyhood) to aquire all locks or none [reason: performance]

2) There is a pathological case that two threads running at the same time will keep failing, if they hit the code for aquiring the locks in the for loop at the same time (since this is the case the code is written to handle it needs changing) - by implementing a variable amount of sleep time, thus ensuring that two threads that go to sleep at the same time don't wake up at the same time [reason: functional]

~socket(); // death of socket programming?

~socket(); // death of socket programming?

Interesting article on sockets, a technology created in 1982. It shows how some of the limitations that were around in 1982 are expressed in the sockets architecture and how we are still being affected by the design decisions in this stack.

It talks about the need for multihoming, but I also wonder on the implications for moving away from a client/server model, and the transistion to SOA/ESB/Cloud type technologies - do we need to rethink some of the lower level stack?

Enumerable character ranges

I was reading Eric Lippert's Blog entry A nasality talisman for the sultana analyst where he was writing some code to help in playing scrabble like games. And I saw a piece of code that I had written myself before and I thought, there must be a better way....

The code:

    foreach (char c in "ABCDEFGHIJKLMNOPQRSTUVWXYZ")
    {
        // do stuff
    }

what did I not like about the code? the literal ABCDEFGHIJKLMNOPQRSTUVWXYZ, it's too easy to type this in wrong - so I thought I could improve this using the Range function of Enumerable which allows you to write:

    foreach (int i in Enumerable.Range(1, 10))
    {
        // do stuff
    }

neat! but wait a second, the Range function only accepts int as the data type - hmm, so I came up with:

    foreach (int i in
        Enumerable.Range('a', 'z' - 'a' + 1).Select(charCode => (char)charCode))
    {
        // do stuff
    }

way to go! apart from the code being even longer than it was before, and not exactly the sort of code the drips of your finger-tips.

I then found Using LinqPad to Create a Time-Selector Drop-Down List, and the implementation of a "To" extension method:

public static IEnumerable To(this int first, int last) {
  return Enumerable.Range(first, last - first + 1);
}

(Note: on Richard Bushnell's blog I found www.extensionmethod.net a repository of .Net Extension Methods).

I took Richard's implementation and combined it with mine to create a "To" method for characters:

  public static IEnumerable<char> To(this char first, char last)
  {
   var result = Enumerable.Range(first, last - first + 1).Select(charCode => (char)charCode);

   return result;
  }

Which allows you to write:

    foreach (char c in 'A'.To('Z'))
    {
        // do stuff
    }
 // vs.
    foreach (char c in "ABCDEFGHIJKLMNOPQRSTUVWXYZ")
    {
        // do stuff
    }

And finally, I changed the "To" method to cope with ranges in reverse order:

 public static class EnumerableExtensions
 {
  private static void Swap(ref char a, ref char b)
  {
   var temp = a;
   a = b;
   b = temp;
   // swap code updated to reflect eric's comments
   // http://blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx#comments
  }

  public static IEnumerable<char> To(this char first, char last)
  {
   bool reverseRequired = (first > last);

   if (reverseRequired)
    Swap(ref first, ref last);

   var result = Enumerable.Range(first, last - first + 1).Select(charCode => (char)charCode);

   if (reverseRequired)
    result = result.Reverse();

   return result;
  }
 }

Which allows you to write:

    foreach (char c in 'a'.To('z'))
        Console.WriteLine(c);
    foreach (char c in 'A'.To('Z'))
        Console.WriteLine(c);
    foreach (char c in 'z'.To('a'))
        Console.WriteLine(c);
    foreach (char c in '0'.To('9'))
        Console.WriteLine(c);

Anaglyphs and 3D vision

Oh a post about vision systems (about time!)

So you can write alot of code to try and interpret the 3D space in images or you can cheat and use the same technique that the brian uses (well it probably does not use pointers but thats another conversation)

So if you have two cameras you can position them side by side like eyes, and using a bit of DirectX coding take some pictures at the same time:

In the pictures above you can see that the images are slightly offset from each other (the wall on the left is not visible in the right picture), and from this you can generate Anaglyph image:

Now if you put your 3D spec's on (the kind that came with Shrek 3D DVD) you can see it in 3D!

The code? something like this does the trick (cue screams of fear! its unsafe code! it's got pointers and stuff! hide behind the sofa!

unsafe public Bitmap MakeAnaglyph()
  {
   Bitmap result = (Bitmap)_right.Clone();

   FastBitmap fbitRight = new FastBitmap(result, ImageLockMode.ReadWrite);
   FastBitmap fbitLeft = new FastBitmap(_left);

   FastBitmap.PixelData* pPixelRight;
   FastBitmap.PixelData* pPixelLeft;

   for (int y = 0; y < _right.Height; y++)
   {
    for (int x = 0; x < _right.Width; x++)
    {
     pPixelRight = fbitRight[x, y];
     pPixelLeft = fbitLeft[x, y];

     pPixelRight->red = pPixelLeft->red;
     pPixelRight->green = (byte)(pPixelRight->green * .82);
     pPixelRight->blue = (byte)(pPixelRight->blue * .95);
    }
   }

   fbitRight.Dispose();
   fbitLeft.Dispose();

   return result;
  }

This code uses my FastBitmap class, which justs makes working with the raw data a bit more obvious:

unsafe class FastBitmap: IDisposable
 {
  Bitmap _source;
  Rectangle _bounds;
  BitmapData _lockedBitmap;
  byte* _pBase;
  int _stride;

  [StructLayout(LayoutKind.Sequential)]
  public struct PixelData
  {
   public byte blue;
   public byte green;
   public byte red;
  }

  public FastBitmap(Bitmap source): this(source, ImageLockMode.ReadOnly)
  {
  }

  public FastBitmap(Bitmap source, ImageLockMode mode)
  {
   _source = source;
   _bounds = Bounds;
   _lockedBitmap = _source.LockBits(_bounds, mode, source.PixelFormat);
   _pBase = (byte*)(void*)_lockedBitmap.Scan0;
   _stride = _lockedBitmap.Stride;
  }
  public PixelData* this[int x, int y]
  {
   get
   {
    // Format32bppArgb - Specifies that the format is 32 bits per pixel; 
    // 8 bits each are used for the alpha, red, green, and blue components
    const int bytesPerPixel = 4; 

    PixelData* result = (PixelData*)(_pBase + (y * _stride) + (x * bytesPerPixel));

    return result;
   }
  }

  public Rectangle Bounds
  {
   get
   {
    GraphicsUnit unit = GraphicsUnit.Pixel;
    RectangleF bounds = _source.GetBounds(ref unit);

    Rectangle result = SizeToRectangle(bounds.Location, bounds.Size.ToSize());

    return result;
   }
  }


  private Rectangle SizeToRectangle(Size size)
  {
   return SizeToRectangle(new Point(0, 0), size);
  }

  private Rectangle SizeToRectangle(Point point, Size size)
  {
   return new Rectangle(point, size);
  }

  private Rectangle SizeToRectangle(PointF point, Size size)
  {
   return new Rectangle(new Point((int)point.X, (int)point.Y), size);
  }

  #region IDisposable Members

  public void Dispose()
  {
   if (_lockedBitmap != null)
   {
    _source.UnlockBits(_lockedBitmap);
    _lockedBitmap = null;
   }
  }

  #endregion
 }

How does this get you nearer to 3D vision? hint: red-blue differencing of the result...

Getting mobile location on Windows Mobile 6

As part of my ongoing mapping project I wanted to be able to update my server with my location - the first step was to use the GPS built into my Windows Mobile 6.

I used the GPS Intermediate Driver to do this, and the code provided by the Windows Mobile 6 SDK.

The simplest code that can be written references the sample library provided by the SDK. My sub-80 line program to do this looks like this:

using System.Linq;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using Microsoft.WindowsMobile.Samples.Location;

namespace MobileLocate
{
 public partial class FormMain : Form
 {
  Gps gps = new Gps();
  GpsDeviceState device = null;
  GpsPosition position = null;

  public FormMain()
  {
   InitializeComponent();

   // updates from GPS need to be delgate to the UI thread
   EventHandler uiUpdatesOnApplicationThread = new EventHandler(UpdateUI);

   // handle device state updates
   gps.DeviceStateChanged += new DeviceStateChangedEventHandler(delegate(object sender, DeviceStateChangedEventArgs args)
   {
    device = args.DeviceState;

    Invoke(uiUpdatesOnApplicationThread);
   });

   // handle location updates
   gps.LocationChanged += new LocationChangedEventHandler(delegate(object sender, LocationChangedEventArgs args)
   {
    position = args.Position;

    Invoke(uiUpdatesOnApplicationThread);
   });

   gps.Open();
  }

  void UpdateUI(object sender, System.EventArgs args)
  {
   if (device != null)
    textBoxDev.Text = device.FriendlyName + " " + device.ServiceState + ", " + device.DeviceState;

   if (position != null)
   {
    if (position.LatitudeValid && position.LongitudeValid)
     textBoxLocation.Text = String.Format("{0}, {1}", position.Latitude, position.Longitude);

    if (position.SatellitesInSolutionValid &&
      position.SatellitesInViewValid &&
      position.SatelliteCountValid)
    {
     textBoxSats.Text = "Satellite Count:\n   " + position.GetSatellitesInSolution().Length + "/" +
       position.GetSatellitesInView().Length + " (" +
       position.SatelliteCount + ")\n";
    }
   }
  }

  private void FormMain_Closed(object sender, EventArgs e)
  {
   // ensures application closes cleanly
   if (gps.Opened)
    gps.Close();
  }
 }
}

I ran this just now, and stuck the co-ordinates into a map - and it works a treat!

I plan to extend this code to allow it to report into a central server (with a username/password) and then be able to show this on the map. This will form one of the overlays (more later on this) that can be incorporated onto a map - this means you could chose to have the location of a set of users appear on a map (they will have to be permissions on this, and maybe a "how precise" feature to mask exact location)

From the mobile viewpoint, it should be easy enough to use the vector maps to show a local map on the mobile phone as well. For the moment I may just add the ability for the system to tell you where you are (for example postcode in the UK using http://www.freethepostcode.org/ data), or just the nearest city or pub! ;-)

Fibonacci and Big-Oh reduction

I was asked to write some C# to implement a Fibonacci sequence, which falls into two parts: 1) generate a single number in the sequence, 2) generating the whole sequence.

Note that most examples of this sequence generator have a nasty bug in them. Most examples use the int data type, whilst this code uses the long data type, otherwise this function overflows around n=47.

The naive way to implement this is recursively:

  /// <summary>
  /// slow version of fib calc for testing - warning
  /// runs in O(1.618..n) 
  /// </summary>
  internal long Fibonacci(int n)
  {
   if (n < 2)
    return n;
   else
    return Fibonacci(n - 1) + Fibonacci(n - 2);
  }

And a more optimal approach is:

  /// <summary>
  /// returns the Fibonacci number for N
  /// </summary>
  public long Fibonacci(int n)
  {
   // returns N where n < 2, for higher values of N
   // avoids recursive solution by keeping track
   // of previous results

   long fn = 0;

   if (n < 0) // offset must be positive
    throw new NotSupportedException("Fibonacci sequence offset must be positive");
   else if (n < 2) // returns N where N < 2
    fn = n;
   else // use caching technique for higher values of N
   {
    long fnMinusTwo = 0;
    long fnMinusOne = 1;

    for (long ni = 2; ni <= n; ni++)
    {
     // effectively: fn = Fibonacci(n - 1) + Fibonacci(n - 2)
     fn = fnMinusOne + fnMinusTwo;

     fnMinusTwo = fnMinusOne;
     fnMinusOne = fn;
    }
   }

   return fn;
  }

The latter approach is much more efficient O(n) vs O(1.618..ⁿ). However its not as simple as the former. Another approach is to take the former solution and use a local cache:

  /// <summary>
  /// caching version of fib calc
  /// </summary>
  Dictionary<int, long> fibCache = new Dictionary<int, long>();
  internal long Fibonacci(int n)
  {
   long fn = 0;

   // use value from cache if already calculated
   if (fibCache.ContainsKey(n))
    return fibCache[n];

   // not cached, need to work it out
   if (n < 2)
    fn = n;
   else
    fn = Fibonacci(n - 1) + Fibonacci(n - 2);

   // add to cache
   fibCache.Add(n, fn);

   return fn;
  }

This gives us an O(n) runtime with a reasonably simple implementation. This is of course the classic trade-off of time vs. space - we have increased space used (the dictionary) to decrease time.

Finally we want to generate the whole sequence, which we can do in a lazy evaluation way using the yield keyword:

  /// <summary>
  /// returns the first N items in the Fibonacci sequence
  /// </summary>
  public static IEnumerable<long> FibonacciSequence(int n)
  {
   for (int fn = 0; fn < n; fn++)
    yield return Fibonacci(fn);
  }

OpenStreetMap rendering in Silverlight part XI

I had a look to see what was causing the serial drawing nature of the map, and it does appear to being caused by going via the Dispatcher. Silverlight supports multithreading, but any code that want to do UI work must do it in the main thread.

   // get the tile data
   quadrant = GetTileData();
   // we are creating UI elements, go via dispatcher
   map.Dispatcher.BeginInvoke(delegate()
   {
    Canvas canvas = new Canvas();

    Tile tile = new Tile(quadrant, canvas);

    // create instance of renderer
    ITileRenderer tileDrawer = RenderFactory.CreateRenderer(tile);

    // render the tile
    tileDrawer.Render();

    // tell the requester that the tile available to add to UI
    tileLoaded(quadrant.Path, tile);
   });

This means multithreading is great if you have complex calculations going in, and just need to update a simple UI. However for code where the complex work is the UI then you end up hitting a bottleneck. In the code for drawing London I am creating 24 tiles which in total contain about 60k poly-line/gons. I am effectively forced to create them in a serial fashion (my code is non-serial, but each tile has to wait for the last tile to stop using the Dispatcher).

On my PC it took about 30seconds to draw the map of London (once you have run it once all the data should be cached). I've made some changes to speed this up, so it now runs in 15 seconds. I updated the Silverlight Map demo to use this version (you may have to delete the XAP file from your cache to get the newer version)

For the production version I will not be trying to draw the whole of London like this, but it does suggest that progressive rendering will be needed to make the application more responsive. (Progressive as in only draw large items on the tile for the first pass, and then add detail in the subsequent background passes)

I'm not sure if this UI blocking issue will be a problem for other developers (most complex UIs are made using bitmap based tile operations so in this case they would only have 24 UI elements vs. my 60k) and for other non UI intensive applications the current threading model is fine. However it would be nice if this large block could be removed - for example only require the Dispatcher when the tile is added to a visible UI element...

Toggle door puzzle, fast solution

I was recently asked the following question:

You have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door.

question: what state are the doors in after the last pass? which are open which are closed?

If the questions is expressed as is door N open, the answer is

bool doorOpen = (Math.Sqrt(doorNumber) % 1) == 0;

However, as part of going through the puzzle I noticed that there seemed to be a sequence in the offset of the open doors (1, 4, 9), which looked suspiciouly like odd number offsets: 1=1, 4=1+3, 9=4+5 i.e. the value of the offset of the next open door is the previous open door offset plus the next odd number.

Which when I applied it to larger doorsets worked as well. Looking at 50 doors, which doors are open (O) vs closed (c):
[OccOccccOccccccOccccccccOccccccccccOccccccccccccOc]

If you are given the problem of find all open doors in the set, then using the square root approach is O(n). So the square root approach would look like:

private static BitArray GenerateDoorTogleSeriesResult(int doors)
  {
   BitArray result = new BitArray(doors);

   for (int door = 1; door <= doors; door++)
    result[door - 1] = (Math.Sqrt(door) % 1) == 0;

   return result;
  }

whilst my approach looks like:

private static BitArray GenerateDoorTogleResult(int doors)
  {
   BitArray result = new BitArray(doors);

   int odd = 1;
   for (int door = odd; door <= doors; door += odd)
   {
     result[door - 1] = true;
     odd += 2; // next odd number
   }
   return result;
  }

The difference being that for 1,000 doors the square root apprach requires 1,000 square root calculation, whilst mine requires 31 summations. Or in big-oh O(√n).

The calling code looks like:

static void Main(string[] args)
  {
   const int DOORS = 10;
   BitArray suggestedAnswer = GenerateDoorTogleResult(DOORS);
   BitArray fastAnswer = GenerateDoorTogleSeriesResult(DOORS);

   Console.WriteLine("suggested:\n{0}", ShowDoors(suggestedAnswer));
   Console.WriteLine("fast\n{0}", ShowDoors(fastAnswer));
   Debug.Assert(ShowDoors(suggestedAnswer).CompareTo(ShowDoors(fastAnswer)) == 0);
  }

  private static string ShowDoors(BitArray doors)
  {
   StringBuilder sb = new StringBuilder(doors.Length+4);
   sb.Append("[");
   foreach (bool doorOpen in doors)
    sb.Append(doorOpen == true ? 'O' : 'c');
   sb.Append("]\n");

   return sb.ToString();
  }

I subsequently found the proof for this by Francesco Maurolico in 1575.

1575: "Arithmeticorum Libri Duo" by Francesco Maurolico is the first book
to prove a theorem by Mathematical Induction. The theorem was known 2000
years earlier by Pythagorus, but they proved it geometrically. The
theorem is that the sum of the first N odd numbers
1 + 3 + 5 + 7 + 9 + 11 + 13 +... + (2N-1) = N x N

OpenStreetMap into SQL Server 2008 first steps

So as I said in my previous post "OpenStreetMap - show me some data" the next step in evaluating the use of the OSM data was to see how SQL Server 2008 Spatial features might help.

The first thing I wanted to look at was how to define the structure in SQL and work with it from C#. This was mainly to get a feeling for the data types involved. In SQL I created a database (UKGeo) and a table:

CREATE TABLE [dbo].[Nodes](
 [id] [int] NOT NULL,
 [location] [geography] NOT NULL,
 CONSTRAINT [PK_Nodes] PRIMARY KEY CLUSTERED 
(
 [id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

The key point is to note the datatype "geography" being used for the location field, this datatype can handle a number of GIS related structures. We also need a stored procedure to load the data:

CREATE PROCEDURE [dbo].[sp_NodeCreate]
 @id int, 
 @location geography
AS
BEGIN
 -- SET NOCOUNT ON added to prevent extra result sets from
 -- interfering with SELECT statements.
 SET NOCOUNT ON;

 INSERT INTO Nodes(id, location) VALUES (@id, @location);
END

Once again it's a simple enough procedure, with the use of "geography" being the only complexity. From C# we just need to create a command pointing to this stored procedure:

   string sql = "sp_NodeCreate";
   SqlCommand command = new SqlCommand(sql, connection);
   command.CommandType = CommandType.StoredProcedure;

and when setting up the parameters we need to specify that the @location parameter is a Udt (user defined type), in this case geography is already registered in SQL, so we can just name it:

   SqlParameter idParam = new SqlParameter("@id", SqlDbType.Int);
   SqlParameter geoParam = new SqlParameter("@location", SqlDbType.Udt);
   geoParam.UdtTypeName = "geography";
   command.Parameters.Add(idParam);
   command.Parameters.Add(geoParam);

and finally a function to call the procedure:

 private void CreateNodeInDatabase(string id, string longtitude, string latitude)
  {
   SqlGeographyBuilder builder = new SqlGeographyBuilder();
   builder.SetSrid(4326);

   builder.BeginGeography(OpenGisGeographyType.Point);

   builder.BeginFigure(double.Parse(longtitude), double.Parse(latitude));
   builder.EndFigure();

   builder.EndGeography();

   SqlGeography geo = builder.ConstructedGeography;

   command.Parameters["@id"].Value = id;
   command.Parameters["@location"].Value = geo;

   command.ExecuteNonQuery();
  }

This code uses the SqlGeographyBuilder to create an instance of type Point, which is what we want location to contain. I'm sure this code is not the best way to do this, but it serves as a starting point for understanding the relationship between SQL and CLR implementations of spatial information.

OpenStreetMap - show me some data

Project Colbolt requires some understanding of space (actually another project does as well, but one thing at a time!) so I am going to use OpenStreetMap, as it gives me access to the underlying data. I'm not sure I can go the whole way using this - I will have to read the copyright and terms.

 

However, the first part of the plan is to take the OSM data and start to understand it. What I already like is that this is a real sized data set, the UK alone is ~1.2gb of XML, the world is 5.3gb as a zip file. So I'm looking forward to some proper coding. Since I worked in direct marketing a few years ago large geographical datasets are great fun for me (sad git).

 

The stats say that the dataset for the world contains :

• nodes 278 millon;
• ways 23 millon;
• relations 41 thousand.

Node = GPS point (long/lat)

Way = a list of nodes describing a map feature (streets, fields etc)

Relation = a more complex grouping, normally of ways

 

My first step was to play with just the UK data, (always start with a small dataset that you know roughly what it should look like).

 

I wrote a little C# application to read the UK file, which gave me back some stats:

• nodes 6,441,456;
• ways 873,054;
• relations 1,362

So this means we can apply a rough estimate that anything about the UK data can be sized up to the world by multiplying it by 42 (thanks for all the fish!).

Knowing there was no sensible way to try and load the whole XML file into memory (especially when we come back to the world data) I used an XmlReader to process the data. A quick scan which processed all the tags and added up these counts takes less than 30 secs for the UK - so the rule of 42 says it would take about 20 minutes to read the whole world.

 

A stripped down node (removing editing information) looks like:

 

<node id="int" lat="float" long="float">

 

In terms of trying to hold it in memory, stuffing the UK nodes into a List<float[2]> as a pair of floats required 150mb of memory, a sparse array fell over after 1gb and a Dictionary<int, float[2]> used 379 mb.

 

The List<float[2]> approach would lose the node id, which is not really a valid comparison, though I could just use a BitArray to hold the id (as big as the largest ID, a 1 indicating if its in the List<float[2]>, and the number of 1s before it indicating its offset) - this would require another 1mb of memory, but would be slower that the Dictionary approach (not validated this). In either case this is all moot as the rule of 42 shows we would need 7gb just to hold the nodes for the world - and at this stage I'm not doing that!. So we are going to need a storage system...

 

The code so far, is skeletal, but shows what we have to do to process the OSM format - note I could have skipped most of the data, but I wanted to get a fair idea of what reading the data takes:

 

 

  static void Main(string[] args)
  {
   XmlReader reader = XmlReader.Create(@"k:\geo\uk-081015.osm");

   Importer importer = new Importer(reader);
  }

and the Importer class:

 public class Importer
 {
  int nodes = 0;
  int ways = 0;
  int relations = 0;

  public Importer(XmlReader reader)
  {
   // skip boring stuff
   reader.MoveToContent();

   reader.ReadStartElement("osm");

   while (reader.IsStartElement())
   {
    string name = reader.Name;

    switch (name)
    {
     case "bounds":
      ReadBound(reader);
      break;
     case "node":
      ReadNode(reader);
      break;
     case "way":
      ReadWay(reader);
      break;
     case "relation":
      ReadRelation(reader);
      break;
     default:
      throw new Exception("Unknown element encounterd " + name);
    }
   }

   reader.ReadEndElement(); // osm

   Console.WriteLine("nodes {0} ways {1} relations {2}", nodes, ways, relations);
  }

  private void ReadBound(XmlReader reader)
  {
   reader.ReadStartElement();
   reader.Skip();
  }

  private void ReadNode(XmlReader reader)
  {
   // get attributes
   string id = reader.GetAttribute("id");
   string latitude = reader.GetAttribute("lat");
   string longtitude = reader.GetAttribute("lon");

   reader.ReadStartElement(); // node
   reader.Skip();
   nodes++;

   while (reader.Name == "tag")
   {
    reader.ReadStartElement();
    reader.Skip();
   }

   if (reader.NodeType == XmlNodeType.EndElement)
    reader.ReadEndElement(); // node
  }

  private void ReadWay(XmlReader reader)
  {
   // get attributes
   string id = reader.GetAttribute("id");

   reader.ReadStartElement(); // way
   reader.Skip();
   ways++;

   while (reader.Name == "nd")
   {
    reader.ReadStartElement();
    reader.Skip();
   }
   while (reader.Name == "tag")
   {
    reader.ReadStartElement();
    reader.Skip();
   }

   if (reader.NodeType == XmlNodeType.EndElement)
    reader.ReadEndElement(); // way
  }

  private void ReadRelation(XmlReader reader)
  {
   // get attributes
   string id = reader.GetAttribute("id");

   reader.ReadStartElement(); // relation
   reader.Skip();
   relations++;

   while (reader.Name == "member")
   {
    reader.ReadStartElement();
    reader.Skip();
   }
   while (reader.Name == "tag")
   {
    reader.ReadStartElement();
    reader.Skip();
   }

   if (reader.NodeType == XmlNodeType.EndElement)
    reader.ReadEndElement(); // relation
  }

So as a first pass I'm going to stick it into SQL Server 2008 and see what the spatial features can do...

Exception: The DOM/scripting bridge is disabled

Silverlight throws this error if you try and navigate the hosting browser page without setting permissions explicitly.

My calling code in C# looked like this:

HtmlPage.Window.Navigate(new Uri(url), "_top");

Stopping this exception can be done according to MSDN by setting the correct flags.

I was doing this in javascript, using the silverlight.js functions - I just had to add it to the calling code:

  var properties = { width: slWidth, height: slHeight, version: "2.0.31005.0", enableHtmlAccess: "true" };
  var events = { };
  var initParams = params;
  Silverlight.createObject(source, parentElement,
   callbackId, properties, events, initParams);

In the above excerpt I had to add the "enableHtmlAccess" to "true", note that setting it to true without quotes does not work!

Embedding Silverlight in blogger

A post to test embedding of Silverlight applications into blogger

which was achieved by adding to my blogger html template:

<script type="text/javascript" src="http://www.figmentengine.com/assets/script/silverlight.js" ></script>

and then each time I want to embed Silverlight in a post, a holder for the control:

<div id="simplekineticsHost" style="text-align: center;"><object data="data:application/x-silverlight-2," type="application/x-silverlight-2"></object></div>

and some javascript to control the silverlight settings:

<script type="text/javascript">  var host = "http://www.figmentengine.com/";  var source = host + "silverlight/kinetics/simplekinetics.xap";  var parentElement = document.getElementById("simplekineticsHost");  var callbackId = "simplekineticsHost2";  var properties = { width: "500", height: "350", version: "2.0.31005.0"};  var events = {};  Silverlight.createObject(source, parentElement,   callbackId, properties, events);</script>

this was based on this article, with a minor update for the release of silverlight 2.

Markov chain code

A follow up to my markov chain posts, here's the code for a generic markov chain in C#:

A markov chain:

 /// <summary>
 /// Chain implements a markov chain for a type T
 /// allows the generation of sequences based on
 /// a sample set of T items
 /// </summary>
 /// <typeparam name="T">the type of elements</typeparam>
 public class Chain<T>
 {
  Link<T> root = new Link<T>(default(T));
  int length;

  /// <summary>
  /// creates a new chain
  /// </summary>
  /// <param name="input">Sample set</param>
  /// <param name="length">window size for sequences</param>
  public Chain(IEnumerable<T> input, int length)
  {
   this.length = length;
   root.Process(input, length);
  }

  /// <summary>
  /// generate a new sequence based on the samples first entry
  /// </summary>
  /// <param name="max">maximum size of result</param>
  /// <returns></returns>
  public IEnumerable<T> Generate(int max)
  {
   foreach (Link<T> next in root.Generate(root.SelectRandomLink().Data, length, max))
    yield return next.Data;
  }

  /// <summary>
  /// generate a new sequence based on the sample
  /// </summary>
  /// <param name="start">the item to start with</param>
  /// <param name="max">maximum size of result</param>
  /// <returns></returns>
  public IEnumerable<T> Generate(T start, int max)
  {
   foreach (Link<T> next in root.Generate(start, length, max))
    yield return next.Data;
  }
 }

consists of links:

 /// <summary>
 /// parts of a chain (markcov)
 /// </summary>
 /// <typeparam name="T">link type</typeparam>
 internal class Link<T>
 {
  T data;
  int count;
  // following links
  Dictionary<T, Link<T>> links;

  private Link()
  {
  }

  /// <summary>
  /// create a new link
  /// </summary>
  /// <param name="data">value of the item in sequence</param>
  internal Link(T data)
  {
   this.data = data;
   this.count = 0;

   links = new Dictionary<T, Link<T>>();
  }

  /// <summary>
  /// process the input in window sized chunks
  /// </summary>
  /// <param name="input">the sample set</param>
  /// <param name="length">size of sequence window</param>
  public void Process(IEnumerable<T> input, int length)
  {
   // holds the current window
   Queue<T> window = new Queue<T>(length);

   // process the input, a window at a time (overlapping)
   foreach (T part in input)
   {
    if (window.Count == length)
     window.Dequeue();
    window.Enqueue(part);

    ProcessWindow(window);
   }
  }

  /// <summary>
  /// process the window to construct the chain
  /// </summary>
  /// <param name="window"></param>
  private void ProcessWindow(Queue<T> window)
  {
   Link<T> link = this;

   foreach (T part in window)
    link = link.Process(part);
  }

  /// <summary>
  /// process an item following us
  /// keep track of how many times
  /// we are followed by each item
  /// </summary>
  /// <param name="part"></param>
  /// <returns></returns>
  internal Link<T> Process(T part)
  {
   Link<T> link = Find(part);

   // not been followed by this
   // item before
   if (link == null)
   {
    link = new Link<T>(part);
    links.Add(part, link);
   }

   link.Seen();

   return link;
  }

  private void Seen()
  {
   count++;
  }

  public T Data
  {
   get
   {
    return data;
   }
  }

  public int Occurances
  {
   get
   {
    return count;
   }
  }

  /// <summary>
  /// Total number of incidences after this link
  /// </summary>
  public int ChildOccurances
  {
   get
   {
    // sum all followers occurances
    int result = links.Sum(link => link.Value.Occurances);

    return result;
   }
  }

  public override string ToString()
  {
   return String.Format("{0} ({1})", data, count);
  }

  /// <summary>
  /// find a follower of this link
  /// </summary>
  /// <param name="start">item to be found</param>
  /// <returns></returns>
  internal Link<T> Find(T follower)
  {
   Link<T> link = null;

   if (links.ContainsKey(follower))
    link = links[follower];

   return link;
  }

  static Random rand = new Random();
  /// <summary>
  /// select a random follower weighted
  /// towards followers that followed us
  /// more often in the sample set
  /// </summary>
  /// <returns></returns>
  public Link<T> SelectRandomLink()
  {
   Link<T> link = null;

   int universe = this.ChildOccurances;

   // select a random probability
   int rnd = rand.Next(1, universe+1);

   // match the probability by treating
   // the followers as bands of probability
   int total = 0;
   foreach (Link<T> child in links.Values)
   {
    total += child.Occurances;

    if (total >= rnd)
    {
     link = child;
     break;
    }
   }

   return link;
  }

  /// <summary>
  /// find a window of followers that
  /// are after this link, returns where
  /// the last link if found, or null if
  /// this window never occured after this link
  /// </summary>
  /// <param name="window">the sequence to look for</param>
  /// <returns></returns>
  private Link<T> Find(Queue<T> window)
  {
   Link<T> link = this;

   foreach (T part in window)
   {
    link = link.Find(part);

    if (link == null)
     break;
   }

   return link;
  }

  /// <summary>
  /// a generated set of followers based
  /// on the likelyhood of sequence steps
  /// seen in the sample data
  /// </summary>
  /// <param name="start">a seed value to start the sequence with</param>
  /// <param name="length">how bug a window to use for sequence steps</param>
  /// <param name="max">maximum size of the set produced</param>
  /// <returns></returns>
  internal IEnumerable<Link<T>> Generate(T start, int length, int max)
  {
   var window = new Queue<T>(length);

   window.Enqueue(start);

   for (Link<T> link = Find(window); link != null && max != 0; link = Find(window), max--)
   {
    var next = link.SelectRandomLink();

    yield return link;

    if (window.Count == length-1)
     window.Dequeue();
    if (next != null)
     window.Enqueue(next.Data);
   }
  }
 }

which can be called:

static void Main(string[] args)
{
 // sample data set
 string seed = Tidy(@"Twinkle, twinkle, little star,
 How I wonder what you are!
 Up above the world so high,
 Like a diamond in the sky!

 When the blazing sun is gone,
 When he nothing shines upon,
 Then you show your little light,
 Twinkle, twinkle, all the night.

 Then the traveller in the dark,
 Thanks you for your tiny spark,
 He could not see which way to go,
 If you did not twinkle so.

 In the dark blue sky you keep,
 And often through my curtains peep,
 For you never shut your eye,
 Till the sun is in the sky.

 As your bright and tiny spark,
 Lights the traveller in the dark,—
 Though I know not what you are,
 Twinkle, twinkle, little star.
 ");

 // tokenise the input string
 var seedList = new List<string>(Split(seed.ToLower()));
 // create a chain with a window size of 4
 var chain = new Chain<string>(seedList, 4);

 // generate a new sequence using a starting word, and maximum return size
 var generated = new List<string>(chain.Generate("twinkle", 2000));
 // output the results to the console
 generated.ForEach(item => Console.Write("{0}", item));
}

// tokenise a string into words (regex definition of word)
private static IEnumerable<string> Split(string subject)
{
 List<string> tokens = new List<string>();
 Regex regex = new Regex(@"(\W+)");
 tokens.AddRange(regex.Split(subject));

 return tokens;
}

Giving output such as:

twinkle, little star,
how i know not twinkle so.

in the sky.

as your tiny spark,
lights the sky!

when the night.

then the traveller in the dark blue sky you never shut your eye,
till the sky.

as your eye,
till the sun is gone,
when he nothing shines upon,
then you are!
up above the dark,
thanks you did not what you are,
twinkle, twinkle, all the sky!

One of the interesting side-effects of tokenizing using a simple regex is that if the input stream is HTML the Markov chain will treat HTML as words as well and therefore not only generate text that looks like the input, but is also formatted like the input - this also works for punctuation.

Rotating a string

Code snippet to rotate a string:

static void Main(string[] args)
{
 string subject = "abcdefg";

 // test harness, check it handles multiples of size and negatives and zero
 for (int amount = -subject.Length * 3; amount < subject.Length * 3; amount++)
 {
  string result = RotateStringTest(subject, amount);

  char[] inplace = subject.ToCharArray();

  RotateString(inplace, amount);

  if (amount % subject.Length == 0)
   Debug.Assert(result.CompareTo(subject) == 0);
  Debug.Assert(result.CompareTo(new String(inplace)) == 0);
 }
}

/// <summary>
/// Rotates a string
/// </summary>
/// <param name="subject">string to rotate</param>
/// <param name="amount">&lt; 0 left, 0 none, &gt; 0 right</param>
/// <returns></returns>
private static void RotateString(char[] subject, int amount)
{
 int length = subject.Length;

 // negate rotations can be re-expressed as positive amounts
 if (amount < 0)
  amount = length - (-amount % length);

 // 0 rotation mean return unchanged
 if (amount % length == 0)
  return;

 int dest = amount;
 char prev = subject[0];

 do
 {
  dest %= length;

  Swap(ref subject[dest], ref prev);

  dest += amount;
 } while (dest != amount);
}

/// <summary>
/// swaps two chars wihout using temp variable
/// </summary>
private static void Swap(ref char a, ref char b)
{
 a ^= b;
 b ^= a;
 a ^= b;
}

/// <summary>
/// Rotates a string test (slow)
/// </summary>
/// <param name="subject">string to rotate</param>
/// <param name="amount">&lt; 0 left, 0 none, &gt; 0 right</param>
/// <returns></returns>
private static string RotateStringTest(string subject, int amount)
{
 char[] result = subject.ToCharArray();
 int length = subject.Length;

 // negate rotations can be re-expressed as positive amounts
 if (amount < 0)
  amount = length - (-amount % length);

 // 0 rotation mean return unchanged
 if (amount % length != 0)
 {
  for (int pos = 0; pos < length; pos++)
  {
   int dest = (pos + amount) % length;

   result[dest] = subject[pos];
  }
 }

 return new String(result);
}

ps this post was really just to test this javascript code hightlighter.. It seems to work very well for both Xaml and C# - cool!

Silverlight Eyes (Seyes) : eyes follow the mouse in Silverlight (aka xeyes)

Silverlight Eyes (Seyes) watches what you do and reports it to the Boss:



This code uses two main mechanism to achieve the effect

1. It uses Polar coordinates to calculate where the focal point is relative to the centre of each eyeball. (Often the problem people look for as finding the angle between two points). The code uses the angle to calculate what direction the pupil should be facing, and uses the radius (or distance) to proportionally move the pupil away from the centre.


2. It uses clipping to ensure that the pupil is always within the eye ball, which is accomplished by grouping the shapes into a canvas with a clipping region the same size of the eyeball.

The code also allows the user to visualize the calculations taking place by checking/unchecking the checkbox in the top left hand corner. Checking this shows the focal point, the lines of sight from each eye and the key values at the top (angle, distance, start point, end point)

There are a number of implementations of eye movement on the web, however a lot of them do not proportionally move the pupil away from the centre, this means the pupil in these animations are generally stuck at the edge of the eye. If you play with the application you will see that a proportional movement is more realistic - human brains are very good at calculating what other people are looking at based on the pupil positions.

Clipping can be seen in this picture:


The Xaml is as expected with the complication of grouping the parts of the eye together using a Canvas, with a Canvas.Clip to stop drawing outside of the eyeball:

<UserControl x:Class="Eyes.Page"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    >
    <Canvas x:Name="LayoutRoot" Background="White" MouseMove="LayoutRoot_MouseMove" Cursor="Arrow">
    <TextBlock Name="TextDebug" Canvas.Left="10" Canvas.Top="0" Width="1000" Height="100" />
    <CheckBox Name="ShowCalculation" Canvas.Left="0" Canvas.Top="0"
           Checked="CheckBox_Changed" Unchecked="CheckBox_Changed" Canvas.ZIndex="7"
           Cursor="Arrow"/>

    <Ellipse Canvas.Left="300" Canvas.Top="100" Width="230" Height="300" Stroke="Black" Name="Face" Fill="WhiteSmoke" Canvas.ZIndex="1"/>

    <Canvas Canvas.Left="340" Canvas.Top="200" Canvas.ZIndex="2" >
      <Ellipse Canvas.Left="0" Canvas.Top="0" Width="60" Height="40" Stroke="Black" Name="LeftEye" Fill="White" Canvas.ZIndex="2" />
      <Ellipse Canvas.Left="10" Canvas.Top="10" Width="20" Height="20" Fill="Green" Name="LeftPupil" Canvas.ZIndex="2" />
      <Canvas.Clip>
        <EllipseGeometry Center="30,20" RadiusX="30" RadiusY="20" />
      </Canvas.Clip>
    </Canvas>

    <Canvas Canvas.Left="420" Canvas.Top="200" Canvas.ZIndex="2" >
      <Ellipse Canvas.Left="0" Canvas.Top="0" Width="60" Height="40" Stroke="Black" Name="RightEye" Fill="White"  Canvas.ZIndex="2" />
      <Ellipse Canvas.Left="10" Canvas.Top="10" Width="20" Height="20" Fill="Green" Name="RightPupil" Canvas.ZIndex="2" />
      <Canvas.Clip>
        <EllipseGeometry Center="30,20" RadiusX="30" RadiusY="20" />
      </Canvas.Clip>
    </Canvas>

    <Ellipse Canvas.Left="395" Canvas.Top="270" Width="30" Height="40" Stroke="Black" Name="Nose" Fill="DarkGray" Canvas.ZIndex="1"/>

    <Ellipse Canvas.Left="380" Canvas.Top="320" Width="60" Height="30" Stroke="Black" Name="Mouth" Fill="DarkGray" Canvas.ZIndex="1"/>

    <Ellipse Canvas.Left="10" Canvas.Top="60" Width="10" Height="10" Fill="Red" Name="FocusPoint" Canvas.ZIndex="6" />
    <Line Stroke="Red" Name="LineSightLeft"  Canvas.ZIndex="5" StrokeDashArray="2 5" />
    <Line Stroke="Red" Name="LineSightRight"  Canvas.ZIndex="5" StrokeDashArray="2 5" />
  </Canvas>
</UserControl>

The code behind simply responds to the mouse moving, for each eye calculates the polar coordinates and then moves the eyeball proportionally towards the mouse:

public partial class Page : UserControl
{
 bool showCalcs;

 public Page()
 {
  InitializeComponent();

  // default to showing calculations
  ShowCalculation.IsChecked = this.showCalcs = true;
 }

 private void LayoutRoot_MouseMove(object sender, MouseEventArgs e)
 {
  // update UI based on cursor location
  Point cursorPoint = e.GetPosition(LayoutRoot);

  UpdateUI(cursorPoint);
 }

 private void UpdateUI(Point cursorPoint)
 {
  // calculate the location of the focus based using the center of the circle
  Point centerPoint = new Point(cursorPoint.X, cursorPoint.Y);

  if (this.showCalcs)
   FocusPoint.PointSet(new Point(cursorPoint.X - (FocusPoint.Width / 2), cursorPoint.Y - (FocusPoint.Height / 2)));

  // focus eyes on point
  FocusEye(centerPoint, LeftEye, LeftPupil, LineSightLeft);
  FocusEye(centerPoint, RightEye, RightPupil, LineSightRight);
 }

 private void FocusEye(Point pointFocus, Ellipse eye, Ellipse pupil, Line sight)
 {
  // the centre of the eye needs to be converted to a global coordinate
  // which it's parent has
  Point pointStart = new Point(eye.Parent.PointGet().X + (eye.Width / 2), eye.Parent.PointGet().Y + (eye.Height / 2));
  Point pointEnd = pointFocus;
  
  // cartesian to polar conversion
  double angle = Trigonometry.CalculateAngleInDegreesBetween(pointStart, pointEnd);
  double distance = Trigonometry.CalculateDistanceBetween(pointStart, pointEnd);

  if (this.showCalcs)
   TextDebug.Text = String.Format("  {2:N1}deg  {3:N1}    {0}    {1}", new object[] { pointStart, pointEnd, angle, distance });

  // maximum focal distance
  const double MAX_DISTANCE = 500d;

  // the eye will move away from the center
  // of the eye ball proportionally to its maxim view
  // reduced by π to keep some of it visible
  double pupilDistance = (eye.Width / Math.PI) * (distance / MAX_DISTANCE);

  // polar to cartesian conversion
  Point pointPupilOffset = Trigonometry.ConvertPolarToPoint(pupilDistance, angle);

  // adjust for centre of eyeball and pupil
  Point pupilLocation = new Point(
    (eye.Width / 2) + pointPupilOffset.X - (pupil.Width / 2),
    (eye.Height / 2) - pointPupilOffset.Y - (pupil.Height / 2));

  pupil.PointSet(pupilLocation);

  if (this.showCalcs)
  {
   sight.X1 = pointStart.X;
   sight.Y1 = pointStart.Y;
   sight.X2 = pointEnd.X;
   sight.Y2 = pointEnd.Y;
  }
 }

 private void CheckBox_Changed(object sender, RoutedEventArgs e)
 {
  // show calculations visually
  this.showCalcs = ShowCalculation.IsChecked ?? false;

  Visibility visibility = (this.showCalcs) ? Visibility.Visible : Visibility.Collapsed;

  FocusPoint.Visibility = visibility;
  LineSightLeft.Visibility = visibility;
  LineSightRight.Visibility = visibility;
  TextDebug.Visibility = visibility;

  if (this.showCalcs)
   LayoutRoot.Cursor = Cursors.None;
  else
   LayoutRoot.Cursor = Cursors.Arrow;
 }
}

The code uses some extension methods, as I started doing in my previous blog entry:

public static class XamlExtensions
{
 public static Point PointGet(this DependencyObject sobj)
 {
  Point point = new Point((double)sobj.GetValue(Canvas.LeftProperty), (double)sobj.GetValue(Canvas.TopProperty));

  return point;
 }

 public static void PointSet(this DependencyObject shape, Point newLocation)
 {
  shape.SetValue(Canvas.LeftProperty, newLocation.X);
  shape.SetValue(Canvas.TopProperty, newLocation.Y);
 }

 public static Point GetCenterPoint(this Shape shape)
 {
  Point location = shape.PointGet();

  Point centerPoint = new Point(location.X + (shape.Width / 2), location.Y + (shape.Height / 2));

  return centerPoint;
 }
}

and a helper class for doing the trig:

public class Trigonometry
{
 public static double DegreesToRadians(double angle)
 {
  return ((angle * Math.PI) / 180f);
 }

 public static double RadiansToDegrees(double angle)
 {
  return ((angle * 180) / Math.PI);
 }

 public static double CalculateAngleInDegreesBetween(Point pointStart, Point pointEnd)
 {
  // difference between points on Y-Axis
  // Silverlight Y axis needs to be inverted of cartesian coordinates
  double dy = -(pointEnd.Y - pointStart.Y);
  // difference between points on X-Axis
  double dx = (pointEnd.X - pointStart.X);

  // angle of the vector defined by dy, dx
  double angleRadians = Math.Atan2(dy, dx);

  // results in (-π,π], which needs mapping to [0,2π) by adding 2π to negative 
  if (angleRadians < 0)
   angleRadians += 2 * Math.PI;

  double angleDegrees = RadiansToDegrees(angleRadians);

  return angleDegrees;
 }

 public static double CalculateDistanceBetween(Point pointStart, Point pointEnd)
 {
  double dySquared = Math.Pow(pointEnd.Y - pointStart.Y, 2);
  double dxSquared = Math.Pow(pointEnd.X - pointStart.X, 2);

  double distance = Math.Sqrt(dySquared + dxSquared);

  return distance;
 }


 internal static Point ConvertPolarToPoint(double radius, double angleDegrees)
 {
  double angleRadians = DegreesToRadians(angleDegrees);
  
  double x = radius * Math.Cos(angleRadians);
  double y = radius * Math.Sin(angleRadians);

  return new Point(x, y);
 }
}

Moving shapes in Silverlight

Having written the same code too many times, I thought I better start making life more easy for myself. In Silverlight you often want to change the location of a shape (or more correctly a DependancyObject)

The code I kept writing was move the location of a shape, such as in drag-n-drop.

I've written this as an Extension method, giving:

public static class XamlExtensions
{
  public static void PointSet(this DependencyObject shape, Point newLocation)
  {
    shape.SetValue(Canvas.LeftProperty, newLocation.X);
    shape.SetValue(Canvas.TopProperty, newLocation.Y);
  }
}

which allows:

shape.PointSet(cursorPoint);

rather than

PointSet(shape, cursorPoint);