Sorting a List

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));

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

try my java sorting algorithm:

package drawFramePackage;

import java.awt.geom.AffineTransform;
import java.util.ArrayList;
import java.util.ListIterator;
import java.util.Random;

public class QuicksortAlgorithm {
    ArrayList<AffineTransform> affs;
    ListIterator<AffineTransform> li;
    Integer count, count2;

    /**
     * @param args
     */
    public static void main(String[] args) {
        new QuicksortAlgorithm();
    }

    public QuicksortAlgorithm(){
        count = new Integer(0);
        count2 = new Integer(1);
        affs = new ArrayList<AffineTransform>();

        for (int i = 0; i <= 128; i++) {
            affs.add(new AffineTransform(1, 0, 0, 1, new Random().nextInt(1024), 0));
        }

        affs = arrangeNumbers(affs);
        printNumbers();
    }

    public ArrayList<AffineTransform> arrangeNumbers(ArrayList<AffineTransform> list) {
        while (list.size() > 1 && count != list.size() - 1) {
            if (list.get(count2).getTranslateX() > list.get(count).getTranslateX()) {
                list.add(count, list.get(count2));
                list.remove(count2 + 1);
            }

            if (count2 == list.size() - 1) {
                count++;
                count2 = count + 1;
            } else {
                count2++;
            }
        }
        return list;
    }

    public void printNumbers(){
        li = affs.listIterator();

        while (li.hasNext()) {
            System.out.println(li.next());
        }
    }
}

Answer 5

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);