I was introduced to cellular automatons a good decade ago through books written by Peter Small. Back then, we were using Adobe (then Macromedia) Director as our primary development platform, where object-oriented programming was still a bit of a novelty. Small's writings explained OOP using artificial life forms such as cellular automatons, with Conway's Game of Life being an oft used concrete example. I was hooked and would spend hours running patterns on a simple implementation of the game that shipped with Windows Entertainment Pack.

But I never got around to implementing the application myself until now. The game has a fairly simple model that does not take much effort to build. This is handy when learning a new platform or language, leaves the programmer free to explore the features of the framework instead of spending cycles trying to nail down the business logic correctly using an unfamiliar language syntax.

Background

There are plenty of resources available online that describe, implement and demonstrate this game. The basic essence of the game is a two-dimensional array of cells and an endless loop that iterates over these cells to update their state depending upon some simple rules.

1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

Implementation

This implementation is made up of the following classes.

MainWindow.xaml and MainWindow.xaml.cs

<DockPanel Name="layout">
    <ToolBar DockPanel.Dock="Top">
        <Button Content="Start" Name="btnStart" Height="23" Width="75" Margin="5" Click="toggleStart_Click" />
        <Button Content="Next" Name="btnNext" Height="23" Width="75" Margin="5" Click="nextIteration_Click" />
        <Button Content="Clear" Name="btnClear" Height="23" Width="75" Margin="5" Click="clear_Click" />
        <Button Content="Randomize" Name="btnRandomize" Height="23" Width="75" Margin="5" Click="randomize_Click" />
    </ToolBar>
    <ScrollViewer HorizontalScrollBarVisibility="Auto" VerticalScrollBarVisibility="Auto">
        <life:BoardView x:Name="view" DockPanel.Dock="Top" Margin="10" Click="view_Click"></life:BoardView>
    </ScrollViewer>
</DockPanel>

The MainWindow class stores a reference to an instance of BoardModel as a private field. Buttons in the toolbar are wired to trigger event handlers in the MainWindow class, which in turn trigger public methods exposed by the model and view instances.

BoardModel.cs

BoardView.cs

private void drawCells()
{
    if (null == this.values)
    {
        return;
    }

    using (DrawingContext dc = this.cells.RenderOpen())
    {
        int x = 0;
        int y = 0;
        Rect rect = new Rect(OUTLINE_WIDTH, OUTLINE_WIDTH, Constants.CELL_SIZE - OUTLINE_WIDTH, Constants.CELL_SIZE - OUTLINE_WIDTH);

        for (int i = 0; i < values.Length; i++)
        {
            x = (i % Constants.CELLS_X);
            y = (i / Constants.CELLS_X);
            rect.Location = new Point((x * Constants.CELL_SIZE) + OUTLINE_WIDTH, (y * Constants.CELL_SIZE) + OUTLINE_WIDTH);

            if (1 == values[i])
            {
                dc.DrawRectangle(Brushes.Red, null, rect);
            }
        }
    }
}

One must fetch a reference to a DrawingContext in order to draw content onto a DrawingVisual. This is done through the RenderOpen() method of the DrawingVisual. Since we are only drawing basic rectangles, we can use the in-built DrawRectangle() method of the DrawingContext class to draw this shape for us. Internally, this method still uses a GeometryDrawing and a subclass of the Geometry class, but abstracts away those details for convenience.

The drawing is displayed on the screen by adding the Visual instances to the visual tree of the BoardView class, which is done in its constructor.

public BoardView()
    : base()
{
    this.AddVisualChild(this.grid);
    this.AddLogicalChild(this.grid);

    this.AddVisualChild(this.cells);
    this.AddLogicalChild(this.cells);

    this.visuals = new DrawingVisual[] { this.grid, this.cells };

    this.drawGrid();
    this.drawCells();
}

Additionally, the BoardView class also overrides the VisualChildrenCount, GetVisualChild and MeasureOverride members of the FrameworkElement class.

protected override int VisualChildrenCount
{
    get
    {
        return this.visuals.Length;
    }
}

protected override Visual GetVisualChild(int index)
{
    if (index < 0 || index > this.visuals.Length)
    {
        throw new ArgumentOutOfRangeException("index");
    }

    return this.visuals[index];
}

