Sorting custom data structure on Key in TreeMap

Question

I am trying to sort a TreeMap on key. Key is some custom DataStructure having int, List, String, etc. The member on which I am expecting a sort has some duplicates. Let's say that member is Rank. More than 1 object can have same rank.

Simplified version example:

NOTE: in the CompareTo method below 0 is not returned intentionally to NOT ignore duplicates.(Please correct me if this is not the right way to avoid duplicates)

import java.util.TreeMap;


public class TreeTest {

public static void main(String[] args) {
    TreeMap<Custom,String> t = new TreeMap<Custom,String>();
    Custom c1 = new Custom();
    c1.setName("a");
    c1.setRank(0);

    Custom c2 = new Custom();
    c2.setName("b");
    c2.setRank(1);

    Custom c3 = new Custom();
    c3.setName("c");
    c3.setRank(0);

    t.put(c1, "first");
    t.put(c2, "Second");
    t.put(c3, "Third");

    System.out.println(t.keySet());

    for(Custom c:t.keySet()){
        System.out.println(t.get(c));
    }
  }
}

And Custom Object

package com.example.ui;

 public class Custom implements Comparable<Custom>{

int rank;
String name;

public int getRank() {
    return rank;
}

public void setRank(int rank) {
    this.rank = rank;
}

public String getName() {
    return name;
}

public void setName(String name) {
    this.name = name;
}



@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((name == null) ? 0 : name.hashCode());
    result = prime * result + rank;
    return result;
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Custom other = (Custom) obj;
    if (name == null) {
        if (other.name != null)
            return false;
    } else if (!name.equals(other.name))
        return false;
    if (rank != other.rank)
        return false;
    return true;
}

    // 0 is not returned intentionally to NOT ignore duplicates.
 public int compareTo(Custom o) {
    if(o.rank>this.rank)
        return 1;
    if(o.rank==this.rank)
        return -1;
    return -1;
 }
 }

Output::

[com.example.ui.Custom@fa0, com.example.ui.Custom@fbe, com.example.ui.Custom@f80]
null
null
null

Expected: First, Second, Third based on Rank 0,1,0 respectively.

I looked at couple of examples on Google. Most of them were basic usage on TreeMap sort using keys or values with primitive datatypes, but none with duplicates when sorting member is a part of custom key DataStructure.

Please help?

Answer 1

The problem is that your implementation of compareTo is not consistent with equals, which is required by TreeMap. From the API docs:

Note that the ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with equals if this sorted map is to correctly implement the Map interface.

One possible consistent implementation would be to first compare by rank and then by name if the rank values are equal. For two instances of Custom with equal ranks and identical names you should not expect to be able to store them both as keys within the same Map - This violates the contract of Map.

public int compareTo(Custom o) {
  int ret = this.rank - o.rank;

  // Equal rank so fall back to comparing by name.
  if (ret == 0) {
    ret = this.name.compareTo(o.name);
  }

  return ret;
}

Answer 2

As mentioned, your implementation of equals and compareTo are not consistent with each other. If I read your question correctly, what you require is to preserve duplicates that have the same key. I'd recommend you to look into the TreeMultimap of the Google Guava collections. It creates set containers for each value object sothat different values having the same key are preserved. e.g.

treeMultimap.put ("rank1", "Joe");
treeMultimap.put ("rank1", Jane");
treeMultimap.get ("rank1"); // Set("Joe","Jane");

The constrain in this data structure is that K,V pairs must be unique. That is, you can't insert ("rank1", "Joe") twice in the Multimap.

One important note: The reason why you see so many examples of Map, using simple types and, in particular, strings, is that keys in a map must be immutable. The equals and hashcode values of an object must not change in the time it's used as a key in a map. Translated to your example, you cannot do customObject.setRank(...) and updates a rank value when it's used as a key. To do so, you first need to remove the key and its values, update it and then insert it again.

Answer 3

You can also do it by implementing Comparator as anonymous inner type and override compare() to return desired comparison.

public class TreeMaps 
{
    public static void main(String[] args) 
    {
    Custom c1 = new Custom(1,"A");
    Custom c2 = new Custom(3,"C");
    Custom c3 = new Custom(2,"B");

    TreeMap<Custom , Integer > tree = new TreeMap<Custom, Integer>  (new Comparator<Custom>() {

                                            @Override
                                            public int compare(Custom o1, Custom o2) {

                                                return o1.rank - o2.rank;
                                            }
                                        });
    tree.put(c1, 1);
    tree.put(c2, 2);
    tree.put(c3, 3);

    System.out.println(tree);
}
}

class Custom
{
int rank ; 
String name  ; 
public Custom(int rank , String name) {
    this.rank = rank ;
    this.name = name ;

}

@Override
public String toString()
{
    return "Custom[" + this.rank + "-" + this.name + "]" ;
}
}