Java, Strings and Custom Comparators

I recently needed to sort a list of strings according to a custom, non-native order defined at run time. For example given a list of strings:

  1. seven
  2. one
  3. four
  4. three
  5. two
  6. six
  7. 5
  8. N|ne
  9. eight
  10. zten
  11. aleven
  12. btwelve
  13. dthirteen
  14. cfourteen

one might need to sort these dynamically at run time in perhaps the following order, which may or may not change during runtime:

  1. One
  2. Two
  3. three
  4. four
  5. 5
  6. six
  7. seven
  8. eight
  9. n|ne

In addition, the algorithm would need to be able to handle strings that were not defined in the ¬†’desiredOrder’ list such that unrecognized strings would be placed at the end of the known, ordered list, and then sorted natively from there. An example of how the original list above should look after the sort is:

  1. one
  2. two
  3. three
  4. four
  5. 5
  6. six
  7. seven
  8. eight
  9. N|ne
  10. aleven
  11. btwelve
  12. cfourteen
  13. dthirteen
  14. zten

I decided that creating a new class implementing the Java Comparator¬†interface would be the most efficient way of doing this and was hoping that there would be some immediate cut & paste code gleaned from a simple Google search, but, no dice. Hopefully, at some point in the future, someone else in my position will find this code useful. Here’s what I came up with (comments, suggestions, criticism is welcome):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class ADynamicStringComparator implements Comparator
{
    private ArrayList order = new ArrayList();
 
    /**
     * String Comparator class that takes an explicit desired order. 
     * Case insensitive. If an encountered String is not contained within the
     * provided desiredOrder, then it will be placed at the end of the known
     * list within desiredOrder and then sorted natively.  
     * @param desiredOrder 
     */
    ADynamicStringComparator(List desiredOrder)
    {
        if(desiredOrder == null){
            throw new IllegalArgumentException("desiredOrder cannot be null.");
        }
        //set everything to lowercase
        for (String string : desiredOrder) {
            this.order.add(string.toLowerCase());
        }
    }
 
    @Override
    public int compare(String s1, String s2) 
    {
        s1 = s1.toLowerCase();
        s2 = s2.toLowerCase();
 
        //get index for 1
        int indexOfS1 = order.indexOf(s1);
        if(indexOfS1 == -1){
            indexOfS1 = order.size();
        }
 
        //get index for 2
        int indexOfS2 = order.indexOf(s2);
        if(indexOfS2 == -1){
            indexOfS2 = order.size();
        }
 
        if(indexOfS1 == order.size() && indexOfS2 == order.size())
        {
            return s1.compareTo(s2);
        }else{
            return indexOfS1 - indexOfS2;
        }
    }
}

Because the Java List interface preserves order, we can use a list as a parameter to the comparator’s constructor to define our order at runtime. Below is some simple test code as an example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
public void testCompare() 
{
    ArrayList list = new ArrayList();
    list.add("seven");
    list.add("one");
    list.add("four");
    list.add("three");
    list.add("two");
    list.add("six");
    list.add("5");
    list.add("N|ne");
    list.add("eight");
    list.add("zten");
    list.add("aleven");
    list.add("btwelve");
    list.add("dthirteen");
    list.add("cfourteen");
 
    /*The desired sort order. */
    ArrayList desiredOrder = new ArrayList();
    desiredOrder.add("One");
    desiredOrder.add("Two");
    desiredOrder.add("three");
    desiredOrder.add("four");
    desiredOrder.add("5");
    desiredOrder.add("six");
    desiredOrder.add("seven");
    desiredOrder.add("eight");
    desiredOrder.add("n|ne");
 
    /*Another desired sort order. */
    ArrayList desiredOrder2 = new ArrayList();
    desiredOrder.add("Two");
    desiredOrder.add("three");
    desiredOrder.add("four");
    desiredOrder.add("six");
    desiredOrder.add("One");
    list.add("dthirteen");        
    desiredOrder.add("seven");
    desiredOrder.add("eight");
    desiredOrder.add("5");
    desiredOrder.add("n|ne");        
 
    System.out.println("----------------");
    System.out.println("before sort 1");
    System.out.println("----------------");
    for (String string : list) {
        System.out.println(string);
    }        
 
    System.out.println("----------------");
    System.out.println("desiredOrder 1");
    System.out.println("----------------");
    for (String string : desiredOrder) {
        System.out.println(string);
    }
 
    Collections.sort(list, new ADynamicStringComparator(desiredOrder));
    System.out.println("----------------");
    System.out.println("after sort 1");
    System.out.println("----------------");
    for (String string : list) {
        System.out.println(string);
    }
 
    assertEquals(list.get(0), "one");
    assertEquals(list.get(1), "two");
    assertEquals(list.get(2), "three");
    assertEquals(list.get(3), "four");
    assertEquals(list.get(4), "5");
    assertEquals(list.get(5), "six");
    assertEquals(list.get(6), "seven");
    assertEquals(list.get(7), "eight");
    assertEquals(list.get(8), "N|ne");
    assertEquals(list.get(9), "aleven");
    assertEquals(list.get(10), "btwelve");
    assertEquals(list.get(11), "cfourteen");
 
    Collections.sort(list, new ADynamicStringComparator(desiredOrder2));
    System.out.println("----------------");
    System.out.println("after sort 2");
    System.out.println("----------------");
    for (String string : list) {
        System.out.println(string);
    }        
 
    /*Sorry, got lazy writing asserts. Feel free to add your own ;)*/
}

For easier to read code or contributions, check out the google code project here.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>