protected override Size MeasureOverride(Size availableSize)
{
    return new Size(Constants.CELLS_X * Constants.CELL_SIZE, Constants.CELLS_Y * Constants.CELL_SIZE);
}

The BoardView class instance also dispatches an event when the user clicks on a cell on the board. This is in turn passed over to the model instance via the window, causing the model to toggle the state of the cell that was clicked.

ClickEventArgs.cs

Bit packing and unpacking is a handy way of consolidating multiple data values into a single variable, thus compressing the amount of data being stored or transmitted. The number of values that can be stored depends upon the width of the data to be stored as well as the type of the value that it is packed into. A simple byte can store up to 8 bits of data. Larger types such as ints can store up to 16, 32 or 64 bits. This is an especially efficient technique for storing several small-width values, often smaller than the smallest width supported by a platform (such as byte or boolean flags) into a single large value such as a 32-bit integer.

Bit flags are commonly used for implementing low-level features, such as storing file access-permissions or packing values into a single value before transmitting across a bus. However, they can be applied with equal ease to higher level tasks such as storing user preferences or choosing which widgets to display from an enumerated list. We will see here how to use bit flags to store font formatting preferences, and apply them later to a label.

Bitwise Operators

There are a couple of operators we need to understand before we can move on to the implementation. Bitwise operators, by definition, work on individual bits inside a value. Since they are implemented directly by the processor itself, they are much faster than arithmetic operators such as division and multiplication. We will use bitwise AND (&), bitwise OR (|) and left shifts (<<) in this exercise.

A bitwise AND operation takes the binary representations of two values and performs a logical AND operation on each bit. The result is 1 in every position where both the bits are 1, and 0 if either or both bits are 0.

    001010
AND 011011
    ------
    001010

Bitwise OR on the other hand, compares two bits in corresponding positions, and sets the result to 1 if either of them is 1, or to 0 if both of them are 0.

    001010
OR  011011
    ------
    011011

Bitwise left shift operator moves individual bits within a single value by the number of places specified in the second operand. The value is padded with 0s on the right, and the left-most bits are dropped off.

    001010 << 1 = 010100

Implementation

We set up a simple Windows Forms project and draw three checkboxes and one label on the form. The aim is to have the checkboxes control three font properties of the label - weight, style and underlining. All checkboxes are given appropriate labels and configured to execute the _changeFormatting method of the form every time the CheckStateChanged event is fired. The code for this method is shown below.

private void _changeFormatting(object sender, EventArgs e)
{
    byte flags = 0;

    flags = (byte)(
        Convert.ToByte(this.chkUnderline.Checked) << 2 |
        Convert.ToByte(this.chkItalic.Checked) << 1 |
        Convert.ToByte(this.chkBold.Checked)
        );

    Font f = new Font(this.label1.Font.FontFamily, this.label1.Font.Size, (FontStyle)(
        (flags & (byte)FontStyle.Underline) |
        (flags & (byte)FontStyle.Italic) |
        (flags & (byte)FontStyle.Bold)
        ));

    this.label1.Font = f;
}

Packing

In the first statement, the flags variable is populated with the values of each checkbox. We want to store the three flags in the last three bits of a single byte.

In order to do so, we take the value of each boolean (either true or false), convert it into a byte, then shift it by an appropriate number of positions. The value of the underline flag is to be stored in the 2nd bit (starting from 0). So we left-shift its value by 2. Similarly, the italic flag is stored in the 1st position, so its boolean value is shifted by 1. The value of the bold flag does not need to be shifted at all.

    00000001 << 2 = 00000100 // Underline
    00000001 << 1 = 00000010 // Italic
    00000001                 // Bold (no shifting required)

A consolidated value can be generated by ORing the three values together.

    00000100
 OR 00000010
 OR 00000001
    --------
    00000111 // Decimal value 7

    00000000
 OR 00000010
 OR 00000001
    --------
    00000011 // Decimal value 3

    00000100
 OR 00000000
 OR 00000001
    --------
    00000101 // Decimal value 5

The decimal value can then be stored in a database or other persistent storage system as an integer or byte. This is better than having to store three boolean fields. This information can transmitted across systems too as a packed unit, to be unpacked later only when the preferences have to be applied to a display element.

