1

Situation:

I have a Map, a TreeMap to be more exact that looks like

TreeMap<String, Integer>

I have to be able to sort it on either the key OR the value in an ascending OR descending way. The result must be a Map like

Map<String, Integer>

Not an ArrayList or anything like that because the rest (read: allot) of my code won't work anymore. I've searched but couldn't find anything that suits my needs. Is this even possible? Double values may not be lost.

Bhesh Gurung
  • 50,430
  • 22
  • 93
  • 142
Wouter
  • 430
  • 2
  • 5
  • 13
  • You could write your own implementation of Map that allows you to order by value. As far as I know, such a thing does not exist. Your custom implementation could keep an index of the items in the tree sorted by value to allow for quick retrieval. – jgitter May 12 '14 at 14:34
  • – Raghu May 12 '14 at 14:41
  • What do you mean by - *Double values may not be lost.*? Do you mean duplicate values? And the other point that's not clear is that if all of your code is written against the `Map` or the `TreeMap`. – Bhesh Gurung May 12 '14 at 14:48

5 Answers5

3

If you use two BiMaps which each back each other, then you effectively have one map. Somthing like:

import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;

private BiMap<Integer, String> localid = HashBiMap.create();
private BiMap<String, Integer> inverse = localid.inverse();

you can treat each reference, localid & inverse, as their own map, but changes to one are reflected in the other. The only slight downside is that now both the keys and values must be unique, as the values of one are the keys of the other. For most cases this is not a problem.

For sorting it, you can at any time make a local copy which is a treeMap, and that imposes an ordering. E.g. 

ImmutableMap.copyOf(Maps.newTreeMap(bimap))

Now if you are never making changes to your map, this will provide a sorted view, and you can do it by either.

EDIT: A TreebasedTable has two keys for each value, and you can sort either keyset with a comparator. I am not sure that this is exactly what you need, here as the keysets are independent, but you might be able to refactor your code slightly to make this a viable solution.

phil_20686
  • 4,000
  • 21
  • 38
  • +1 for `TreeBasedTable`. Then you can have a `Table` or whatever and get free sorting on row or column. – Russell Zahniser May 12 '14 at 14:58
  • Yes, but can I get from a given string to a given integer efficiently? I am not sure, but am somewhat unfamiliar with it, compared to the BiMap which I use a lot. – phil_20686 May 12 '14 at 15:00
  • Hmm, now that I look more closely, I see that there's no way to get a sorted view by column, just by row. – Russell Zahniser May 12 '14 at 15:01
  • getRowMap and getColumnMap both return sorted maps, but they are not quite the answer to the problem. A TreeBasedTable acts like a matrix where a value is identified by two keys. Thus, getRowMap returns all the entries with a given row value independently of its column value, and is a sorted map, by column value. But that is not quite what the OP asked for - but it could be made to work, by having an object All, so the rowMap(All) gets all the values sorted by the column set. Just doesn't feel right somehow. – phil_20686 May 12 '14 at 15:05
1

If the map is small and iterating over it is an infrequent operation, one solution would be to just use a HashMap (for lookup speed) and then sort the entries every time you iterate.

Another solution, if you do these iterations frequently compared to direct map lookups, and if the values (and not just the keys) are unique, would be to maintain two sorted maps, one <String, Integer> and one <Integer, String>.

Russell Zahniser
  • 16,188
  • 39
  • 30
  • One key thing to understand here is that using a `TreeMap` means that the map is *stored* in sorted order, but any map can be *iterated* in sorted order (just copy the entries into a list and sort them before iterating). – Russell Zahniser May 12 '14 at 14:55
0

Guava has the concept of BiMap. Is that what you're looking for?

Ray
  • 3,084
  • 2
  • 19
  • 27
0

A TreeMap's keys are sorted by it's comparable.

GeekyDaddy
  • 384
  • 2
  • 12
0

Try a SortedMap

A Map that further provides a total ordering on its keys. The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time. This order is reflected when iterating over the sorted map's collection views (returned by the entrySet, keySet and values methods). Several additional operations are provided to take advantage of the ordering. (This interface is the map analogue of SortedSet.)

GeekyDaddy
  • 384
  • 2
  • 12
  • He's already using a `SortedMap`. A `TreeMap` *is a* `SortedMap`. He needs to be able to sort it on the values as well, which a `SortedMap` doesn't do. – David Conrad May 12 '14 at 14:54