Итератор (шаблон проектирования)

Итератор
Iterator
Тип	поведенческий
Описан в Design Patterns	Да

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

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

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

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

Конечно же, (в C++) почти в любом агрегате можно выполнять итерации указателем void*, но при этом:

• не ясно, что является значением «конец агрегата», для двусвязного списка это &ListHead, для массива это &array[size], для односвязного списка это NULL
• операция Next сильно зависит от типа агрегата.

Итераторы позволяют абстрагироваться от типа и признака окончания агрегата, используя полиморфный Next (часто реализованный как operator++ в C++) и полиморфный aggregate.end(), возвращающий значение «конец агрегата».

Таким образом, появляется возможность работы с диапазонами итераторов, при отсутствии знания о типе итерируемого агрегата. Например:

Iterator itBegin = aggregate.begin();
Iterator itEnd = aggregate.end();
func(itBegin, itEnd);

И далее:

void func(Iterator itBegin, Iterator itEnd)
{
 for( Iterator it = itBegin, it != itEnd; ++it )
 {
 }
}

Примеры

С#

Исходный текст на языке С#

/*
sample code in C#

This structural code demonstrates the Iterator pattern which provides for a way to traverse (iterate) over a collection of items without detailing the underlying structure of the collection.
*/
Hide code 

// Iterator pattern -- Structural example

using System;
using System.Collections;
 
namespace DoFactory.GangOfFour.Iterator.Structural
{
    /// <summary>
    /// MainApp startup class for Structural
    /// Iterator Design Pattern.
    /// </summary>
    class MainApp
    {
        /// <summary>
        /// Entry point into console application.
        /// </summary>
        static void Main()
        {
            ConcreteAggregate a = new ConcreteAggregate();
            a[0] = "Item A";
            a[1] = "Item B";
            a[2] = "Item C";
            a[3] = "Item D";
 
            // Create Iterator and provide aggregate
            ConcreteIterator i = new ConcreteIterator(a);
 
            Console.WriteLine("Iterating over collection:");
 
            object item = i.First();
            while (! i.IsDone())
            {
                Console.WriteLine(item);
                item = i.Next();
            }
 
            // Wait for user
            Console.ReadKey();
        }
    }
 
    /// <summary>
    /// The 'Aggregate' abstract class
    /// </summary>
    abstract class Aggregate
    {
        public abstract Iterator CreateIterator();
        public abstract int Count { get; protected set; }
        public abstract object this[int index] { get; set; }
    }

    /// <summary>
    /// The 'ConcreteAggregate' class
    /// </summary>
    class ConcreteAggregate : Aggregate
    {
        private readonly ArrayList _items = new ArrayList();

        public override Iterator CreateIterator()
        {
            return new ConcreteIterator(this);
        }

        // Gets item count
        public override int Count
        {
            get { return _items.Count; }
            protected set { }
        }

        // Indexer
        public override object this[int index]
        {
            get { return _items[index]; }
            set { _items.Insert(index, value); }
        }
    }
 
    /// <summary>
    /// The 'Iterator' abstract class
    /// </summary>
    abstract class Iterator
    {
        public abstract object First();
        public abstract object Next();
        public abstract bool IsDone();
        public abstract object CurrentItem();
    }
 
    /// <summary>
    /// The 'ConcreteIterator' class
    /// </summary>
    class ConcreteIterator : Iterator
    {
        private readonly Aggregate _aggregate;
        private int _current;

        // Constructor
        public ConcreteIterator(Aggregate aggregate)
        {
            this._aggregate = aggregate;
        }
 
        // Gets first iteration item
        public override object First()
        {
            return _aggregate[0];
        }
 
        // Gets next iteration item
        public override object Next()
        {
            object ret = null;

            _current++;

            if (_current < _aggregate.Count)
            {
                ret = _aggregate[_current];
            }
 
            return ret;
        }
 
        // Gets current iteration item
        public override object CurrentItem()
        {
            return _aggregate[_current];
        }
 
        // Gets whether iterations are complete
        public override bool IsDone()
        {
            return _current >= _aggregate.Count;
        }
    }
}

Output
Iterating over collection:
Item A
Item B
Item C
Item D

PHP5

Исходный текст на языке PHP5

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

