Martin Doms

In part 2 we created a working lighting model for our ray tracer and got a step closer to creating a realistic-looking sphere. Soon we will increase the realism further by applying reflections and creating shapes other than spheres. However, this article is going to be about multiplicity. We are going to extend our program to handle multiple spheres and multiple light sources. This will help teach you about working with important concepts in functional programming as well as learn about some of the F# collections libraries.

But before we get started I just want to tidy up the code a little, because it is just a bit badly formed.

At the moment a sphere has a diffuse colour and we are assuming that specular highlights are always white. While this generally gives good results, it’s not perfect. Because we will want to do more with a shape’s material than just lighting at some point (textures, translucency, etc) let’s break out material properties into another type. Also, the intersection type doesn’t really need a reference to the shape it intersects – it only needs to know the material (as well as the other information it has). So let’s change that too. After you make these simple changes to your types, go through the code and make the appropriate changes, including fixing the code that breaks and removing magic constants from the colorAt function.

type Material = { diffuseColor: Color; specularColor: Color; shininess:float }
type Sphere   = { center:Point3D; radius:float; material:Material }
type Intersection = { normal:Vector3D; point:Point3D; ray:Ray; material:Material; t:float }

//.... and constructing the sphere will look like
let material = { diffuseColor=Color(0.8, 0.1, 0.1); specularColor=Color(0.7,0.7,0.7); shininess=40.0 }
let sphere = { center=Point3D(1.0,1.0,1.0); radius=0.4; material=material }

For completeness, here is the colorAt function.

let colorAt intersections scene =
    let closest = List.minBy(fun i -> i.t) intersections
    let kd = closest.material.diffuseColor
    let ks = closest.material.specularColor
    let Ia = scene.ambientLight
    let L = norm (scene.light.position - closest.point)
    let Id = Math.Max(0.0, Vector3D.DotProduct(L, closest.normal))
    let V = scene.camera.position - closest.point
    let H = norm (L + V)
    let Is = Math.Pow(Math.Max(0.0, Vector3D.DotProduct(H,closest.normal)), closest.material.shininess)
    let ambient = kd * Ia
    let diffuse = kd * Id
    let specular = ks * Is
    ambient + diffuse + specular

I’m still not quite happy with the layout of this code. It’s weird that colorAt does the calculation to find the closest intersection point to the camera (or ray origin, more precisely). I’d prefer to move that into the calling function, so in the main nested loop

match intersects with
            | [] -> bmp.SetPixel(x,y,Color.Gray)
            | _ -> let color = colorAt intersects scene
                   bmp.SetPixel(x,y, Color.FromArgb(255, (int)(color.r*255.0), (int)(color.g*255.0), (int)(color.b*255.0)))

becomes

match intersects with
            | [] -> bmp.SetPixel(x,y,Color.Gray)
            | _ -> let color = colorAt (List.minBy(fun i -> i.t) intersects) scene
                   bmp.SetPixel(x,y, Color.FromArgb(255, (int)(color.r*255.0), (int)(color.g*255.0), (int)(color.b*255.0)))

And making the corresponding change in colorAt is simple:

let colorAt intersection scene =
    let kd = intersection.material.diffuseColor
    let ks = intersection.material.specularColor
    // etc...

Now we want to allow for multiple spheres. Change the definition for Scene so it looks like

type Scene = { camera:Camera; spheres:Sphere list; ambientLight:Color; light:Light }

Note the word ‘list’. This means that the ‘spheres’ field will carry a typed list of Sphere values.

This of course breaks our castRay function, which depends heavily on the Scene having just a single sphere. So currently the castRay function performs the task of calculating intersection points. Really what castRay should be doing is delegating this task to another function and simply collecting and returning the results. So let’s make some changes to castRay and also define a separate intersect function to handle the sphere intersect code.

