Friday, May 4, 2007

Equality checking on interrelated objects

Most, if not all, object-oriented programming languages allow you to define what it means for two objects to be “equal”. In C# and Java, this is done by overriding the Equals or equals function, respectively.

But what to test when comparing two objects? You'll obviously want to compare (most) instance fields, for example the name of a person or the number of wheels of a car. But it's less obvious when an object is (conceptually) part of another object, or dependent on it in some other way. I ran into such a situation today.

Consider the class Pig. A Pig is associated with a Farmer, the owner. Each farmer has, in turn, a list of ownedPigs. (I use Java capitalization conventions here to make a clear distinction between types and fields/methods.)

Suppose we want to check whether two Pigs are equal. (Do not just return true. Some animals are more equal than others.) Clearly, two Pigs are not equal if they are owned by a different Farmer, so we need to compare their owner fields. Reference equality on this field is not enough: if we can have multiple Pig objects representing the same pig, then the owner fields may well refer to different objects representing the same farmer. So we do a value comparison of the owner fields, by calling owner.equals.

Of course, two Farmers are not equal unless they own the same Pigs. We have to call Pig.equals for each owned pig. This, in turn, calls Farmer.equals, which calls Pig.equals … and so on ad infinitum (which is Latin for “stack overflow”).

How to solve this problem? The key is, when equality of type A depends on equality of A's fields of type B and vice versa, to check not the entire B objects for equality, but only compare the parts we're interested in.

For example, a Pig couldn't care less what the social security number of its owner is. It does, however, care where he lives: a pig on the South Pole will have very different life circumstances from one in the Sahara. In Pig.equals we would then only compare the addresses of the owners, and not the entire Farmer objects.

With this modification, the cycle is already broken. We could also tackle the problem from the other side: the Farmer cares only about how fat his pigs are, but not about their political preference. When comparing two Farmers we could look only at the weight of all their ownedPigs, disregarding their vote field.

I admit this example is a little contrived. I'm not programming an animal farm. But if you ever do, and your Pig.equals method gets called with a Farmer object, remember to return false.

No comments: