Итератор

Итератор — это поведенческий паттерн проектирования, который даёт возможность последовательно обходить элементы составных объектов, не раскрывая их внутреннего представления.

Проблема

Коллекции — самая распространённая структура данных, которую вы можете встретить в программировании. Это набор объектов, собранный в одну кучу по каким-то критериям.

Разные типы коллекций.

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

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

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

Одну и ту же коллекцию можно обходить разными способами.

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

Решение

Идея паттерна Итератор состоит в том, чтобы вынести поведение обхода коллекции из самой коллекции в отдельный класс.

Итераторы содержат код обхода коллекции. Одну коллекцию могут обходить сразу несколько итераторов.

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

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

Аналогия из жизни

Варианты прогулок по Риму.

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

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

Таким образом, Рим выступает коллекцией достопримечательностей, а ваш мозг, навигатор или гид — итератором по коллекции. Вы, как клиентский код, можете выбрать один из итераторов, отталкиваясь от решаемой задачи и доступных ресурсов.

Структура

1. Итератор описывает интерфейс для доступа и обхода элементов коллекции.
2. Конкретный итератор реализует алгоритм обхода какой-то конкретной коллекции. Объект итератора должен сам отслеживать текущую позицию при обходе коллекции, чтобы отдельные итераторы могли обходить одну и ту же коллекцию независимо.
3. Коллекция описывает интерфейс получения итератора из коллекции. Как мы уже говорили, коллекции не всегда являются списком. Это может быть и база данных, и удалённое API, и даже дерево Компоновщика. Поэтому сама коллекция может создавать итераторы, так как она знает, какие именно итераторы способны с ней работать.
4. Конкретная коллекция возвращает новый экземпляр определённого конкретного итератора, связав его с текущим объектом коллекции. Обратите внимание, что сигнатура метода возвращает интерфейс итератора. Это позволяет клиенту не зависеть от конкретных классов итераторов.
5. Клиент работает со всеми объектами через интерфейсы коллекции и итератора. Так клиентский код не зависит от конкретных классов, что позволяет применять различные итераторы, не изменяя существующий код программы.
   В общем случае клиенты не создают объекты итераторов, а получают их из коллекций. Тем не менее, если клиенту требуется специальный итератор, он всегда может создать его самостоятельно.

Псевдокод

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

Пример обхода социальных профилей через итератор.

Так, итератор друзей перебирает всех друзей профиля, а итератор коллег — фильтрует друзей по принадлежности к компании профиля. Все итераторы реализуют общий интерфейс, который позволяет клиентам работать с профилями, не вникая в детали работы с социальной сетью (например, в авторизацию, отправку REST-запросов и т. д.)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

// Общий интерфейс коллекций должен определить фабричный метод
// для производства итератора. Можно определить сразу несколько
// методов, чтобы дать пользователям различные варианты обхода
// одной и той же коллекции.
interface SocialNetwork is
    method createFriendsIterator(profileId):ProfileIterator
    method createCoworkersIterator(profileId):ProfileIterator


// Конкретная коллекция знает, объекты каких итераторов нужно
// создавать.
class Facebook implements SocialNetwork is
    // ...Основной код коллекции...

    // Код получения нужного итератора.
    method createFriendsIterator(profileId) is
        return new FacebookIterator(this, profileId, "friends")
    method createCoworkersIterator(profileId) is
        return new FacebookIterator(this, profileId, "coworkers")


// Общий интерфейс итераторов.
interface ProfileIterator is
    method getNext():Profile
    method hasMore():bool


// Конкретный итератор.
class FacebookIterator implements ProfileIterator is
    // Итератору нужна ссылка на коллекцию, которую он обходит.
    private field facebook: Facebook
    private field profileId, type: string

    // Но каждый итератор обходит коллекцию, независимо от
    // остальных, поэтому он содержит информацию о текущей
    // позиции обхода.
    private field currentPosition
    private field cache: array of Profile

    constructor FacebookIterator(facebook, profileId, type) is
        this.facebook = facebook
        this.profileId = profileId
        this.type = type

    private method lazyInit() is
        if (cache == null)
            cache = facebook.socialGraphRequest(profileId, type)

    // Итератор реализует методы базового интерфейса по-своему.
    method getNext() is
        if (hasMore())
            result = cache[currentPosition]
            currentPosition++
            return result

    method hasMore() is
        lazyInit()
        return currentPosition < cache.length


// Вот ещё полезная тактика: мы можем передавать объект
// итератора вместо коллекции в клиентские классы. При таком
// подходе клиентский код не будет иметь доступа к коллекциям, а
// значит, его не будут волновать подробности их реализаций. Ему
// будет доступен только общий интерфейс итераторов.
class SocialSpammer is
    method send(iterator: ProfileIterator, message: string) is
        while (iterator.hasMore())
            profile = iterator.getNext()
            System.sendEmail(profile.getEmail(), message)


// Класс приложение конфигурирует классы, как захочет.
class Application is
    field network: SocialNetwork
    field spammer: SocialSpammer

    method config() is
        if working with Facebook
            this.network = new Facebook()
        if working with LinkedIn
            this.network = new LinkedIn()
        this.spammer = new SocialSpammer()

    method sendSpamToFriends(profile) is
        iterator = network.createFriendsIterator(profile.getId())
        spammer.send(iterator, "Very important message")

    method sendSpamToCoworkers(profile) is
        iterator = network.createCoworkersIterator(profile.getId())
        spammer.send(iterator, "Very important message")

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

Когда у вас есть сложная структура данных, и вы хотите скрыть от клиента детали её реализации (из-за сложности или вопросов безопасности).

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

Когда вам нужно иметь несколько вариантов обхода одной и той же структуры данных.

Нетривиальные алгоритмы обхода структуры данных могут иметь довольно объёмный код. Этот код будет захламлять всё вокруг — будь то сам класс коллекции или часть бизнес-логики программы. Применив итератор, вы можете выделить код обхода структуры данных в собственный класс, упростив поддержку остального кода.

Когда вам хочется иметь единый интерфейс обхода различных структур данных.

Итератор позволяет вынести реализации различных вариантов обхода в подклассы. Это позволит легко взаимозаменять объекты итераторов, в зависимости от того, с какой структурой данных приходится работать.

Шаги реализации

1. Создайте общий интерфейс итераторов. Обязательный минимум — это операция получения следующего элемента коллекции. Но для удобства можно предусмотреть и другое. Например, методы для получения предыдущего элемента, текущей позиции, проверки окончания обхода и прочие.
2. Создайте интерфейс коллекции и опишите в нём метод получения итератора. Важно, чтобы сигнатура метода возвращала общий интерфейс итераторов, а не один из конкретных итераторов.
3. Создайте классы конкретных итераторов для тех коллекций, которые нужно обходить с помощью паттерна. Итератор должен быть привязан только к одному объекту коллекции. Обычно эта связь устанавливается через конструктор.
4. Реализуйте методы получения итератора в конкретных классах коллекций. Они должны создавать новый итератор того класса, который способен работать с данным типом коллекции. Коллекция должна передавать ссылку на собственный объект в конструктор итератора.
5. В клиентском коде и в классах коллекций не должно остаться кода обхода элементов. Клиент должен получать новый итератор из объекта коллекции каждый раз, когда ему нужно перебрать её элементы.

Преимущества и недостатки

Преимущества

• Упрощает классы хранения данных.
• Позволяет реализовать различные способы обхода структуры данных.
• Позволяет одновременно перемещаться по структуре данных в разные стороны.

Недостатки

• Не оправдан, если можно обойтись простым циклом.

Примеры реализации паттерна

Python

• Сложность: 2/3
• Популярность: 3/3
• Применимость: Паттерн можно часто встретить в Python-коде, особенно в программах, работающих с разными типами коллекций, и где требуется обход разных сущностей.
• Признаки применения паттерна: Итератор легко определить по методам навигации (например, получения следующего/предыдущего элемента и т. д.). Код использующий итератор зачастую вообще не имеет ссылок на коллекцию, с которой работает итератор. Итератор либо принимает коллекцию в параметрах конструктора при создании, либо возвращается самой коллекцией.

