[Util] Sorting a Map by value (Integer) - Highest to lowest (vice versa)

Discussion in 'Resources' started by KingFaris11, Mar 17, 2014.

Thread Status:
Not open for further replies.
  1. SortedMap code: http://pastie.org/pastes/8938472/text?key=ahrpdo2n0v69z5xgvvgqog
    CustomisableEntry code: http://pastie.org/pastes/8938420/text?key=oxv5dyltyk9tcdtpovrga

    Hello, I have made these two fairly simple classes that allow you to sort a Map<K, Integer> (K being any key Object) from the either highest to lowest or lowest to highest as there is a parameter (boolean) that asks if you want it from lowest to highest.
    I added in an extra small feature that allows you to remove entries by the value. If you have more than one entry with the same value, it would remove all of them, which is pretty useful in my opinion!

    Note: I have not tested this code as a whole new class although I've tested it in a similar manner...

    Note: You must call map.resort() after you use map.put(K key, Integer value) but not when using putAll(). I did this because it increases performance if you're using map.put() in a for loop.

    Sorting kills example:
    Code:
    public SortedMap<String> playerKills = new SortedMap<String>(false);
     
    @Override
    public boolean onCommand(CommandSender sender, Command cmd, String label, String[] args) {
        if (cmd.getName().equals("topkills")) {
            sender.sendMessage(ChatColor.GOLD + "Top 8 players: ");
            List<Entry<String, Integer>> entryList = this.playerKills.entryList();        if (entryList.isEmpty()) {            sender.sendMessage(ChatColor.DARK_RED + "There are no players with kills.");        } else {
                for (int i = 0; i < entryList.size(); i++) {
                    if (i < 8) {
                        sender.sendMessage(entryList.get(i).getKey() + ": " + entryList.get(i).getValue());
                    } else {
                        break;
                    }
                }
            }
            return true;
        }
        return false;
    }
     
    public void addKills(Player player) {
        int playerKill = 0;
        if (this.playerKills.containsKey(player.getName()) playerKill = this.playerKills.get(player.getName());
        this.playerKills.put(player.getName(), playerKill + 1);
        this.playerKills.resort();
    }
    
     
    Garris0n likes this.
  2. Offline

    Comphenix

    You may want to take a look at TreeMap in the JDK. Then you don't have to explicitly call sort, as the entries are all stored in a sorted data structure (specifically a red-black tree).
     
    Garris0n likes this.
  3. TreeMap sorts them by key. After doing some research I found that there are no Maps that sort it by value.

     
  4. Offline

    LCastr0

    Code:
    Multiple markers at this line
        - Incorrect number of arguments for type SortedMap<K>; it cannot be parameterized with arguments <String,
        Integer>
        - Incorrect number of arguments for type SortedMap<K>; it cannot be parameterized with arguments <String,
        Integer>
     
  5. Sorry, ignore my previous comment if you read it. I made a mistake in the example, basically you only input the key Object as the value is ALWAYS an Integer and therefore not required. Look at the updated example (SortedMap<String>) in your case.
     
  6. Offline

    LCastr0

    Thank :)

    Oh, I need a little bit of help D:
    I'm making a plugin that shows a player's stats. When a player runs the command /stats, it'll show his wins, and his rank. His rank is based on a config file with all the players' wins.
    Example:
    config.yml
    Code:
    players:
    - playerOne
    - playerTwo
    - playerThree
    playerOne:
      wins: 5
    playerTwo:
      wins: 10
    playerThree:
      wins: 8
    If playerOne runs the command /stats, it'd show:
    Wins: 5
    Rank: 3 (because there's 2 players with more wins than him)

    And I'm trying to use the SortedMap, but how can I get the rank with it? Like, if it sorts the map with the rank, I'd get his name by his rank, but I want it to get his rank by his name.
    (Example: entryList.get(<the Integer from SortedMap here>).getValue(); is the right one, but I need one that works with entryList.get(<the name of the player that I added to the SortedMap>).getKey();)
    How can I do it?

    EDIT by Moderator: merged posts, please use the edit button instead of double posting.
     
    Last edited by a moderator: Jun 7, 2016
    KingFaris11 likes this.
  7. Offline

    Comphenix

    Ah, sorry - I completely missed you were sorting by value.

    Yeah, there's no such sorted map by value built-in (or bundled with Guava). But after reading your implementation, I'm not entirely convinced there should be either. The problem is that you have to remember to call resort() after insertion, which seems like a fairly ugly hack. Another downside, is that you perform a linear scan through a linked list on each insertion/retrieval, significantly affecting performance on larger data sets.

    I'd also recommend benchmarking the use of linked list here - in my experience, linked list traversal is usually slower than reallocating an equivalent list (as memory allocation is cheap on modern hardware - following pointers isn't).

    I think it would be better to use HashMap while constructing or updating the map, and simply sort it to a list when you're done. This probably fits in a static utility class (download):
    Code:java
    1. @SuppressWarnings("rawtypes")
    2. public class MapSorting {
    3. // Building block - extract key from entry
    4. private static final Function EXTRACT_KEY =
    5. new Function<Entry<Object, Object>, Object>() {
    6. public Object apply(Entry<Object, Object> input) {
    7. return input.getKey();
    8. }
    9. };
    10. // Same as above, only we extract the value
    11. private static final Function EXTRACT_VALUE =
    12. new Function<Entry<Object, Object>, Object>() {
    13. public Object apply(Entry<Object, Object> input) {
    14. return input.getValue();
    15. }
    16. };
    17.  
    18. /**
    19.   * Sort the given map by the value in each entry.
    20.   * @param map - map of comparable values.
    21.   * @return A new list with the sort result.
    22.   */
    23. public static <T, V extends Comparable<V>> List<Entry<T, V>> sortedValues(Map<T, V> map) {
    24. return sortedValues(map, Ordering.<V>natural());
    25. }
    26.  
    27. /**
    28.   * Sort the given map by the value in each entry.
    29.   * @param map - map of comparable values.
    30.   * @param valueComparator - object for comparing each values.
    31.   * @return A new list with the sort result.
    32.   */
    33. public static <T, V> List<Entry<T, V>> sortedValues(Map<T, V> map, Comparator<V> valueComparator) {
    34. return Ordering.from(valueComparator).onResultOf(MapSorting.<T, V>extractValue()).sortedCopy(map.entrySet());
    35. }
    36.  
    37. /**
    38.   * Retrieve every key in the entry list in order.
    39.   * @param entryList - the entry list.
    40.   * @return Every key in order.
    41.   */
    42. public static <T, V> Iterable<T> keys(List<Entry<T, V>> entryList) {
    43. return Iterables.transform(entryList, MapSorting.<T, V>extractKey());
    44. }
    45.  
    46. /**
    47.   * Retrieve every value in the entry list in order.
    48.   * @param entryList - the entry list.
    49.   * @return Every value in order.
    50.   */
    51. public static <T, V> Iterable<V> values(List<Entry<T, V>> entryList) {
    52. return Iterables.transform(entryList, MapSorting.<T, V>extractValue());
    53. }
    54.  
    55. @SuppressWarnings("unchecked")
    56. private static <T, V> Function<Entry<T, V>, T> extractKey() {
    57. return EXTRACT_KEY;
    58. }
    59.  
    60. @SuppressWarnings("unchecked")
    61. private static <T, V> Function<Entry<T, V>, V> extractValue() {
    62. return EXTRACT_VALUE;
    63. }
    64. }

    Using it is about as easy:
    Code:java
    1. Map<String, Integer> test = Maps.newHashMap();
    2. test.put("aadnk", 2);
    3. test.put("Notch", 10);
    4. test.put("Dinnerbone", -10);
    5. test.put("Null", 0);
    6.  
    7. for (Entry<String, Integer> entry : MapSorting.sortedValues(test)) {
    8. System.out.println(entry);
    9. }

    Then Guava make it easy to reverse the order of the elements (and control the location of NULLs):
    Code:java
    1. for (Entry<String, Integer> entry :
    2. MapSorting.sortedValues(test, Ordering.<Integer>natural())) {
    3. System.out.println(entry);
    4. }


    The rank here is just the index of the player when sorted by wins, so use that:
    Code:java
    1. Map<String, Integer> test = Maps.newHashMap();
    2. test.put("playerOne", 5);
    3. test.put("playerTwo", 10);
    4. test.put("playerThree", 8);
    5.  
    6. List<Entry<String, Integer>> sorted = MapSorting.sortedValues(test);
    7. List<String> ranked = Lists.newArrayList(MapSorting.keys(sorted));
    8.  
    9. // Get by rank
    10. System.out.println("First place: " + ranked.get(0));
    11. System.out.println("Rank of player: " + (ranked.indexOf("playerTwo") + 1));

    KingFaris11's version is very similar - just use Lists.newArrayList(sortedMap.keySet()) instead. Remember to call resorted() if you use put().

    EDIT by Moderator: merged posts, please use the edit button instead of double posting.
     
    Last edited by a moderator: Jun 7, 2016
  8. Offline

    LCastr0

    Ok I'll try both ways.
    In your way, I cannot import MapSorting :(
    I should read the full thread... :p
     
  9. Offline

    Comphenix

    Incidentally, I'm loving Java 8:
    Code:java
    1. package com.comphenix.test;
    2.  
    3. import java.util.*;
    4. import java.util.Map.Entry;
    5. import java.util.stream.Collectors;
    6.  
    7. public class MapSorting {
    8. /**
    9.   * Sort the given map by the value in each entry.
    10.   * @param map - map of comparable values.
    11.   * @return A new list with the sort result.
    12.   */
    13. public static <T, V extends Comparable<V>> List<Entry<T, V>> sortedValues(Map<T, V> map) {
    14. return sortedValues(map, Comparator.<V>naturalOrder());
    15. }
    16.  
    17. /**
    18.   * Sort the given map by the value in each entry.
    19.   * @param map - map of comparable values.
    20.   * @param valueComparator - object for comparing each values.
    21.   * @return A new list with the sort result.
    22.   */
    23. public static <T, V> List<Entry<T, V>> sortedValues(Map<T, V> map, Comparator<V> valueComparator) {
    24. return map.entrySet().stream().
    25. sorted(Comparator.comparing(Entry::getValue, valueComparator)).
    26. collect(Collectors.toList());
    27. }
    28.  
    29. /**
    30.   * Retrieve every key in the entry list in order.
    31.   * @param entryList - the entry list.
    32.   * @return Every key in order.
    33.   */
    34. public static <T, V> List<T> keys(List<Entry<T, V>> entryList) {
    35. return entryList.stream().map(Entry::getKey).collect(Collectors.toList());
    36. }
    37.  
    38. /**
    39.   * Retrieve every value in the entry list in order.
    40.   * @param entryList - the entry list.
    41.   * @return Every value in order.
    42.   */
    43. public static <T, V> List<V> values(List<Entry<T, V>> entryList) {
    44. return entryList.stream().map(Entry::getValue).collect(Collectors.toList());
    45. }
    46. }

    But it's going to take a long time before enough servers upgrade and it can be used for general plugin development.
     
  10. Stop using big words :/ I'll re-read through your messages and actually understand what you mean once I've finished playing. =P Comphenix

    Aha :p Yeah, I want to explore Java 8 but I really don't know where to start. Oh, and about your other class, I don't like relying on others except the plugin APIs really.. :p

    EDIT by Moderator: merged posts, please use the edit button instead of double posting.
     
    Last edited by a moderator: Jun 7, 2016
  11. Offline

    LCastr0

    #I'mSoIdiot.
    Sorry, I've made a little mistake D:
    If you've read my question, please, don't answer :p
     
    KingFaris11 likes this.
Thread Status:
Not open for further replies.

Share This Page