How can I rank keys in a TreeMap by their values?

Question

I have a Treemap implementation that takes in Strings as keys and Integers as their values.

//YearWord is an TreeMap<String, Integer> implementation
YearWord yr = new YearWord();
yr.put("terminal", 95);        
yr.put("aggregate", 340);
yr.put("catalyst", 181);

if I want to write a function rank which takes in a String word and returns an int value corresponding to the rank of the keyword, how would I approach this? I tried using arrayLists but they're kinda slow. Thanks!

My method signature is

public int rank(String word) {
    ????
}

See answer: http://stackoverflow.com/questions/12947088/java-treemap-comparator You need write comparator. — Andrey Pushin, Mar 06 '15 at 19:34
And can the argument of this method NOT be a key of the map? — fge, Mar 06 '15 at 19:34
@AndreyPushin that won't help; a `TreeMap` is already sorted (by its keys) — fge, Mar 06 '15 at 19:34
@fge the question to which Andrey points does provide an answer to this question. Its accepted solution creates a `SortedSet` with a custom comparator which sorts based on values rather than keys. — Bobulous, Mar 06 '15 at 19:40
Are all the values different? If not, how are you defining rank? E.g. if the values were 10, 14, 15, 15, 19, what would the ranks be? 1, 2, 3, 3, 5? — Paul Boddington, Mar 06 '15 at 19:44
The values can be the same, and if there is a tie, I can break it arbitrarily. If two keys have the same value I can randomly choose one of them — Limone_77, Mar 06 '15 at 19:46

score 3 · Answer 1 · answered Mar 06 '15 at 20:30

You could try something like this. If two or more values are tied, they are ordered by the keys instead.

public final class RankableMap<K extends Comparable<K>, V extends Comparable<V>> extends TreeMap<K, V> {

    private static final class Pair<K extends Comparable<K>, V extends Comparable<V>> implements Comparable<Pair<K, V>> {
        private final K k;
        private final V v;
        private Pair(K k, V v) {
            this.k = k;
            this.v = v;
        }
        @Override
        public int compareTo(Pair<K, V> that) {
            int a = v.compareTo(that.v);
            return a != 0 ? a : k.compareTo(that.k);
        }
    }

    private final SortedSet<Pair<K, V>> set = new TreeSet<>();

    @Override
    public V put(K k, V v) {
        V v2 = super.put(k, v);
        if (v.equals(v2))
            return v2;
        if (v2 != null)
            set.remove(new Pair<>(k, v2));
        set.add(new Pair<>(k, v));
        return v2;
    }

    @Override
    public V remove(Object k) {
        V v = super.remove(k);
        if (v != null)
            set.remove(new Pair<>((K) k, v));
        return v;
    }

    @Override
    public void clear() {
        super.clear();
        set.clear();
    }

    public int rank(K k) {
        return 1 + set.headSet(new Pair<K, V>(k, get(k))).size();
    }
}

I tested this class with the following code

RankableMap<String, Integer> map = new RankableMap<>();
map.put("quayside", 95);
map.put("surrogate", 340)   
map.put("merchantman", 181);
map.put("foo", 340);
map.put("bar", 42);
for (String key : map.keySet())
    System.out.println(key + " rank = " + map.rank(key));
map.remove("bar");
System.out.println();     
for (String key : map.keySet())
    System.out.println(key + " rank = " + map.rank(key));

and it gave the following result:

bar rank = 1
foo rank = 4
merchantman rank = 3
quayside rank = 2
surrogate rank = 5

foo rank = 3
merchantman rank = 2
quayside rank = 1
surrogate rank = 4

How can I rank keys in a TreeMap by their values?

1 Answers1