namespace iterator1 {
    /**
     * Наличие общего интерфейса удобно для клиента, поскольку клиент отделяется от реализации коллекции объектов.
     *
     * ConcreteAggregate содержит коллекцию объектов и реализует метод, который возвращает итератор для этой коллекции.
     */
    interface IAggregate
    {
        /**
         * Каждая разновидность ConcreteAggregate отвечает за создание экземпляра Concrete Iterator,
         * который может использоваться для перебора своей коллекции объектов.
         */
        public function createIterator();
    }

    /**
     * Интерфейс Iterator должен быть реализован всеми итераторами.
     *
     * ConcreteIterator отвечает за управление текущей позицией перебора.
     */
    interface IIterator
    {
        /**
         * @abstract
         * @return boolean есть ли следующий элемент в коллекции
         */
        public function hasNext();

        /**
         * @abstract
         * @return mixed следующий элемент массива
         */
        public function next();

        /**
         * Удаляет текущий элемент коллекции
         * @abstract
         * @return void
         */
        public function remove();
    }

    /**
     * В моём примере обе коллекции используют одинаковый итератор - итератор массива.
     */
    class ConcreteAggregate1 implements IAggregate
    {
        /**
         * @var Item[] $items
         */
        public $items = array();

        public function __construct()
        {
            $this->items = array(
                new Item(1, 2),
                new Item(1, 2),
                new Item(1, 2),
            );
        }

        public function createIterator()
        {
            return new ConcreteIterator1($this->items);
        }
    }

    class ConcreteAggregate2 implements IAggregate
    {
        /**
         * @var Item[] $items
         */
        public $items = array();

        public function __construct()
        {
            $this->items = array(
                new Item(2, 3),
                new Item(2, 3),
                new Item(2, 3),
            );
        }

        public function createIterator()
        {
            return new ConcreteIterator1($this->items);
        }
    }

    class ConcreteIterator1 implements IIterator
    {
        /**
         * @var Item[] $items
         */
        protected $items = array();

        /**
         * @var int $position хранит текущую позицию перебора в массиве
         */
        public $position = 0;

        /**
         * @param $items массив объектов, для перебора которых создается итератор
         */
        public function __construct($items)
        {
            $this->items = $items;
        }

        public function hasNext()
        {
            if ($this->position >= count($this->items) || count($this->items) == 0) {
                return (false);
            } else {
                return (true);
            }
        }

        public function next()
        {
            $menuItem = $this->items[$this->position];
            $this->position++;
            return ($menuItem);
        }

        public function remove()
        {
            if ($this->position <= 0) {
                throw new \Exception('Нельзя вызывать remove до вызова хотя бы одного next()');
            }
            if ($this->items[$this->position - 1] != null) {
                for ($i = $this->position - 1; $i < count($this->items); $i++) {
                    $this->items[$i] = $this->items[$i + 1];
                }
                $this->items[count($this->items) - 1] = null;
            }
        }
    }

    class Client
    {
        /**
         * @var ConcreteAggregate1 $aggregate1
         */
        public $aggregate1;
        /**
         * @var ConcreteAggregate2 $aggregate2
         */
        public $aggregate2;

        public function __construct($aggregate1, $aggregate2)
        {
            $this->aggregate1 = $aggregate1;
            $this->aggregate2 = $aggregate2;
        }

        public function printAggregatesItems()
        {
            $iterator1 = $this->aggregate1->createIterator();
            echo "\n First";
            $this->printIteratorItems($iterator1);

            $iterator2 = $this->aggregate2->createIterator();
            echo "\n\n Second";
            $this->printIteratorItems($iterator2);
        }

        /**
         * @param $iterator IIterator
         */
        private function printIteratorItems($iterator)
        {
            while ($iterator->hasNext()) {
                $item = $iterator->next();
                echo "\n $item->name $item->price $item->description";
            }
        }
    }

    class Item
    {
        public $price;
        public $name;
        public $description;

        public function __construct($name, $price, $description = '')
        {
            $this->name = $name;
            $this->price = $price;
            $this->description = $description;
        }
    }


    $runner = new Client(new ConcreteAggregate1(), new ConcreteAggregate2());
    $runner->printAggregatesItems();
}

Пример итератора компоновщика на PHP5

