Iterator

Iteratorul

Definitie
Reprezinta un mecanism de accesare a elementelor unui agregat de obiecte fara a expune reprezentarea interna a agregatului. Se mai numeste si cursor.

Context
Vom lua ca exemplu de agregat o lista. De cele mai multe ori este de preferat ca accesul la elementele listei sa se faca fara a fi necesar sa se cunoasca "dedesubturile" implementarii listei si fara a incarca clasa respectiva cu operatii necesare parcurgerii listei. Un client trebuie sa poata traversa lista intr-un sens sau altul, respectiv sa poata initia mai multe traversari paralele asupra aceleiasi liste.
Aceste probleme se pot rezolva cu ajutorul sablonului Iterator. Ideea de baza a sablonului este ca accesul si traversarea unei liste sa constituie responsabilitatea unui alt obiect. Clasa iterator defineste interfata necesara accesului la elementele listei. Un obiect iterator tine evidenta elementului curent, adica stie in orice moment care nod al listei tocmai a fost accesat.
Relatia dintre o clasa Lista si o clasa IteratorLista este redata in figura de mai jos:

Pentru a putea instantia clasa IteratorLista este necesar sa se furnizeze constructorului o referinta la un obiect Lista. Apoi, prin intermediul obiectului IteratorLista se pot accesa elementele listei in mod secvential. Astfel, operatia CurrentItem returneaza elementul curent al listei, First initializeaza elementul curent cu primul element din lista, Next realizeaza avansul cu o pozitie, iar IsDone testeaza daca s-a ajuns la capatul listei.
Separarea mecanismului de parcurgere de Lista propriu-zisa permite definirea de iteratori pentru diverse politici de parcurgere, fara a incarca interfata clasei Lista. De exemplu, se poate defini un iterator IteratorCuFiltru, care sa acceseze doar acele elemente care satisfac criteriile unui anumit filtru.
Trebuie remarcat ca Lista si IteratorLista sunt clase cuplate, iar clientul trebuie sa stie ca agregatul care se parcurge este o lista si nu altceva, deci clientul este legat de un anumit agregat. Ar fi de dorit sa putem sa schimbam agregatul, fara a afecta codul clientului. Aceasta se poate face generalizand conceptul de iterator, astfel incat acesta sa suporte iteratia polimorfica.
Sa presupunem ca, pe langa Lista, mai avem un agregat ArboreBinar si dorim ca un client sa foloseasca acelasi cod pentru a lucra cu ambele agregate. In acest scop vom defini o clasa ListaAbstracta a carei interfata sa contina operatiile comune de manipulare a elementelor unei liste, respectiv ale unui arbore. Similar, vom avea o clasa Iterator a carei interfata contine operatiile comune de traversare. In continuare vom putea defini clase abstracte pentru iteratori, care sa fie adecvate fiecarui tip de agregat, asa ca in figura de mai jos:

Problema care apare aici este accea a creerii iteratorului. Daca vrem sa mentinem independenta clientului fata de subclasele concrete ale lui AbstractList, nu putem instantia un anumit iterator concret. De aceea, vom pasa responsabilitatea creerii iteratorului chiar claselor agregat, incluzand in interfata lor operatia CreateIterator. Aceasta operatie se realizeaza aplicand sablonul FactoryMethod, unde cele doua ierarhii paralele sunt AbastractList si Iterator.

Motivatii

Sablonul Iterator se aplica pentru:

a accesa elementele unui agregat, fara a se cunoste reprezentarea interna a acestuia;
a permite traversari multiple simultane ale aceluiasi agregat;
a crea o interfata uniforma in vederea traversarii diferitelor structuri de agregate (cu alte cuvinte, pentru a crea suportul iterarii polimorfice).

Solutie
In figura de mai jos este data structura de clase care constituie sablonul Iterator:

Iterator - defineste interfata pentru accesarea si traversarea elementelor agregatului;

IteratorConcret

implementeaza interfata Iterator;
tine evidenta pozitiei curente la traversarea agregatului;

Agregat - defineste interfata pentru crearea unui obiect Iterator;

AgregatConcret - implementeaza interfata de creare a iteratorului, sub forma:

return new ConcreteIterator(this);

Consecinte

Exista 3 consecinte importante:

1. Sablonul Iterator ofera posibilitatea de a modifica tipul de traversare a unui agregat. Exista agregate care pot fi traversate in mai multe feluri. De exemplu, intr-un compilator, analiza semantica si generarea de cod se fac in timpul traversarii arborelui sintactic. Acesta poate fi parcurs in inordine sau in preordine. Pentru a schimba tipul parcurgerii doar se inlocuieste iteratorul.
2. Iteratorul simplifica interfata Agregat, care nu mai trebuie sa contina operatii specifice parcurgerii (parcurgerilor).
3. Deoarece fiecare instanta a unui iterator pastreaza pozitia elementului curent pe durata parcurgerii unui agregat, este posibil ca acelasi agregat sa fie parcurs in paralel prin intermediul a mai multi ietartori.

Implementare

