Why is EnumMap not a SortedMap in Java?

Question

EnumMap<K extends Enum<K>, V> in Java is clearly ordered by definition of the associated enum, as you can also see in the javadoc:

Enum maps are maintained in the natural order of their keys (the order in which the enum constants are declared). This is reflected in the iterators returned by the collections views (keySet(), entrySet(), and values()).

What I need is a SortedMap using an enum as key type. I want to use methods like headMap() or firstKey(), but I want to profit from the added cpu+memory performance of EnumMaps. A TreeMap sounds like way too much overhead here.

Question: was this just missed in implementation, was it laziness (derived from AbstractMap) or is there a good reason why EnumMap is not a SortedMap?

Marietta

What about TreeSet? – Road

@MohammedDeifallah That is totally different, it has no keys... Did you mean TreeMap? – Standee

I was able to find this issue for openjdk. It is from 2005 yet still open/unresolved. I'd assume there isn't any "good reason" for this being not implemented. – Ritzy

Thanks for the really quick answers, I have added that I find TreeMap too much overhead here, plus O(log n) for queries. But my question of course also counts for EnumSet and SortedSet, same problem. – Marietta

@Amongalen: your answer qualifies as answer to my question, even though it does not answer the root cause, besides "Oracle does not fogging care". Not even google found the OpenJDK issue you mentioned, so at least it will help others with the same problem. – Marietta

Answer 1

This won't make an answer to your primary question (because only the original designers have the answer), but one approach I was considering was for you to implement it yourself. While trying to make a SortedMap implementation based on EnumMap, I came up with the following class.

This is surely a quick and dirty implementation (and note that it is not fully compliant with SortedMap - because the view requirements is not met), but if you need one, you can improve it:

class SortedEnumMap<K extends Enum<K>, V> 
    extends EnumMap<K, V> 
    implements SortedMap<K, V> {

    private Class<K> enumClass;
    private K[] values;

    public SortedEnumMap(Class<K> keyType) {
        super(keyType);
        this.values = keyType.getEnumConstants();
        this.enumClass = keyType;

        if (this.values.length == 0) {
            throw new IllegalArgumentException("Empty values");
        }
    }

    @Override
    public Comparator<? super K> comparator() {
        return Comparator.comparingInt(K::ordinal);
    }

    @Override
    public SortedMap<K, V> subMap(K fromKey, K toKey) {
        List<K> keys = Arrays.stream(this.values)
                .dropWhile(k -> k.ordinal() < fromKey.ordinal())
                .takeWhile(k -> k.ordinal() < toKey.ordinal())
                .collect(Collectors.toList());

        return this.forKeys(keys);
    }

    @Override
    public SortedMap<K, V> headMap(K toKey) {
        List<K> keys = new ArrayList<>();

        for (K k : this.values) {
            if (k.ordinal() < toKey.ordinal()) {
                keys.add(k);
            } else {
                break;
            }
        }

        return this.forKeys(keys);
    }

    @Override
    public SortedMap<K, V> tailMap(K fromKey) {
        List<K> keys = new ArrayList<>();

        for (K k : this.values) {
            if (k.ordinal() >= fromKey.ordinal()) {
                keys.add(k);
            }
        }

        return this.forKeys(keys);
    }

    //Returned map is NOT a "view" or the current one
    private SortedEnumMap<K, V> forKeys(List<K> keys) {
        SortedEnumMap<K, V> n = new SortedEnumMap<>(this.enumClass);
        keys.forEach(key -> n.put(key, super.get(key)));

        return n;
    }

    @Override
    public K firstKey() {
        return this.values[0];
    }

    @Override
    public K lastKey() {
        return this.values[this.values.length - 1];
    }
}

And for a quick test (bugs yet to be found):

SortedMap<Month, Integer> m = new SortedEnumMap(Month.class);

for (Month v : Month.values()) {
    m.put(v, v.getValue());
}

System.out.println("firstKey():       " + m.firstKey());
System.out.println("lastKey():        " + m.lastKey());
System.out.println("headMap/June:     " + m.headMap(Month.JUNE));
System.out.println("tailMap/June:     " + m.tailMap(Month.JUNE));
System.out.println("subMap/April-July " + m.subMap(Month.APRIL, Month.JULY));

I get:

firstKey():       JANUARY
lastKey():        DECEMBER
headMap/June:     {JANUARY=1, FEBRUARY=2, MARCH=3, APRIL=4, MAY=5}
tailMap/June:     {JUNE=6, JULY=7, AUGUST=8, SEPTEMBER=9, OCTOBER=10, NOVEMBER=11, DECEMBER=12}
subMap/April-July {APRIL=4, MAY=5, JUNE=6}

Intercolumniation

You comment that "returned map is NOT a "view" or the current one", but these methods (head/sub/tail-Map) MUST return views. – Lundell

I see that neither of your answers are really an answer to my primary question, but your answer will be at least very helpful to other people with this problem, so I will give you the credits for your efforts. Maybe someone at Oracle will read and pull it... – Marietta

@Lundell That's right, and I made explicit mention of it in the post – Intercolumniation

A sorted map that implements all those operations, intended to exploit the sorted nature, via linear searches… – Foredo

Answer 2

Open feature request

I was able to find this issue for OpenJDK. It is from 2005 yet still open/unresolved.

I'd assume there isn't any "good reason" for this being not implemented.

Ritzy

thank you for doing this. In the meantime I have seen ernest_k's answer which also does not answer my question actually, but brings up a nice solution for the problem underlying my question. I'm sorry I did not give you the credits as I mentioned first, but I think ernest_k deserves it for the work. – Marietta

@Marietta That is totally understandable. If I were you I would accept ernest_k's answer as well - it is way more helpful than mine. – Ritzy