How to create a custom comparator to sort a numbering system

Question

Here is the code I have so far:

package Demo;

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

public class Demo {

    public static void main(String[] args) {

        ArrayList<String> list = new ArrayList<String>();

        list.add("3.3.x");
        list.add("1.2.x");
        list.add("2.3.x");

        VersionComparator x = new VersionComparator();

        Collections.sort(list, x );

        for(String str : list)
            System.out.println(str);

    }

    static class VersionComparator implements Comparator {
        public int compare(String str1, String str2) {

            String firstNumberStringOne = str1.split(".")[0]; 
            String firstNumberStringTwo = str2.split(".")[0];  
            String secondNumberStringOne = str1.split(".")[1]; 
            String secondNumberStringTwo = str2.split(".")[1];  

            return;
        }

        @Override
        public int compare(Object o1, Object o2) {
            // TODO Auto-generated method stub
            return 0;
        }
    }
}

I would like to sort the items in my list by the first number that appears before the period. If those two numbers are equal then go to the second number and compare those numbers. And if equal just return them.

I am not sure how to use the comparator. I tried to implement it and the compiler complained that I needed to add in the second compare method with the override. I also do not know how to do the comparison in terms of how it is being returned. I understand that if its equal then it returns a 0 and its less than then it returns a -1 and greater than a 1. But in terms of coding I am lost as to how does the program know how to sort it.

`split(".")` doesn't look good. Please read one of: http://stackoverflow.com/q/14833008/1393766 http://stackoverflow.com/q/7935858/1393766 http://stackoverflow.com/q/3387622/1393766 http://stackoverflow.com/q/2755945/1393766 — Pshemo, Apr 29 '15 at 19:26

score 2 · Answer 1 · answered Apr 29 '15 at 19:26

Your VersionComparator class is implementing the raw form of the Comparator interface, where the compare method will take 2 Objects instead of 2 Strings.

Implement the interface by supplying String as a type parameter. Then the compiler will recognize your compare method taking Strings as parameters as the proper implementation of the interface. You don't need a compare method taking Objects.

static class VersionComparator implements Comparator<String> {

You will of course need to implement the comparison logic in your compare method, returning an int less than 0, 0, or greater than 0 if str1 compares less than, equal to, or greater then str2 according to your custom sort order.

Pshemo · Accepted Answer · 2018-07-25T12:07:18.367

There are few problems with your code:

You are using raw type Comparator
```
class VersionComparator implements Comparator // no <Type> here
```
so compiler for Comparator<T> will try to use Object as T. This means that it will be compiling compare(T t1, T t2) method as compare(Object t1, Object t2).

If you want that method to compile as compare(String t1, String o2) so
- it would only accept String arguments
- it could internally use String methods like length()
set <String> as generic type via
```
class VersionComparator implements Comparator<String>
```
Now compiler will know that T is String.
When you are calling split(".") you are not splitting on dot, but on any character (except line separators) because split is using regular expression (regex), and in regex . represents any character beside line separators. Because of this at start you will get array of empty elements, which will then be cleared because split(regex) removes empty trailing strings. More info here: https://stackoverflow.com/a/21790319/1393766.

To solve this problem you will need to escape . for instance with "\\.".

This should cover main problems in your code. But if you would like to create nice solution then consider avoiding sorting Strings but rather instances of your own Version class.
Advantage of this approach is that you will not have to parse your String to int each time you want to compare two strings (which can be costly), but you will be able to store parsed version of "1.2.3" as array [1, 2, 3] and reuse it when needed.
Also Version class can implement Comparable<Vector> to provide default comparing method.

So your code can look more like:

class Version implements Comparable<Version> {

    private String versionStr;
    private int[] arr;

    public String getVersionStr() { return versionStr; }

    @Override public String toString() { return versionStr; }

    @Override
    public int compareTo(Version other) {

        int result = Integer.compare(arr[0], other.arr[0]);

        if (result != other)
            return result;

        return Integer.compare(arr[1], other.arr[1]);
    }

    public Version(String versionStr) {
        this.versionStr = versionStr;
        this.arr = Stream.of(versionStr.split("\\."))
                .limit(2)//get only two first elements
                .mapToInt(Integer::parseInt)//convert String to int
                .toArray();//create array with integers
    }

}

class Demo {

