Iterable, Iterator и Spliterator

В рамках сегодняшнего урока поговорим о том, откуда берутся Stream’ы.

Начнем с интересного факта: Stream, в отличии от Optional, не хранит обрабатываемые элементы внутри себя. Он лишь обрабатывает данные, которые поставляются из другого источника информации - массива, коллекции, InputStream’а и пр.

Для того, чтобы понять всю эволюционную цепочку, нырнем в практически забытого предка Collection - Iterable и посмотрим, какие методы он нам предоставляет. Возвращаемый тип одного из них является той основой, на которой строится Stream API.

Интерфейс Iterable

Сам интерфейс, как понятно из названия, характеризует его наследников как “итерируемых”, т.е. обрабатываемых итерациями.

Интерфейс Iterable предоставляет 3 метода:

1.    void forEach(). С ним мы уже знакомы, он представляет собой аналог цикла foreach: выполнит переданную параметром лямбду для каждого из элементов Iterable;

2.   Iterator iterator(). Возвращает объект типа Iterator, позволяющий обрабатывать элементы, содержащимися в наследнике Iterable, в определенном (реализацией итератора) порядке. Подробнее мы рассмотрим интерфейс Iterator в следующем пункте статьи;

3.    Spliterator spliterator(). Метод, возвращающий объект типа Spliterator. Он же Iterator на стероидах, он же гвоздь сегодняшней программы – основа Stream. Ему будет посвящен отдельный пункт ниже.

Важно понимать, что любой класс, имплементирующий Iterable декларирует существование итератора и сплитератора у такого класса. А любой сплитератор может быть обработан как Stream. В более широком смысле – любой объект, чей итератор мы можем получить, можно обработать как Stream, ведь любой итератор может быть превращен в сплитератор (возможно, топорный и не самый эффективный, но все же).

Отсюда следует, что Stream’ом можно обработать не только коллекцию, а объект любого класса, имплементирующий Iterable или Iterator. К таким, например, относятся Scanner, что, по сути, означает возможность обработать Stream’ом любой InputStream и некоторые другие классы, связанные с IO (и NIO).

Кроме того, некоторые классы не имплементируют Iterable, но имеют методы, возвращающие уже готовый Stream. К таким относятся, например, BufferedReader, знакомый нам по теме I/O Stream. Или Optional, знакомый по последним урокам. Коллекции (кроме Map) тоже имеют метод stream(), но у них он не так важен – это лишь обертка над сплитератором, т.е. Stream на основе коллекций можно создать и без данного метода.

Iterator

Однако вернемся к основам. К временам, когда о ФП и Stream API еще никто не думал, но обрабатывать элементы по порядку уже хотелось, а foreach не всегда давал нужную функциональность.

До конца не уверен, но думаю, что foreach для циклов использует именно итератор.

Кроме того, не всегда заранее известен размер обрабатываемого массива данных. Скажем, при реализации итератора у Scanner, работающего на базе System.in, мы понятия не имеем, сколько вводов совершит пользователь. А значит не знаем, сколько элементов будет обработано.

Итератор выступил отличным решением – ведь он позволяет производить обход элементов, абстрагируясь от способа хранения этих элементов. Используя итератор, мы можем обработать элементы списка, дерева, InputStream’а или другого объекта, предоставляющего доступ к массиву данных одного типа.

К слову, итератор является паттерном проектирования. Подробнее можно почитать здесь (сайт не доступен из РФ без VPN).

Вернемся к Java. Iterator<E> является интерфейсом, реализации которого можно найти в качестве вложенных классов некоторых коллекций, в классе Scanner и ряде других. Рассмотрим, какие методы у него есть, и какие из них требуют явного переопределения – ведь часть имеет дефолтную реализацию:

·      boolean hasNext(). Возвращает true, если следующий элемент существует;

·      E next(). Возвращает объект типа, которым параметризован Iterator. Если объекта нет – бросает NoSuchElementException. Не советую вызывать данный метод, предварительно не проверив наличие объекта с помощью hasNext();

·      void remove(). Удаляет текущий элемент (полученный с помощью последнего вызова next()) из источника данных (например, из коллекции). Может быть вызван не более одного раза после next(). Имеет реализацию по умолчанию, которая бросает исключение UnsupportedOperationException. Таким образом, не каждый итератор поддерживает удаление элементов;