let intersect ray sphere =
    let s = ray.origin - sphere.center
    let rayDir = norm ray.direction
    let sv = Vector3D.DotProduct(s,rayDir)
    let ss = Vector3D.DotProduct(s,s)
    let discr = sv*sv - ss + sphere.radius*sphere.radius
    if discr < 0.0 then []
    else
        let normalAtTime t = norm (pointAtTime ray t - sphere.center)
        let (t1,t2) = (-sv + sqrt(discr), -sv - sqrt(discr))
        [ { normal = normalAtTime t1; point = pointAtTime ray t1; ray = ray; material=sphere.material; t=t1 };
          { normal = normalAtTime t2; point = pointAtTime ray t2; ray = ray; material=sphere.material; t=t2 } ]

let castRay ray (scene:Scene) =
    scene.spheres |> List.collect (fun x -> intersect ray x)

The intersect function merely returns a list of intersections with a sphere. We will be making this more generic to handle other shapes later, but for now this works fine. Incidentally, this is the reason we’re using a list instead of a tuple or something where handling only two results would have been more appropriate.

Notice the |> operator in castRay. This is called the pipeline operator and Dom Syme, the man behind the F# language, it is “perhaps the most important operator in F# programming.” (This quote is from Expert F# 2.0). Basically it allows us to “pipe” the value of some expression into another expression, which results in some pretty cool looking code. We’ll be using the pipelining feature more later on.

So this is pretty much all we need to render multiple shapes. Let’s add another shape to the scene and take a look.

    let material1 = { diffuseColor=Color(0.8, 0.1, 0.1); specularColor=Color(0.7,0.7,0.7); shininess=40.0 }
    let sphere1 = { center=Point3D(-0.1, -0.1, 1.8); radius=0.39; material=material1 }
    let material2 = { diffuseColor=Color(0.1, 0.1, 0.8); specularColor=Color(0.7,0.7,0.7); shininess=20.0 }
    let sphere2 = { center=Point3D(0.4, 0.3, 2.0); radius=0.3; material=material2 }

    let scene = { camera=camera; spheres=[sphere1;sphere2]; ambientLight=Color(0.2,0.2,0.2); light=light }

Of course you are free to use as many spheres as you like – experiment with procedurally creating arrays of spheres, it can be pretty fun.

We’re going to take a similar approach for using multiple light sources. Here we’re going to use nested inner functions (closures) to break our code into functions which we can hide from the calling code. colorAt now looks like

let colorAt intersection scene =
    // nested function for ambient color
    let ambientColorAt intersection scene =
        scene.ambientLight * intersection.material.diffuseColor

    // nested function for specular color
    let specularColorAt intersection scene =
        let ks = intersection.material.specularColor
        let V = scene.camera.position - intersection.point

        let specularAtLight light =
            let L = norm (light.position - intersection.point)
            let H = norm (L + V)
            let Is = light.color * Math.Pow(Math.Max(0.0, Vector3D.DotProduct(H,intersection.normal)), intersection.material.shininess)
            ks * Is

        List.sumBy(fun x -> specularAtLight x) scene.lights

    //nested function for diffuse color
    let diffuseColorAt intersection scene =
        let kd = intersection.material.diffuseColor

        let diffuseAtLight light =
            let L = norm (light.position - intersection.point)
            let Id = light.color * Math.Max(0.0, Vector3D.DotProduct(L, intersection.normal))
            kd * Id

        List.sumBy(fun x -> diffuseAtLight x) scene.lights

    let ambient = ambientColorAt intersection scene
    let specular = specularColorAt intersection scene
    let diffuse = diffuseColorAt intersection scene

    ambient + diffuse + specular

On a side note, I just noticed that throughout this series I have made an embarrassing mistake – I forgot to multiply the light intensity values with the surface reflectance, resulting in all lights behaving as though they were coloured 1.0,1.0,1.0. This is fixed in the preceding code.