Этот пример показывает структуру паттерна Итератор, а именно — из каких классов он состоит, какие роли эти классы выполняют и как они взаимодействуют друг с другом.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

from __future__ import annotations
from collections.abc import Iterable, Iterator
from typing import Any


"""
Для создания итератора в Python есть два абстрактных класса из
встроенного модуля collections - Iterable, Iterator. Нужно реализовать
метод __iter__() в итерируемом объекте (списке), а метод __next__() в
итераторе.
"""


class AlphabeticalOrderIterator(Iterator):
    """
    Конкретные Итераторы реализуют различные алгоритмы обхода. Эти
    классы постоянно хранят текущее положение обхода.
    """

    """
    Атрибут _position хранит текущее положение обхода. У итератора
    может быть множество других полей для хранения состояния итерации,
    особенно когда он должен работать с определённым типом коллекции.
    """
    _position: int = None

    """
    Этот атрибут указывает направление обхода.
    """
    _reverse: bool = False

    def __init__(self, collection: WordsCollection,
        reverse: bool = False) -> None:
        self._collection = collection
        self._reverse = reverse
        self._position = -1 if reverse else 0

    def __next__(self) -> Any:
        """
        Метод __next __() должен вернуть следующий элемент в
        последовательности. При достижении конца коллекции и в
        последующих вызовах должно вызываться исключение
        StopIteration.
        """
        try:
            value = self._collection[self._position]
            self._position += -1 if self._reverse else 1
        except IndexError:
            raise StopIteration()

        return value


class WordsCollection(Iterable):
    """
    Конкретные Коллекции предоставляют один или несколько методов для
    получения новых экземпляров итератора, совместимых с классом
    коллекции.
    """

    def __init__(self, collection: list[Any] | None = None) -> None:
        self._collection = collection or []


    def __getitem__(self, index: int) -> Any:
        return self._collection[index]

    def __iter__(self) -> AlphabeticalOrderIterator:
        """
        Метод __iter__() возвращает объект итератора, по умолчанию мы
        возвращаем итератор с сортировкой по возрастанию.
        """
        return AlphabeticalOrderIterator(self)

    def get_reverse_iterator(self) -> AlphabeticalOrderIterator:
        return AlphabeticalOrderIterator(self, True)

    def add_item(self, item: Any) -> None:
        self._collection.append(item)


if __name__ == "__main__":
    # Клиентский код может знать или не знать о Конкретном Итераторе
    # или классах Коллекций, в зависимости от уровня косвенности,
    # который вы хотите сохранить в своей программе.
    collection = WordsCollection()
    collection.add_item("First")
    collection.add_item("Second")
    collection.add_item("Third")

    print("Straight traversal:")
    print("\n".join(collection))
    print("")

    print("Reverse traversal:")
    print("\n".join(collection.get_reverse_iterator()), end="")

Straight traversal:
First
Second
Third

Reverse traversal:
Third
Second
First

PHP

• Сложность: 2/3
• Популярность: 2/3
• Применимость: Паттерн можно часто встретить в PHP-коде, особенно в программах, работающих с разными типами коллекций, и где требуется обход разных сущностей.
  PHP имеет встроенный интерфейс для поддержки итераторов (Iterator), на основании которого можно строить свои Итераторы, совместимые с остальным PHP-кодом.
• Признаки применения паттерна: Итератор легко определить по методам навигации (например, получения следующего/предыдущего элемента и т. д.). Код использующий итератор зачастую вообще не имеет ссылок на коллекцию, с которой работает итератор. Итератор либо принимает коллекцию в параметрах конструктора при создании, либо возвращается самой коллекцией.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108

<?php
/**
* Конкретные Итераторы реализуют различные алгоритмы обхода. Эти классы
* постоянно хранят текущее положение обхода.
*/

class AlphabeticalOrderIterator implements \Iterator
{
    /**
    * @var WordsCollection
    */
    private $collection;

    /**
    * @var int Хранит текущее положение обхода. У итератора может быть
    * множество других полей для хранения состояния итерации, особенно когда он
    * должен работать с определённым типом коллекции.
    */
    private $position = 0;

