Обзор шаблона проектирования Iterator и его реализации в Dart и Flutter

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

Оглавление

  • Что такое шаблон проектирования Iterator?
  • Анализ
  • Реализация
  • Другие статьи из этой серии
  • Ваш вклад

Что такое шаблон проектирования Iterator?

Итератор - это поведенческий шаблон проектирования, также известный как Курсор. Назначение этого паттерна проектирования описано в Книге GoF:

Обеспечивает способ последовательного доступа к элементам агрегированного объекта, не раскрывая его базовое представление.

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

Как я уже упоминал, вы, вероятно, уже использовали этот шаблон проектирования (по крайней мере, его реализацию), даже не замечая этого, особенно если вы знакомы с разработкой с использованием Java или C # /. NET. Например, все коллекции Java предоставляют некоторые внутренние реализации интерфейса Iterator, который используется для перебора элементов коллекции. В контексте C # есть несколько специальных типов контейнеров, способных хранить коллекцию значений, например. List и ArrayList, которые имеют возможность перебирать их.

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

Анализ

Общая структура шаблона проектирования Iterator выглядит так:

  • IterableCollection - определяет интерфейс для создания объекта Iterator;
  • ConcreteCollection - реализует интерфейс создания Iterator для возврата нового экземпляра определенного конкретного класса итератора каждый раз, когда клиент запрашивает его. Этот класс также может содержать дополнительный код / ​​логику, например. для хранения структуры данных, которую следует повторять;
  • Итератор - определяет интерфейс для доступа и перемещения элементов коллекции;
  • ConcreteIterator - реализует интерфейс Iterator. Кроме того, этот класс должен отслеживать прогресс обхода, например. текущая позиция в обходе коллекции;
  • Клиент - ссылается и использует как коллекции, так и итераторы через свои интерфейсы.

Применимость

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

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

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

Реализация

Прежде всего, чтобы лучше понять часть реализации, вы должны быть знакомы с древовидной структурой данных. Если вы не следите за серией, я объяснил это при анализе паттерна Composite, но если вы уже читали эту статью - 10 баллов за Гриффиндор!

На этот раз мы исследуем одну из фундаментальных частей теории графов - обход графа. Обход графа определяется как:

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

На этот раз мы сосредоточимся только на случае обхода дерева. Доступно несколько алгоритмов обхода графа / дерева:

  • Поиск в глубину (DFS) - посещает дочерние вершины перед посещением родственных вершин; то есть, он проходит глубину любого конкретного пути, прежде чем исследовать его широту;
  • Поиск в ширину (BFS) - посещает родственные вершины перед посещением дочерних вершин.

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

Диаграмма классов

На диаграмме классов ниже показана реализация шаблона проектирования Iterator:

ITreeCollection определяет общий интерфейс для всех конкретных древовидных коллекций:

  • createIterator () - создает итератор для конкретной древовидной коллекции;
  • getTitle () - возвращает заголовок коллекции дерева, которая используется в пользовательском интерфейсе.

DepthFirstTreeCollection и BreadthFirstTreeCollection - это конкретные реализации интерфейса ITreeCollection. DepthFirstTreeCollection создает DepthFirstIterator, а BreadthFirstTreeCollection создает BreadthFirstIterator. Кроме того, в обеих этих коллекциях хранится объект Graph для сохранения самой древовидной структуры данных.

ITreeIterator определяет общий интерфейс для всех конкретных итераторов коллекции дерева:

  • hasNext () - возвращает true, если итератор еще не дошел до конца коллекции, иначе false;
  • getNext () - возвращает следующее значение коллекции;
  • reset () - сбрасывает итератор и устанавливает его текущую позицию в начало.

DepthFirstIterator и BreadthFirstIterator - это конкретные реализации интерфейса ITreeIterator. DepthFirstIterator реализует алгоритм в глубину для обхода коллекции дерева. Соответственно, BreadthFirstIterator реализует алгоритм в ширину. Основное различие между этими двумя алгоритмами заключается в порядке посещения всех узлов. Следовательно, алгоритм в глубину реализуется с использованием структуры данных стека, в то время как алгоритм в ширину использует структуру данных очередь для хранения узлов (вершин), которые должны быть посещены в следующий раз. .

IteratorExample ссылается на оба интерфейса - ITreeCollection и ITreeIterator - чтобы указать требуемую коллекцию дерева и создать для нее соответствующий итератор.

График

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

ITreeCollection

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

Коллекции деревьев

DepthFirstTreeCollection - класс коллекции дерева, который хранит объект графика и реализует метод createIterator () для создания итератора, который использует алгоритм в глубину для обхода графа.

BreadthFirstTreeCollection - класс коллекции дерева, который хранит объект графа и реализует метод createIterator () для создания итератора, который использует алгоритм в ширину для обхода графа.

ITreeIterator

Интерфейс, определяющий методы, которые будут реализованы всеми конкретными итераторами коллекции дерева.

Итераторы дерева

DepthFirstIterator - конкретная реализация итератора дерева, который просматривает коллекцию дерева с использованием алгоритма в глубину. Этот алгоритм использует структуру данных stack для хранения вершин (узлов), которые следует посетить следующим образом с помощью метода getNext ().

BreadthFirstIterator - конкретная реализация итератора дерева, который просматривает коллекцию дерева с использованием алгоритма в ширину. Этот алгоритм использует структуру данных queue для хранения вершин (узлов), которые должны быть посещены следующим образом с помощью метода getNext ().

Пример

Прежде всего, подготавливается файл разметки, который предоставляется как описание шаблона:

Виджет IteratorExample отвечает за построение дерева (графа) с использованием класса Graph и содержит список объектов коллекции дерева. После выбора конкретной древовидной коллекции из списка и запуска метода traverseTree () создается соответствующий итератор этой конкретной древовидной коллекции, который используется для обхода древовидной структуры данных.

Как вы можете видеть в методе traverseTree (), все детали реализации обхода коллекции дерева скрыты от клиента, он использует только hasNext () и getNext (), определенные интерфейсом ITreeIterator для перебора всех вершин (узлов) построенного объекта (дерева) Graph.

Окончательный результат реализации шаблона проектирования Iterator выглядит так:

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

Все изменения кода для шаблона проектирования Iterator и его пример реализации можно найти здесь.

Другие статьи из этой серии

Ваш вклад

👏 Нажмите кнопку хлопка ниже, чтобы выразить свою поддержку и побудить меня писать лучше!
💬 Оставьте отзыв на эту статью, поделившись своими мыслями, комментариями или пожеланиями относительно серии.
📢 Поделитесь этой статьей со своими друзья, коллеги в социальных сетях.
➕ Подписывайтесь на меня на Medium.
⭐ Пометьте репозиторий Github.



Сообщество Flutter
Последние твиты от сообщества Flutter (@FlutterComm). Следуйте, чтобы получать уведомления о новых статьях и пакетах с… www.twitter.com