You can see from this snippet that we are summing the values of all colours collected from all light to create specular and diffuse values. Setting up a second light source allows us to view the results.

    let light = { position=Point3D(1.0,4.0,-3.0); color=Color(0.5,0.5,0.5) }
    let light2 = { position=Point3D(-3.0,-2.0,-1.0); color=Color(0.8,0.8,0.8) }
    let scene = { camera=camera; spheres=[sphere1;sphere2]; ambientLight=Color(0.2,0.2,0.2); lights=[light;light2] }

Now there’s one more thing I want to do before I close off this entry. Right now other objects are ignored when we are summing up the lights. If we just check for intersections between each intersection point and the light source we are inspecting we can see if that intersection point should be in shadow. Seems simple enough, so let’s implement some simple shadowing.

So all we need to do is check whether a ray between the intersection point and the light source intersects ANY other shapes. If not, we know there’s a clear path to the light source. If so, that light source doesn’t contribute to the lighting at that intersection point. We can ignore ambient lighting, because it applies whether we are in shadow or not. Make the following modifications to the colorAt function.

let colorAt intersection scene =
    // check if we're in shadow
    let inShadow point light =
        let ray = { origin = intersection.point; direction = light.position - intersection.point}
        let intersections = castRay ray scene
        if intersections.Length = 0 then false
        else true
// ...then where diffuse light is calculated...
    let diffuseColorAt intersection scene =
        let kd = intersection.material.diffuseColor

        let diffuseAtLight light =
            let L = norm (light.position - intersection.point)
            let Id = light.color * Math.Max(0.0, Vector3D.DotProduct(L, intersection.normal))
            if inShadow intersection.point light then Color(0.0,0.0,0.0)
            else kd * Id            

        List.sumBy(fun x -> diffuseAtLight x) scene.lights

Although I’m sure technically we should do the same for specular light, in my experience it looks like ass with these sharp shadows, so I keep specular light around. I’ll let you judge for yourself which is better. At some stage we’ll implement more advanced lighting and shadowing and we won’t need to decide. So here’s the scene rendered earlier with our shadow model. On the left if with specular lighting shadowed, the right not shadowed. I prefer the right.

The banding effect on the shadows occurs because I included a third light to demonstrate that shadows can have multiple levels of darkness, depending on how many lights are blocked.

In the next article we will finally start actually ray tracing, which means reflections! We’ll get to play with recursion and we’ll also start using shapes other than spheres. The source code so far is available here.

In the previous post we set up the bones of a ray caster and got it rendering a very basic “sphere” with no shading or anything. Today we’re going to make the sphere look more like a real sphere by applying a Phong shading model to it.

If we want to shade each pixel on the sphere correctly then we’re going to need to get some information about the point of intersection between the ray and the sphere. Before getting into code, we’ll just start with the mathematical description of our lighting model. This will be brief and I encourage you to investigate further if you have never done any kind of shading or lighting before.

We are going to be working with three different kinds of lighting:

1. Ambient – ambient lighting is a general light that applies to every surface in the scene, regardless of orientation, shadows, etc. Ambient light has no source. You can think of ambient light as the base-line or “zero-point” of the scene’s lighting. It’s the amount of light that a portion of the scene will have when in complete shadow. Although there is no basis for ambient light in physics, without it things just look unrealistic. Perfectly black shadows look wrong.
2. Diffuse – When light from a source strikes a surface, the surface reflects that light in the same quantity in every direction (think of this as a surface reflecting photons in perfectly random directions). The strength of a diffuse reflection is dependent on the angle of the surface with the light travel path. If a surface is perfectly perpendicular to the ray of light then the reflection will be total (100%). The reflectivity drops as the surfaces turns its face on an angle to the light, until it reaches 0% when the surface is 90′ to the light source (this will be described in more detail soon).
3. Specular – Specular lights are those little highlights in a scene, particularly on curved surfaces. Like diffuse reflections, specular highlights are dependent on the angle of the surface, but in a different way. Specular lighting will be described in detail towards the end of this article.

