JEP 431: Sequenced Collections

Аннотация

Мы вводим новые интерфейсы для коллекций с определённым порядком обхода (encounter order). У каждой такой коллекции есть чётко определённые первый элемент, второй элемент и так далее, вплоть до последнего элемента. Кроме того, такая коллекция предоставляет единообразные API для доступа к первому и последнему элементам и для обработки элементов в обратном порядке.

«Жизнь можно понять, только оглядываясь назад, но прожить её можно, только глядя вперёд».
— Kierkegaard

Мотивация

В фреймворке коллекций Java нет типа коллекции, который представлял бы последовательность элементов с определённым порядком обхода. В нём также нет единообразного набора операций, применимых ко всем таким коллекциям. Эти пробелы постоянно вызывали проблемы и жалобы.

Например, и List, и Deque определяют порядок обхода, но их общий супертип Collection его не определяет. Аналогично, Set не определяет порядок обхода, и такие подтипы, как HashSet, тоже его не определяют, а такие подтипы, как SortedSet и LinkedHashSet, определяют. Таким образом, поддержка порядка обхода разбросана по иерархии типов, и некоторые полезные понятия трудно выразить в API. Ни Collection, ни List не могут описать параметр или возвращаемое значение, у которого есть порядок обхода. Collection слишком общий: такие ограничения остаются только в текстовой спецификации, что может приводить к ошибкам, которые трудно отладить. List слишком конкретный: он исключает SortedSet и LinkedHashSet.

С этим связана и другая проблема: коллекции-представления часто вынуждены переходить к более слабой семантике. Если обернуть LinkedHashSet с помощью Collections::unmodifiableSet, получится Set, и информация о порядке обхода теряется.

Без интерфейсов, которые определяли бы операции, связанные с порядком обхода, эти операции либо несогласованы, либо отсутствуют. Многие реализации позволяют получить первый или последний элемент, но каждая коллекция делает это по-своему, а в некоторых случаях способ неочевиден или его нет вовсе:

	Первый элемент	Последний элемент
List	list.get(0)	list.get(list.size() - 1)
Deque	deque.getFirst()	deque.getLast()
SortedSet	sortedSet.first()	sortedSet.last()
LinkedHashSet	linkedHashSet.iterator().next()	// missing

Некоторые из этих способов без необходимости громоздки, например получение последнего элемента List. Некоторые вообще невозможны без героических усилий: единственный способ получить последний элемент LinkedHashSet — перебрать всё множество.

Аналогично, перебор элементов коллекции от первого к последнему прост и единообразен, а перебор в обратном порядке — нет. Все эти коллекции можно перебирать в прямом порядке с помощью Iterator, расширенного цикла for, stream() или toArray(). Перебор в обратном порядке в каждом случае устроен по-разному. NavigableSet предоставляет для обратного перебора представление descendingSet():

for (var e : navSet.descendingSet())
    process(e);

Deque делает это с помощью обратного Iterator:

for (var it = deque.descendingIterator(); it.hasNext();) {
    var e = it.next();
    process(e);
}

List тоже делает это, но с помощью ListIterator:

for (var it = list.listIterator(list.size()); it.hasPrevious();) {
    var e = it.previous();
    process(e);
}

Наконец, LinkedHashSet вообще не поддерживает обратный перебор. Единственный практический способ обработать элементы LinkedHashSet в обратном порядке — скопировать их в другую коллекцию.

Аналогично, обработка элементов коллекции с помощью потоков данных (streams) — мощная и эффективная альтернатива обработке в циклах, но получить поток данных в обратном порядке бывает трудно. Из всех коллекций, определяющих порядок обхода, удобно это поддерживает только NavigableSet:

navSet.descendingSet().stream()

Для остальных нужно либо скопировать элементы в другую коллекцию, либо создать поток данных из специально написанного Spliterator, который выполняет обратный перебор.

Такое положение дел неудачно. Понятие коллекции с определённым порядком обхода встречается во фреймворке коллекций в нескольких местах, но нет единого типа, который бы его представлял. В результате некоторые операции над такими коллекциями несогласованы или отсутствуют, а обработка элементов в обратном порядке бывает от неудобной до невозможной. Эти пробелы следует заполнить.

Описание

Мы определяем новые интерфейсы для упорядоченных коллекций, упорядоченных множеств и упорядоченных отображений, а затем встраиваем их в существующую иерархию типов коллекций. У всех новых методов, объявленных в этих интерфейсах, есть реализации по умолчанию.

Упорядоченные коллекции

Упорядоченная коллекция (sequenced collection) — это Collection, элементы которой имеют определённый порядок обхода. (Слово «sequenced» здесь — причастие прошедшего времени от глагола to sequence, означающего «расположить элементы в определённом порядке».) У упорядоченной коллекции есть первый и последний элементы, а у элементов между ними есть последующие и предыдущие элементы. Упорядоченная коллекция поддерживает типичные операции на обоих концах, а также обработку элементов от первого к последнему и от последнего к первому (то есть в прямом и обратном порядке).