    /**
    * @var bool Эта переменная указывает направление обхода.
    */
    private $reverse = false;

    public function __construct($collection, $reverse = false)
    {
        $this->collection = $collection;
        $this->reverse = $reverse;
    }

    public function rewind()
    {
        $this->position = $this->reverse ?
        count($this->collection->getItems()) - 1 : 0;
    }

    public function current()
    {
        return $this->collection->getItems()[$this->position];
    }

    public function key()
    {
        return $this->position;
    }

    public function next()
    {
        $this->position = $this->position + ($this->reverse ? -1 : 1);
    }

    public function valid()
    {
        return isset($this->collection->getItems()[$this->position]);
    }
}

/**
* Конкретные Коллекции предоставляют один или несколько методов для получения
* новых экземпляров итератора, совместимых с классом коллекции.
*/

class WordsCollection implements \IteratorAggregate
{
    private $items = [];

    public function getItems()
    {
        return $this->items;
    }

    public function addItem($item)
    {
        $this->items[] = $item;
    }

    public function getIterator(): Iterator
    {
        return new AlphabeticalOrderIterator($this);
    }

    public function getReverseIterator(): Iterator
    {
        return new AlphabeticalOrderIterator($this, true);
    }
}

/**
* Клиентский код может знать или не знать о Конкретном Итераторе или классах
* Коллекций, в зависимости от уровня косвенности, который вы хотите сохранить в
* своей программе.
*/
$collection = new WordsCollection();
$collection->addItem("First");
$collection->addItem("Second");
$collection->addItem("Third");

echo "Straight traversal:\n";
foreach ($collection->getIterator() as $item) {
    echo $item . "\n";
}

echo "\n";
echo "Reverse traversal:\n";
foreach ($collection->getReverseIterator() as $item) {
    echo $item . "\n";
}

Straight traversal:
First
Second
Third

Reverse traversal:
Third
Second
First

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

<?php
/**
* Итератор CSV-файлов.
*
* @author Josh Lockhart
*/

class CsvIterator implements \Iterator
{
    const ROW_SIZE = 4096;

    /**
    * Указатель на CSV-файл.
    *
    * @var resource
    */
    protected $filePointer = null;

    /**
    * Текущий элемент, который возвращается на каждой итерации.
    *
    * @var array
    */
    protected $currentElement = null;

    /**
    * Счётчик строк.
    *
    * @var int
    */
    protected $rowCounter = null;

    /**
    * Разделитель для CSV-файла.
    *
    * @var string
    */
    protected $delimiter = null;

    /**
    * Конструктор пытается открыть CSV-файл. Он выдаёт исключение при ошибке.
    *
    * @param string $file CSV-файл.
    * @param string $delimiter Разделитель.
    *
    * @throws \Exception
    */
    public function __construct($file, $delimiter = ',')
    {
        try {
            $this->filePointer = fopen($file, 'rb');
            $this->delimiter = $delimiter;
        } catch (\Exception $e) {
            throw new \Exception('The file "' . $file . '" cannot be read.');
        }
    }

    /**
    * Этот метод сбрасывает указатель файла.
    */
    public function rewind(): void
    {
        $this->rowCounter = 0;
        rewind($this->filePointer);
    }

    /**
    * Этот метод возвращает текущую CSV-строку в виде двумерного массива.
    *
    * @return array Текущая CSV-строка в виде двумерного массива.
    */
    public function current(): array
    {
        $this->currentElement = fgetcsv($this->filePointer, self::ROW_SIZE, $this->delimiter);
        $this->rowCounter++;

        return $this->currentElement;
    }

    /**
    * Этот метод возвращает номер текущей строки.
    *
    * @return int Номер текущей строки.
    */
    public function key(): int
    {
        return $this->rowCounter;
    }

    /**
    * Этот метод проверяет, достигнут ли конец файла.
    *
    * @return bool Возвращает true при достижении EOF, в ином случае false.
    */
    public function next(): bool
    {
        if (is_resource($this->filePointer)) {
            return !feof($this->filePointer);
        }
        return false;
    }

