Итераторы

Дополните свою коллекцию итераторами и почувствуйте волшебство.

В чем проблема?

Что, если мы хотим перебрать элементы в коллекции (стек, очередь,…), не раскрывая реализацию, используем ли мы массив или связанный список. В Java это можно сделать, реализовав интерфейс Iterable.

Итерируемый и итераторный интерфейсы

Итерируемый интерфейс имеет метод, называемый итератором. Этот метод возвращает объект Итератор.

Интерфейс Iterator - это интерфейс, в котором есть методы next и hasNext. Класс реализует интерфейс итератора, который будет использоваться для перебора элементов в коллекции.

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

Как сделать стек итерируемым?

Во-первых, нам нужно посмотреть, как может выглядеть класс Stack.

public class Stack<Item> {
    private Node first = null;

    private class Node {
        Item item;
        Node next;
    }
    
    public void push(Item item) { /* … */ }
    public Item pop() { /* … */ }
}

Это может быть реализовано с использованием связного списка или массива. В любом случае вы будете следовать одним и тем же шагам:

1. Реализуйте итерируемый интерфейс.

Класс Stack должен реализовывать Iterable Interface.

import java.util.Iterator;
public class Stack<Item> implements Iterable<Item> { /* … */ }

Обратите внимание, что Iteratble и Iterator являются универсальными интерфейсами. Итак, класс Stack также должен быть универсальным классом. Потому что вы собираетесь перебирать элементы универсального типа в стеке.

2. Переопределить метод итератора

Переопределите метод Iterable Interface, называемый итератором. Он возвращает объект Iterator универсального типа.

public Iterator<Item> iterator() { return new StackIterator(); }

Теперь ясно, что нам нужно создать класс под названием «StackIterator», который должен реализовать интерфейс Iterator.

3. Реализуйте интерфейс итератора.

Создайте внутренний класс, реализующий интерфейс итератора. Вам нужно будет поддерживать ссылку на текущий элемент, на который указывает итератор.

private class StackIterator implements Iterator<Item> {
    private Node current = first;
}

4. Переопределить методы next и hasNext.

public boolean hasNext()  { return current != null;  }
    
public Item next() {
    if (!hasNext()) throw new NoSuchElementException();
    Item item = current.item;
    current = current.next; 
    return item;
}

Стеки, реализованные с помощью массивов

Опять же, вы выполните те же действия. Небольшие изменения для работы с массивами вместо связанных списков.

private class StackIterator implements Iterator<Item> {
    private int i = N;
    public boolean hasNext()  { return i > 0;  }
    
    public Item next() {
        if (!hasNext()) throw new NoSuchElementException();
        return s[--i];
    }
}

Другие способы сделать коллекцию итеративной?

Да это так. Вы можете сделать коллекцию Iterable, используя другую коллекцию Iterable.

Например, имея Map, коллекцию пар ключ-значение, в которой мы хотим перебирать ключи. Мы можем хранить все ключи в стеке или очереди (объект Iterable) и использовать этот стек или очередь для перебора ключей.

Есть два способа сделать это, один из них - реализовать Iterable Interface в классе Map (точно так же, как мы сделали со стеком).

Реализация метода iterator () в классе Map проста; Просто верните метод iterator () выбранного объекта Iterable; будь то стек, очередь или любой объект Iterable. Это точная реализация, как мы сделали со стеками.

public class Map<Key, Value> implements Iterable<Key> {
    // ...

    public Iterator<Key> iterator() {
        Queue<Key> queue = new Queue<Key>();
        for (int i = 0; i < N; i++) 
            queue.enqueue(keys[i]);
        return queue.iterator();    // return an Iterator object
    }
}

Другой способ - вернуть сам объект Iterable. Таким образом, классу Map не нужно реализовывать Iterable Interface. Просто определите метод, скажем, keys (),, который заполняет объект Iterable ключами и вернет его. Теперь мы можем использовать возвращенный объект Iterable для перебора ключей.

Обратной стороной этого подхода является то, что Map не является объектом Iterable, поскольку не реализует Iterable Interface. Мы должны использовать метод keys (), чтобы получить доступ к объекту Iterable, который будет использоваться для перебора ключей.

public class Map<Key, Value> {
    // ...

    public Iterable<Key> keys() {
        Queue<Key> queue = new Queue<Key>();
        for (int i = 0; i < N; i++) 
            queue.enqueue(keys[i]);
        return queue;               // return an Iterable object
   }
}

Цикл foreach против итератора

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

Stack<Apple> stack = new Stack<Apple>();
stack.push(new Apple());
// ...
Iterator<Apple> it = stack.iterator();
while(it.hasNex()) { 
    Apple a = it.next();
    System.out.println(a);
}

Цикл foreach - это сокращенное обозначение итерации по итерируемой коллекции.

foreach(Apple a: stack)
    System.out.println(a);