Implementing a comparable numeric data type in Java the TDD way
Originally, this was going to be part of my article “Taking a broader view of what test-driven development is,” but I thought it was getting too long, so I’ve broken it up into smaller parts.
This is the third of three parts, and it has turned out a bit longer than either the first part or the second part.
Originally, the article was going to conclude with two exercises. The first exercise stays an exercise. But the second exercise turned out to be a lot more interesting than I realized at first: implementing the Comparable interface in Java.
By implementing Comparable for a custom numeric data type in Java, you can use some of Java’s standard functions to sort collections or arrays of your custom numeric data type, instead of having to reinvent the wheel.
You can also use Scala’s standard functions, too, thanks to the fairly smooth interoperability between Java and Scala, even though in Scala immutable collections are preferred to mutable collections.
There are tutorials already about implementing Comparable. The problem is, though, at least with the ones that I’ve read, is that the example class they choose does not feel like an organic fit for Comparable, in my opinion.
For example, a class to represent iTunes tracks, which can be sorted by many different criteria: title, artist, album, composer, last played, play count, to name just a few.
But not one of these seems a more natural criterion for sorting than the others, even though surely iTunes users use some sorting criteria more often than others, and might not even know about certain ways to sort their tracks.
Numbers can also be sorted by many different criteria, but when we’re talking about purely real numbers, there is one sorting criterion that presents itself as the most natural: location on the real number line.
Zero is at the center of the real number line, the positive integers are to one side of 0, and the negative integers are to the opposite side of 0.
And, at the risk of getting philosophical, negative infinity is less than 0, and 0 is less than positive infinity.
We see, for example, that −4/3 < 3/4, even though −4/3 is farther away from 0 than 3/4 is. However, comparing absolute values, we see that 3/4 < 4/3.
And so I conclude that the Fraction class we’ve been working on (in the previous two parts) is one of the best examples we could use to illustrate how to implement the Comparable interface.
Also, I haven’t seen any tutorials approach the topic of implementing Comparable from the perspective of test-driven development (TDD).
In the first part of this article, linked above, we started working on the classes Fraction and FractionTest, the latter using JUnit 4. We got testEquals() to pass.
For the second part, “A little bit about refactoring in TDD,” I assumed you had also gotten testToString() to pass, and illustrated how the Fraction constructor is the right place to put the fraction in lowest terms.
For this part, I assume that either all your other tests in FractionTest are still failing, or you don’t have any other tests besides the ones mentioned so far.
We might need a good test for Fraction.plus(), and definitely a good test for Fraction.minus().
Making a numeric approximation function
The first exercise, which will come in handy for the second exercise, is easy and you should be able to complete it quickly enough if you’ve been following along in your favorite Java IDE.
Despite the pitfalls of floating point precision, numeric approximations (like 1.33333333 for 4/3) are still often useful. I would like a way to get a floating point precision value for the number represented by a Fraction object.
Writing the stub first or writing the test first for this easy exercise hardly makes any difference. I’ll still present the stub first:
// STUB TO FAIL THE FIRST TEST
public double getNumericValue() {
return 0.0;
}Now the test:
@Test
public void testGetNumericValue() {
Fraction fract = new Fraction(-1, 2);
double expected = -0.5;
double testDelta = 0.00000001;
double actual = fract.getNumericValue();
assertEquals(expected, actual, testDelta);
fract = new Fraction(2, 7);
expected = 0.28571428;
actual = fract.getNumericValue();
assertEquals(expected, actual, testDelta);
}Generally the test delta should be close to 0 but not exactly 0. This way we don’t have to worry that a test might fail because of a tiny variance we might not really care about.
Even if I wasn’t providing the stub and the test, this exercise would still not take more than five minutes.
Making a numeric data type comparable
The second exercise, like I mentioned earlier, is much more interesting… and involved. It might even seem a little daunting, and would be worth some extra credit points if this was a class for grades.
Also, if you’re dyslexic, you’ll have to be extra careful on this one. However, with TDD, it’ll turn out to be much easier than you might expect.
I would like to be able to sort a collection or array of fractions using Collections.sort() or Arrays.sort().
In order to be able to do that, the Fraction class needs to be Comparable, to enable the sorting functions to figure out whether one fraction is less than, equal to or greater than some other fraction.
Change the Fraction class definition to include “implements Comparable<Fraction>”.
You may leave out the “<Fraction>” part, but that would complicate the exercise, since it would theoretically be possible to compare a Fraction object to any other Comparable object.
With “<Fraction>”, we only need to worry about comparing a Fraction object to other Fraction objects.
Almost immediately the IDE should warn you that Fraction does not implement this or that from Comparable<T>. Actually, the Comparable interface requires only one thing: that you implement compareTo().
Go ahead and put in a stub:
// STUB TO FAIL THE FIRST TEST
@Override
public int compareTo(Fraction other) {
return 0;
}Your IDE might offer to write a compareTo() stub for you. NetBeans creates a stub that throws an UnsupportedOperationException (this is configurable, though).
The idea is that if this fraction is greater than the other fraction, this.compareTo(other) returns 1 (or any other positive integer); if they’re equal, it returns 0; and if this fraction is less than the other fraction, it returns −1 (or any other negative integer).
So our stub will give the misleading result that all fractions are equal, which is of course wrong.
Another deficiency of our stub is that this.compareTo(null) is supposed to throw a NullPointerException. In this way, and in other ways, compareTo() is somewhat different from equals().
Since Java primitives are objects in Scala, and the standard Java object wrappers of numeric primitives implement Comparable, the Scala REPL is a great way to play around with compareTo() with hardly any overhead.
scala> 7.compareTo(6)
res9: Int = 1scala> 7.compareTo(7)
res10: Int = 0scala> 7.compareTo(8)
res11: Int = -1scala> 7.compareTo(null)
java.lang.NullPointerException
at java.lang.Integer.compareTo(Unknown Source)
... 28 elidedscala> 7 == null
<console>:12: warning: comparing values of types Int and Null using `==' will al
ways yield false
7 == null
^
res13: Boolean = falsescala> 7.equals(null)
res14: Boolean = false
This is probably enough information to start writing tests.
You might decide that you want to implement Fraction.compareTo() so that it returns strictly only −1, 0 or 1. However, I recommend that you write your tests so that they’ll pass with any negative number instead of just −1 and any positive number instead of just 1.
@Test
public void testCompareTo() {
Fraction negThreeHalves = new Fraction(-3, 2);
Fraction approxPiFiftieths = new Fraction(157, 50);
Fraction approxPi113ths = new Fraction(355, 113);
Fraction approxPiSevenths = new Fraction(22, 7);
int comparison =
negThreeHalves.compareTo(approxPiFiftieths);
String assertionMessage = negThreeHalves.toString()
+ " should be found to be less than "
+ approxPiFiftieths.toString();
assertTrue(assertionMessage, comparison < 0);
comparison = approxPiFiftieths.compareTo(approxPi113ths);
assertionMessage = approxPiFiftieths.toString()
+ " should be found to be less than "
+ approxPi113ths.toString();
assertTrue(assertionMessage, comparison < 0);
comparison = approxPi113ths.compareTo(approxPiSevenths);
assertionMessage = approxPi113ths.toString()
+ " should be found to be less than "
+ approxPiSevenths.toString();
assertTrue(assertionMessage, comparison < 0);
comparison = approxPiFiftieths.compareTo(approxPiFiftieths);
assertEquals(0, comparison);
comparison = approxPi113ths.compareTo(approxPi113ths);
assertEquals(0, comparison);
comparison = approxPiSevenths.compareTo(approxPiSevenths);
assertEquals(0, comparison);
comparison = approxPiFiftieths.compareTo(negThreeHalves);
assertionMessage = approxPiFiftieths.toString()
+ " should be found to be greater than "
+ negThreeHalves.toString();
assertTrue(assertionMessage, comparison > 0);
comparison = approxPi113ths.compareTo(approxPiFiftieths);
assertionMessage = approxPi113ths.toString()
+ " should be found to be greater than "
+ approxPiFiftieths.toString();
assertTrue(assertionMessage, comparison > 0);
comparison = approxPiSevenths.compareTo(approxPi113ths);
assertionMessage = approxPiSevenths.toString()
+ " should be found to be greater than "
+ approxPi113ths.toString();
assertTrue(assertionMessage, comparison > 0);
}This should fail on the first assertion:
junit.framework.AssertionFailedError: -3/2 should be found to be less than 157/50Of course you can break this up into smaller tests if you prefer to be more granular, and IntelliJ makes it easy to run just one test at a time.
The easiest way to make the first assertion pass would be to use the floating point approximations of this and other to determine which one is greater, if they’re not equal.
If you completed the first exercise, then you can do something like this for this second exercise:
@Override
public int compareTo(Fraction other) {
double thisVal = this.getNumericValue();
double otherVal = other.getNumericValue();
if (thisVal < otherVal) {
return -1;
}
if (thisVal > otherVal) {
return 1;
}
return 0;
}However, that once again brings up the possibility of false equality, which I mentioned in the previous part. We can write a test for that:
@Test
public void testCompareToCloseFraction() {
Fraction numberA = new Fraction(1, Long.MAX_VALUE);
Fraction numberB = new Fraction(1, Long.MAX_VALUE - 1);
String assertionMessage = numberA.toString()
+ " should be found to be less than "
+ numberB.toString();
assertTrue(assertionMessage,
numberA.compareTo(numberB) < 0);
assertionMessage = numberB.toString()
+ " should be found to be greater than "
+ numberA.toString();
assertTrue(assertionMessage,
numberB.compareTo(numberA) > 0);
}So if you implemented compareTo() using getNumericValue(), then testCompareToCloseFraction() will most likely fail.
1/9223372036854775807 should be found to be less than 1/9223372036854775806However, you might decide such denominators are much larger than what you have any practical use for. In my case, in what I need Fraction for, I will be satisfied if I can rely on Fraction.compareTo() to distinguish fractions with denominators as large as 2³¹ − 1, but no larger than that.
scala> 1.0 / 2147483647.0
res15: Double = 4.656612875245797E-10scala> 1.0 / 2147483646.0
res16: Double = 4.656612877414201E-10scala> res15 == res16
res17: Boolean = false
And indeed if we replace Long.MAX_VALUE with Integer.MAX_VALUE, then testCompareToCloseFraction() should pass.
However… doesn’t the use of getNumericValue() in compareTo() seem somehow… inelegant? Can we really be certain there is no other pair of fractions with denominators less than Integer.MAX_VALUE (but greater than 0) such that compareTo() gives the wrong result?
After all, the whole point of making a Fraction class is to do arithmetic with fractions without having to worry about floating point precision at all. If you have successfully tested and implemented Fraction.minus(), you can use it to compute the difference between two fractions.
If not, here’s a test for Fraction.minus():
@Test
public void testSubtract() {
Fraction minuend = new Fraction(1, 3);
Fraction subtrahend = new Fraction(1, 7);
Fraction expected = new Fraction(4, 21);
Fraction actual = minuend.minus(subtrahend);
assertEquals(expected, actual);
}And here’s one way to implement Fraction.minus():
public Fraction minus(Fraction subtrahend) {
return this.plus(subtrahend.negate());
}This of course needs Fraction.plus() and Fraction.negate() to work correctly. In the first part, I had a test for the former that was basically 1/3 + 1/7 = 10/21. Here’s a test for Fraction.negate():
@Test
public void testNegate() {
Fraction fract = new Fraction(8, 13);
Fraction expected = new Fraction(-8, 13);
Fraction actual = fract.negate();
assertEquals(expected, actual);
fract = new Fraction(-55, 89);
expected = new Fraction(55, 89);
actual = fract.negate();
assertEquals(expected, actual);
}Once you have Fraction.minus() working correctly, you can use it in Fraction.compareTo().
@Override
public int compareTo(Fraction other) {
Fraction diff = this.minus(other);
if (diff.numer < 0) {
return -1;
}
if (diff.numer > 0) {
return 1;
}
// and if diff.numer is 0 then
return 0;
}This is neater and cleaner than using getNumericValue(), even though it’s only slightly shorter, and even though it probably offers no noticeable improvement in performance.
If you still have Long.MAX_VALUE in testCompareToCloseFraction(), that’s probably still failing, unless you have some workaround to avoid the 64-bit integer overflow with the multiplication of the denominators.
If you have the Scala REPL, you can load into it class files compiled from Java sources. The following Scala REPL session quote assumes the Fraction class is in the fractions package.
In Scala, we can use the “operandA.function(operandB)” syntax like in Java, but I personally prefer to use the operandA function operandB syntax. We can use that syntax regardless of whether the class files were compiled from Java or Scala sources.
A further refinement would be possible if we defined the Fraction class in Scala and took advantage of “operator overloading.” But this is good enough to try out a few things in the Scala REPL:
scala> var numberA = new fractions.Fraction(1, 2147483647)
numberA: fractions.Fraction = 1/2147483647scala> var numberB = new fractions.Fraction(1, 2147483646)
numberB: fractions.Fraction = 1/2147483646scala> numberA minus numberB
res18: fractions.Fraction = -1/4611686011984936962scala> numberA minus numberA
res19: fractions.Fraction = 0scala> numberB minus numberA
res20: fractions.Fraction = 1/4611686011984936962
I used var rather than val to initialize numberA and numberB because I used those same identifiers for other fractions in experiments I’m not including in this article.
These subtractions with numberA and numberB make the point that the result of compareTo() is very similar to the result of subtraction.
In the example shown above, 1/2147483647 − 1/2147483646 = −1/4611686011984936962 (a negative number, like −1), 1/2147483646 − 1/2147483647 = 1/4611686011984936962 (a positive number, like 1), and, of course, 1/2147483647 − 1/2147483647 = 0 and 1/2147483646 − 1/2147483646 = 0 also.
To drive the point home:
scala> numberA.compareTo(numberB)
res21: Int = -1scala> numberA.compareTo(numberA)
res22: Int = 0scala> numberB.compareTo(numberA)
res23: Int = 1
And with the right import into the Scala REPL, we can use the comparison operators <, == and >.
scala> import scala.math.Ordering.Implicits._
import scala.math.Ordering.Implicits._scala> numberA > numberB
res24: Boolean = falsescala> numberA == numberA
res25: Boolean = truescala> numberB == numberB
res26: Boolean = truescala> numberA < numberB
res27: Boolean = true
The REPL is a great way to quickly check little details on a whim and it can even help you come up with ideas for tests.
But it’s no substitute for automated tests that you can run at the push of a button any time you’re wondering if changes you’ve made have broken the program.
Now we move on to the test that will really put dyslexics at ease. You’ll need to add a couple of java.util imports in FractionTest for this one, if the IDE doesn’t do it for you automatically.
@Test
public void testCompareToThroughCollectionSort() {
Fraction negThreeHalves = new Fraction(-3, 2);
Fraction approxPiFiftieths = new Fraction(157, 50);
Fraction approxPi113ths = new Fraction(355, 113);
Fraction approxPiSevenths = new Fraction(22, 7);
List<Fraction> expectedList = new ArrayList<>();
expectedList.add(negThreeHalves);
expectedList.add(approxPiFiftieths);
expectedList.add(approxPi113ths);
expectedList.add(approxPiSevenths);
List<Fraction> unsortedList = new ArrayList<>();
unsortedList.add(approxPi113ths);
unsortedList.add(negThreeHalves);
unsortedList.add(approxPiSevenths);
unsortedList.add(approxPiFiftieths);
Collections.sort(unsortedList);
assertEquals(expectedList, unsortedList);
}Note that the fractions are initialized and added to expectedList in ascending order, but they’re added to unsortedList in the following sequence: 355/113, −3/2, 22/7, 157/50.
To get a first fail on this one, you might have to revert compareTo() back to a stub, and then simply undo that after getting the first fail:
expected:<[-3/2, 157/50, 355/113, 22/7]> but was:<[355/113, -3/2, 22/7, 157/50]>I find this reassuring because it lets me know that even if two instances of ArrayList have the same elements, they will not register as equal if the elements are in a different order.
Restoring compareTo(), this test should now pass. Having seen it fail first should give us confidence that now the collection of fractions really is getting sorted, that the computer isn’t just showing us what we want to see.
In the Scala REPL, and in Scala in general, it’s very easy to create immutable collections. But java.util.Collections.sort() works on mutable collections like ArrayList, not on immutable collections.
However… with java.lang.Comparable implemented for a class loaded into the Scala REPL, we can avail ourselves to Scala’s collection sorting functions to create Scala immutable collections from other immutable collections of objects defined in Java.
For example, it’s very easy, with what we have so far, to create an immutable list of unit fractions from 1 to 1/32.
scala> for (n <- 1 to 32) yield new fractions.Fraction(1, n)
res28: scala.collection.immutable.IndexedSeq[fractions.Fraction] = Vector(1, 1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 1/8, 1/9, 1/10, 1/11, 1/12, 1/13, 1/14, 1/15, 1/16, 1/17, 1/18, 1/19, 1/20, 1/21, 1/22, 1/23, 1/24, 1/25, 1/26, 1/27, 1/28, 1/29, 1/30, 1/31, 1/32)Although the denominators are in ascending order, the fractions are actually in descending order. For example, 1/2 = 0.5, while 1/32 = 0.03125.
If we want them in ascending order, as 1/32, 1/31, 1/30, … 1/2, 1, we can’t use java.util.Collections.sort() on res28 because res28 is an immutable Scala collection. Well, we can try, we’ll get a type mismatch error.
I don’t know of any simple way to convert an IndexedSeq[Fraction] to an ArrayList[Fraction]. We don’t have to, though, we can just use IndexedSeq.sorted().
That will invoke Fraction.compareTo() and use it to produce a new immutable collection with our unit fractions sorted in ascending order:
scala> res28.sorted
res29: scala.collection.immutable.IndexedSeq[fractions.Fraction] = Vector(1/32, 1/31, 1/30, 1/29, 1/28, 1/27, 1/26, 1/25, 1/24, 1/23, 1/22, 1/21, 1/20, 1/19, 1/18, 1/17, 1/16, 1/15, 1/14, 1/13, 1/12, 1/11, 1/10, 1/9, 1/8, 1/7, 1/6, 1/5, 1/4, 1/3, 1/2, 1)If we didn’t have Comparable implemented, we would have gotten an error message instead:
scala> res28.sorted
<console>:13: error: No implicit Ordering defined for fractions.Fraction.
res28.sorted
^Lastly, let’s try it on sequence of pseudorandom fractions.
scala> var rnd = new java.util.Random
rnd: java.util.Random = java.util.Random@786a9781scala> for (n <- 1 to 10) yield new fractions.Fraction(rnd.nextInt(100), rnd.nextInt(100) + 1)
res30: scala.collection.immutable.IndexedSeq[fractions.Fraction] = Vector(61/4, 69/22, 50/73, 31/22, 53/55, 10/3, 34/7, 81/23, 91/37, 88/89)
I do know Scala has its own pseudorandom number functions, and I’ll look into them later, but for now it’s easier to just use Java’s.
Note the “+ 1” part in the denominator parameter: since nextInt() could give 0, we need to nudge it off 0 so as to avoid an exception for an invalid denominator.
If you run this on your own computer, you should get a different sequence of fractions. Hopefully it’ll be a good mix of fractions that are less than 1 and fractions that are greater than 1.
In the run shown above, 61/4 is clearly the largest fraction, as it is 15.25. Next, 69/22 is a little bit greater than 3, then 50/73 is obviously less than 1, and 31/22 being almost 1.5 shows that this sequence is neither in descending nor ascending order.
So let’s get these fractions sorted:
scala> res30.sorted
res31: scala.collection.immutable.IndexedSeq[fractions.Fraction] = Vector(50/73, 53/55, 88/89, 31/22, 91/37, 69/22, 10/3, 81/23, 34/7, 61/4)These are all positive numbers, but the fractions up to an including 88/89 are less than 1, while the fractions from 31/22 and up are greater than 1.
If we have any doubt that these fractions are indeed in ascending order, we can take advantage of getNumericValue() from the first exercise:
scala> res31.map(_.getNumericApproximation)
res32: scala.collection.immutable.IndexedSeq[Double] = Vector(0.684931506849315, 0.9636363636363636, 0.9887640449438202, 1.4090909090909092, 2.4594594594594597, 3.1363636363636362, 3.3333333333333335, 3.5217391304347827, 4.857142857142857, 15.25)Oops, I forgot I called getNumericValue() something else in my implementation that wasn’t meant for the tutorial. I only mention this in case you look in my GitHub repository.
I could certainly have edited the Scala REPL session quotation above to use getNumericValue() rather than getNumericApproximation(). Other Scala REPL quotations in these articles do have other edits for the sake of clarity and conciseness.
This suggests a test to add to FractionTest: a test that comes up with a few pseudorandom fractions, puts them in a collection, invokes a sorting function and then checks that the collection is indeed sorted.
But would such a test really be necessary? If you were on a deadline to commit to Git, then I guess not. We already have a working implementation of Comparable<Fraction> here.
In conclusion, TDD simplifies the implementation of the Comparable interface in Java, giving us the confidence that our implementation works correctly in most cases, as well as giving us an awareness of our implementation’s limitations when necessary.
We also saw that Scala’s sorting functions for immutable collections can fully take advantage of this mechanism that was originally intended for mutable collections in Java.