How to sort a Collection of generic Pairs

Question

This is homework, so I would prefer some explanation rather than just giving me the answer.

I have a generic Pair class that can take any key value K, and any value V.

The goal is to write a generic method:

public static <...> Collection<Pair<...>> sortPairCollection(Collection <Pair<....>> col)

The only other guideline is that the K type must implement Comparable<...>.

After some digging, I saw people recommend something like this:

public static Collection<Pair<?,?>> sortPairCollection(Collection<Pair<?,?>> col)
{
    Collections.sort(col, new Comparator<Pair<?,?>>(){
        @Override
        public int compare(Pair<?, ?> x, Pair<?, ?> y) {
            return (Integer)x.v() - (Integer)y.v();
        }
    });
}

But that doesn't work for me, I get an error that says the sort method is not applicable to those parameters. I don't really know where to go from here.

score 6 · Accepted Answer · edited May 23 '17 at 11:58

6

Collections.sort only works on List instances, not on general Collections. It does not make sense to sort a HashSet for example.

Secondly, due to arithmetic overflow, you should avoid using subtraction in a comparator like that. It is always better to use Integer.compare.

Also, a method with return type Collection<Pair<?,?>> must return something. You could return col, but as you are mutating col it makes more sense to make the method void.

Another point is that it looks like your method will throw a ClassCastException unless the second type parameter is Integer (I am assuming v() has return type V). If this is the case, there is no point writing your method for Pair<?, ?> as you could just use Pair<?, Integer>.

Finally, due to the way generics work in Java, you won't actually be able to pass in a List<Pair<String, Integer>> with your current signature, because a List<Pair<String, Integer>> is not a List<Pair<?, Integer>> (see this question or this one). If you want to be able to do that, the argument should have type List<? extends Pair<?, Integer>>.

Edit

I now realise that I haven't really answered the question. The idea is not to mutate the original collection, but return a new one. Also the sorting should be done by key, not value, because K must implement Comparable.

In order to use the compareTo method, you need to indicate that K extends Comparable. The way to do this is to use the signature

public static <K extends Comparable<? super K>, V> Collection<Pair<K, V>> sortPairCollection(Collection<Pair<K, V>> col)

This is a bit of a mouthful - generics have significantly increased the complexity of method signatures.

K extends Comparable<? super K> says that Ks can be compared with other Ks.

You will still need to use a List though. You could use the ArrayList constructor that accepts a Collection.

As requested, I'll leave it up to you to write the correct code.

edited May 23 '17 at 11:58

Community

1
1

answered Apr 03 '16 at 14:52

Paul Boddington

37,127
10
65
116

2

Also, the method declares to return `Collection>` but in fact does not. – Tunaki Apr 03 '16 at 14:54
@Tunaki You're right about that. I never got around to that yet since I was trying to figure out the sorting first. – ozzymado Apr 03 '16 at 14:55
1

@Tunaki Thanks, I missed that. – Paul Boddington Apr 03 '16 at 14:56
I have two problems with this answer. 1) You don't cover *"K type must implement Comparable<...>"*. To me, it implies that the sorting should sort the pairs by the key, not by the value. 2) If the *"goal is to write [the shown] generic method"*, you can do it. The reason it returns a `Collection` is that it should not mutate the parameter, which is also why it's ok for the parameter to be a `Collection` and not a `List`. – Andreas Apr 03 '16 at 15:22
@Andreas You're right. I didn't actually notice the part about `K`. I was too busy analysing the code I missed the entire point of the question. I'll edit. – Paul Boddington Apr 03 '16 at 15:26
I otherwise like your answer. Maybe help OP by showing the completed method signature, where the first `<...>` should be `, V>`? – Andreas Apr 03 '16 at 15:31
@Andreas Thanks for that. I just added a `? super`. – Paul Boddington Apr 03 '16 at 15:37
Thank you for all of your help. I was getting close to the answer before the edit but apparently I was missing the `? super` part of `? super K`. Code works perfectly now. – ozzymado Apr 03 '16 at 15:44
Glad to hear it. In almost all cases you don't need to use `? super`, but it's best to include it anyway. This says that Ks can be compared with instances of a type that could actually be larger than K. However in practice there are few real examples of different classes that are mutually comparable. – Paul Boddington Apr 03 '16 at 15:46

score -1 · Answer 2 · edited May 26 '16 at 19:19

-1

Here is the complete program:

public static <K extends Comparable<? super K>, V extends Comparable<? super V>> void sortPairCollection(List<Pair<K, V>> col){

        Collections.sort(col, new Comparator<Pair<K,V>>(){

            public int compare(Pair<K, V> o1, Pair<K, V> o2) {

                int keyflag = o1.getValue().compareTo(o2.getValue()) == 0 ? o1.getKey().compareTo(o2.getKey()): o1.getValue().compareTo(o2.getValue()) ;

                return keyflag;

            }});

    }

edited May 26 '16 at 19:19

Laurel

5,965
14
31
57

answered May 26 '16 at 12:29

Arun

1
2

clearly stated in the question: so I would prefer some explanation rather than just giving me the answer. so this is not an answer – Martin Frank May 26 '16 at 12:54

How to sort a Collection of generic Pairs

2 Answers2