Un aspect fundamental in ceea ce priveste implementarea il constituie modul in care este controlata iterarea, mai precis cine este cel care controleaza iterarea: clientul sau iteratorul? Cand clientul controleaza iterarea, iteratorul se numeste iterator extern si presupune ca clientul realizeaza avansul in cadrul agregatului (apeland metoda Next) si solicita explicit iteratorului accesul la elementul curent. Cand iteratorul controleaza iterarea, el se numeste iterator intern. Iteratorul intern executa singur parcurgerea agregatului, aplicand asupra fiecarui element o anumita operatie, specificata la inceput de client.
Iteratorii externi sunt mai flexibili decat cei interni si anumite tipuri de operatii se pot realiza numai cu iteratori externi. De exemplu, compararea a doua colectii este practic imposibil de realizat cu iteratori interni.
Iteratorul nu este singurul loc in care se poate defini algoritmul de traversare a unui agregat. Algoritmul poate fi definit in agregat, iar iteratorul este folosit atunci doar pentru a memora stadiul curent al traversarii. In acest caz iteratorul se numeste cursor. Clientul va invoca operatia Next dand cursorul ca argument, iar operatia Next va modifica starea interna a cursorului.
Daca traversarea este definita in iterator, este mai usor sa se aplice diferiti algoritmi de parcurgere asupra unui agregat, respectiv sa se aplice acelasi algoritm asupra mai multor agregate diferite. Daca un anumit algoritm de traversare necesita accesul la variabile private ale agregatului, nu este recomandabil ca el sa fie plasat in iterator.
Iteratori robusti. Un iterator robust este priectat in asa fel incat daca pe durata traversarii au loc modificari ale agregatului (insertii sau eliminari de elemente), acestea sa nu afecteze traversarea si fara ca, in acest scop, sa se realizeze copii ale agregatului. O solutie a acestei probleme ar fi sa ca agregatul sa tina o evidenta a iteratorilor pe care i-a creat si cand are loc o insertie sau o stergere de element agregatul sa ajusteze starea interna a iteratorilor sai.
Interfata minimala a unui iterator consta din operatiile: First, Next, IsDone si CurrentItem care pot fi realizate ca atare (adica separat) sau putem comasa intr-o singura operatie (Next, de exemplu) functiile Next, IsDone si CurrentItem. Pe langa acestea, mai pot fi utile operatii ca Previous (daca agregatul presupune o anumita ordine a elementelor) sau SkipTo (pentru agregate sortate sau indexate).
Realizarea iteratorilor polimorfici in C++. Iteratorii polimorfici presupun alocare dinamica si, din acest motiv, ei vor fi utilizati doar daca sunt absolut necesari. Fiind alocati dinamic, clientul are responsabilitatea dealocarii lor, motiv pentru care programele care utilizeaza iteratori polimorfici sunt expuse erorilor cauzate de omiterea dealocarii. Acesta omisiune devine cu atat mai probabila, cu cat secventa care lucreaza cu iteratorii respectivi are mai multe puncte de iesire, respectiv cand au loc emiteri de exceptii.
In sprijinul rezolvarii unor asemenea situatii exista solutia utilizarii unei clase infasuratoare pentru pointerul prin care se creaza iteratorul si aplicarea principiului "alocarii resurselor prin initializare" (v. Lucrarea nr.9, laboratorul IP1), asa cum este ilustrat in secventa de mai jos:

class Iterator;
class IteratorPtr {
    public:
        IteratorPtr (Iterator *i) : ii( i ) { }
        ~IteratorPtr( ) { delete ii; }
        Iterator operator->( ) { return ii; }
        Iterator operator*( ) { return *ii; }
    private:
        IteratorPtr(const IteratorPtr&);
        IteratorPtr& operator=(const IteratorPtr&);
        //punand in private copy-constructorul si operatorul de asignare
        //se evita situatiile de stergere multipla a lui ii, posibil sa fie
        //cauzate prin copiere/asignare
        Iterator *ii;
};
AbstractList *oLista;
//. . .
IteratorPtr iterator( oLista -> CreateIterator( ) );

Pentru cresterea sigurantei, obiectele IteratorPtr se recomanda a fi create doar static (in stiva). In acest scop se poate aplica urmatoarea solutie: se plaseaza in sectiunea private operatorii new si delete pentru clasa IteratorPtr. Astfel, orice tentativa de a crea dinamic obiecte IteratorPtr va fi sanctionata la compilare.

Tema
Se cere sa se aplice sablonul Iterator la realizarea unui program in care sunt definite urmatoarele agregate: lista inlantuita, multime si arbore binar. Elementele agregatului vor avea definit operatorul '+' (se lasa la latitudinea programatorului sa defineasca tipul nodurilor agregatului si semnificatia operatorului '+').
Pentru acestea se vor crea cate un iterator extern si unul intern. Iteratorul intern se va folosi pentru urmatoarele operatii:

afisarea informatiilor din elementele agregatelor
aplicarea operatorului '+' cu un argument dat asupra fiecarui element din agregat.