    /**
    * Этот метод проверяет, является ли следующая строка допустимой.
    *
    * @return bool Если следующая строка является допустимой.
    */
    public function valid(): bool
    {
        if (!$this->next()) {
            if (is_resource($this->filePointer)) {
                fclose($this->filePointer);
            }
            return false;
        }
        return true;
    }
}

/**
* Клиентский код.
*/
$csv = new CsvIterator(__DIR__ . '/cats.csv');

foreach ($csv as $key => $row) {
    print_r($row);
}

Array
(
    [0] => Name
    [1] => Age
    [2] => Owner
    [3] => Breed
    [4] => Image
    [5] => Color
    [6] => Texture
    [7] => Fur
    [8] => Size
)
Array
(
    [0] => Steve
    [1] => 3
    [2] => Alexander Shvets
    [3] => Bengal
    [4] => /cats/bengal.jpg
    [5] => Brown
    [6] => Stripes
    [7] => Short
    [8] => Medium
)
Array
(
    [0] => Siri
    [1] => 2
    [2] => Alexander Shvets
    [3] => Domestic short-haired
    [4] => /cats/domestic-sh.jpg
    [5] => Black
    [6] => Solid
    [7] => Medium
    [8] => Medium
)
Array
(
    [0] => Fluffy
    [1] => 5
    [2] => John Smith
    [3] => Maine Coon
    [4] => /cats/Maine-Coon.jpg
    [5] => Gray
    [6] => Stripes
    [7] => Long
    [8] => Large
)

Задачи

Задача 1. Итератор дерева с разными обходами

Реализуйте паттерн Итератор для бинарного дерева поиска. Создайте три итератора: InOrderIterator (симметричный: лево → корень → право), PreOrderIterator (прямой: корень → лево → право) и PostOrderIterator (обратный: лево → право → корень). Клиентский код должен обходить дерево через единый интерфейс, не зная о структуре узлов.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

from __future__ import annotations
from typing import Iterator

class TreeNode:
    def __init__(self, value: int):
        self.value = value
        self.left:  TreeNode | None = None
        self.right: TreeNode | None = None

class BinarySearchTree:
    def __init__(self):
        self._root: TreeNode | None = None

    def insert(self, value: int) -> None:
        def _insert(node, val):
            if node is None:
                return TreeNode(val)
            if val < node.value:
                node.left  = _insert(node.left,  val)
            else:
                node.right = _insert(node.right, val)
            return node
        self._root = _insert(self._root, value)

    def get_root(self) -> TreeNode | None:
        return self._root

# TODO: реализовать итераторы (каждый реализует __iter__ и __next__):
# InOrderIterator(root: TreeNode | None)
#   — симметричный обход: лево → корень → право
#   — реализовать без рекурсии (используя стек)
#
# PreOrderIterator(root: TreeNode | None)
#   — прямой обход: корень → лево → право
#
# PostOrderIterator(root: TreeNode | None)
#   — обратный обход: лево → право → корень

# TODO: добавить в BinarySearchTree методы:
# __iter__() — возвращает InOrderIterator (по умолчанию)
# iter_preorder() -> Iterator[int]
# iter_postorder() -> Iterator[int]

# Ожидаемый клиентский код:
# bst = BinarySearchTree()
# for val in [5, 3, 7, 1, 4, 6, 8]:
#     bst.insert(val)

# print("InOrder:  ", list(bst))                    # [1, 3, 4, 5, 6, 7, 8]
# print("PreOrder: ", list(bst.iter_preorder()))    # [5, 3, 1, 4, 7, 6, 8]
# print("PostOrder:", list(bst.iter_postorder()))   # [1, 4, 3, 6, 8, 7, 5]

# # Совместимость с for-each и встроенными функциями
# print("Min:", min(bst))   # 1
# print("Max:", max(bst))   # 8
# print("Sum:", sum(bst))   # 34

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

<?php
class TreeNode {
    public ?TreeNode $left  = null;
    public ?TreeNode $right = null;

    public function __construct(public int $value) {}
}

class BinarySearchTree {
    private ?TreeNode $root = null;

    public function insert(int $value): void {
        $this->root = $this->insertNode($this->root, $value);
    }

