Sorting a List<Number>

Question

How to sort a List<Number>?

Example:

List<Number> li = new ArrayList<Number>(); //list of numbers
li.add(new Integer(20));
li.add(new Double(12.2));
li.add(new Float(1.2));

Solution 1

Collections.sort(li,new Comparator<Number>() {
    @Override
    public int compare(Number o1, Number o2) {
        Double d1 = (o1 == null) ? Double.POSITIVE_INFINITY : o1.doubleValue();
        Double d2 = (o2 == null) ? Double.POSITIVE_INFINITY : o2.doubleValue();
        return  d1.compareTo(d2);
    }
});

Have a look at Andreas_D's answer for explanation.In the above code all null values and +Infinity values are handled such that they move to the end.

Update 1:

As jarnbjo and aioobe points out a flaw in the above implementation.So I thought it's better to restrict the implementation's of Number.

Collections.sort(li, new Comparator<Number>() {
    HashSet<Class<? extends Number>> allowedTypes;
    {
        allowedTypes = new HashSet<Class<? extends Number>>();
        allowedTypes.add(Integer.class);
        allowedTypes.add(Double.class);
        allowedTypes.add(Float.class);
        allowedTypes.add(Short.class);
        allowedTypes.add(Byte.class);

    }

    @Override
    public int compare(Number o1, Number o2) {
        Double d1 = (o1 == null) ? Double.POSITIVE_INFINITY : o1.doubleValue();
        Double d2 = (o2 == null) ? Double.POSITIVE_INFINITY : o2.doubleValue();

        if (o1 != null && o2 != null) {
            if (!(allowedTypes.contains(o1.getClass()) && allowedTypes.contains(o2.getClass()))) {
                throw new UnsupportedOperationException("Allowed Types:" + allowedTypes);
            }
        }

        return d1.compareTo(d2);

    }
});

Update 2:

Using guava's constrained list (will not allow entry of null or unsupported type to list):

List<Number> li = Constraints.constrainedList(new ArrayList<Number>(),
    new Constraint<Number>() {
        HashSet<Class<? extends Number>> allowedTypes;
        {
            allowedTypes = new HashSet<Class<? extends Number>>();
            allowedTypes.add(Integer.class);
            allowedTypes.add(Double.class);
            allowedTypes.add(Float.class);
            allowedTypes.add(Short.class);
            allowedTypes.add(Byte.class);

        }

        @Override
        public Number checkElement(Number arg0) {
            if (arg0 != null) {
                if (allowedTypes.contains(arg0.getClass())) {
                    return arg0;
                }
            }

            throw new IllegalArgumentException("Type Not Allowed");
        }
    }
);

li.add(Double.POSITIVE_INFINITY);
li.add(new Integer(20));
li.add(new Double(12.2));
li.add(new Float(1.2));
li.add(Double.NEGATIVE_INFINITY);
li.add(Float.NEGATIVE_INFINITY);
// li.add(null); //throws exception
// li.add(new BigInteger("22"); //throws exception
li.add(new Integer(20));
System.out.println(li);

Collections.sort(li, new Comparator<Number>() {
    @Override
    public int compare(Number o1, Number o2) {
        Double d1 = o1.doubleValue();
        Double d2 = o2.doubleValue();

        return d1.compareTo(d2);
    }
});

System.out.println(li);

Solution 2

As jarnbjo points out in his answer, there is no way to implement a Comparator<Number> correctly, as instances of Number may very well represent numbers larger than Double.MAX_VALUE (and that's unfortunately as far as the Number interface allows us to "see"). An example of a Number larger than Double.MAX_VALUE is

new BigDecimal("" + Double.MAX_VALUE).multiply(BigDecimal.TEN)

The solution below however, handles

• Bytes, Shorts, Integers, Longs, Floats and Doubles

• Arbitrary large BigIntegers

• Arbitrary large BigDecimals

• Instances of {Double, Float}.NEGATIVE_INFINITY and {Double, Float}.POSITIVE_INFINITY

  Note that these should always come before/after any BigDecimal even though the BigDecimal.doubleValue may return Double.NEGATIVE_INFINITY or Double.POSITIVE_INFINITY

• null elements

• A mixture of all of the above, and

• Unknown implementations of Number that also implements Comparable.

  (This seems to be a reasonable assumption since all Numbers in the standard API implements Comparable.)

 

@SuppressWarnings("unchecked")
class NumberComparator implements Comparator<Number> {

    // Special values that are treated as larger than any other.
    private final static List<?> special =
            Arrays.asList(Double.NaN, Float.NaN, null);
    
    private final static List<?> largest =
            Arrays.asList(Double.POSITIVE_INFINITY, Float.POSITIVE_INFINITY);
    
    private final static List<?> smallest =
            Arrays.asList(Double.NEGATIVE_INFINITY, Float.NEGATIVE_INFINITY);
    
    public int compare(Number n1, Number n2) {
        
        // Handle special cases (including null)
        if (special.contains(n1)) return  1;
        if (special.contains(n2)) return -1;
        
        if (largest.contains(n1) || smallest.contains(n2)) return  1;
        if (largest.contains(n2) || smallest.contains(n1)) return -1;
        
        // Promote known values (Byte, Integer, Long, Float, Double and
        // BigInteger) to BigDecimal, as this is the most generic known type.
        BigDecimal bd1 = asBigDecimal(n1);
        BigDecimal bd2 = asBigDecimal(n2);
        if (bd1 != null && bd2 != null)
            return bd1.compareTo(bd2);
        
        // Handle arbitrary Number-comparisons if o1 and o2 are of same class
        // and implements Comparable.
        if (n1 instanceof Comparable<?> && n2 instanceof Comparable<?>)
            try {
                return ((Comparable) n1).compareTo((Comparable) n2);
            } catch (ClassCastException cce) {
            }
        
        // If the longValue()s differ between the two numbers, trust these.
        int longCmp = ((Long) n1.longValue()).compareTo(n2.longValue());
        if (longCmp != 0)
            return longCmp;
        
        // Pray to god that the doubleValue()s differ between the two numbers.
        int doubleCmp = ((Double) n1.doubleValue()).compareTo(n2.doubleValue());
        if (doubleCmp != 0)
            return longCmp;
        
        // Die a painful death...
        throw new UnsupportedOperationException(
                "Cannot compare " + n1 + " with " + n2);
    }
    
    
    // Convert known Numbers to BigDecimal, and the argument n otherwise.
    private BigDecimal asBigDecimal(Number n) {
        if (n instanceof Byte)       return new BigDecimal((Byte) n);
        if (n instanceof Integer)    return new BigDecimal((Integer) n);
        if (n instanceof Short)      return new BigDecimal((Short) n);
        if (n instanceof Long)       return new BigDecimal((Long) n);
        if (n instanceof Float)      return new BigDecimal((Float) n);
        if (n instanceof Double)     return new BigDecimal((Double) n);
        if (n instanceof BigInteger) return new BigDecimal((BigInteger) n);
        if (n instanceof BigDecimal) return (BigDecimal) n;
        return null;
    }
}

Here is a small test program (here is an ideone.com demo):

public class Main {

    public static void main(String[] args) {
        List<Number> li = new ArrayList<Number>();

        // Add an Integer, a Double, a Float, a Short, a Byte and a Long.
        li.add(20);         li.add((short) 17);
        li.add(12.2);       li.add((byte) 100);
        li.add(0.2f);       li.add(19518926L);
        li.add(Double.NaN); li.add(Double.NEGATIVE_INFINITY);
        li.add(Float.NaN);  li.add(Double.POSITIVE_INFINITY);
        
        // A custom Number
        li.add(new BoolNumber(1));
        li.add(new BoolNumber(0));
        
        // Add two BigDecimal that are larger than Double.MAX_VALUE.
        BigDecimal largeDec = new BigDecimal("" + Double.MAX_VALUE);
        li.add(largeDec/*.multiply(BigDecimal.TEN)*/);
        li.add(largeDec.multiply(BigDecimal.TEN).multiply(BigDecimal.TEN));
        
        // Add two BigInteger that are larger than Double.MAX_VALUE.
        BigInteger largeInt = largeDec.toBigInteger().add(BigInteger.ONE);
        li.add(largeInt.multiply(BigInteger.TEN));
        li.add(largeInt.multiply(BigInteger.TEN).multiply(BigInteger.TEN));
        
        // ...and just for fun...
        li.add(null);
        
        Collections.shuffle(li);
        Collections.sort(li, new NumberComparator());
        
        for (Number num : li)
            System.out.println(num);
    }
    
    static class BoolNumber extends Number {
        boolean b;
        public BoolNumber(int i)    { b = i != 0; }
        public double doubleValue() { return b ?  1d :  0d; }
        public float floatValue()   { return b ?  1f :  0f; }
        public int intValue()       { return b ?   1 :   0; }
        public long longValue()     { return b ?  1L :  0L; }
        public String toString()    { return b ? "1" : "0"; }
    }
}

...which prints (I removed a few zeros):

-Infinity
0
0.2
1
12.2
17
20
100
19518926
1.7976931348623157E+308
17976931348623157000000000...00000000010
1.797693134862315700E+310
179769313486231570000000000000...00000100
Infinity
NaN
null
NaN

Solution 3

Simple answer: You can't. A proprietary Number implementation may have higher precision or a larger value range than what is available through the getXXX() methods defined for the actual value in the Number interface.

Solution 4

You'll need a solution for null values, because they may be in the collection - you can't create a collection of objects that doesn't take null.

So you could check for null and throw IllegalArgumentException - with the sideeffect, that you won't be able to sort "polluted" lists and have to handle those exceptions at runtime.

Another idea is to convert a null to some kind of number. I've shown this approach (based on you own solution from your own answer) by converting any null to Double.NaN by convention. You could also consider converting them to 0 or to Double.POSITIVE_INFINITY or Double.NEGATIVE_INFINITY if you want null values sorted to the far ends.

Collections.sort(li,new Comparator<Number>() {
    @Override
    public int compare(Number o1, Number o2) {

        // null values converted to NaN by convention
        Double d1= (o1 == null) ? Double.NaN : o1.doubleValue();
        Double d2= (o2 == null) ? Double.NaN : o2.doubleValue();

        return  d1.compareTo(d2);
    }
});

Further Information

Here's some code that shows how thoses special values are handled by "default":

Set<Double> doubles = new TreeSet<Double>();
doubles.add(0.);
// doubles.add(null);   // uncommenting will lead to an exception!
doubles.add(Double.NaN);
doubles.add(Double.POSITIVE_INFINITY);
doubles.add(Double.NEGATIVE_INFINITY);

for (Double d:doubles) System.out.println(d);

The result (with no null addded) is:

-Infinity
0.0
Infinity
NaN

View more solutions

Comments

[Jon Skeet]

Note that that will fail if the double values are too far apart. I would convert either to Double values and call compareTo on them, or use greater-than/less-than operators.

[Emil]

@Andreas_D:The null is going to throw exception anyway.do you have a better idea to handle it ?

[Adeel Ansari]

@Emil: Put a condition there so, all null will go in the end.

[Emil]

@Adeel Ansari: The collections default sort method does not check for null conditions.It just throws exception.Thats why i left it unchecked.If at all i'm to give a condition what should it be ?

[Adeel Ansari]

@Emil: Why should a sort() method check that. And BTW, you are not implementing the sort() method, but compare(). And its completely your choice to define the behaviour.

[Emil]

@Adeel Ansari:There can be null in List<Integer> or List<String> .These null always throw exception.

[Andreas Dolk]

@Emil - look at my reply ("answer") below. There's a short discussion about the standard null problem.

[madhurtanwani]

Here is what I think : in the compare method, check if o1 and o2 are instanceof of Comparable. If yes, then the Java code has already implemented the best possible comparison for the numerical types - use that (by calling o1.compareTo(o2). If it does not implement Comparable, I would recommend working off BigDecimal instead of Double.

[jarnbjo]

@Emil: Not without writing a lot of obvious code. What if you have two Number instances with the internal values "Double.MAX_VALUE * 2" and "Double.MAX_VALUE * 3". Their getDouble() implementation must truncate the value to fit into the range of a double and hence probably both return Double.MAX_VALUE, making it impossible to implement a generic comparator for these types.

[Emil]

@jarnbjo:Are you talking about Number instance of BigDecimal or BigInteger ?

[jarnbjo]

@Emil: They are just examples. Anyone can write their own implementations of the Number interface, you don't have to restrict your consideration to classes in the standard API.

[Emil]

@jarnbjo:Yes i understand.So is there any way to restrict to certain number implementations using generics ?

[jarnbjo]

Unfortunately not. Even the Number implementations in the standard API don't have any other common types to use as a generic restriction.

[aioobe]

@madhurtanwani, check out my answer :-)

[Emil]

@aioobe: Your implementation is good but i think it's better to restrict the types at runtime,since any new implementation of Number can be made and handling all the cases in the same comparator wouldn't be practical.Moreover we cannot get numbers greater than double from number instances.Check my updated answer.

[aioobe]

Note that this implementation may see new BigDecimal("" + Double.MAX_VALUE).multiply(BigDecimal.TEN) as larger than Double.POSITIVE_INFINITY.

[aioobe]

Well, you asked for a way to sort Number s, not for a way to sort a mixture of Integer, Double, Float, Short, Byte, right? I claim that it can't be solved completely, but you can get far. You say, "Moreover we cannot get numbers greater than double from number instances." Depends on if you're referring to the class Number. (Sure we can get Numbers greater than doubles from Numbers.)

[Emil]

aioobe:Yes your right .I did ask so,but then i was not aware that BigInteger and BigDecimals also implemented Number.Any way thanks for your answer.

[aioobe]

@Emil, Now you know :-) and now you know how far you can get when it comes to sorting Numbers. Both our solutions may fail at runtime when fed with strange Numbers, but my solution will get you a bit further than yours.

