CompareTo may return 0, alternative to TreeSet/TreeMap

Question

I need a sorted set of objects and am currently using the TreeSet. My problem is that the compareTo of the objects will often return 0, meaning the order of those two objects is to be left unchanged. TreeMap (used by TreeSet by default) will then regard them as the same object, which is not true.

What alternative to TreeMap can I use?

---

Use case: I have a set of displayable objects. I want to sort them by Y coordinate, so that they are rendered in the correct order. Of course, two objects may well have the same Y coordinate.

Answer 1

I have one idea of my own, but it's more of a workaround

int compare(Object a, Object b) {
   an = a.seq + (a.sortkey << 16); // allowing for 65k items in the set
   bn = b.seq + (a.sortKey << 16);
   return an - bn; // can never remember whether it's supposed to be this or b - a.
}

• sortKey = what really matters for the sorting, for example an Y coordinate
• seq = a sequence number assigned to objects when added to the set

Answer 2

You're defining one criteria to compare, but you need to add extra criteria.

You say:

I have a set of displayable objects. I want to sort them by Y coordinate, so that they are rendered in the correct order. Of course, two objects may well have the same Y coordinate.

So, If two elements have the same Y coordinate, what you you put first? What would be the other criteria?

It may be the creation time, it may be the x coordinate, you just have to define it:

Map<String,Thing> map = new TreeMap<String,Thing>(new Comparator<Thing>(){
     public int compare( Thing one, Thing two ) {
         int result = one.y - two.y;
         if( result == 0 ) { // same y coordinate use another criteria
             result = one.x - two.x;
             if( result == 0 ) { //still the same? Try another criteria ( maybe creation time
                 return one.creationTime - two.creationTime
             }
          }
          return result;
     }
});

You have to define when one Thing is higher / lower / equal / than other Thing . If one of the attributes is the same as other, probably you should not move them. If is there other attribute to compare the use it.

Answer 3

There are 2 important things to remember when using sorted sets (e.g. TreeSet) :

1) They are sets; two equal elements are not allowed in the same collection

2) Equality must be consistent with the comparison mechanism (either comparator or comparable)

Therefore, in your case you should "break ties" by adding some secondary ordering criteria. For example: first use Y axis, then X, and then some unique object identifier.

See also http://eyalsch.wordpress.com/2009/11/23/comparators/

Answer 4

The issue you're running into is that compareTo returning 0 means that the objects are equal. At the same time, you're putting them into a set, which does not allow multiple copies of equal elements.

Either re-write your compareTo so that unequal elements return different values, or use something like a java.util.PriorityQueue which allows multiple copies of equal elements.

Answer 5

I've done this before. It's an ordered multi-map and it is just a TreeMap of List objects. Like this..

Map<KeyType, List<ValueType>> mmap = new TreeMap<KeyType, List<ValueType>>();

You need to construct a new LinkedList every time a new key is introduced, so it might be helpful to wrap it in a custom container class. I'll try to find something.

---

So, I threw this custom container together quickly (completely untested), but it might be what you are looking for. Keep in mind that you should only use this type of container if you are truly looking for an ordered map of value lists. If there is some natural order to your values, you should use a TreeSet as others have suggested.

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class MTreeMap<K, V> {

   private final Map<K, List<V>> mmap = new TreeMap<K, List<V>>();
   private int size = 0;

   public MTreeMap() {
   }

   public void clear() {
      mmap.clear();
      size=0;
   }

   public boolean containsKey(K key) {
      return mmap.containsKey(key);
   }

   public List<V> get(K key) {
      return mmap.get(key);
   }

   public boolean isEmpty() {
      return mmap.isEmpty();
   }

   public Set<K> keySet() {
      return mmap.keySet();
   }

   public Collection<List<V>> valueLists() {
      return mmap.values();
   }

   public void put(K key, V value) {

      List<V> vlist = mmap.get(key);
      if (null==vlist) {
         vlist = new LinkedList<V>();
         mmap.put(key, vlist);
      }
      vlist.add(value);
      ++size;
   }

   public List<V> remove(Object key) {
      List<V> vlist = mmap.remove(key);

      if (null!=vlist) { 
         size = size - vlist.size() ;
      }
      return vlist;
   }

   public int size() {
      return size;
   }

   public String toString() {
      return mmap.toString();
   }

}

---

Here's a rudimentary test:

public class TestAnything {

   public static void main(String[] args) {

      MTreeMap<Integer, String> mmap  = new MTreeMap<Integer, String>();

      mmap.put(1, "Value1");
      mmap.put(2, "Value2");
      mmap.put(3, "Value3");
      mmap.put(1, "Value4");
      mmap.put(3, "Value5");
      mmap.put(2, "Value6");
      mmap.put(2, "Value7");

      System.out.println("size (1) = " + mmap.get(1).size());
      System.out.println("size (2) = " + mmap.get(2).size());
      System.out.println("size (3) = " + mmap.get(3).size());
      System.out.println("Total size = " + mmap.size());

      System.out.println(mmap);
   }

}

The output is this:

size (1) = 2
size (2) = 3
size (3) = 2
Total size = 7
{1=[Value1, Value4], 2=[Value2, Value6, Value7], 3=[Value3, Value5]}