9
\$\begingroup\$

A common task I often face is ordering a collection of items according to some predefined model, typically expressed as an ordered list of ranks. For example, credit agencies might rate financial products as:

  • AAA (excellent investment)
  • AA (very good investment)
  • B (not so good investment)
  • BB (poor investment)
  • BBB (why are we investing in this steamy pile of garbage?)
  • NR (not rated / unknown)

I often need a way of ordering a collection of objects by such ratings. I could try to hack something together roughly based on the alphabet, but it seems more extensible to take a model list of the defined order, and use that in the comparison: when given two ratings, find their indexes in the model list, and use the indexes to decide the ordering.

To make this a reusable general purpose utility, I came up with this:

class EnumeratedRankComparator<T> implements Comparator<T> {
    private final Map<T, Integer> itemsToIndex;

    private EnumeratedRankComparator(List<T> items) {
        itemsToIndex = new HashMap<>(items.size());

        int index = 0;
        for (T item : items) {
            if (itemsToIndex.containsKey(item)) {
                throw new IllegalArgumentException("Inconsistent ranks: there should be no duplicates");
            }
            itemsToIndex.put(item, ++index);
        }
    }

    public static <T> EnumeratedRankComparator<T> fromLowToHigh(List<T> items) {
        return new EnumeratedRankComparator<>(items);
    }

    public static <T> EnumeratedRankComparator<T> fromHighToLow(List<T> items) {
        List<T> copy = new ArrayList<>(items);
        Collections.reverse(copy);
        return new EnumeratedRankComparator<>(copy);
    }

    @Override
    public int compare(T o1, T o2) {
        return Integer.compare(itemsToIndex.get(o1), itemsToIndex.get(o2));
    }
}

To illustrate the usage with an example, consider this enumeration of Rating values:

enum Rating {
    AAA_PLUS("AAA+"),
    AAA("AAA"),
    AAA_MINUS("AAA-"),
    AA_PLUS("AA+"),
    AA("AA"),
    AA_MINUS("AA-"),
    BB("BB"),
    NR("Non-rated")
    ;

    private final String label;

    Rating(String label) {
        this.label = label;
    }

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

I can compose a custom RatingComparator like this:

private static class RatingComparator implements Comparator<Rating> {

    private final EnumeratedRankComparator<Rating> comparator;

    public RatingComparator() {
        comparator = EnumeratedRankComparator.fromHighToLow(Arrays.asList(Rating.values()));
    }