The three kinds of light add together to form a fully lighted scene:

So let’s define a new data type in our program that represents an intersection between a ray and our sphere. For now we’re still working under the assumption that the scene will only ever have a single sphere. I find working iteratively like this is a good workflow for F#, especially with F# interactive.

type Intersection = { normal:Vector3D; point:Point3D; ray:Ray; sphere:Sphere; t:float }

An intersection has a surface normal, a point in space, an associated ray and a t value, which describes how far along the ray the intersection happens. We can just derive t from point (or vice versa) but I find it convenient to store both.

Now we’re going to want our castRay function to return Intersection objects instead of true or false. It should be capable of returning multiple intersections for a given ray. A sphere will usually have two intersections with a ray, and it’s not difficult to imagine shapes that will have more than two. So we’ll return a list of intersections.

In the previous article all we did for the ray-sphere intersection was compute the discriminant of a quadratic, but in order to find the exact point in space of the intersection we’ll need to solve the full equation for both solutions (if you don’t know the quadratic formula, read this). Here is the modified castRay function. I have also included a small utility function which we’ll make use of, pointAtTime, which just computes the point of some line given by p = a + bt for a given value of t.

/// Get the position of a ray at a given time
let pointAtTime ray time =
    ray.origin + time * ray.direction

let castRay ray (scene:Scene) =
    let s = ray.origin - scene.sphere.center
    let rayDir = norm ray.direction
    let sv = Vector3D.DotProduct(s,rayDir)
    let ss = Vector3D.DotProduct(s,s)
    let discr = sv*sv - ss + scene.sphere.radius*scene.sphere.radius
    if discr < 0.0 then []
    else
        let normalAtTime t = norm (pointAtTime ray t - scene.sphere.center)
        let (t1,t2) = (-sv + sqrt(discr), -sv - sqrt(discr))
        [ (t1, { normal = normalAtTime t1; point = pointAtTime ray t1; ray = ray; sphere=scene.sphere });
          (t2, { normal = normalAtTime t2; point = pointAtTime ray t2; ray = ray; sphere=scene.sphere }) ]

Just for a sanity check let’s modify the guts of the nested for-loop that computes the image just to make sure that what we have got is still producing a correct image.

for x in 0..(width-1) do
        for y in 0..(height-1) do
            let rayPoint = vpc + float(x-width/2)*pw*u + float(y-height/2)*ph*v
            let rayDir = norm (rayPoint - scene.camera.position)
            let ray = { origin = scene.camera.position; direction = rayDir }
            match castRay ray scene with
            | [] -> bmp.SetPixel(x,y,Color.Gray)
            | _ -> bmp.SetPixel(x,y,Color.Red)

The output is now the same image we were getting at the end of the previous article. Now for some shading. What we need to do is create a function that will transform a list of intersections into the correct colour value. The process for this will be

1. Get intersection with the lowest t value (closest to the camera).
2. Add the ambient, diffuse and specular lighting components for this ray on this sphere with this surface normal.
3. Return the aggregate colour value

The fact that I can easily break the function into 3 parts like that suggests it shouldn’t be a single function, but we are going to refactor later so let’s just go for it.

Before we can light something, we need to give it a colour, so let’s give our sphere some colour. Because we’re going to be doing some operations on colours we’ll define our own colour type. The built-in .NET colours don’t have affordance for multiplying or adding colours together or multiplying colours by scalar values.

type Color(r: float, g: float, b:float) =
    member this.r = r
    member this.g = g
    member this.b = b
    static member ( * ) (c1:Color, c2:Color) =
        Color (c1.r*c2.r, c1.g*c2.g, c1.b*c2.b)
    static member ( * ) (c:Color, s:float) =
        Color (c.r*s, c.g*s, c.b*s)
    static member ( + ) (c1:Color, c2:Color) =
        let r = Math.Min (c1.r+c2.r, 1.0)
        let g = Math.Min (c1.g+c2.g, 1.0)
        let b = Math.Min (c1.b+c2.b, 1.0)
        Color (r,g,b)
    static member Zero = Color(0.0,0.0,0.0)