Исходный текст итератора компоновщика на языке PHP5

 /**
 * Паттерн-компоновщик с внешним итератором 
 * Итератор использует рекурсию для перебора дерева элементов
 */
namespace compositeIterator {
    /**
     * Клиент использует интерфейс AComponent для работы с объектами.
     * Интерфейс AComponent определяет интерфейс для всех компонентов: как комбинаций, так и листовых узлов.
     * AComponent может реализовать поведение по умолчанию для add() remove() getChild() и других операций
     */
    abstract class AComponent
    {

        public $customPropertyName;

        public $customPropertyDescription;

        /**
         * @param AComponent $component
         */
        public function add($component)
        {
            throw new \Exception("Unsupported operation");
        }

        /**
         * @param AComponent $component
         */
        public function remove($component)
        {
            throw new \Exception("Unsupported operation");
        }

        /**
         * @param int $int
         */
        public function getChild($int)
        {
            throw new \Exception("Unsupported operation");
        }

        /**
         * @return  IPhpLikeIterator
         */
        abstract function createIterator();

        public function operation1()
        {
            throw new \Exception("Unsupported operation");
        }
    }

    /**
     * Leaf наследует методы add() remove() getChild( которые могут не иметь смысла для листового узла.
     * Хотя листовой узер можно считать узлом с нулём дочерних объектов
     *
     * Leaf определяет поведение элементов комбинации. Для этого он реализует операции, поддерживаемые интерфейсом Composite.
     */
    class Leaf extends AComponent
    {
        public function __construct($name, $description = '')
        {
            $this->customPropertyName = $name;
            $this->customPropertyDescription = $description;
        }

        public function createIterator()
        {
            return new NullIterator();
        }

        public function operation1()
        {
            echo ("\n I'am leaf {$this->customPropertyName}, i don't want to do operation 1. {$this->customPropertyDescription}");
        }
    }

    class NullIterator implements IPhpLikeIterator
    {
        public function valid()
        {
            return (false);
        }

        public function next()
        {
            return (false);
        }

        public function current()
        {
            return (null);
        }

        public function remove()
        {
            throw new \CException('unsupported operation');
        }
    }

    /**
     * Интерфейс Composite определяет поведение компонентов, имеющих дочерние компоненты, и обеспечивает хранение последних.
     *
     * Composite также реализует операции, относящиеся к Leaf. Некоторые из них не могут не иметь смысла для комбинаций; в таких случаях генерируется исключение.
     */
    class Composite extends AComponent
    {

        private $_iterator = null;

        /**
         * @var \ArrayObject AComponent[] $components для хранения потомков типа AComponent
         */
        public $components = null;

        public function __construct($name, $description = '')
        {
            $this->customPropertyName = $name;
            $this->customPropertyDescription = $description;
        }

        /**
         * @param AComponent $component
         */
        public function add($component)
        {
            if (is_null($this->components)) {
                $this->components = new \ArrayObject;
            }
            $this->components->append($component);
        }

        public function remove($component)
        {
            foreach ($this->components as $i => $c) {
                if ($c === $component) {
                    unset($this->components[$i]);
                }
            }
        }

        public function getChild($int)
        {
            return ($this->components[$int]);
        }

        public function operation1()
        {
            echo "\n\n $this->customPropertyName $this->customPropertyDescription";
            echo "\n --------------------------------";

            $iterator = $this->components->getIterator();
            while ($iterator->valid()) {
                $component = $iterator->current();
                $component->operation1();
                $iterator->next();
            }
        }

        /**
         * @return CompositeIterator
         */
        public function createIterator()
        {
            if (is_null($this->_iterator)) {
                $this->_iterator = new CompositeIterator($this->components->getIterator());
            }
            return ($this->_iterator);
        }
    }

    /**
     *  Рекурсивный итератор компоновщика
     */
    class CompositeIterator implements IPhpLikeIterator
    {

        public $stack = array();

        /**
         * @param \ArrayIterator $componentsIterator
         */
        public function __construct($componentsIterator)
        {
            //$this->stack= new \ArrayObject;
            $this->stack[] = $componentsIterator;
        }

        public function remove()
        {
            throw new \CException('unsupported operation');
        }