In our example, we are unpacking and applying the values immediately for brevity. But a more practical situation would probably involve serializing the value somewhere, then deserializing and applying the font properties later at another location.

Unpacking

In order to apply the font styles on a display element, the individual values of each style parameter must be extracted from the packed value and then applied. The .NET framework defines enumerations for each of these style parameters in the System.Drawing.FontStyle enum. The values for each style parameter are listed below.

You will notice that each enumeration is double the value of its predecessor, hence moving the digit 1 by one position leftwards with every increase. This is a key feature of bit flags. Each element differs from the others only in the position of the 1 bit. Thus, the value of a given flag can be extracted from the packed value by ANDing the packed value with the value of the enumeration.

     00000111 // Packed value decimal 7
AND  00000100 // Underline enum decimal 4
     --------
     00000100 // Result - show underlines

This operations shows that the value of the underline flag is true. If the packed value was the decimal 3 instead of 7, then the operation would play out as shown below, resulting in the value 0 for the underline flag.

     00000011 // Packed value
AND  00000100 // Underline enum
     --------
     00000010 // Result - hide underlines

All that is needed then is to convert the result byte into a boolean and apply it wherever required. In our example above, the constructor of the Font class requires the values packed together any way as a FontStyle enum. To do this, each bit is ANDed with its corresponding enum, then all of them are combined together again using an OR operation. The resultant byte is cast into a FontStyle before being passed to the constructor.

Long years in the software industry have conditioned me to dread last-minute feature additions. Something as innocuous as a mailer subscription form can turn into a minefield of security and privacy concerns if done incorrectly. In the book Peopleware, writers Tom DeMarco and Timothy Lister have expressed how managing software projects is less of a technical challenge and more of a social interaction maze. Keeping clients happy while still being able to convince them about the intensive behind-the-scenes work behind the simplest of features takes a lot of people-skill.

Incomplete or inaccurate specifications can complicate the problem even further. This can be a result of the specifications being created by inexperienced people, or people with little or no understanding of UX or software. This becomes particularly insidious because the presence of a specification (even if it is only superficial) lulls stakeholders into thinking that the project is under control. But all sorts of bad things begin to happen once the rubber meets the road. Designers work towards an incomplete layout. Engineers make an incomplete product, which results either in customer dissatisfaction or time and cost overruns.

A seemingly simple feature such as pagination requires quite a bit of programming just to make it work at all. More code has to be written to consider common cases such as representation of and navigation through large data sets. Usability issues have to be taken into account, such as device specifics to handle different input systems such as touch screens, keyboards and mouse clicks.

Product requirements often begin with a very vague idea of what is required. "A blog application needs comments", says the product manager. So the engineering team gets to work and churns out a comment form, and a display mechanism. But nobody expected Jeff Atwood to deploy the software on his website, which regularly gets 3000 comments in the first 10 minutes of a post being put up, and nobody can now open his website any more because the database server choked on retrieving so many comments for a million simultaneous visitors (yes, even if they are flat discussions).

After Jeff posts a rant on his website, the product manager eats his hat and gets back to writing a specification for the comment pagination, as he should have to begin with. This is his design from the first draft of the specification.

Previous | 1 | 2 | 3 | 4 | 5 | Next

The engineering lead looks at the design and notices that it is still incomplete. The Previous and Next buttons will not do anything useful if the visitor is already on the first or last page. So those links will have to be disabled as necessary. The revised design looks like this.

Previous | 1 | 2 | 3 | 4 | 5 | Next

Previous | 1 | 2 | 3 | 4 | 5 | Next

But what happens when there are more than 5 pages of comments on the post? If they keep increasing the page count, eventually it will have to be wrapped to the next line or made to run off the screen, either of which looks very ugly.

Previous | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | Next

Somebody suggests letting users type in the page number in a text field that also doubles up as the current page indicator.

First |  | Last

While this is easy, it is not very user friendly. How many pages of comments do we have in all? What happens if the visitor enters too large a number or a non-numeric value? Visitors on mobile devices probably will not be very pleased to have to type very frequently.

After yet another round of discussion, the team finally decides that visitors are probably not interested in viewing every comment on the blog. Yet, showing the total number of comments would be desirable for Jeff because it is a measure of his popularity. Fitness models measure bicep circumference. Geeks measure blog comments.