Here we’re defining a simple 3-tuple for RGB colour values where 0.0 <= colour <= 1.0. We're defining operations on these types in the same way you would in C# or other OO languages. We've defined a multiplication operation for both scalar and colour multiplication.

Quick note on spelling. I’m from New Zealand where we use mostly English spelling for words like “colour”. However in my code I use American spelling because I feel that is the de factor worldwide standard for programming.

One last thing to do before computing some shading here is to actually place a light in the scene. We’ll also set the scene’s ambient light. In this code the Light type is new, the Scene and Sphere types are modified.

type Sphere = { center:Point3D; radius:float; diffuseColor:Color }
type Light  = { position:Point3D; color:Color }
type Scene  = { camera:Camera; sphere:Sphere; ambientLight:Color; light:Light }

Also modify our scene declaration a bit

    // scene
    let light = { position=Point3D(0.0,3.0,4.0); color=Color(0.8,0.8,0.8) }
    let scene = { camera=camera; sphere=sphere; ambientLight=Color(0.2,0.2,0.2); light=light }

Okay, let’s do some light computation. We’ll start with the simplest one – ambient light. Ambient light is given by the expression

where is the intensity of our ambient lighting in the scene and is the diffuse reflectivity of the sphere’s material. Sometimes people model ambient light with , giving objects a different diffuse and ambient reflectivity. In my opinion this case is rare enough that we can skip it for now.

let colorAt intersections scene =
    let closest = List.maxBy(fun i -> i.t) intersections
    let kd = closest.sphere.diffuseColor
    let Ia = scene.ambientLight
    Ia * kd

And a small modification to the nested for-loop to make this all work.

    for x in 0..(width-1) do
        for y in 0..(height-1) do
            let rayPoint = vpc + float(x-width/2)*pw*u + float(y-height/2)*ph*v
            let rayDir = norm (rayPoint - scene.camera.position)
            let ray = { origin = scene.camera.position; direction = rayDir }
            let intersects = castRay ray scene
            match intersects with
            | [] -> bmp.SetPixel(x,y,Color.Gray)
            | _ -> let color = colorAt intersects scene
                   bmp.SetPixel(x,y, Color.FromArgb(255, (int)(color.r*255.0), (int)(color.g*255.0), (int)(color.b*255.0)))

We should really create a new function to do the transformation between our Color type and the built-in one, but for now we’ll leave it. Running the program now results in the image on the right. This is the sphere lit only by our 20% ambient light.

Now for diffuse lighting. The diffuse portion is the diffuse colour of the sphere multiplied by the projection of a vector from the intersection point to the light source (normalized) on the normal vector (normalized) of the intersection point. In other words, the dot product of these two vectors. Mathematically, diffuse lighting is given by

where is the material’s diffuse reflectivity (as before), L is the vector between the light source and the intersection point (light.position – intersection.point), N is the normal of the intersection point (both normalized) and is the intensity of the light. (That’s a dot product between L and N, amazingly my maths library doesn’t seem to have a dot product character!).

So we add diffuse reflection and ambient together:

let colorAt intersections scene =
    let closest = List.maxBy(fun i -> i.t) intersections
    let kd = closest.sphere.diffuseColor
    let Ia = scene.ambientLight
    let Id = Math.Max(0.0, Vector3D.DotProduct(norm (scene.light.position - closest.point), norm closest.normal))
    let ambient = kd * Ia
    let diffuse = kd * Id
    ambient + diffuse

We’re getting there! See the image on the left. I’d like to take a moment to explain that List.maxBy call above, because it is quintessential functional programming. If you have never done functional programming before it probably looks a bit strange. Something to understand about this paradigm is that functions are first-class objects. This means that functions can be passed around as parameters and returned from other functions. Essentially we can treat functions as though they were data members in functional languages.