[aioobe]

@Emil, you broke the null-handling in your update. Your solution now throws NullPointerExceptions.

[aioobe]

@Emil, "In the above code all null values are handled such that they move to the end.".. - No they aren't.

[jarnbjo]

aioobe: Your implementation does not need very strange Numbers to fail. Longs have a much higher precision than double for large values, so using doubleValue() as a fallback will fail to compare e.g. Long.MAX_VALUE and (Long.MAX_VALUE-1), as they are equivalent after being cast to double.

[aioobe]

@jarnbjo, you're right. I made an attempt to fix it. Wow, this is getting really tricky...

[aioobe]

@Emil, as @jarnbjo points out below my answer: Longs have a much higher precision than double for large values, so using doubleValue() as a fallback will fail to compare e.g. Long.MAX_VALUE and (Long.MAX_VALUE-1), as they are equivalent after being cast to double.

[Emil]

@aioobe: That's true.I removed Long from allowed types in my implementation.

[jarnbjo]

Now it would fail when comparing e.g. Long.MAX_VALUE and (1. + Long.MAX_VALUE). Calling Double#longValue() is equivalent to casting a primitive double to a primitive long, which is covered in JLS §5.1.3 (Narrowing Primitive Conversions). If the double value is greater than Long.MAX_VALUE, the result of the cast is Long.MAX_VALUE.

[aioobe]

No. Long and Doubles are converted and compared through BigDecimal. Those values are fine.

[dacwe]

Good question +1 but bad answer, -1. Use the solution that aioobe provided - it works, this doesn't!