Somebody suggests the following user interface, which seems to fit the bill.

1 | 2 | 3 | 4 | 5 ... 274

1 ... 65 | 66 | 67 | 68 ... 274

1 ... 270 | 271 | 272 | 273 | 274

The first and last page links are always displayed. The rest of the links are dedicated to displaying the current page number and a range of values around it. For the end user - the website visitor - the control is very simple and easy to learn at a glance.

Of course, this entire exercise is moot if it is done without proper usability testing with relevant target audiences in mind. Formal testing methods are often inaccessible to small teams, but hallway tests can still provide feedback, and results in a much better product.

Bit manipulations are second nature to electronics engineers, embedded programmers and a swathe of engineers who work with low-level systems software such as operating systems, languages and critical frameworks. While it does seem daunting at first, the fundamentals are very simple as explained in my previous post. This post builds upon those concepts to implement a simple binary clock using C#.

The core of the clock is in the BinaryClock class that inherits PictureBox, since this is primarily a visual control and needs a visual context to display its output. Inheriting from PictureBox also makes it easy to use as a drag-and-drop control in the Visual Studio IDE.

BinaryClock consolidates the timekeeping and drawing capabilities into a single class (the OO design crowd may cringe now). An instance of the Timer class ticks every second to invalidate the display and trigger a refresh. The mode field determines the method used to display the clock face - pure binary or binary-coded decimals. Its value can be set from one of the values in the imaginatively-named enum in the same class called Modes.

This brings us to the paint method which is triggered whenever the control has to be redrawn.

void _paint(object sender, PaintEventArgs e)
{
    DateTime dt;
    int h;
    int m;
    int s;
    Rectangle area;
    int offsetX;
    int offsetY;

    dt = DateTime.Now;
    h = dt.Hour;
    m = dt.Minute;
    s = dt.Second;

    area = new Rectangle(0, this.Height - BinaryClock.RECT_SIZE, BinaryClock.RECT_SIZE, BinaryClock.RECT_SIZE);
    offsetX = this._columns * (BinaryClock.RECT_SIZE + BinaryClock.RECT_OFFSET);
    offsetY = BinaryClock.COL_OFFSET;

    // Get bits for the hours component
    this._draw(h, e.Graphics, ref area);
    area.Offset(offsetX, offsetY);

    // Get bits for the minutes component
    this._draw(m, e.Graphics, ref area);
    area.Offset(offsetX, offsetY);

    // Get bits for the seconds component
    this._draw(s, e.Graphics, ref area);
}

This method begins by fetching the current time and extracting its components. Offset values required for the drawing are also initialized depending upon the current display mode. It then makes three calls to the drawing method to draw the appropriate graphics for the hour, minute and second values. Two draw methods are implemented in this class - drawBinary and drawBCD. Both take three parameters - the value to be represented, the Graphics object, and initial position.

Binary Drawing

The drawBinary method draws 6 boxes, vertically stacked, in a single column to represent the value in pure binary.

The application running in pure binary mode

for (i = 0; i < 6; i++)
{
    bit = value & (1 << i);

    if (0 == bit)
        g.FillRectangle(_offBrush, area);
    else
        g.FillRectangle(_onBrush, area);

    area.Offset(0, - (BinaryClock.RECT_SIZE + BinaryClock.RECT_OFFSET));
}

The value of each bit in a single number is extracted through the following snippet.

bit = value & (1 << i);

This is an application of testing if the n-th bit is set in a number. The digit 1 (0b00000001) is left-shifted to the position at which the bit in the value is to be inspected, then ANDed with the value.

0b00001010 & 0b00000001 = 0b00000000
0b00001010 & 0b00000010 = 0b00000010
0b00001010 & 0b00000100 = 0b00000000
0b00001010 & 0b00001000 = 0b00001000

The bit has been set if the result is greater than 0.

This is applied in a continuous loop through all the bits in the number. The colour of the box is determined by the value of the bit in that position. Zero is filled with the off colour, and any other value is filled with the on colour.

Binary-coded Decimal

The second function - drawBCD - has the same signature as drawBinary. The only difference is in the way it represents the number on the canvas. Instead of drawing the component value in a single column, it splits it into two decimal digits and draws each digit in its own column. The individual digits are extracted by dividing and modding with 10, then calling the drawBinary function for each digit.