    private function insertNode(?TreeNode $node, int $value): TreeNode {
        if ($node === null) return new TreeNode($value);
        if ($value < $node->value) $node->left  = $this->insertNode($node->left,  $value);
        else                       $node->right = $this->insertNode($node->right, $value);
        return $node;
    }

    public function getRoot(): ?TreeNode { return $this->root; }
}

// TODO: реализовать итераторы (каждый реализует Iterator):
// InOrderIterator implements Iterator  — лево → корень → право
// PreOrderIterator implements Iterator — корень → лево → право
// PostOrderIterator implements Iterator — лево → право → корень

// TODO: добавить методы в BinarySearchTree:
// getIterator(): Iterator (по умолчанию InOrder)
// getPreOrderIterator(): Iterator
// getPostOrderIterator(): Iterator

// Ожидаемый клиентский код:
// $bst = new BinarySearchTree();
// foreach ([5, 3, 7, 1, 4, 6, 8] as $val) $bst->insert($val);

// echo "InOrder:  ";
// foreach ($bst->getIterator() as $v) echo "$v ";    // 1 3 4 5 6 7 8
// echo "\nPreOrder: ";
// foreach ($bst->getPreOrderIterator() as $v) echo "$v "; // 5 3 1 4 7 6 8
// echo "\nPostOrder: ";
// foreach ($bst->getPostOrderIterator() as $v) echo "$v "; // 1 4 3 6 8 7 5

Задача 2. Итератор плоского списка из вложенной коллекции

Реализуйте паттерн Итератор для коллекции NestedList, которая содержит смесь целых чисел и вложенных списков произвольной глубины. Итератор FlatIterator должен «разворачивать» структуру и выдавать все числа последовательно, как если бы список был одноуровневым. Клиентский код не должен знать о вложенности.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from typing import Iterator

# Элемент может быть числом или вложенным списком
NestedItem = int | list  # рекурсивный тип

class NestedList:
    def __init__(self, data: list):
        self._data = data

    # TODO: реализовать FlatIterator или метод __iter__,
    # который обходит структуру любой вложенности и выдаёт только int

# Ожидаемый клиентский код:
# nl = NestedList([1, [2, 3], [4, [5, 6]], 7, [[8, [9, 10]]]])
# print(list(nl))   # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# print(sum(nl))    # 55
# print(list(NestedList([])))  # []
# print(list(NestedList([[[1]], [[2, [3]]]])))  # [1, 2, 3]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

<?php
class NestedList implements IteratorAggregate {
    public function __construct(private array $data) {}

    // TODO: реализовать getIterator(): Iterator
    // который рекурсивно разворачивает вложенные массивы и выдаёт только int

    public function getIterator(): Iterator {
        // ...
    }
}

// Ожидаемый клиентский код:
// $nl = new NestedList([1, [2, 3], [4, [5, 6]], 7, [[8, [9, 10]]]]);
// foreach ($nl as $v) echo "$v "; // 1 2 3 4 5 6 7 8 9 10
// echo "\n";

// $sum = 0;
// foreach ($nl as $v) $sum += $v;
// echo "Сумма: $sum\n"; // 55

Задача 3. Итератор с фильтрацией и трансформацией

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

from typing import Iterator, Callable, TypeVar, Generic, Iterable

T = TypeVar('T')
R = TypeVar('R')

# TODO: реализовать:
# FilterIterator(source: Iterable[T], predicate: Callable[[T], bool])
#   — реализует __iter__ и __next__
#   — пропускает элементы, для которых predicate(item) == False
#
# MapIterator(source: Iterable[T], transform: Callable[[T], R])
#   — применяет transform к каждому элементу

from dataclasses import dataclass

@dataclass
class User:
    id: int
    name: str
    age: int
    active: bool
    score: float

users = [
    User(1, "Анна",   28, True,  4.8),
    User(2, "Иван",   17, True,  3.2),
    User(3, "Мария",  32, False, 4.5),
    User(4, "Пётр",   25, True,  4.9),
    User(5, "Светла", 16, True,  3.8),
    User(6, "Алекс",  45, True,  4.7),
]