List.maxBy is a function that takes two parameters – the first parameter is another function which takes some object of the list type (T’) and returns some other object of type U’ with which we make the comparison. The second parameter is a list of type T’ and the return type is the T’ which has the maximum value of all of the U’s associated with the T’s in the list. In this case T’ is type Intersection and U’ is type float (the t value of our intersection). So we’re asking the List.maxBy function to give us the Intersection in this list which has the highest t value. Understand? It’s a little tricky if you’ve never seen it before, but it’s a very powerful technique.

All we have left to compute is the specular component and we have a complete lighting model. Specular light can be given as

where is the specular reflectivity of the material (the same as ambient/diffuse reflectivity earlier, but usually a white colour), N is the surface normal at intersection (normalized), is the specular intensity of the light source, is a material constant (usually on the order or 100-500) and H is a vector called the “half-way vector”. H is the vector half way between the view vector (camera.position – intersection.point) and the light vector (light.position – intersection.point). I won’t go into detail about the geometry that makes this work because it has been covered all over the place (see Blinn-Phong shading model), but suffice it to say that this expression will give us nice-looking specular highlights You can vary the value of to change the size and sharpness of the specular highlight – this value is often referred to as the “shininess” value of a material. So here is the modified code to include all three shading modes.

let colorAt intersections scene =
    let closest = List.maxBy(fun i -> i.t) intersections
    let kd = closest.sphere.diffuseColor
    let Ia = scene.ambientLight
    let L = norm (scene.light.position - closest.point)
    let Id = Math.Max(0.0, Vector3D.DotProduct(L, closest.normal))
    let V = scene.camera.position - closest.point
    let H = norm (L + V)
    let Is = Math.Pow(Math.Max(0.0, Vector3D.DotProduct(H,closest.normal)), 500.0)
    let ambient = kd * Ia
    let diffuse = kd * Id
    let specular = Color(1.0,1.0,1.0) * Is
    ambient + diffuse + specular

This is a little messy, but we’ll tidy up later! I have actually cheated here and just used pure white light for . We will implement a material type in the next article.

Notice how when we add all of these shading methods together we get the expression

When dealing with multiple light sources, this will become

Which is the Phong shading model! (modified to use the Blinn-Phong specular method). We will implement this multiplicity (of lights and shapes) in the next article (now available). Stay tuned!

Source code so far.

On January 20, 1992, Air Inter Flight 148 crashed into the Vosges Mountains while approaching Strasbourg Airport in Strasbourg, France. 87 of the 96 crew and passengers on board were killed. So why am I writing about a horrible accident on my programming blog? Because of the cause of the crash.

Many factors came together to cause Air Inter Flight 148 to hit a mountain. However one of the primary causes should be of concern to anyone developing software or designing the UI over top of it. The Airbus A320 had the most advanced cockpit in the world. The majority of the gauges and instruments in front of the pilots in this machine are digital.

When the captain of the aircraft was approaching the runway through thick clouds, he thought he had set a descent angle of a mild 3.3 degrees for a gentle descent above the Vosges Mountains. However, unbeknownst to him the plane was descending at a rate of 3,300 feet per minute, much faster than the descent would have been at 3.3′. The aircraft struck a mountain top and exploded. Air accident investigators noticed the similarities between those two numbers – the pilot’s intended descent rate (3.3′) and the actual descent rate (3,300 fpm).

As it turns out, the airbus A320 used a single display for two different descent modes – Vertical Speed (VS) Mode and Flight Path Angle (FPA) mode. The display showed FPA as two digits separated by a decimal point, and VS as just two digits (and both had a minus sign where their values were negatives). To the right is an image of the display showing an FPA of -2.8′. I wasn’t able to find a picture of the display in VS mode, but you can see from the pictures in this study how similar the two displays are – nearly impossible to tell apart.

