Iterator

Návrhový vzor Iterátor (Iterator) slouží k vytvoření rozhraní, které umožňuje sekvenčně procházet objekty uložené v nějaké složité struktuře (kontejneru). Samotná implementace tohoto rozhraní zůstává uživateli skryta. Iterátor patří mezi tzv GoF (Gang of Four) vzory – je součástí bible návrhových vzorů – knihy Design Patterns: Elements of Reusable Object-Oriented Software.

Motivace

Iterátor použijeme v několika částečně se překrývajících situacích.

Průchod složitého objektu

První z nich je, chceme-li procházet objekt, jehož struktura není na první pohled zřejmá. Příkladem může být třída Rodina, ve které existuje velké množství vazeb (rodič, potomek, švagr, teta, sestřenice...). Rozhraní iterátoru nám zaručí, že projdeme systematicky všechny členy rodiny (žádného nevynecháme, ani nezpracujeme vícekrát).

Jednotné rozhraní

Druhou situací je, když chceme vytvořit jednotné rozhraní pro mnoho různých kolekcí. Toto rozhraní pak implementujeme například pro spojový seznam, strom, dynamické pole a podobně. V programu má pak uživatel možnost procházet všechny kolekce jednotným způsobem, aniž by se musel zajímat o to, jak jsou data uložená.

Optimalizace průchodu

Třetím uplatněním iterátoru je optimalizace průchodu kolekcí. Uvažme spojový seznam, který pro přístup používá pouze běžně implementovanou metodu get (pokud chceme n-tý prvek, tak musíme přeiterovat vždy n-1 předchozích uzlů). Pokud bychom chtěli projít postupně všechny prvky, tak potřebujeme $1+2+3 + \\cdots + n = (n+n^{2})/2 = O(n^{2})$ operací. V případě použití iterátoru, který by si držel stav (pozici ve spojovém seznamu) a vždy pouze přešel o uzel dál, by počet operací klesl na O(n) .

Příklad

Implementujte iterátor pro jednosměrně zřetězený spojový seznam. Iterátor bude obsahovat metody hasNext – dotaz na existenci dalšího prvku – a next – přechod na další prvek (uzel). Navrácený iterátor bude pro usnadnění průchodu kolekcí vždy inicializován na pozici -1 (tj. před první prvek).

Java

/**
 * Jednosmerne zretezeny spojovy seznam
 * @author Pavel Micka
 * @param <ENTITY> typovy parametr specifikujici ukladany typ
 */
public class MyLinkedList<ENTITY>{
 
    private Node first;
    private Node last;
    private int size;
 
    /**
     * Konstruktor spojoveho seznamu
     */
    public MyLinkedList() {
        this.size = 0;
    }
 
    /**
     * Vlozi na konec seznamu prvek
     * @param i prvek k vlozeni
     */
    public void add(ENTITY i) {
        Node n = new Node(i);
        if (size == 0) {
            this.first = n;
            this.last = n;
        } else {
            this.last.next = n;
            this.last = n;
        }
        size++;
    }
 
    /**
     * Vrati prvek na indexu i
     * @param i index prvku
     * @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu
     * @throws IllegalArgumentException pokud je i zaporne
     * @return prvek na indexu i
     */
    public ENTITY get(int i) {
        if (i >= size) {
            throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
        }
        if (i < 0) {
            throw new IllegalArgumentException("Index mensi nez 0");
        }
        Node curr = first;
        for (int j = 0; j < i; j++) {
            curr = curr.next;
        }
        return curr.value;
    }
 
    /**
     * Smaze prvek na indexu i
     * @param i index mazaneho prvku
     * @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu
     * @throws IllegalArgumentException pokud je i zaporne
     */
    public void remove(int i) {
        if (i >= size) {
            throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
        }
        if (i < 0) {
            throw new IllegalArgumentException("Index mensi nez 0");
        }
        if (i == 0) {
            first = first.next;
        } else {
            Node curr = first;
            for (int j = 0; j < i - 1; j++) { //najdeme predchozi
                curr = curr.next;
            }
            curr.next = curr.next.next; //a mazany prvek vynechame
            if (i == size - 1) { //pokud mazeme posledni
                last = curr;
            }
        }
        size--;
    }
 
    /**
     * Dotaz na delku seznamu
     * @return delka seznamu
     */
    public int size() {
        return this.size;
    }
 
    /**
     * Klasicka toString metoda, vraci textovou reprezentaci objektu
     * @return textova reprezentace objektu
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node curr = first;
        for (int i = 0; i < this.size; i++) {
            builder.append(curr.value);
            builder.append(" ");
            curr = curr.next;
        }
        return builder.toString();
    }
 
    public Iterator<ENTITY> iterator() {
        return new LinkedListIterator();
    }
     
    /**
     * Vnitrni trida reprezentujici jeden uzel spojoveho seznamu
     */
    private class Node {
 
        private ENTITY value;
        private Node next;
 
        private Node(ENTITY value) {
            this.value = value;
        }
    }    
     
    /* *************************************************
     *                   ITERATOR                      *  
     * *************************************************/
      
    /**
     * Jednoduchy iterator pro spojovy seznam
     * Neresi situaci, kdy je iteratoru pod rukou pozmena kolekce (tj. neni fail fast)
     * @param <ENTITY> typovy parametr specifikujici typ ulozeny v prochazene kolekce
     * 
     * Poznamka: Jelikoz je iterator vytvaren jako soukroma vnitrni trida, tak 
     * je dokanale skryt (zapouzdren) pred okolnim svetem. Veskera jeho volani
     * mohou byt uskutecnena pouze skrze inteface iterator
     * 
     * Poznamka2: V realnem Java svete bychom pouzili pro iterator interface
     * java.util.Iterator a pro iterovanou tridu interface java.lang.Iterable.
     * Tato implementace slouzi pouze jako ukazka vzoru samotneho bez navaznosti
     * na tato Java-specific rozhrani 
     */
    private class LinkedListIterator implements Iterator<ENTITY>{
        /**
         * Odkaz na soucasny uzel spojoveho seznamu
         */
        private Node currNode;
        /**
         * Priznak toho, ze je iterator nastaven na -1 prvek 
         * (tj. jeste nebyl pouzit k prechodu na prvni prvek)
         */
        private boolean start;
 
        public LinkedListIterator() {
            this.currNode = null;
            this.start = true;
        }
 
        @Override
        public boolean hasNext() {
            if (start) {
                return first != null;
            }
            return currNode.next != null;
        }
 
        @Override
        public ENTITY next() {
            if (start) {
                start = false;
                currNode = first;
            } else {
                currNode = currNode.next;
            }
            return currNode.value;
        }
    }
}
 
/**
 * Rozhrani iteratoru. Iterator slouzi k sekvencnimu pruchodu pres objekty ulozene v kolekci/kontejneru
 * @author Pavel Micka
 * @param <ENTITY> typovy parametr iteratoru 
 */
interface Iterator<ENTITY>{
    /**
     * Dotaz na existenci dalsiho prvku
     * @return @true, pokud dalsi prvek existuje, @false v opacnem pripade
     */
    public boolean hasNext();
    /**
     * Navrati dalsi entitu
     * @return dalsi entita ("dalsi" je zavisle na konkretni implementaci iteratoru)
     */
    public ENTITY next();
}

Motivace

Průchod složitého objektu

Jednotné rozhraní

Optimalizace průchodu

Příklad

Doporučujeme