March 08, 2016

Составной итератор. Java

Представьте, что у вас есть две коллекции объектов разного типа. Обе коллекции отсортированы по какому-то правилу. Вам нужно обойти обе коллекции, сохраняя порядок сортировки. Как, например, здесь:
Я хочу поделиться простой, но эффективной техникой использования интерфейсов Iterator и Iterable.


Предположим, у нас есть такая структура классов:


Метод compareTo() реализовывает сравнение по полю id в естественном порядке. Метод toString() возвращает конкретное имя класса наследника и его id.

Оджнажды я встретил подобную иерархию в рабочем коде. Вдобавок объекты хранились в двух разных списках: List<Bar> и List<Qux>. Напомню, что оба списка отсортированы!


Итак, наша задача - обойти оба списка эффективно: линейная сложность по времени O(n), без копирования коллекций, без дополнительных сортировок, без лишних циклов.

"Простейшее", на первый взгляд, решение - это написать два цикла, потом взять два элемента (по одному из каждого списка), сравнить их, решить какой из них использовать, перейти на первый шаг. Если один из списков закончится раньше другого, то там нужно будет проверить эту ситуацию дополнительным циклом. Этот код будет очень сложным и не используемым повторно. (Я не хочу приводить никаких примеров здесь, просто попробуйте написать это самостоятельно, в качестве тестовой задачи.)

С другой стороны мы можем избежать многих усложнений, если мы будем использовать интерфейс Iterator. Объявим класс CompositeIterator таким образом:


Поля it1 и it2 будут ссылаться на итераторы, полученные из обоих коллекций. Comparator используется для решения задачи сортировки. Поле lastUsed будет хранить ссылку на итератор, из которого последним было возвращено значение. Поля obj1 и obj2 хранят объекты, полученные из итераторов it1 и it2 соответственно. Что ж, как это будет работать?


Метод hasNext() будет проверять по меньшей мере один объект obj1 или obj2, полученный из итераторов. Если оба они равны null, мы проверим как минимум один итератор, вызывая его метод hasNext().

Если одно из этих четырёх условий равно true, мы попадём в метод next(). Теперь нам нужно убедиться, что мы используем объекты из обоих итераторов, если obj1 и/или obj2 равны null, то мы "достанем" их из итераторов. Теперь если оба они не равны null, то там нужно сравнить их и выбрать один, который необходимо вернуть. Иначе мы просто возвращаем тот, который не равен null. В случае, если оба объекта равны null в конце этого метода, то это значит, что метод next() вызывается некорректно - нужно бросать исключение NoSuchElementException.

Обратите внимание на два метода obj1() и obj2(). Они сделаны для того, чтобы сохранить ссылку на последний используемый итератор, а также, чтобы очистить ссылку на объект, который будет возвращён.

Метод remove() будет использовать поле lastUsed для того, чтобы удалить последний возвращённый элемент из правильного итератора.

Для того, чтобы удобно использовать этот класс составного итератора, мы добавим простую реализацию интерфейса Iterable, который будет создавать CompositeIterator каждый раз, когда вызывается метод iterator():


И на этом всё! Не верите? Проверьте!


Ух ты! Я даже не думал, что получу такой красивый код. Вот вывод:


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

Я надеюсь, что это решение поможет вам работать с коллекциями более эффективно. Вы можете скачать все исходные файлы с Github. Спасибо за прочтение!

No comments:

Post a Comment