java-8 Stream of Map.entry to SortedMap with a custom comparator

Question

This method takes a Map with all values equal to null and returns a SortedMap of the same keys, with new values (obtained via objectiveFitness)

Step 1. First, I take the keys from the input Map and construct a new HashMap with the same keys, new values are objectiveFitness(key).

public SortedMap<Integer[], Integer> evaluate(Map<Integer[], Integer> population, Integer[] melody, Integer[] mode) { 

    Map<Integer[], Integer> fitPop = new HashMap<>();
    fitPop = population.keySet() //you just have the keys.
            .stream()
            .collect(Collectors.toMap(p -> p, p -> this.objectiveFitness(p)));

Step 2. The next step is to use a Stream to collect all of the entries from the HashMap into a SortedMap with a custom Comparator.

After reading this from the Oracle website: http://docs.oracle.com/javase/tutorial/collections/interfaces/order.html

...I found since I want to maintain sortedness of the SortedMap based on something other than the natural ordering of the entries, i need to implement a Comparator with 2 parts. I'll be sorting based on fitness value, using the key to compare for uniqueness. *Also, I want the case for where 2 values can be similar, but I don't want to

One part is to do with sorting and returns (1,0, or -1) depending on the values. The other part of the Comparator has to do with uniqueness (since Maps don't allow duplicates. Here's my best shot so far, but I'm struggling.

    Comparator<Map.Entry<Integer[], Integer>> fitnessOrder = 
                                new Comparator<Map.Entry<Integer[], Integer>>() {
            public int compare(Map.Entry<Integer[], Integer> m1, Map.Entry<Integer[], Integer> m2) {
            int fitCmp = m2.getValue().compareTo(m1.getValue());
            if (fitCmp != 0)
                return fitCmp;


            if(m1.getKey().equals(m2.getKey())) return 0;
                for(int i = 0; i < m1.getKey().length; i++){
                    if(m1.getKey()[i] > m2.getKey()[i]){
                        return 1;
                    }
                    if(m1.getKey()[i] < m2.getKey()[i]){
                        return -1;
                }
            }
            return 0;
            }
            };

Does that look like it is consistent with equals? I can't really tell how to implement it.

If it is correct, I want to use the Comparator above to help me collect into a TreeMap using lambdas, however I'm just getting stuck over and over.

I also looked at: Java TreeMap Comparator and I see the comments about ordering of a SortedMap based on the keys because it uses a NavigableMap and therefor sorts on keys, else by a comparator. Is there really no good way to do this without using a SortedSet?

    SortedMap<Integer[], Integer> sortedFitPop = fitPop.entrySet()
            .stream()
          //now I want to insert entries into the TreeMap
          //with sortedness according to the Comparator above
            .collect(Collectors.toCollection((k,v) -> (k,v), new TreeMap(fitnessOrder)
   ));

the keys should still be the keys, the values should still be what they were in the HashMap, but now when collecting, I want the TreeMap should always be sorted from the beginning and after every entry is put.

& yes, of course it would be even better not to collect into a HashMap to start, and I feel like there is a way to do so using Java-8/streams/lambdas to do it cleanly.

Thank you in advance! I want to know this stuff so hard!

Ideally, I would like to return a SortedMap where the Map has a Comparator, sorting based on the Integer value, rather than the Integer[] key. — Adam, Aug 24 '16 at 11:29
First look [HERE](http://stackoverflow.com/questions/1448369/how-to-sort-a-treemap-based-on-its-values). You cannot sort your `Map` by values using `TreeMap` because it is sorted by keys. You should sort your entries and put it in a `LinkedHashMap` which remembers the order of insertion. — Flown, Aug 24 '16 at 12:01

score 2 · Accepted Answer · edited May 23 '17 at 12:01

As already said by Flown, it is impossible to create a TreeMap sorted by values. Think about it. How should a map implement a lookup, when it needs the result of that lookup to determine its place within the map? That would only work if all map operations degrade to linear searches through the whole map or worse.

The other issue has already been mentioned by yourself: consistency with equals. A comparator using the value of a map can’t be consistent with equals of the keys, but even a comparator dedicated to the Integer[] keys can’t be consistent with equals as Java arrays don’t have an equals method. This also strikes you when using, e.g. a LinkedHashMap and sort by value before insertion. In that case, a lookup will only work with the identical array object instance rather than an equivalent sequence of elements, as arrays have no appropriate hashCode or equals implementation.

This is the point to consider that you shouldn’t use Integer[] arrays anyway. You might have been confused by the fact the Generics don’t support primitive types, but an array of a primitive type is not a primitive type. So there’s no reason not to use int[] here.

When using int[] arrays, you can use IntBuffer to wrap them, getting a type which implements Comparable, hashCode and equals consistently based on the int[]’s contents. Then, you can create a LinkedHashMap from a sorted stream. It will reflect the encounter order of the stream’s elements, which will be the desired ordering, as long as you don’t modify the map later-on.

// convert int[] arrays to IntBuffer via IntBuffer.wrap first
public Map<IntBuffer, Integer> evaluate(Map<IntBuffer, Integer> population, …) {
  Map<IntBuffer, Integer> fitPop = population.keySet().stream()
    .map(ia -> new AbstractMap.SimpleImmutableEntry<>(ia, objectiveFitness(ia.array())))
    .sorted(Map.Entry.<IntBuffer,Integer>comparingByValue()
            .thenComparing(Map.Entry.comparingByKey()))
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
            (a,b)->{ throw new IllegalStateException(); }, LinkedHashMap::new));
  return fitPop;
}

Seeing this, you might think about whether a map from integer array to integer really is an appropriate representation of a population. When you create a dedicated type for a population member holding the identity criteria and current fitness, you can get rid of all these obstacles. A simple list or array of these population members would be sufficient to represent a population. Recalculating the fitness would be a simple forEach operation and sorting a list or array according to a fitness property is easy as well (you don’t need to think about the ordering of elements with the same fitness then, as there’s no problem having elements with the same fitness in an array or list).

Holger, thanks for the detailed explanation (and for reminding me to use int[]). — Adam, Aug 24 '16 at 15:17
My initial decision was to make a class which had fields Integer[] notes, and int fitness. For some background: this is the abstract method implementing a functional interface which is a subcomponent of a genetic algorithm I'm writing. The algorithm uses implementations of 6 different functional interfaces, where collections are passed around the entire time. The objectiveFitness is by far the most computationally intensive task, so computing it once is ideal. However, I take your point and I think as I extend the algorithm — Adam, Aug 24 '16 at 15:23
continued... as I extend to include more fitness criterion and perhaps add another layer of representation, it may be useful to have a class to deal with rather than as I've done. — Adam, Aug 24 '16 at 15:27
Having a fitness function represented via a functional interface doesn’t prevent having an ordinary class holding a parameter set and last result of the function evaluation. You don’t need to put everything into functional interfaces, only the things you want to abstract. This can be combined with delegation. — Holger, Aug 24 '16 at 15:43
could it be fair to say the one abstraction being passed is an int[](notes which will be evaluated by objectiveFitness)... in the main algorithm class, I could collect the Map produced by this method into one of many fields of another class? So rather than using those objects within the algorithm (carrying around extra memory costs), I can implement int[] instead (for this aspect of an individual), as you suggested, and only set a field at the main algorithm level. (for example, another int[] could represent rhythm, whereas the first represents pitch).. am I understanding you? thanks — Adam, Aug 24 '16 at 15:49
It seems, you have an idea, but it’s not easy to describe within a single comment, but that’s not necessary anyway. Try to implement your idea and only if you encounter a problem, you may open a new question, then with code examples… — Holger, Aug 25 '16 at 08:50
Thanks @Holger, you've given me some great stuff to think about! I appreciate it. — Adam, Aug 25 '16 at 12:46

java-8 Stream of Map.entry to SortedMap with a custom comparator

1 Answers1