        public function valid()
        {
            if (empty($this->stack)) {
                return (false);
            } else {
                /** @var $componentsIterator \ArrayIterator */
                // берём первый элемент
                $componentsIterator = array_shift(array_values($this->stack));
                if ($componentsIterator->valid()) {
                    return (true);
                } else {
                    array_shift($this->stack);
                    return ($this->valid());
                }
            }
        }

        public function next()
        {
            /** @var $componentsIterator \ArrayIterator */
            $componentsIterator = current($this->stack);
            $component = $componentsIterator->current();
            if ($component instanceof Composite) {
                array_push($this->stack, $component->createIterator());
            }
            $componentsIterator->next();
            //return($component);
        }

        public function current()
        {
            if ($this->valid()) {
                /** @var $componentsIterator \ArrayIterator */
                // берём первый элемент
                $componentsIterator = array_shift(array_values($this->stack));
                return ($componentsIterator->current());
            } else {
                return (null);
            }
        }
    }

    /**
     * Интерфейс Iterator должен быть реализован всеми итераторами.
     * Данный интерфейс является частью интерфейса стандартного php итератора.
     * Конкретный Iterator отвечает за управление текущей позицией перебора в конкретной коллекции.
     */
    interface IPhpLikeIterator
    {
        /**
         * @abstract
         * @return boolean есть ли текущий элемент
         */
        public function valid();

        /**
         * @abstract
         * @return mixed перевести курсор дальше
         */
        public function next();

        /**
         * @abstract
         * @return mixed получить текущий элемент
         */
        public function current();

        /**
         * удалить текущий элемент коллекции
         * @abstract
         * @return void
         */
        public function remove();
    }


    class Client
    {
        /**
         * @var AComponent
         */
        public $topItem;

        public function __construct($topItem)
        {
            $this->topItem = $topItem;
        }

        public function printOperation1()
        {
            $this->topItem->operation1();
        }

        public function printOperation2()
        {
            echo "\n\n\n";
            $iterator = $this->topItem->createIterator();
            while ($iterator->valid()) {
                /** @var $component AComponent */
                $component = $iterator->current();
                if (strstr($component->customPropertyName, 'leaf1')) {
                    echo ("\n I'm Client, I found leaf {$component->customPropertyName}, I'll just leave it here (for my 'first-leafs' tea collection). {$component->customPropertyDescription}");
                }
                $iterator->next();
            }
        }
    }

    class Test
    {
        public static function go()
        {
            $a = new Composite("c1");
            $b = new Composite("c2");
            $c = new Composite("c3");

            $topItem = new Composite("top item");
            $topItem->add($a);
            $topItem->add($b);
            $topItem->add($c);

            $a->add(new Leaf("c1-leaf1"));
            $a->add(new Leaf("c1-leaf2"));

            $b->add(new Leaf("c2-leaf1"));
            $b->add(new Leaf("c2-leaf2"));
            $b->add(new Leaf("c2-leaf3"));

            $c->add(new Leaf("c3-leaf1"));
            $c->add(new Leaf("c3-leaf2"));


            $client = new Client($topItem);
            $client->printOperation1();
            $client->printOperation2();
        }
    }

    Test::go();
}

Python

Исходный текст на языке Python

from abc import ABCMeta, abstractmethod


class Iterator(metaclass=ABCMeta):
    """
    Абстрактный итератор
    """

    _error = None   # класс ошибки, которая прокидывается в случае выхода за границы коллекции

    def __init__(self, collection, cursor):
        """
        Constructor.

        :param collection: коллекция, по которой производится проход итератором
        :param cursor: изначальное положение курсора в коллекции (ключ)
        """
        self._collection = collection
        self._cursor = cursor

    @abstractmethod
    def current(self):
        """
        Вернуть текущий элемент, на который указывает итератор
        """
        pass

    @abstractmethod
    def next(self):
        """
        Сдвинуть курсор на следующий элемент коллекции и вернуть его
        """
        pass

    @abstractmethod
    def has_next(self):
        """
        Проверить, существует ли следующий элемент коллекции
        """
        pass

    @abstractmethod
    def remove(self):
        """
        Удалить текущий элемент коллекции, на который указывает курсор
        """
        pass

    def _raise_key_exception(self):
        """
        Прокинуть ошибку, связанную с невалидным индексом, содержащимся в курсоре
        """
        raise self._error('Collection of class {} does not have key "{}"'.format(
            self.__class__.__name__, self._cursor))


