Data-structure sorted by value

Question

I am trying to store a score for a large about of players. So I will need a map that is sorted based on the value, but because of the amount of players it's inefficient to sort it each time I retrieve it. I would also like the ability to find a players rank in the map. It would be very similar to the score datatype in redis. Something like:

    ScoreMap<String, Integer> scores = new ScoreMap<String, Integer>();

    scores.put("Bill", 2);
    scores.put("Tom", 6);
    scores.put("Jim", 3);
    scores.put("Jake", 3);


    System.out.println("Rank = " + scores.getRank("Bill"));

    System.out.println();
    System.out.println("All:");
    for (Entry<String, Integer> entry : scores.entrySet()) {
        System.out.println(entry.getKey() + " => " + entry.getValue());
    }

    System.out.println();
    System.out.println("Rank Range:");
    for (Entry<String, Integer> entry : scores.entryRankRange(0, 2)) {
        System.out.println(entry.getKey() + " => " + entry.getValue());
    }

    System.out.println();
    System.out.println("Score Range:");
    for (Entry<String, Integer> entry : scores.entryScoreRange(2, 3)) {
        System.out.println(entry.getKey() + " => " + entry.getValue());
    }

This would return

    Rank = 3

    All:
    Tom => 6
    Jake => 3
    Jim => 3
    Bill => 2

    Rank Range:
    Tom => 6
    Jake => 3
    Jim => 3

    Score Range:
    Jake => 3
    Jim => 3
    Bill => 2

I know this is kinda specific and I will probably have to make a custom data-structure. But a point in the right direction would be much appreciated. :)

See http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java — copeg, May 30 '15 at 23:11

score 2 · Answer 1 · edited May 23 '17 at 12:02

2

Simplest way to do this would be to use a Set (namely, TreeSet) and encapsulate the player information (including the score) into a specific class:

public class CompetitivePlayer implements Comparable<CompetitivePlayer>{

    private String name;
    private int score;    

    public CompetitivePlayer(String name, int score) {
        this.name = name;
        this.score = score;
    }

    public String getName() {
        return name;
    }

    public int getScore() {
        return score;
    }

    public void incrementScore() {
        score++;
    }

    @Override
    public int compareTo(CompetitivePlayer o) {
        return score - o.score;
    }
}

TreeSet assumes that entires stored in it implement the Comparable interface for determining the natural ordering of its elements.

Edit:

If you need to frequently modify the scores of players, then a Map<String, Integer>-based solution is a better fit, because there's no get in Java's Set. This thread discusses the Map-based approach in great detail.

One simplictic solution (as suggested in the mentioned thread) is a one-liner, using the Guava library:

Map<String, Integer> sortedScores = ImmutableSortedMap.copyOf(scores,
    Ordering.natural().onResultOf(Functions.forMap(scores)));

edited May 23 '17 at 12:02

Community

1
1

answered May 30 '15 at 23:17

Mick Mnemonic

7,808
2
26
30

How would you change a player's score if you did it this way? (Without iterating through the whole thing, then removing the old one) – May 30 '15 at 23:27
This example implementation only exposes the `incrementScore` method for incrementing the score by one. If you frequently need to change the score of a player, then a `Map` might be a better fit, because (unfortunately) [you cannot `get` elements from Java `Set`s](http://stackoverflow.com/questions/7283338/getting-an-element-from-a-set). What is your exact requirement? – Mick Mnemonic May 30 '15 at 23:32
Ah, yeah, I need to be able to change scores frequently. What I would like is something similar to the TreeMap but sorts based on the value not the key. – May 30 '15 at 23:38
I edited my answer with an example that uses the Guava library. If your players have no attributes other than names and you don't want to include any external libraries, then @BruceWayne 's answer looks like a good solution. – Mick Mnemonic May 31 '15 at 00:00
The Guava example I provided will not work if different players have equal scores (you get a `java.lang.IllegalArgumentException: Multiple entries with same key: Jake=3 and Jim=3`). I'll try to fix this tomorrow. – Mick Mnemonic May 31 '15 at 00:40
Beware changing the value used for sorting/comparing in a sorted data structure like `TreeSet` or `TreeMap`... many such data structures assume that the sorting criteria is _invariant_ once the object has been inserted. – William Price May 31 '15 at 00:50
Yes, that is a good point; you'd always need to re-`put` the value into the map if the score changes. That's why sorting explicitly using a `Comparator` / `Ordering` is attractive in this case. – Mick Mnemonic May 31 '15 at 00:56

score 0 · Answer 2 · answered May 30 '15 at 23:23

Use Collections.sort() and provide a custom Comparator to sort a map based on its values:

Collections.sort( map, new Comparator<Map.Entry<K, V>>()
{
    @Override
    public int compare( Map.Entry<K, V> entry1, Map.Entry<K, V> entry2)
    {
        return (entry1.getValue()).compareTo( entry2.getValue() );
    }
} );

score 0 · Answer 3 · answered May 31 '15 at 00:33

Can you rewrite your name and score as a class player, then you can use TreeSet to keep the order, and override equals() and compareTo(), it seems like you want to use name as identifier, and keep players ordered by score, then you can do

@Override
public boolean equals(Object obj) {
    if(obj instanceof Player)
        return this.name.equals(((Player)obj).name);
    return false;
}
@Override
public int compareTo(Player p) {
    return p.score - this.score;
}

It is not a good idea to not override `hashCode` if you override `equals`. — Tom, May 31 '15 at 07:50

Data-structure sorted by value

3 Answers3