    public static void main(String[] args) {

        List<Version> list = new ArrayList<Version>();

        list.add(new Version("3.3.x"));
        list.add(new Version("1.2.x"));
        list.add(new Version("1.11.x"));
        list.add(new Version("2.3.x"));

        Collections.sort(list);//with use default order provided by compareTo(Version other)

        for (Version str : list)
            System.out.println(str);
    }
}

Dhaval Patel · Answer 3 · 2015-04-29T20:59:14.523

0

 public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<String>();
    list.add("3.3.x");
    list.add("1.2.x");
    list.add("1.11.x");
    list.add("1.1.x");
    list.add("2.3.x");

    Collections.sort(list, new VersionComparator());

    for(String str : list)
       System.out.println(str);

}

static class VersionComparator implements Comparator<String> {
    //Temporary Cache Map to hold Split String value. String as Key and Split String array as value is this in this map.
    Map<String, String[]> mCacheMap = new HashMap<>();

    @Override
    public int compare(String string1, String string2) {

        if(!mCacheMap.containsKey(string1)){
            //Put Split String of string1 to map if it does not contain it.
            mCacheMap.put(string1, string1.split("\\."));
        }
        if(!mCacheMap.containsKey(string2)){
           //Put Split String of string2 to map if it does not contain it.
           mCacheMap.put(string2, string2.split("\\."));
        }
        //Get First Digit of first string1 from Map
        Integer string1Val1 = Integer.valueOf(mCacheMap.get(string1)[0]); 
        //Get First Digit of second string2 from Map            
        Integer string2Val1 = Integer.valueOf(mCacheMap.get(string2)[0]);

        //Compare Both Digit. compareTo Method return a negative integer, zero, or a positive integer as first Integer value is less than, equal to, or greater than the seconf Integer value.
        int cmp = string1Val1.compareTo(string2Val1);

        if( cmp != 0 ){
            return cmp;
        }else {
            //If First digit of both string is same compare second digit. 
            Integer string1Val2 = Integer.valueOf(mCacheMap.get(string1)[1]); 
            Integer string2Val2 = Integer.valueOf(mCacheMap.get(string2)[1]); 
            return string1Val2.compareTo(string2Val2);
        }

    }
}

Results:

1.1.x
1.2.x
1.11.x
2.3.x
3.3.x

edited Apr 29 '15 at 20:59

answered Apr 29 '15 at 19:26

Dhaval Patel

10,119
5
43
46

I will post the Update Soon. – Dhaval Patel Apr 29 '15 at 19:44
Works better. Now you just need to explain OP what was wrong with his/her approach and why/how your approach works. – Pshemo Apr 29 '15 at 20:10
Also consider avoiding repeating your code (do you really need to recreate array each time you want to read one element?). – Pshemo Apr 29 '15 at 20:11
And `Ineger.parseInt` returns `int`, not `Integer` which means compiler will need to add autoboxing code to convert `int` to `Integer` (like `Integer i = Integer.valueOf(someInt)` ). You can get `Integer` from `String` by using `Integer.valueOf(string)`. – Pshemo Apr 29 '15 at 20:13
@Pshemo Yeh, you have a valid point. I think use of substring method is a better approach here. – Dhaval Patel Apr 29 '15 at 20:15
`split` is OK, just store its values somewhere and reuse them instead of recreating same array over and over again. – Pshemo Apr 29 '15 at 20:16
Yehh it is also good point. So i think we can use Map to store array. – Dhaval Patel Apr 29 '15 at 20:23
Yes, it is valid solution, but IMO easiest and cleanest way to achieve it is to create separate class like `Version` which would hold `String` and `int[]` array which will represent current version. Each time we will create instance of `Version` its `int[]` array should be also created like `Stream.of(versionStr.split("\\.").mapToInt(Integer::parseInt).toArray()`. Such class can also implement `Comparable` interface to provide default sorting method. This way when we will have list of vectors we can simply call its `sort()` method. – Pshemo Apr 29 '15 at 20:28

How to create a custom comparator to sort a numbering system

3 Answers3