CODEWITHSUNDEEP
javacollections
JavaGeek
JavaGeek

Reputation: 1539

Sorting problem using TreeMap

I'm trying to put some key values in HashMap and then trying to sort out using TreeMap as below. Problem is that if there were similar values in map, then after sorting it is considering any one of them.

   import java.util.*;

public class HashmapExample {

            public static void main(String[] args) {

            HashMap<String,Integer> map = new HashMap<String,Integer>();
            ValueComparator bvc =  new ValueComparator(map);
            TreeMap<String,Integer> sorted_map = new TreeMap(bvc);

            map.put("A",99);
            map.put("B",67);
            map.put("C",123);
            map.put("G",67);
            map.put("F",67);
            map.put("H",67);
            map.put("D",6);

            System.out.println("unsorted map");
            for (String key : map.keySet()) {
                System.out.println("key/value: " + key + "/"+map.get(key));
            }

            sorted_map.putAll(map);

            System.out.println("results after sorting");
            for (String key : sorted_map.keySet()) {
                System.out.println("key/value: " + key + "/"+sorted_map.get(key));
            }
        }

    }

    class ValueComparator implements Comparator {

      Map base;
      public ValueComparator(Map base) {
          this.base = base;
      }

      public int compare(Object a,Object b) {

        if((Integer)base.get(a) > (Integer)base.get(b)) {
          return 1;
        } else if((Integer)base.get(a) == (Integer)base.get(b)) {
          return 0;
        } else {
          return -1;
        }
      }
    }

After this the output is like below

unsorted map
key/value: D/6
key/value: A/99
key/value: F/67
key/value: H/67
key/value: C/123
key/value: B/67
key/value: G/67
results after sorting
key/value: D/6
key/value: F/67
key/value: A/99
key/value: C/123

For B,G,F and H keys i gave value as 67. After sorting map, it is displaying only F value and eleminating B,G and H values. I want to display outputsomething like below

    key/value: D/6
    key/value: B/67
    key/value: G/67
    key/value: F/67
    key/value: H/67
    key/value: A/99
    key/value: C/123

Upvotes: 3

Views: 3005

Answers (6)

Anping
Anping

Reputation: 1

Based on Jeff's answer, I wrote a generic version:

public class MapValueComparator<K extends Comparable<K>, V extends Comparable<V>> implements Comparator<K> {
    private final Map<K, V> base;
    private final boolean ascending;

    public MapValueComparator(Map<K, V> base) {
        this.base = base;
        this.ascending = true;
    }

    public MapValueComparator(Map<K, V> base, boolean ascending) {
        this.base = base;
        this.ascending = ascending;
    }

    @Override
    public int compare(K a, K b) {
        int r = base.get(a).compareTo(base.get(b));
        if (r == 0)
            r = a.compareTo(b);

        if (ascending)
            return r;
        else
            return -r;
    }
}

It could be used as follows:

Map<String,Integer> map = new HashMap<String,Integer>();
// add some contents to map ...

MapValueComparator<String, Integer> mvc = new MapValueComparator<String, Integer>(map);
TreeMap<String, Integer> sorted_map = new TreeMap<String, Integer>(mvc);
sorted_map.putAll(map);

Upvotes: 0

AmaDaden
AmaDaden

Reputation: 1204

As everyone has said your compare code is broken. Replace it with this. This will not consider two pairs with the same value, but different keys, equal.

  public int compare(Object a,Object b) {

    if((Integer)base.get(a) > (Integer)base.get(b)) {
      return 1;
    } else if((Integer)base.get(a) == (Integer)base.get(b)) {
      return ((String)a).compareTo((String)b);
    } else {
      return -1;
    }

  }

Upvotes: 1

Stan Kurilin
Stan Kurilin

Reputation: 15812

Do not use TreeSet for this purpose or make smt like

class ValueComparator implements Comparator<String> {
    private final Map<String, Integer> base;

    public ValueComparator(Map<String, Integer> base) {
        this.base = base;
    }

    public int compare(String a, String b) {
        int compareInts = base.get(a).compareTo(base.get(b));
        if (compareInts == 0) {
            return a.compareTo(b);
        } else {
            return compareInts;
        }
    }
}

Upvotes: 2

Jeff Storey
Jeff Storey

Reputation: 57222

The reason keys B,G and H are being eliminated is because the comparator you provided compares based only on the values. Since they all have the same values, they are all equal keys, which means one will overwrite the others.

To print out what you want, your comparator would need to first compare the values, and then if they are equal, compare the keys.

int compare(Comparable key1, Comparable key2) {
   // I'm guessing you are doing something like:
   // return map.get(key1).compareTo(map.get(key2));

    // you can change it to something like
    int result = key1.compareTo(key2);
    if ( result == 0 ) {
      result= key1.compareTo(key2) 
    }

    return result;

}

Upvotes: 4

cheekoo
cheekoo

Reputation: 877

Your comparator has problem. e.g. compare method returns 0 for G and F. Hence the treemap doesnt have key-value pair associated with one of them.

You need to work on comparator.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533880

A TreeSet removes duplicates ie when compareTo() == 0.

I suggest you have the comparator compare the keys when the values are the same and you should get.

key/value: D/6
key/value: B/67
key/value: F/67
key/value: G/67
key/value: H/67
key/value: A/99
key/value: C/123

Upvotes: 1

Related Questions