Sunday, November 22, 2009

Puzzle 59 – Comparing the Java way.

A really cool part of the collection framework is the Collections.sort() function. The function sorts out a collection based on the natural ordering of elements. Of course – for you own data types you need to define what the ‘natural’ ordering is. Doing that is really simple though – just implement the compareTo() method of the Comparable interface and we are ready to go.

That brings me to today’s questions. The code below for the Points class implements the compareTo() method. Now my manager kept insisting that there is something not right about it – but the code looks alright to me.

What do you folks think – are there any problems with the code below?

package com.twister;

import java.util.ArrayList;
import java.util.Collections;

public class Points implements Comparable<Points>{
int xCoordinate;
/*
* 1. Returns 0 if both points have same xCoordinate (say 3 & 3) - returns 3-3=0
* 2. Returns +ve if first point is on the
* right hand side of the second point (say 5, -3) - returns 5 - (-3) = 8
* 3. Returns -ve if first point is on the
* left hand side of the second point (say -5, 3) - returns (-5) - (3) = -8
*/
public int compareTo(Points p) {
return xCoordinate - p.xCoordinate;
};

public static void main(String[] args) {
ArrayList
<Points> arrPoints = new ArrayList<Points>();
/* Add lots of points to the array list */
Collections.sort(arrPoints);
/*Print the sorted collection */
}
}

Got a view? Leave one here.

4 comments:

  1. Just try this out:
    {code}
    arrPoints.add(new Points(Integer.MAX_VALUE));
    arrPoints.add(new Points(-3));
    arrPoints.add(new Points(Integer.MIN_VALUE));
    arrPoints.add(new Points(2));

    Collections.sort(arrPoints);
    for (Points p : arrPoints) {
    System.out.println(p);
    }
    {code}

    The output would be:
    {code}
    com.twister.Points@42e816 (2147483647)
    com.twister.Points@9304b1 (-2147483648)
    com.twister.Points@190d11 (-3)
    com.twister.Points@a90653 (2)
    {code}

    ReplyDelete
  2. See my previous post for problem.
    Solution:
    1. Quick and dirty:
    {code}
    public int compareTo(Points p) {
    return (int) (1.0 * xCoordinate + -1.0 * p.xCoordinate);
    }
    {code}

    ReplyDelete
  3. The problem with the code is that the integer substraction can lead to overflow.
    If we add to the array the values:
    arrPoints.add( new Points( Integer.MAX_VALUE ) );
    arrPoints.add( new Points( -1 ) );
    arrPoints.add( new Points( 1 ) );
    arrPoints.add( new Points( Integer.MIN_VALUE ) );
    the order will be [2147483647, -1, 1, -2147483648]

    One way to compare two integers:
    public int compareTo(Points p) {
    return xCoordinate > p.xCoordinate ? 1 : xCoordinate == p.xCoordinate ? 0 : -1;
    };

    ReplyDelete
  4. This code will produce incorrect result if list will contain positive number and Integer.MIN_VALUE

    ReplyDelete

Solution for this question?