# Ожидаемый клиентский код:
# Активные совершеннолетние пользователи с рейтингом >= 4.5
# active_adults = FilterIterator(users, lambda u: u.active and u.age >= 18)
# high_rated    = FilterIterator(active_adults, lambda u: u.score >= 4.5)
# names         = MapIterator(high_rated, lambda u: f"{u.name} ({u.score})")

# print("Топ пользователи:")
# for name in names:
#     print(f"  {name}")
# # Анна (4.8)
# # Пётр (4.9)
# # Алекс (4.7)

# # Средний рейтинг активных взрослых
# scores = list(MapIterator(
#     FilterIterator(users, lambda u: u.active and u.age >= 18),
#     lambda u: u.score
# ))
# print(f"Средний рейтинг: {sum(scores)/len(scores):.2f}")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

<?php
class User {
    public function __construct(
        public int    $id,
        public string $name,
        public int    $age,
        public bool   $active,
        public float  $score,
    ) {}
}

// TODO: реализовать:
// FilterIterator implements Iterator
//   — __construct(iterable $source, callable $predicate)
//   — пропускает элементы, для которых $predicate($item) === false
//
// MapIterator implements Iterator
//   — __construct(iterable $source, callable $transform)
//   — применяет $transform к каждому элементу

$users = [
    new User(1, 'Анна',   28, true,  4.8),
    new User(2, 'Иван',   17, true,  3.2),
    new User(3, 'Мария',  32, false, 4.5),
    new User(4, 'Пётр',   25, true,  4.9),
    new User(5, 'Света',  16, true,  3.8),
    new User(6, 'Алекс',  45, true,  4.7),
];

// Ожидаемый клиентский код:
// $activeAdults = new FilterIterator($users, fn($u) => $u->active && $u->age >= 18);
// $highRated    = new FilterIterator($activeAdults, fn($u) => $u->score >= 4.5);
// $names        = new MapIterator($highRated, fn($u) => "{$u->name} ({$u->score})");

// echo "Топ пользователи:\n";
// foreach ($names as $name) echo "  $name\n";
// // Анна (4.8)
// // Пётр (4.9)
// // Алекс (4.7)

Задача 4. Итератор страниц (пагинация)

Реализуйте паттерн Итератор для постраничного обхода данных. Класс PaginatedIterator получает функцию fetch_page(page, size) и автоматически подгружает следующую страницу по мере обхода. Итератор должен корректно завершаться, когда страницы закончились, и поддерживать стандартный цикл for.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

from typing import Iterator, Callable

# Симуляция источника данных
def make_data_source(total: int):
    """Возвращает функцию fetch_page(page, size) -> list[dict]"""
    data = [{"id": i, "name": f"Item #{i}", "value": i * 10} for i in range(1, total + 1)]

    def fetch_page(page: int, size: int) -> list[dict]:
        start = (page - 1) * size
        end   = start + size
        result = data[start:end]
        print(f"  [API] Загружена страница {page} ({len(result)} записей)")
        return result

    return fetch_page

# TODO: реализовать PaginatedIterator:
# - __init__(fetch_page: Callable[[int, int], list], page_size: int = 10)
# - реализует __iter__ и __next__
# - загружает первую страницу при создании (или при первом обращении)
# - автоматически загружает следующую страницу когда текущая исчерпана
# - завершается (StopIteration) когда fetch_page вернул пустой список

# Ожидаемый клиентский код:
# fetch = make_data_source(total=25)
# iterator = PaginatedIterator(fetch, page_size=10)

# print("Обход всех 25 элементов:")
# for item in iterator:
#     print(f"  {item['name']}")
# # Загружена страница 1 (10 записей)  <- автоматически
# # Item #1 ... Item #10
# # Загружена страница 2 (10 записей)
# # Item #11 ... Item #20
# # Загружена страница 3 (5 записей)
# # Item #21 ... Item #25

# # Подсчёт через sum без хранения всех данных в памяти
# total_value = sum(item["value"] for item in PaginatedIterator(fetch, page_size=10))
# print(f"Сумма значений: {total_value}")  # 3250

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

