Maintain SortedMap by value

Question

As we know that, SortedMap maintains the entries as sorted by keys. I read many threads in this forum and saw lots of example which sorts the SortedMap, by values. However, as you know when I put an item to default SortedMap it does not sort the Map again just put this new entry where it is supposed to be.

For example,

SortedMap<String,Person> sortedMap = new TreeMap();
Person p1 = new Person("John",38);
sortedMap.put(p1.getName(), p1);
Person p2 = new Person("Tom",34);
sortedMap.put(p2.getName(), p2); // does not sort, maintains sorted set by comparing the other values 
Person p3 = new Person("Susan",21);
sortedMap.put(p3.getName(), p3); // does not sort, maintains sorted set by comparing the other values

In many threads in this forum, I saw many many code that sorts the SortedMap by values by calling a sort method like:

sortedMap.sort(sortedMap.entries());

This or something else method is being called to get values as sorted.

But, I need to a Map implementation which keeps the values as sorted without a calling sort method as I explained in above. For example, in above code I just can call the firstKey() method; but instead I need to call a firstValue() method.

Person minimumAgePerson = sortedMap.firstValue().
System.out.println(minimumAgePerson.getName()); // it should print "Susan"

SortedSet is not appropriate for my requiremenets because I can put some new Objects ( Person ) whose key values already in the map, these just added entries should override the existing objects ( so I need a map ):

Person p4 = new Person("Susan",39);
sortedMap.put(p4.getName(),p4);
Person newMinimumAgePerson = sortedMap.firstValue(); 
System.out.println(newMinimumAgePerson.getName()); // it should print "Tom"

Is there an implementation to accomplish this taks or do I need to implement SortedSet myself?

Why would you need such a thing? I believe you have chosen the wrong data structure for your task, as I can imagine virtually no application of a Map sorted by values where some other structure cant be used (for example a sorted list or something). — bezmax, May 14 '13 at 14:38

Zerdligham · Answer 1 · 2013-05-14T15:07:32.887

3

I think the best way for you is to create a custom type containing both a Map (for the key association), and a SortedSet (in order to sort values)

It is not clear to me if you want to be able to have the same value for two different keys. In this case, you'd need to use some kind of SortedMultiSet.

edited May 14 '13 at 15:07

answered May 14 '13 at 14:39

Zerdligham

33
5

I'm currently wondering if it is a good idea to extend one of these two contained collections. I guess it depends on how you use it, but i'd be scared I may forget to override a method returning something wrong – Zerdligham May 14 '13 at 14:43

score 3 · Answer 2 · answered May 14 '13 at 14:54

Often, the simplest and safest way of dealing with this type of problem is to write a class that uses two different standard collections. The class can offer exactly the methods you need, not necessarily conforming to any of the java.util interfaces.

Given the stated requirements, I would use a SortedMap to contain the values, combined with a HashMap mapping keys to values. To prevent duplicate keys, put the key-value pair in the HashMap, checking the put result. If the key was already present, remove the old value from the SortedMap before adding the new value.

If you have additional requirements, this particular design may not cover everything, but the concept of combining java.util structures is a generally useful one.

score 1 · Answer 3 · answered May 14 '13 at 14:34

There is no implementation that contains a sort by both Key and Value. But really any implementation that did do this would need a separate datastructure for the sorting by value anyway, so you might as well create that datastructure yourself.

I would suggest either just implementing a sorted structure, using an existing one Like TreeMap or a PriorityQueue depending on your needs. Once that was done I would probably extend TreeMap with a custom structure and override the put,remove,addAll, etc methods to place it both in the super map, and also in your sort by keys structure.

Maintain SortedMap by value

3 Answers3

Linked