interface SequencedCollection<E> extends Collection<E> {
    // new method
    SequencedCollection<E> reversed();
    // methods promoted from Deque
    void addFirst(E);
    void addLast(E);
    E getFirst();
    E getLast();
    E removeFirst();
    E removeLast();
}

Новый метод reversed() возвращает представление исходной коллекции в обратном порядке. Любые изменения исходной коллекции видны в этом представлении. Если изменения представления разрешены, они передаются в исходную коллекцию.

Представление в обратном порядке позволяет всем упорядоченным типам обрабатывать элементы в обоих направлениях с помощью всех обычных механизмов перебора: расширенных циклов for, явных циклов iterator(), forEach(), stream(), parallelStream() и toArray().

Например, раньше получить поток данных в обратном порядке из LinkedHashSet было довольно трудно, а теперь это просто

linkedHashSet.reversed().stream()

(Метод reversed() — по сути переименованный NavigableSet::descendingSet, поднятый в SequencedCollection.)

Следующие методы SequencedCollection подняты из Deque. Они позволяют добавлять, получать и удалять элементы на обоих концах:

• void addFirst(E)
• void addLast(E)
• E getFirst()
• E getLast()
• E removeFirst()
• E removeLast()

Методы add*(E) и remove*() необязательны, в первую очередь для поддержки неизменяемых коллекций. Методы get*() и remove*() выбрасывают NoSuchElementException, если коллекция пуста.

В SequencedCollection нет определений equals() и hashCode(), потому что в его подинтерфейсах эти методы определены несовместимо.

Упорядоченные множества

Упорядоченное множество (sequenced set) — это Set, которое является SequencedCollection и не содержит повторяющихся элементов.

interface SequencedSet<E> extends Set<E>, SequencedCollection<E> {
    SequencedSet<E> reversed();    // covariant override
}

Коллекции, такие как SortedSet, которые располагают элементы путём их относительного сравнения, не могут поддерживать операции явного размещения, такие как методы addFirst(E) и addLast(E), объявленные в суперинтерфейсе SequencedCollection. Поэтому эти методы могут выбрасывать UnsupportedOperationException.

У методов addFirst(E) и addLast(E) интерфейса SequencedSet особая семантика для таких коллекций, как LinkedHashSet: если элемент уже есть в множестве, он перемещается в соответствующую позицию. Это устраняет давний недостаток LinkedHashSet — невозможность переместить элементы.

Упорядоченные отображения

Упорядоченное отображение (sequenced map) — это Map, записи которого имеют определённый порядок обхода.

interface SequencedMap<K,V> extends Map<K,V> {
    // new methods
    SequencedMap<K,V> reversed();
    SequencedSet<K> sequencedKeySet();
    SequencedCollection<V> sequencedValues();
    SequencedSet<Entry<K,V>> sequencedEntrySet();
    V putFirst(K, V);
    V putLast(K, V);
    // methods promoted from NavigableMap
    Entry<K, V> firstEntry();
    Entry<K, V> lastEntry();
    Entry<K, V> pollFirstEntry();
    Entry<K, V> pollLastEntry();
}

У новых методов put*(K, V) особая семантика, аналогичная соответствующим методам add*(E) интерфейса SequencedSet: для таких отображений, как LinkedHashMap, они дополнительно перемещают запись, если она уже есть в отображении. Для таких отображений, как SortedMap, эти методы выбрасывают UnsupportedOperationException.

Следующие методы SequencedMap подняты из NavigableMap. Они позволяют получать и удалять записи на обоих концах:

• Entry<K, V> firstEntry()
• Entry<K, V> lastEntry()
• Entry<K, V> pollFirstEntry()
• Entry<K, V> pollLastEntry()

Встраивание в существующие типы

Три новых интерфейса, определённых выше, аккуратно встраиваются в существующую иерархию типов коллекций (нажмите, чтобы увеличить):

Точнее, чтобы встроить их в существующие классы и интерфейсы, мы вносим следующие изменения:

• у List непосредственным суперинтерфейсом теперь является SequencedCollection,
• у Deque непосредственным суперинтерфейсом теперь является SequencedCollection,
• LinkedHashSet дополнительно реализует SequencedSet,
• у SortedSet непосредственным суперинтерфейсом теперь является SequencedSet,
• LinkedHashMap дополнительно реализует SequencedMap, и
• у SortedMap непосредственным суперинтерфейсом теперь является SequencedMap.

Мы определяем ковариантные переопределения метода reversed() в соответствующих местах. Например, List::reversed переопределён так, что возвращает значение типа List, а не значение типа SequencedCollection.

Мы также добавляем в служебный класс Collections новые методы, создающие неизменяемые обёртки для трёх новых типов:

• Collections.unmodifiableSequencedCollection(sequencedCollection)
• Collections.unmodifiableSequencedSet(sequencedSet)
• Collections.unmodifiableSequencedMap(sequencedMap)

Альтернативы

Типы

