CODEWITHSUNDEEP
java
Rose Perrone
Rose Perrone

Reputation: 63546

TreeMap<Integer, Integer> remove not working

I'm trying to get the top 10 elements of a TreeMap by executing this loop:

        TreeMap<Integer, Integer> sortedMap = sortMap(m);
        String outString = "";
        int count = 10;
        while (count > 0) {
            count--;
            Integer k = sortedMap.firstKey();
            outString += String.valueOf(k);
            sortedMap.remove(k);
            if (count != 0) {
                outString += ",";
            }
        }

        System.out.println("outVal is " + outVal);

This prints outVal is 11377,11377,11377,11377,11377,11377,11377,11377,11377,11377 Integer implements Comparable, so why might remove not be working?

UPDATE Here's my sortMap implementation:

        public static TreeMap<Integer, Integer> sortMap(HashMap<Integer, Integer> map) {
           ValueComparator bvc =  new ValueComparator(map);
           TreeMap<Integer,Integer> sorted_map = new TreeMap<Integer,Integer>(bvc);
           sorted_map.putAll(map);
           return sorted_map;
        }

class ValueComparator implements Comparator<Integer> {
    java.util.Map<Integer, Integer> base;
    public ValueComparator(java.util.Map<Integer, Integer> base) {
        this.base = base;
    }

    // Note: this comparator imposes orderings that are inconsistent with equals.    
    public int compare(Integer a, Integer b) {
        if (base.get(a) >= base.get(b)) {
            return -1;
        } else {
            return 1;
        } // returning 0 would merge keys
    }
}

UPDATE This was helpful: Java Map sort by value.

Upvotes: 2

Views: 1289

Answers (3)

Marko Topolnik
Marko Topolnik

Reputation: 200168

After your edit it is clear that your custom comparator is the culprit. What you actually want to achieve is collecting the keys of the ten highest values in the map.

But, your approach is needlessly roundabout, if I may say. You already have some map m, which is your starting point. So what you need is just collect its entrySet, sort it by value, and take the first ten elements:

import java.util.Map.Entry;

final List<Entry<Integer,Integer>> list = new ArrayList<>(m.entrySet());
Collections.sort(list, new Comparator<Entry<Integer, Integer>>() {
  @Override public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {
    return o1.getValue().compareTo(o2.getValue());
  }});
final StringBuilder b = new StringBuilder();
String delimiter = "";
for (Entry<Integer, Integer> e : list.subList(0, 10)) {
  b.append(delimiter).append(e.getKey());
  delimiter = ",";
}
System.out.println(b);

Note that a one-shot sort is more efficient than inserting elements one by one into a binary search tree.

I am also using StringBuilder, which is again more efficient than recreating a full String in each step.

Upvotes: 4

Ian Roberts
Ian Roberts

Reputation: 122364

public int compare(Integer a, Integer b) {
    if (base.get(a) >= base.get(b)) {
        return -1;
    } else {
        return 1;
    } // returning 0 would merge keys
}

This comparator is flawed as (quite apart from it being inconsistent with equals) it does not satisfy the comparator contract which states that compare(a,b) > 0 implies compare(b,a) < 0 and vice versa. And since TreeMap relies on the comparator returning 0 to find the key you're trying to remove() it will never be able to remove anything - no matter what key you try and search for the map will never think that the key is present.

Upvotes: 6

Muhammad
Muhammad

Reputation: 7324

i tried like following it worked for me

    TreeMap<Integer, Integer> sortedMap = new TreeMap<>();
    String outString = "";
    sortedMap.put(1, 10);
    sortedMap.put(2, 20);
    sortedMap.put(3, 30);
    sortedMap.put(4, 40);
    sortedMap.put(5, 50);
    int count = 5;
    while (count > 0) {
        count--;
        Integer k = sortedMap.firstKey();
        outString += sortedMap.get(k);//String.valueOf(k);
        sortedMap.remove(k);
        if (count != 0) {
            outString += ",";
        }
    }

    System.out.println("outVal is " + outString);
    System.out.println(sortedMap.size());

Upvotes: 0

Related Questions