## Saturday, August 29, 2009

### Two More Java Puzzlers

Oh, Java! Will you ever run out of corner cases to confuse and bewilder me? I doubt it. On the bright side, you are an unquenchable fountain of fun programming puzzles for my blog. Thanks, Java!

Odd or Even?

Today's first puzzler comes to us courtesy of @royvanrijn. Take a look at the following code:
    public static void main(String[] args)    {        String a = null;        int n = "number".hashCode();        switch( n % 2 ) {            case 0:                a = "even";                break;            case 1:                a = "odd";                break;        }                System.out.println( a );    }

At first glance it looks like this program should print either "even" or "odd", but looks can be deceiving. The program prints null. The question is, why?

Who uses Vector anyway?

Our second puzzler comes from my boss, Chris. It's a very contrived variation of a problem that he encountered in a very real project. The following code crashes at a point you might not expect. Can you tell why it crashes there, and why it didn't crash before that point?
    public static void main(String[] args)    {        Vector<Integer> numbers = new Vector<Integer>();        int min = 128;        int max = 255;        for( int i = min; i <= max; ++i )        {            numbers.add(i);        }        int element = 100;        numbers.remove(element);        element = 255;        if( numbers.contains(element) )        {            numbers.remove(element);        }    }

A co-worker figured this one out in under a minute after he was told that it wasn't a threading issue (which should be obvious from this contrived example, but wasn't in the original context). See if you can beat his very impressive time.

I'll have the answers to both puzzlers in an upcoming post.

As always, I can't bring up the subject of Java puzzlers without mentioning the book Java Puzzlers: Traps, Pitfalls, and Corner Cases by Josh Bloch and Neal Gafter. It's a collection of 95 Java puzzles plumbed from the depths of the language and its core libraries.

Derrick said...

I figured out the Vector one right away, though I had to confirm my suspicion in the javadocs.

But not only is Vector a bad class to use unless you really need its thread safety, boxing and unboxing make code much less maintainable to my mind. (Not to mention the soaring object counts you can get if you're not careful.)

Bill the Lizard said...

Derrick,
You're a few steps ahead of me in Java debugging skills. I had to run the code, see what error it produced, then check the Javadoc to figure out what the heck was going on. I was extremely impressed when my co-worker, Josh, got it almost instantly without checking the Javadoc. He knew from past experience exactly what method was causing the problem.

The boxing and unboxing cause a very specific bit of trouble in this case. I'll have a detailed explanation in my next post.

Nice job figuring this out so quickly.

Emil said...

I wasn't quite as sharp as you're coworker either. I had to run the code and see where it fail, but I did realize that it was a boxing issue without checking the javadocs. The first thing I tried was to change "int element" to "Integer element" which resolved the problem.

The issue is illustrated very clearly by the following code:
int n = 7171;
Integer a = n;
Integer b = n;
System.out.println("a == b: " + (a == b));
System.out.println("a.equals(b): " + a.equals(b));
System.out.println("System.identityHashCode(a): " + System.identityHashCode(a));
System.out.println("System.identityHashCode(b): " + System.identityHashCode(b));

When run it produces:
a == b: false
a.equals(b): true
System.identityHashCode(a): 4072869
System.identityHashCode(b): 1671711

Anyway. Good one!

Joshua said...

The hashcode returns a long so it overflows when you pass it to the int. The number is negative so it doesn't hit either cases. Adding:
Math.abs(n % 2)

fixes the issue.

Bill the Lizard said...

Emil,
That puzzler is primarily a boxing issue. There's a subtler issue with the Vector class that's revealed by this problem, but changing the int to an Integer makes the problem go away, so nice job.

Bill the Lizard said...

Joshua,
You're mostly right. The hashCode method returns an int, not a long. That doesn't really matter though, because in this case the value returned by the method is negative. The reason the switch doesn't process either of its cases has something specific to do with Java's % operator. I'll explain in more detail in my next post.

Eric said...

The % issue looks like code I might have written. Wouldn't it be nice if we could assume that 0 <= (m%n) < n?

That's the way similar operators are usually defined in my experience, anyway. Does that often differ by language, or is the fact that m%n returns a negative value for negative m something that dates back to, say, C, and we're just living with it because programmers are used to it?

Gary said...

Actually, the first problem is not a Java pitfall per se. The behaviour of the modulus operator with negative numbers is not mathematically defined. Therefore, languages extend the mathematical definition in their own way.

For example, in PLT Scheme, (mod a b) (equivalent to "a mod b", or "a%b", in a more common notation) always returns a positive integer, whatever the signs of a and b.

In Ruby, a%b will always have the sign of b.

And apparently in Java a%n has the sign of a.

As I said, the behaviour of "mod" (often written "%" in programming languages) is not mathematically defined for negative integers (nor for non-integers), so you should always check its behaviour in any new language you learn.

As for the second problem, I would call that an API bug. I think I would probably have written it that way, and I would not have spotted a bug if a didn't know there was one. However, knowing there was a bug in that piece of code, I had figured it out before I had finished reading the code sample. (My first intuition was also "threading" when I saw the Vector.remove call, but I dismissed it when I saw the call was not in a "smart" for-loop.)

Gary said...

Nearly forgot - sorry for the double-post, I didn't find an "edit" button.

If you want to check for oddity in a "specific % implementation"-agnostic way, you can test if the number is even : a%b will always return 0 for an even number, and unless your language makes a difference between -0 and +0 you should be safe. So your switch should be rewritten as
if(n%2==0) { a = "even"; }
else { a = "odd"; }

Bill the Lizard said...

Eric,
That is precisely the issue with the % operator that I was referring to in my earlier comment. It is very dependent on language implementation. Some languages implement % as a mathematically accurate modulus operator (undefined for negative operands) and some, like Java, define it as a remainder operator. In C, the sign of the result is machine-dependent for negative operands (according to K&R). I wrote a quick test on my machine using gcc, and I'm getting the same remainder behavior for the % operator as I am in Java.

Bill the Lizard said...

Gary,
Good insights. Particularly the point you made about always knowing how % is implemented (modulus vs. remainder) in any new language you learn. This isn't a Java-specific issue, since each language implementer (and in some cases, each compiler implementer) has to make the decision on how to specify the % operator's behavior.

Troy said...

I found a similar boxing issue using JUnit.

double expected = 100.0;
double actual = getActual();

Assert.assertEquals("Right value", expected, actual);

compiles just fine. However, it doesn't call assertEquals(String, double, double), since that method doesn't exist. Instead, it boxes the doubles into Doubles and calls assert.Equals(String, Object, Object). Which fails if getActual returns 100.000000001.

What you actual want is

double expected = 100.0;
double actual = getActual();
double epsilon = 0.001;

Assert.assertEquals("Right value", expected, actual, epsilon);

which calls assertEquals(String, double, double, double).

In Java 1.4, the code didn't compile and provided a reminder that you need the "round off error" parameter, but with boxing, it compiles just fine.

Bill the Lizard said...

Troy,
That was one of the more annoying aspects of JUnit 4 when I first encountered it. The assertEquals methods no longer exist for primitives, which broke a lot of old tests. I remember being really confused the first time I ran something like

assertEquals(42, getLongVal());

and got the error message

expected: <42> but was: <42>

This is because the literal 42 gets boxed to an Integer, while the long return value gets boxed to a Long. They're not equal even though they have the same value.