    @Override
    public int compare(Rating o1, Rating o2) {
        return comparator.compare(o1, o2);
    }
}

Unit tests:

private final RatingComparator comparator = new RatingComparator();

@Test
public void test_AA_lessThan_AAA() {
    assertEquals(-1, comparator.compare(Rating.AA, Rating.AAA));
}

@Test
public void test_AAA_lessThan_AAA_PLUS() {
    assertEquals(-1, comparator.compare(Rating.AAA, Rating.AAA_PLUS));
}

@Test
public void test_AAA_greaterThan_AAA_MINUS() {
    assertEquals(1, comparator.compare(Rating.AAA, Rating.AAA_MINUS));
}

@Test
public void test_AAA_equals_AAA() {
    assertEquals(0, comparator.compare(Rating.AAA, Rating.AAA));
}

@Test
public void test_NR_lessThan_A_MINUS() {
    assertEquals(-1, comparator.compare(Rating.NR, Rating.AAA));
}

@Test
public void test_sort_AA_AAA_NR_BB() {
    List<Rating> ratings = Arrays.asList(Rating.AA, Rating.AAA, Rating.NR, Rating.BB);
    Collections.sort(ratings, comparator);
    assertEquals(Arrays.asList(Rating.NR, Rating.BB, Rating.AA, Rating.AAA), ratings);
}

@Test(expected = IllegalArgumentException.class)
public void test_inconsistent_ranks() {
    EnumeratedRankComparator.fromHighToLow(Arrays.asList(Rating.AA, Rating.AA_MINUS, Rating.AA));
}

@Test
public void test_sortIssuersByRating() {
    class Issuer {
        final Rating rating;

        Issuer(Rating rating) {
            this.rating = rating;
        }

        @Override
        public String toString() {
            return "I-" + rating;
        }
    }

    Issuer issuerBB = new Issuer(Rating.BB);
    Issuer issuerAA = new Issuer(Rating.AA);
    Issuer issuerNR = new Issuer(Rating.NR);

    List<Issuer> issuers = Arrays.asList(issuerBB, issuerAA, issuerNR);
    Collections.sort(issuers, new Comparator<Issuer>() {
        @Override
        public int compare(Issuer o1, Issuer o2) {
            return comparator.compare(o1.rating, o2.rating);
        }
    });

    assertEquals(Arrays.asList(issuerNR, issuerBB, issuerAA), issuers);
}

What do you think? Is there an easier way I missed? Can you think of a better name for this thing? I'm interested in a review of all aspects and improvement ideas.

\$\endgroup\$
  • \$\begingroup\$ Is Java 8 available? \$\endgroup\$ – Simon Forsberg Mar 4 '15 at 0:23
  • \$\begingroup\$ Sure, let's say yes! \$\endgroup\$ – janos Mar 4 '15 at 8:34
7
\$\begingroup\$

My first observation is that you are inventing a wheel here. See guava Ordering, and in particular the onResultOf method. You don't need to build an entire Comparator scaffolding of your own, just a ranking function that can be plugged into the library.

private final Map<T, Integer> itemsToIndex;

private EnumeratedRankComparator(List<T> items) {
    itemsToIndex = new HashMap<>(items.size());

    int index = 0;
    for (T item : items) {
        if (itemsToIndex.containsKey(item)) {
            throw new IllegalArgumentException("Inconsistent ranks: there should be no duplicates");
        }
        itemsToIndex.put(item, ++index);
    }
}

I'm not a big fan of doing work in the constructor. Here, you've got the factory methods anyway, so why not do the work there, and inject the completed map?

private EnumeratedRankComparator(Map<T, Integer> itemsToIndex) {
    this.itemsToIndex = itemsToIndex;

Notice that this allows the caller to choose an appropriate map implementation; maybe the caller wants to use a map where the get() method is instrumented, maybe the caller knows that T extends Enum<T>, and that an EnumMap<T, Integer> is a more appropriate choice than a HashMap<T,Integer>.

@Override
public int compare(T o1, T o2) {
    return Integer.compare(itemsToIndex.get(o1), itemsToIndex.get(o2));
}

You can do this, but you might consider that Integer implements compareTo(Integer), and instead write

@Override
public int compare(T o1, T o2) {
    return itemsToIndex.get(o1).compareTo(itemsToIndex.get(o2));
}

You might further recognize that Integer implements Comparable<Integer> (that's where the signature of the compareTo function comes from). This in turn means that you don't need a map to Integer, but a map to Comparable.

public class EnumeratedRankComparator<F,T extends Comparable<T>> implements Comparator<T>{
    private final Map<F, T> itemsToIndex;

    public EnumeratedRankComparator(Map<F, T> itemsToIndex) {
        this.itemsToIndex = itemsToIndex;
    }

    @Override
    public int compare(T o1, T o2) {
        return itemsToIndex.get(o1).compareTo(itemsToIndex.get(o2));
    }
}

Similarly, you might notice that in your factory methods, you are never really using the fact that you've been passed a list of items.

private EnumeratedRankComparator(List<T> items) {
    itemsToIndex = new HashMap<>(items.size());

    int index = 0;
    for (T item : items) {
        if (itemsToIndex.containsKey(item)) {
            throw new IllegalArgumentException("Inconsistent ranks: there should be no duplicates");
        }
        itemsToIndex.put(item, ++index);
    }
}

items here is just an Iterable<T>, isn't it?

Since fromHighToLow() is really the same factory method as fromLowToHigh(), I would probably have the one call the other, rather than having them both call to the constructor (which saves you from duplicating all the logic I recommended you extract from the constructor anyway)

public static <T> EnumeratedRankComparator<T> fromLowToHigh(List<T> items) {
    ...
}

public static <T> EnumeratedRankComparator<T> fromHighToLow(List<T> items) {
    List<T> copy = new ArrayList<>(items);
    Collections.reverse(copy);
    return fromLowToHigh(copy);
}

I might reconsider - or introduce a factory method with a more neutral name, if I expected people to spend a lot of time staring at stack traces here:

public static <T> EnumeratedRankComparator<T> fromLowToHigh(List<T> items) {
    return createFromList(items);
}

public static <T> EnumeratedRankComparator<T> fromHighToLow(List<T> items) {
    List<T> copy = new ArrayList<>(items);
    Collections.reverse(copy);
    return createFromList(items);
}

As rolfl points out, the natural ordering of enums should not be a challenge. You would also have the option of defining a simple comparator to pull some property out of the enum, and sort on that instead (for instance, writing a Comparator that uses o1.name().compareTo(o2.name()) as an alternative to the natural ordering).

\$\endgroup\$
7
\$\begingroup\$

There are two major sections to your question, the first has a general purpose comparator setup, the second has a specific rankings system. The Rankings system is the one that concerns me most.....

... it's an enum. Enums are naturally comparable, and sort in the same order of their declaration. Your entire use case in the second set can be handled (in Java 8) with:

private final Comparator<Rating> comparator = Comparator.naturalOrder();

In earlier versions:

public class EnumComparator<T extends Enum> implements Comparator<T> {

  @Override
  public int compare(T e1, T e2) {
     return e1.compareTo(e2);
  }

};

Sorting of enums in their natural order should not be a problem.

As for the general case, I think your system is OK. I can't think of a better way to do it... the Map seems expensive, but it is small, and limited in size, and should be fine. For small input Lists (less than 5 or so), I would consider a simple Array containing the members, in order, and loop them checking each one.... and returning the index of a match. Benchmarking may prove enlightening.

\$\endgroup\$
  • \$\begingroup\$ +1 I see no need to reimplement something that the standard library already provides based on the Enum ordering. \$\endgroup\$ – skiwi Mar 4 '15 at 13:39
4
\$\begingroup\$

@rolfl beat me to it, but I'll still offer my answer in case it is marginally more useful...

First, in your test_sort_AA_AAA_NR_BB() method, you are expecting that the sorted list is in a low (not rated, yucks) to high (so many As!) order. This either means that your RatingComparator should really be calling

EnumeratedRankComparator.fromLowToHigh(Arrays.asList(Rating.values()))

Or you need to change your enum's ordering, or the unit tests' expected values. Or perhaps I am just over-thinking this and should just treat the definition of 'high-to-low' as 'a higher rating is greater compared to a lower rating'.

Second, @rolfl suggested just calling the enum's compareTo() method, but since you are asserting specifically for the values -1, 0 and 1, you need a light Comparator implementation to make it suitable for your unit tests.

    static Comparator<Rating> getLowToHighComparator() {
        return new Comparator<Rating>() {
            @Override
            public int compare(Rating o1, Rating o2) {
                // a lower ordinal indicates a higher ranking
                return Integer.compare(o2.compareTo(o1), 0);
            }
        };
    }

    static Comparator<Rating> getHighToLowComparator() {
        return new Comparator<Rating>() {
            @Override
            public int compare(Rating o1, Rating o2) {
                // a lower ordinal indicates a lower ranking
                return Integer.compare(o1.compareTo(o2), 0);
            }
        };
    }

Still, I will advise against comparing the result of compare() with these three specific values, as the Javadoc only mentions the result can either be a negative integer, 0 or positive integer. If you are ok with re-writing your unit tests, then simply calling the enum's compareTo() will be simpler and better understood.

Asserting on the lists then becomes:

private final Comparator<Rating> comparator = Rating.getLowToHighComparator();

@Test
public void test_sort_LowHigh_AA_AAA_NR_BB() {
    List<Rating> ratings = Arrays.asList(Rating.AA, Rating.AAA, Rating.NR, Rating.BB);
    Collections.sort(ratings, comparator);
    assertEquals(Arrays.asList(Rating.NR, Rating.BB, Rating.AA, Rating.AAA), ratings);
}

@Test
public void test_sort_HighLow_AA_AAA_NR_BB() {
    List<Rating> ratings = Arrays.asList(Rating.AA, Rating.AAA, Rating.NR, Rating.BB);
    Collections.sort(ratings, Rating.getHighToLowComparator());
    assertEquals(Arrays.asList(Rating.AAA, Rating.AA, Rating.BB, Rating.NR), ratings);
}
\$\endgroup\$
4
\$\begingroup\$

Public?

None of the classes you wrote are declared as public, how did you intend them to be used?

Additionally, your RatingComparator class is private, which makes me wonder how you are testing this? Did you declare this class inside the test class? I see no harm in making this one public

RatingComparator

Your RatingComparator has this field:

private final EnumeratedRankComparator<Rating> comparator;

This should be:

private final Comparator<Rating> comparator;

Your RatingComparator class is not required at all in fact, it is only a wrapper for a EnumeratedRankComparator using the delegation pattern, that can be replaced with:

public static Comparator<Rating> ratingComparator() {
    return EnumeratedRankComparator.fromHighToLow(Arrays.asList(Rating.values()));
}

Which can be generalized into:

public static <E> Comparator<E> comparator(List<E> list) {
    return EnumeratedRankComparator.fromHighToLow(list);
}

public static <E> Comparator<E> comparator(E[] items) {
    return comparator(Arrays.asList(items));
}

Nulls

Nulls. Those horrible creatures.

List<Rating> ratings = Arrays.asList(null, Rating.AAA, Rating.NR, Rating.BB);
Collections.sort(ratings, comparator);

This causes

java.lang.NullPointerException
    at sample.EnumeratedRankComparator.compare(EnumeratedRankComparator.java:32)
    at sample.Main$RatingComparator.compare(Main.java:26)

This can be solved by wrapping a Comparator inside Comparator.nullsFirst/Last

Use the interface, Luke!

Your fromLowToHigh and fromHighToLow methods does not need to reveal the implementation, use Comparator<T> as the return-type instead.

The same goes for your unit test, declare as:

private final Comparator<Rating> comparator = new RatingComparator();

EnumeratedRankComparator

Now let's see what we can do with EnumeratedRankComparator

Let's use some static methods to create the comparator:

public static <T> Map<T, Integer> itemsByIndex(List<T> items) {
    Map<T, Integer> itemsToIndex = new HashMap<>(items.size());
    int index = 0;
    for (T item : items) {
        if (itemsToIndex.containsKey(item)) {
            throw new IllegalArgumentException("Inconsistent ranks: there should be no duplicates");
        }
        itemsToIndex.put(item, ++index);
    }
    return itemsToIndex;
}

public static <T> Comparator<T> compare(Map<T, Integer> itemsToIndex) {
    return Comparator.nullsFirst(Comparator.comparing(e -> itemsToIndex.get(e)));
}

As you see the itemsByIndex is essentially your old constructor, and compare is essentially the actual Comparator implementation.

Calling SomeClass.compare(SomeClass.itemsByIndex(Arrays.asList(Rating.values()))) will get us the same comparator as you used before but in reversed order. We can take that Comparator though and just call .reversed() on it. Let's create a static method for this:

public static <T> Comparator<T> comparator(List<T> list) {
    return SomeClass.compare(SomeClass.itemsByIndex(list)).reversed();
}

But let's not forget fixing the null bug.

public static <T> Comparator<T> comparator(List<T> list) {
    return Comparator.nullsFirst(SomeClass.compare(SomeClass.itemsByIndex(list)).reversed());
}

itemsByIndex can however be written in the following ways as well, using some Java 8 magic:

public static <T> Map<T, Integer> itemsByIndex2(List<T> items) {
    return items.stream().collect(Collectors.toMap(e -> e, e -> items.indexOf(e)));
}

public static <T> Map<T, Integer> itemsByIndex3(List<T> items) {
    AtomicInteger index = new AtomicInteger();
    return items.stream().collect(Collectors.toMap(e -> e, e -> index.getAndIncrement()));
}

Final Result

public class EnumeratedRankComparator {
    public static <T> Map<T, Integer> itemsByIndex(List<T> items) {
        AtomicInteger index = new AtomicInteger();
        return items.stream().collect(Collectors.toMap(e -> e, e -> index.getAndIncrement()));
    }

    public static <T> Comparator<T> compare(Map<T, Integer> itemsToIndex) {
        return Comparator.nullsFirst(Comparator.comparing(e -> itemsToIndex.get(e)));
    }

    public static <T> Comparator<T> comparator(List<T> list) {
        return Comparator.nullsFirst(
            EnumeratedRankComparator.compare(
                 EnumeratedRankComparator.itemsByIndex(list)
            ).reversed()
        );
    }
}

And in your unit test:

private final Comparator<Rating> comparator = EnumeratedRankComparator.comparator(
      Arrays.asList(Rating.values()));
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.