·      void forEachRemaining(). Исполняет лямбду, переданную параметром, для каждого элемента, не обработанного через данный объект итератора ранее. По сути, равноценен forEach() у Iterable, если ни разу не был вызван next(). Реализован по умолчанию.

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

Spliterator

Spliterator, в свою очередь, является следующим шагом в эволюции итератора – он позволяет строить более гибкую работу с учетом характеристик заданного итератора, а также умеет делиться – из одного сплитератора можно получить два, на чем, например, строится возможность параллельной (многопоточной) обработки данных Stream’ами. Но об этом поговорим в свое время.

С особенностями Spliterator можно познакомиться в статье ниже. Она посвящена реализации собственной имплементации Spliterator’а и требует определенного багажа знаний, но все равно достаточно подробно рассказывает о возможностях и роли данного интерфейса в Stream API. Рекомендую обратиться к ней вне зависимости от того, насколько вам будут понятны мои объяснения ниже. Полагаю, статья по ссылке будет интересна даже тем, кто уже был знаком с данным интерфейсом ранее: https://habr.com/ru/post/256905/

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

Начнем с характеристик. Найти их можно в исходниках Spliterator. Каждая из характеристик – константа типа int. Характеристик всего всего 8:

·      ORDERED. Указывает на то, что элементы данного сплитератора должны обрабатываться в заданном порядке.

Такая характеристика актуальна для списков – порядок элементов определен их индексами.
Или для LinkedHashSet – порядок соответствует порядку добавления элементов.
Или для BufferedReader – там порядок элементов, полагаю, очевиден.
А для HashSet данная характеристика не актуальна – коллекция не гарантирует какого-то определенного порядка элементов;

·      DISTINCT. Указывает на то, что все элементы сплитератора уникальны. Уникальность элементов определяется по equals().

Это актуально для сплитераторов на базе Set’ов. Такая же характеристика появляется у сплитератора, лежащего внутри Stream при вызове метода distinct();

·      SORTED. Указывает на то, что элементы сплитератора отсортированы и будут обработаны в порядке, определенном Comparator’ом. Пример класса, имеющего сплитератор с такой характеристикой – TreeSet;

·      SIZED. Указывает на то, что Spliterator знает, сколько элементов будет обработано при полном обходе;

Характерно для сплитераторов большинства коллекций. Но помните, что сплитератор умеет делиться (об этом будет чуть позже).
В ряде случаев, скажем, для сплитераторов на базе списков, это не критично. Что основной сплитератор, что его «дочерние» сплитераторы будут знать свой размер.
А, например, в случае с HashSet нет гарантии разделения сплитератора на два равных, а значит, такие «дочерние» сплитераторы уже не будут знать, сколько элементов должны обработать, следовательно, не будут обладать подобной характеристикой.

·      NONNULL. Характеристика, гарантирующая, что элемент, обрабатываемый сплитератором не может быть равен null. Характерно для ряда коллекций, в основном, из java.util.concurrent;

·       IMMUTABLE. Указывает на то, что состав источника данных не можем быть изменен во время обработки сплитератором. Т.е. данные не будут добавлены или удалены, элементы не будут заменены другими;

Из простых примеров, наверно, только сплитератор потокобезопасного списка в java.util.concurrent – CopyOnWriteArrayList. Вообще, примеры таких сплитераторов можно найти и в Scanner, и в String, но описание ситуаций, в которых они применяются, будет слишком многословным.

·      CONCURRENT. Характеристика, указывающая, что состав источника данных может быть безопасно изменен при обработке сплитератором – реализация сплитератора для такого источника данной характеристикой декларирует умение обрабатывать такие ситуации.

По сути, противоположен IMMUTABLE. Также исключает использование SIZED для верхнеуровневых (не рожденных делением другого сплитератора) сплитераторов. В целом, логично, что сплитератор не может знать свой точный размер, если элементы могут добавиться или удалиться в любой момент. Такая характеристика актуальна для сплитераторов многих потокобезопасных коллекций в java.util.concurrent;

·      SUBSIZED. Указывает на то, что дочерние сплитераторы от данного будут SIZED.

На самом деле, немного интереснее – в зависимости от ситуации может гарантироваться также и характеристика SUBSIZED у дочернего сплитератора. Вы можете разобраться самостоятельно, если интересно. На текущем этапе эта информация кажется мне избыточной;