This simple design error led the pilot to believe he was in one mode while he was in another. It was not the only factor in the accident, but the crash almost certainly would not have happened had the aircraft’s user interface been more clear. This UI design error is one of a well-known class of errors called mode errors.

Despite the fact that anyone who has taken a semester in HCI knows that modes are a Bad Thing, they are still ubiquitous in today’s software, and they’re still as annoying as ever. Unfortunately it’s simply not easy to find alternatives to mode-based interactions sometimes. On the left is an image of Google Chrome in two different modes – regular and ‘private browsing’ mode. The difference between these modes is very subtle – a small picture with little contrast in an area of the window I never look. But the implications of this mode are not trivial. If you close a tab in ‘private browsing’ mode, you can’t simply ctrl-shift-T to bring it back from the dead. It’s gone forever. The browser will not remember your login details, your Amazon shopping cart or your browsing history. Obviously this is the whole point of private browsing, but it’s also significant that this mode is barely distinguishable from regular browsing mode unless you have already made the mistake of closing a tab you still wanted.

I faced my own problems with mode errors when building my university capstone project, a round-trip UML modelling tool. To draw a relationship between two classes, the user selects a relationship type from the palette on the right and then draws the relationship. But how should the tool behave after that? Is it better to immediately jump out of “relationship drawing mode” after the user draws the relationship? Or should the tool remain available for further use? Due to strict time and resource constraints we were never able to perform much usability testing, but from what I saw neither of those answers was correct. They were both awkward and they both led to errors frequently. The modal paradigm is simply broken beyond repair, in my humble opinion.

So I’m not exactly the first one to say it, but I guess the moral of the story is avoid modes whenever possible. Oh, and in case you’re wondering, the new Airbus A320 cockpit displays show Flight Path Angle as a two-digit number while Vertical Speed is shown with a 4-digit representation. It’s not a perfect fix, but it’s a heck of a lot better.

Finding flaws in the Java Collections framework is like shooting fish in a barrel. From an OO design point of view the framework is just plain bad. From the infamous “vector is a list” gaffe to consistent use of inheritance for implementation, it’s enough to send shivers down the spine of any object fanatic.

Today I want to post about an issue I came across in the Java collections hierarchy that I had never seen before. This is a trap that is easy to fall into, so I was surprised that I had never read about it in the many articles I have read about Java collections. The problem is simple and easy to understand, yet it is insidious enough to potentially lead you into a debugging rabbit hole. The problem arises from Oracle’s neglect of contracts (sorry Oracle, when you acquired Sun you acquired their baggage too!).

Java Set Implementations

The wonderful thing about OO design, abstraction and interfaces is the implicit guarantee that if I have some object that conforms to some interface, I don’t need to care what kind of object I’m dealing with. It doesn’t matter if I’m driving a Honda Accord or a Mac truck, when I turn the wheel clockwise I expect my vehicle to turn right accordingly. The fact that the Mac truck implements this through a huge steering box while my little Accord relies on a flimsy rack and pinion system doesn’t matter to me, the driver. The vehicle has exposed an interface to me – a steering wheel – which means they have agreed that it will behave like every other steering wheel I have used. Simple, elegant and the essence of object design.

So let’s take a look at the two main implementations of Java.Collections.Set. We have HashSet and TreeSet, two fundamentally different implementations with very different performance characteristics. All I know is that if someone gives me a Set, it better behave like every other Set I have used.

So what’s the problem here? The problem is, these Sets don’t behave the same, in a subtle but important way. Let’s explore by example. Inspect the following code and try to predict the outcome.

import java.util.*;

public class SetTest {

	Set<Thing> hashSet;
	Set<Thing> treeSet;

