Dlaczego EnumMap nie jest SortedMap w Javie?


9

EnumMap<K extends Enum<K>, V> w Javie jest wyraźnie uporządkowane według definicji powiązanego wyliczenia, co można również zobaczyć w javadoc:

Mapy wyliczeniowe są utrzymywane w naturalnej kolejności ich kluczy (w kolejności, w której deklarowane są stałe wyliczeniowe). Znajduje to odzwierciedlenie w iteratorów zwracanych przez poglądami kolekcje ( keySet(), entrySet(), i values()).

Potrzebuję SortedMapużycia wyliczenia jako klucza. Chcę używać metod takich jak headMap()lub firstKey(), ale chcę czerpać zyski z dodanej wydajności procesora i pamięci EnumMaps. To TreeMapbrzmi jak o wiele za dużo tutaj.

Pytanie : czy zostało to pominięte w realizacji, czy było to lenistwo (wywodzące się z AbstractMap), czy też jest dobry powód, dla którego tak EnumMapnie jest SortedMap?


Co z TreeSet?
Mohammed Deifallah

@MohammedDeifallah To jest zupełnie inne, nie ma kluczy ... Miałeś na myśli TreeMap?
deHaar

3
Znalazłem ten problem dla openjdk. Jest od 2005 roku, ale wciąż jest otwarty / nierozwiązany. Zakładam, że nie ma żadnego „dobrego powodu” dla tego, że nie został zaimplementowany.
Amongalen

1
Dzięki za naprawdę szybkie odpowiedzi, dodałem, że TreeMap znajduje się tutaj zbyt duży narzut plus O (log n) w przypadku zapytań. Ale moje pytanie oczywiście dotyczy także EnumSet i SortedSet, tego samego problemu.
rawcode

@Amongalen: twoja odpowiedź kwalifikuje się jako odpowiedź na moje pytanie, mimo że nie odpowiada na pierwotną przyczynę, poza tym, że „Oracle nie zapuszcza się”. Nawet Google nie znalazło wspomnianego przez ciebie problemu OpenJDK, więc przynajmniej pomoże innym z tym samym problemem.
rawcode

Odpowiedzi:


3

Nie da to odpowiedzi na twoje podstawowe pytanie (ponieważ odpowiedź mają tylko oryginalni projektanci), ale jednym z rozważanych przeze mnie rozwiązań było wdrożenie go samodzielnie. Próbując wykonać SortedMapimplementację opartą na EnumMap, wymyśliłem następującą klasę.

Jest to z pewnością szybka i brudna implementacja (i pamiętaj, że nie jest w pełni zgodna z SortedMap- ponieważ wymagania dotyczące widoku nie są spełnione), ale jeśli potrzebujesz , możesz ją poprawić:

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];
    }
}

I na szybki test (jeszcze nie znaleziono błędów):

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));

Dostaję:

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}

1
Komentujesz, że „zwrócona mapa NIE jest„ widokiem ”ani bieżącym”, ale te metody (mapa głowy / łodzi podwodnej / tylnej) MUSZĄ zwracać widoki.
assylias

1
Widzę, że żadna z twoich odpowiedzi nie jest tak naprawdę odpowiedzią na moje podstawowe pytanie, ale twoja odpowiedź będzie co najmniej bardzo pomocna dla innych osób z tym problemem, więc dam ci punkty za twoje wysiłki. Może ktoś w Oracle go przeczyta i wyciągnie ...
rawcode

@assylias Zgadza się i wyraźnie wspomniałem o tym w poście
ernest_k

Posortowana mapa, która realizuje wszystkie te operacje, mające na celu wykorzystanie posortowanej natury, poprzez wyszukiwanie liniowe…
Holger

3

Otwórz żądanie funkcji

Znalazłem ten problem dla OpenJDK . Jest od 2005 roku, ale wciąż jest otwarty / nierozwiązany.

Zakładam, że nie ma żadnego „dobrego powodu” dla tego, że nie został zaimplementowany.


dziękuję za zrobienie tego. W międzyczasie widziałem odpowiedź ernest_k, która również nie odpowiada na moje pytanie, ale stanowi dobre rozwiązanie problemu leżącego u podstaw mojego pytania. Przepraszam, że nie dałem ci kredytów, jak wspomniałem wcześniej, ale myślę, że ernest_k zasługuje na to za pracę.
rawcode

@rawcode To jest całkowicie zrozumiałe. Gdybym był tobą, zaakceptowałbym również odpowiedź ernest_k - jest to o wiele bardziej pomocne niż moje.
Amongalen
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.