# 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/50`

Of 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/9223372036854775806`

However, 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.