Теоретически, можно добавить сплитератору собственные характеристики. Но разработчики языка не рекомендуют это делать, поскольку набор характеристик может быть изменен по мере развития Java. И тогда особенности хранения характеристик в сплитераторе могут привести к некорректной обработке ваших кастомных характеристик.

Перейдем к обзору методов интерфейса Spliterator<T>. Именно они реализуют те возможности и особенности, которые декларируют рассмотренные выше характеристики:

·      boolean tryAdvance(). Применит лямбду, переданную параметром, к следующему элементу сплитератора, если он существует, и вернет true. Если элементов не осталось – вернет false;

Помните, что элементов может не быть именно сейчас – например, пользователь не произвел следующий ввод. В таком случае будет возвращен false. Но при этом элемент может добавиться впоследствии.

·      void forEachRemaining(). В целом, метод аналогичен таковому у Iterator;

·      Spliterator<T> trySplit(). Разделяет сплитератор на двое, если это возможно;

В идеале – пополам, если деление пополам невозможно – в зависимости от реализации.
Проблемы могут быть как с определением равных половин (скажем, у HashSet), так и с тем, что не всегда определено число элементов в сплитераторе – например, если сплитератор создан на базе Scanner’а.
В общем виде, поведение метода заключается в том, чтобы обработку части элементов делегировать новому сплитератору, а оставшуюся часть обработать текущим (у которого и был вызван trySplit()).

·      long estimateSize(). Возвращает точное или приблизительное число элементов, которые будут обработаны сплитератором, если прямо сейчас вызвать у него forEachRemaining(). Если число элементов неизвестно или вычислять их количество трудозатратно – вернет Long.MAX_VALUE;

·      long getExactSizeIfKnown(). Возвращает результат estimateSize(), если сплитератор имеет характеристику SIZED. В противном случае вернет -1;

·      int characteristics(). Возвращает характеристики сплитератора в виде битовой маски.

Не буду углубляться в особенности реализации, скажу лишь, что такая реализация является причиной, по которой нежелательно добавление кастомных характеристик в сплитератор. Результат метода не очевиден новичку, но достаточен для обработки классам, использующим его. Например, имплементациям интерфейса Stream.

·      boolean hasCharacteristics(). Возвращает true, если переданная параметром характеристика (в виде int’овой константы) актуальна для данного сплитератора. Иначе – false;

·      Comparator<? super T> getComparator(). Возвращает компаратор, по которому были отсортированы значения, если сплитератор имеет характеристику SORTED. В противном случае бросит IllegalStateException.

На этом мы завершаем рассмотрение методов интерфейса Spliterator и знакомство с ним.

В качестве заключения

Сплитератор является достаточно низкоуровневым интерфейсом, обеспечивающим работу Stream API. Как при обработке Optional (почти) каждая новая промежуточная операция возвращает новый объект Optional с новым объектом в поле value, так и каждая новая промежуточная операция при обработке Stream возвращает новый объект Stream c новым сплитератором внутри.

Я сомневаюсь, что большинству из вас придется работать с интерфейсом Spliterator напрямую, не считая создание экземпляров данного типа. Тем более, вряд ли вам придется писать собственную имплементацию для этого интерфейса. Однако понимание, хотя бы на уровне данной статьи, особенностей его работы, поможет понять то, как работает Stream API и, что важнее, позволит понять суть классификации методов Stream, что даст возможность использовать их эффективно.

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

Не становитесь таким разработчиком:)

С теорией на сегодня все!

Переходим к практике

Урок теоретический. Однако желающим предлагаю реализовать Stream на основе System.in. Операции в самом Stream’е можете описать на свой вкус. Главное, разберитесь, когда будет запускаться обработка элементов и в каком порядке она будет происходить.

Подсказки:

1.    Самая простая реализация возможна через BufferedReader – он содержит метод stream();

2.    Более интересная реализация возможна через Scanner. Рекомендую пойти этим путем, он позволит познакомиться с новыми для вас классами, которые могут быть полезны в дальнейшем. Если не удалось самостоятельно – см. следующую подсказку;

3.    Сплитератор на базе итератора можно создать с помощью методов класса Spliterators. Stream на базе сплитератора – с помощью методов класса StreamSupport. 

Если что-то непонятно или не получается – welcome в комменты к посту или в лс:)

Канал: https://t.me/+relA0-qlUYAxZjI6

Мой тг: https://t.me/ironicMotherfucker

Дорогу осилит идущий!