class ListIterator(Iterator):
    """
    Итератор, проходящий по обычному списку
    """

    _error = IndexError

    def __init__(self, collection: list):
        super().__init__(collection, 0)

    def current(self):
        if self._cursor < len(self._collection):
            return self._collection[self._cursor]
        self._raise_key_exception()

    def next(self):
        if len(self._collection) >= self._cursor + 1:
            self._cursor += 1
            return self._collection[self._cursor]
        self._raise_key_exception()

    def has_next(self):
        return len(self._collection) >= self._cursor + 1

    def remove(self):
        if 0 <= self._cursor < len(self._collection):
            self._collection.remove(self._collection[self._cursor])
        else:
            self._raise_key_exception()


class DictIterator(Iterator):
    """
    Итератор, проходящий по словарю - из-за того, что словари в Python'е реализованы,
    как хеш-таблицы, порядок обхода может меняться во время разных запусков
    """

    _error = KeyError

    def __init__(self, collection: dict):
        super().__init__(collection, next(iter(collection)))
        self._keys = list(self._collection.keys())
        self._keys.pop(0)

    def current(self):
        if self._cursor in self._collection:
            return self._collection[self._cursor]
        self._raise_key_exception()

    def next(self):
        if len(self._keys):
            self._cursor = self._keys.pop(0)
            return self._collection[self._cursor]
        else:
            self._raise_key_exception()

    def has_next(self):
        return len(self._keys) > 0

    def remove(self):
        if self._cursor in self._collection:
            del self._collection[self._cursor]
            try:
                self.next()
            except self._error:
                raise KeyError('Collection of type {} is empty'.format(self.__class__.__name__))
        else:
            self._raise_key_exception()


class Collection(metaclass=ABCMeta):
    """
    Абстрактная коллекция
    """

    @abstractmethod
    def iterator(self):
        pass


class ListCollection(Collection):
    """
    Коллекция-обертка для обычного списка
    """

    def __init__(self, collection: list):
        self._collection = collection

    def iterator(self):
        return ListIterator(self._collection)
    

class DictCollection(Collection):
    """
    Коллекция-обертка для словаря
    """

    def __init__(self, collection: dict):
        self._collection = collection

    def iterator(self):
        return DictIterator(self._collection)
    

def test(title=str, collection=Collection):
    print("\n{}\n".format(title))
    iterator = collection.iterator()
    print(iterator.current())
    iterator.next()
    print(iterator.next())
    iterator.remove()
    print(iterator.current())
    print(iterator.has_next())
    print()
    
if __name__ == '__main__':
    print('OUTPUT:')
    test('List testing', ListCollection([1, 2, 3, 4, 5]))
    test('Dictionary testing', DictCollection({'a': 1, 'b': 2, 'c': 3, 'f': 8}))

'''
OUTPUT:

List testing

1
3
4
True


Dictionary testing

1
3
2
False
'''

Rust

Пример для языка Rust

#[derive(Debug, Clone, Copy)]
pub struct ExampleRange
{
	begin : i64,
	current : i64,
	end : i64,
}
impl ExampleRange
{
	pub fn new(begin : i64, end : i64) -> Self
	{
		ExampleRange
		{
			begin,
			current : begin,
			end,
		}
	}
	pub fn iter(&self) -> ExampleRange
	{
		*self
	}
}
use std::fmt;
impl fmt::Display for ExampleRange
{
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result
	{
		write!(f, "{}", self.current)
	}
}
impl Iterator for ExampleRange
{
	type Item = i64;
	fn next(&mut self) -> Option<Self::Item>
	{
		if self.current < self.end
		{
			(Some(self.current), self.current += 1).0
		}
		else
		{
			None
		}
	}
	fn last(mut self) -> Option<Self::Item>
	{
		if self.current > self.begin
		{
			(self.current -= 1, Some(self.current)).1
		}
		else
		{
			None
		}
	}
}


fn main()
{
	let it = ExampleRange::new(0, 6);
	for item in it
	{
		println!("{}", item);
	}
}


'''
OUTPUT:
0
1
2
3
4
5
'''