The application running in BCD mode

The Visual Studio solution for this project can be downloaded from here as a ZIP archive.

Binary clocks are probably one of the epitomes of geek cred. Everybody can read an analog or digital clock that represents numbers in base 10. But it takes a geek to read the time from a gadget that uses an obscure and cryptic number system. Call it the hipsterdom of technology.

Understanding Number Systems

Modern number systems are remarkably similar to each other conceptually. The only difference is their applicability in different scenarios. The decimal system is in common use every day all over the world. Many fundamental concepts that are carried forward into other systems were refined using base 10 numerals. The most essential of these are naming unique digits, and positional notation.

Unique Digits

Numbers are a strange beast in that they have no end. The most primitive counting systems used scratches in the dust or pebbles to keep count. It became easier to represent larger values with the advent of separate symbols to identify different numbers. Roman numerals had special symbols for many numbers such as 5 (V), 10 (X) and 50 (L). While this made representation of larger values more compact, it still wasn't perfect. It took the Indians, and later the Arabs, to finally come up with an extensible, yet concise number system that could represent any imaginable value.

Since it is impossible to have unique representations for every number when they are essentially infinite, the Hindu-Arabic numeral system instead has 10 unique symbols in base 10 to represent the digits from 0 to 9. By applying positional notation, all possible numerals can be represented by using these 10 symbols. Numbers greater than 9 are represented by stringing digits together. The leftmost digit has a greater magnitude than the one to its right, and the value of the numeral is a sum of its digits multiplied by their magnitudes.

Positional Notation

The magnitude itself is a power of the base. In the decimal system, the base is 10. Hence, the magnitude is 10 raised to a power that increases by one for every leftward shift. The rightmost number is multiplied by the 0th power of 10 and represents the ones position. The position to its immediate left is multiplied by 10 raised to 1, the next by 10 raised to 2, and so on.

Let us take the numeral 256 to illustrate this.

256 = 2 × 10² + 5 × 10¹ + 6 × 10⁰
    = 2 × 100 + 5 × 10 + 6 × 1
    = 200 + 50 + 6
    = 256

Binary uses the same concept to represent values. The only difference is that the rollover value in binary is 1 since it has only two digits - 0 and 1, and the number is multiplied by a power of 2 instead of a power of 10. It is also more verbose than the decimal number system. Even a relatively small value like 25 requires 5 digits in binary - 11001.

11001 = 1 × 2⁴ + 1 × 2³ + 0 × 2² + 0 × 2¹ + 1 × 2⁰
      = 1 × 16 + 1 × 8 + 0 × 4 + 0 × 2 + 1 × 1
      = 16 + 8 + 0 + 0 + 1
      = 25

In this sense, number systems are identical to odometers. When the rightmost digit reaches a certain maximum value, it goes down back to zero and the digit to its immediate left increases by one. If the second column is also at the largest digit, then it too resets to zero and the increment is applied to the third column.

Being able to read binary representations is obviously an essential requirement to read the time in a binary clock.

Structure of a Binary Clock Face

There are two types of binary clocks possible - ones that use binary coded decimals, and true binary clocks.

A clock face that uses binary-coded decimal notation

A BCD clock face is divided into six columns - two for each component of the time. Each column contains up to four rows, one for each power of two. The leftmost two columns represent the hour, the middle two are minute columns and the last two represent seconds. Each column represents a single base 10 digit of time. For example, if the value of column one is 1 and that of column 2 is 0, then the clock is representing the 10th hour of the day, or after 10 am. Similarly, if the value in column three and four is 3 and 2 respectively, the clock is in the 32nd minute of the current hour.

A clock face that represents time components in pure binary notation

True binary clocks represent each time component in a single column. Such clocks require only three columns, and up to six rows in each column to adequately cover all required values. Each column represents the absolute value of the component in binary encoding. For example, 0b001010 in the hour column represents 10 (1 × 2³ + 1 × 2¹). 0b100000 in the minutes column represents the 32nd minute of the hour. Together, the two values indicate the time as 10:32 am.

Even if you are not very accomplished at converting from binary to decimal easily, there are only a few values required to display the time in binary. Most people can easily memorize the light sequences and the values they represent after a few days of practicing.