Իտերատոր | |
---|---|
Տեսակ | Վարքագծային |
Նշանակություն | տարանջատում է ալգորիթմը կոնտեյներներից |
Նկարագրությունը ԳօՖի "Design Patterns" գրքում | Այո |
Իտերատոր (անգլ.՝ Iterator pattern), վարքագծային նախագծման ձևանմուշ, որտեղ իտերատորն օգտագործվում է կոնտեյների էլեմենտներով անցնելու և նրանց վրա հասանելիություն ունենալու համար։ Իտերատորն տարանջատում է ալգորիթմը կոնտեյներներից, սակայն որոշ դեպքերում ալգորիթմները կոնտեյներ կողմնորոշված են և հնարավոր չէ այն տարանջատել։
Օրինակ SearchForElement հիպոթետիկ ալգորիթմը կոնկրետ կոնտեյներ սպեցեֆիկ ալգորիթմի փոխարեն իրականացվում է որոշակի տիպի իտերատոր օգտագործելով։ Դա թույլ է տալիս SearchForElement-ն օգտագործել ցանկացած տիպի կոնտեյների համար, եթե իհարկե, այն սպասարվում է տվյալ տիպի իտերատորի կողմից։
/*
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
/**
* Паттерн итератор предоставляет механизм последовательного перебора элементов коллекции без раскрытия реализации коллекции.
*
* Перебор элементов выполняется объектом итератора, а не самой коллекцией.
* Это упрощает интерфейс и реализацию коллекции, а также способствует более логичному распределению обязанностей.
*/
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();
}
/**
* Паттерн-компоновщик с внешним итератором
* Итератор использует рекурсию для перебора дерева элементов
*/
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();
}
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
'''
#[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
'''
|