Вместо добавления новых типов можно было бы использовать интерфейс List в качестве общего типа упорядоченной коллекции. List действительно упорядочен, но он также поддерживает доступ к элементам по целочисленному индексу. Многие упорядоченные структуры данных не поддерживают индексацию естественным образом, и им пришлось бы реализовывать её перебором. В результате доступ по индексу имел бы сложность O(n) вместо ожидаемой O(1), что повторило бы ошибку LinkedList.

Deque выглядит многообещающим кандидатом на роль общего типа последовательности, поскольку уже поддерживает нужный набор операций. Однако он перегружен другими операциями, включая семейство операций, возвращающих null (offer, peek и poll), операции стека (push и pop) и операции, унаследованные от Queue. Эти операции разумны для очереди, но гораздо менее уместны для других коллекций. Если бы Deque стал общим типом последовательности, то List тоже был бы Queue и поддерживал бы операции стека, что привело бы к перегруженному и запутанному API.

Выбор названия

Выбранный нами термин sequence (последовательность) подразумевает элементы, расположенные по порядку. Он широко используется на разных платформах для обозначения коллекций с семантикой, похожей на описанную выше.

Термин ordered (упорядоченный) недостаточно конкретен. Нам нужен перебор в обоих направлениях и операции на обоих концах. Упорядоченная коллекция, такая как Queue, — заметное исключение: она упорядочена, но при этом явно несимметрична.

Термин reversible (обратимый), использовавшийся в более ранней версии этого предложения, не вызывает сразу ассоциации с наличием двух концов. Возможно, более серьёзная проблема в том, что вариант для Map назывался бы ReversibleMap, а это название ошибочно подразумевает поддержку поиска и по ключу, и по значению (такую структуру иногда называют BiMap или BidiMap).

Add, put и UnsupportedOperationException

Как описано выше, API явного размещения, такие как SortedSet::addFirst и SortedMap::putLast, выбрасывают UnsupportedOperationException, потому что порядок их элементов определяется относительным сравнением. Асимметрия, при которой некоторые коллекции реализуют не все операции SequencedCollection, может показаться неприятной. Тем не менее она полезна, потому что включает SortedSet и SortedMap в семейство упорядоченных коллекций и позволяет использовать их шире, чем было бы возможно иначе. Кроме того, эта асимметрия согласуется с прежними проектными решениями во фреймворке коллекций. Например, метод Map::keySet возвращает Set, хотя возвращаемая реализация не поддерживает добавление.

Как вариант, операции добавления можно было бы выделить отдельно, перестроив интерфейсы по структурному принципу. Это привело бы к новым интерфейсным типам с очень скудной семантикой (например, AddableCollection), которые бесполезны на практике и загромождают иерархию типов.

История

Это предложение — поэтапное развитие нашего предложения ReversibleCollections 2021 года. Основные изменения по сравнению с ним — переименование, добавление интерфейса SequencedMap и добавление методов для неизменяемых обёрток.

Предложение ReversibleCollection, в свою очередь, основывалось на предложении OrderedMap/OrderedSet Tagir Valeev 2020 года. Несколько фундаментальных понятий из того предложения сохранились, хотя в деталях различий много.

За прошедшие годы мы получили много запросов и предложений в духе объединения List с Set или Map. Повторяющиеся темы — List, содержащий уникальные элементы, или Set либо Map, сохраняющие порядок. Среди этих запросов — 4152834, 4245809, 4264420, 4268146, 6447049 и 8037382.

Некоторые из этих запросов были частично удовлетворены с появлением LinkedHashSet и LinkedHashMap в Java 1.4. Хотя эти классы и покрывают некоторые сценарии использования, после их появления в абстракциях и операциях фреймворка коллекций остались пробелы, описанные выше.

Тестирование

Мы добавим полный набор тестов в набор регрессионных тестов JDK.

Риски и допущения

Добавление новых методов высоко в иерархии наследования создаёт риск конфликтов из-за очевидных имён методов, таких как reversed() и getFirst().

Особое опасение вызывают ковариантные переопределения метода reversed() в List и Deque. Они несовместимы на уровне исходного кода и на двоичном уровне с существующими коллекциями, которые реализуют и List, и Deque. В JDK есть два примера таких коллекций: LinkedList и внутренний класс sun.awt.util.IdentityLinkedList. Для класса LinkedList проблема решена добавлением нового ковариантного переопределения reversed() в самом LinkedList. Внутренний класс IdentityLinkedList удалён, поскольку больше не нужен.

В более ранней версии предложения вводились ковариантные переопределения методов keySet(), values() и entrySet() интерфейса SequencedMap. После анализа было установлено, что такой подход создаёт слишком большой риск несовместимости: по сути, он делает некорректными все существующие подклассы. Был выбран альтернативный подход: вместо того чтобы превращать существующие методы в ковариантные переопределения, в SequencedMap добавлены новые методы sequencedKeySet(), sequencedValues() и sequencedEntrySet(). Если оглянуться назад, возможно, по той же причине аналогичный подход был выбран в Java 6, когда вместо превращения существующего метода keySet() в ковариантное переопределение был добавлен метод navigableKeySet().

Полный анализ риска несовместимости см. в отчёте, приложенном к CSR JDK-8266572.