<?php
// Симуляция источника данных
function makeDataSource(int $total): callable {
    $data = array_map(
        fn($i) => ['id' => $i, 'name' => "Item #{$i}", 'value' => $i * 10],
        range(1, $total)
    );

    return function(int $page, int $size) use ($data): array {
        $start  = ($page - 1) * $size;
        $result = array_slice($data, $start, $size);
        echo "  [API] Загружена страница {$page} (" . count($result) . " записей)\n";
        return $result;
    };
}

// TODO: реализовать PaginatedIterator implements Iterator:
// - __construct(callable $fetchPage, int $pageSize = 10)
// - загружает страницы по мере обхода
// - завершается когда fetchPage вернул пустой массив

// Ожидаемый клиентский код:
// $fetch    = makeDataSource(total: 25);
// $iterator = new PaginatedIterator($fetch, pageSize: 10);

// echo "Обход всех 25 элементов:\n";
// foreach ($iterator as $item) {
//     echo "  {$item['name']}\n";
// }
// // [API] Загружена страница 1 (10 записей)
// // Item #1 ... Item #10
// // [API] Загружена страница 2 (10 записей)
// // Item #11 ... Item #20
// // [API] Загружена страница 3 (5 записей)
// // Item #21 ... Item #25

// $total = 0;
// foreach (new PaginatedIterator($fetch, pageSize: 10) as $item) {
//     $total += $item['value'];
// }
// echo "Сумма значений: {$total}\n"; // 3250

Задача 5. Итератор графа (обход в ширину и глубину)

Реализуйте паттерн Итератор для обхода графа. Класс Graph хранит вершины и рёбра. Создайте два итератора: BFSIterator (обход в ширину, использует очередь) и DFSIterator (обход в глубину, использует стек). Оба принимают стартовую вершину и корректно обрабатывают циклы (посещают каждую вершину не более одного раза).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

from collections import deque

class Graph:
    def __init__(self):
        self._adjacency: dict[str, list[str]] = {}

    def add_vertex(self, vertex: str) -> None:
        self._adjacency.setdefault(vertex, [])

    def add_edge(self, from_v: str, to_v: str, bidirectional: bool = True) -> None:
        self._adjacency.setdefault(from_v, []).append(to_v)
        if bidirectional:
            self._adjacency.setdefault(to_v, []).append(from_v)

    def neighbors(self, vertex: str) -> list[str]:
        return self._adjacency.get(vertex, [])

    def vertices(self) -> list[str]:
        return list(self._adjacency.keys())

# TODO: реализовать итераторы:
# BFSIterator(graph: Graph, start: str)
#   — использует deque как очередь (FIFO)
#   — посещает каждую вершину не более одного раза
#   — реализует __iter__ и __next__
#
# DFSIterator(graph: Graph, start: str)
#   — использует список как стек (LIFO)
#   — посещает каждую вершину не более одного раза

# Ожидаемый клиентский код:
# g = Graph()
# for v in ["A", "B", "C", "D", "E", "F"]:
#     g.add_vertex(v)
# g.add_edge("A", "B")
# g.add_edge("A", "C")
# g.add_edge("B", "D")
# g.add_edge("B", "E")
# g.add_edge("C", "F")
# g.add_edge("D", "E")  # цикл

# print("BFS от A:", list(BFSIterator(g, "A")))
# # ['A', 'B', 'C', 'D', 'E', 'F']

# print("DFS от A:", list(DFSIterator(g, "A")))
# # ['A', 'C', 'F', 'B', 'E', 'D'] (порядок зависит от реализации)

# # Поиск пути
# def find_path(graph: Graph, start: str, target: str) -> bool:
#     return target in BFSIterator(graph, start)

# print(find_path(g, "A", "F"))  # True
# print(find_path(g, "D", "C"))  # True

public function addVertex(string $vertex): void {
    $this->adjacency[$vertex] ??= [];
}

public function addEdge(string $from, string $to, bool $bidirectional = true): void {
    $this->adjacency[$from][] = $to;
    if ($bidirectional) $this->adjacency[$to][] = $from;
}

public function neighbors(string $vertex): array {
    return $this->adjacency[$vertex] ?? [];
}

public function vertices(): array { return array_keys($this->adjacency); }