	public SetTest() {
		hashSet = new HashSet<Thing>();
		treeSet = new TreeSet<Thing>();

		Thing t1 = new Thing("Thing 1");
		Thing t2 = new Thing("Thing 2");

		hashSet.add(t1);
		hashSet.add(t2);
		treeSet.add(t1);
		treeSet.add(t2);

		System.out.println("Before t1.setString");
		System.out.println("HashSet contains t1: " + hashSet.contains(t1) + ", t2: " + hashSet.contains(t2));
		System.out.println("TreeSet contains t1: " + treeSet.contains(t1) + ", t2: " + treeSet.contains(t2));
		System.out.println();

		t1.setString("Different String");

		System.out.println("After t1.setString");
		System.out.println("HashSet contains t1: " + hashSet.contains(t1) + ", t2: " + hashSet.contains(t2));
		System.out.println("TreeSet contains t1: " + treeSet.contains(t1) + ", t2: " + treeSet.contains(t2));
		System.out.println();
	}

	public static void main(String[] args) {
		new SetTest();
	}
}

class Thing implements Comparable<Thing> {
	private String str;

	public Thing(String str) {
		this.str = str;
	}

	public void setString(String newStr) { str = newStr; }

	public int compareTo(Thing o) { return str.compareTo(o.str); }

	@Override
	public boolean equals(Object o) {
		// flawed equals method for simplicity
		if (o instanceof Thing) return ((Thing)o).str.equals(str);
		return false;
	}

	@Override
	public int hashCode() {
		// flawed hashcode method for simplicity
		return str.hashCode();
	}
}

For those who aren’t in the mood for reading code, here’s what’s happening. We have some class Thing, with a String field, str. This class identifies as its field, str. This means it must also hash on this field. There have been many words written on the theory of hashCode/equals, so I’ll leave it to you to Google around if you don’t know why it’s important to define these methods together.

We now instantiate two Thing objects and two Sets of Things, one HashSet and one TreeSet. The Things are added to each set, and we check that they are indeed in the sets. We then change the name of one Thing and check again. The result?

The HashSet no longer thinks it contains the Thing! So why did this happen? It’s probably fairly obvious by now, but I’ll make it explicit. A HashSet uses a hash table to store values. It uses the hash algorithm to figure out if a value is contained in the table. This means that a HashSet is not only a Set, it’s also a Map, but the details of the Map are hidden behind the Set interface. This seems logical until you consider the contract for a Map.

Maps rely on key values that do not change. It is imperative that the key in a mapped object is immutable in order to find the object later. When we changed that str field in Thing, we implicitly altered the key (the hash code of the previous String). Unfortunately this change was not abstracted away properly in the Set. When we use the contains method we are asking the hash table for an object that is identical to an object already in the set, but that hashes differently to how it hashed when first added.

Incidentally this bug also allows us to add duplicate values to a HashSet.

The result of all of this is that we cannot rely on all Java Sets to behave the same. In our own code we could just start using TreeSets if we know we want to have mutable hashable values. But what if we are given a Set by some other piece of code? The whole point of OO encapsulation and information hiding is that we aren’t supposed to care how it’s implemented. Unfortunately we simply can’t behave like this in the Java Collections framework.

It should be noted that Sun/Oracle did seem to consider, at some point, the issues with mutable Set members. In the Set API they state

Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set. A special case of this prohibition is that it is not permissible for a set to contain itself as an element.

but then fail to follow through with anything at all in the HashSet API description. Regardless, this business of noting in your API, “by the way, depending on the implementation things might break” is not acceptable OO practice, in my opinion.

So what is the solution? If we were to re-implement the Set interface and implementations, what would we do differently? One hacky solution is to force the HashSet to perform a linear search on its hash table when contains() misses. This seems to solve the problem, but we lose the main advantage of a HashSet, O(1) adding, removal and containment checking. Is there a better solution to this problem? What if we were to rewrite the Set hierarchy from scratch, what would we do differently? I don’t have the answers right now, but it’s something I’ll be thinking about.