Strutture Dati - Iterator e positions()

Quinto post dedicato alle Strutture Dati, oggi di preciso implementeremo l'interfaccia java.lang.Iterable nelle strutture dati dei post precedenti (vedere il metodo iterator() ). Un Iteratore è un'oggetto che permette di scandire gli elementi di un contenitore a prescindere dalla sua implementazione.

Ci sono due modi di implementare un iteratore:

1. uno è quello di usare una qualsiasi struttura dati che fornisca un accesso sequenziale ai suoi elementi, in questo caso il costruttore dell'iteratore impiegherà tempo O(n) per copiare tutti gli elementi della struttura nell'iteratore; ma l'iteratore creato in questo modo andrà bene per qualunque struttura dati
2. un altro è quello di utilizzare un cursore, cioè una variabile che tenga traccia dell'elemento corrente, in questo modo il costruttore dell'iteratore non dovrà copiare tutti gli elementi della struttura, ma utilizzerà un riferimento ad essa impiegando tempo O(1); lo svantaggio nell'uso di un cursore è quello di dover fornire un'implementazione specifica di Iterator per ogni tipo di Struttura Dati.

Una volta introdotto il concetto di iteratori e iterabilità possiamo aggiungere a tutti i Tipi di Dato Astratto che implementano il concetto di Position, il metodo Iterable<Position<E>> positions()
che restituisce una collezione iterabile contenente le posizioni del TDA come elementi. Per fare ciò, aggiungiamo la firma di questo metodo all'interfaccia PositionList vista nel 3°post di questa serie, e lo implementiamo in tutte le classi che implementano quest'interfaccia.

public class LinkedIterator<E> implements Iterator<E> 

{

private Node<E> nodo;

private int size;

//il costruttore richiede tempo O(n) per copiare gli elementi

public LinkedIterator(E[] a)

{

nodo = null;

size = a.length;

for(int i=size-1; i>=0; i--)

{

Node<E> tmp = new Node<E>(a[i],nodo); 

nodo = tmp;

}

}

public boolean hasNext() 

{

return (size>0);

}

public E next() 

{

E tmp = nodo.getElement();

remove();

return tmp;

}

public void remove() 

{

if (!hasNext())

throw new NoSuchElementException();

nodo = nodo.getNext();

size--;

}

}

public class ElementIterator<E> implements Iterator<E>

{

private PositionList<E> lista;

private Position<E> cur;

//il costruttore di questa classe impiega tempo O(1)

//a differenza di quello di LinkedIterator che ne impiegava O(n) 

public ElementIterator(PositionList<E> L)

{

lista = L;

if (!L.isEmpty())

cur = L.first();

}

public boolean hasNext() 

{

return (cur!=null);

}

public E next() throws NoSuchElementException

{

if (lista.isEmpty())

throw new NoSuchElementException("Lista vuota! next() non possibile");

E tmp = cur.element();

if (cur == lista.last())

cur = null;

else

cur = lista.next(cur);

return tmp;

}

public void remove() {}

}

public class IndexListIterator<E> implements Iterator<E> 

{

private IndexList<E> a;

private int i;

public IndexListIterator(IndexList<E> A)

{

a = A;

if (!a.isEmpty())

i = 0;

}

public boolean hasNext() 

{

return (i < a.size());

}

public E next() throws NoSuchElementException

{

if (a.isEmpty())

throw new NoSuchElementException("Array vuoto! next() non possibile");

return a.get(i++);

}

public void remove() { }

}

public class TestIteratorAndPositions {

public static void main(String[] args) {

ArrayIndexList<Integer> l = new ArrayIndexList<Integer>();

ArrayIndexSequence<Integer> s = new ArrayIndexSequence<Integer>();

NodeSequence<Integer> s2 = new NodeSequence<Integer>();

NodePositionList<Integer> l2 = new NodePositionList<Integer>();

for(int i=1; i<=10; i++)

l2.addLast(i*4);

System.out.println(l2);

Iterator<Integer> iter = l2.iterator();

System.out.println("Stampa NodePositionList con iterator()");

while(iter.hasNext())

System.out.print(iter.next()+" ");

Iterable<Position<Integer>> posIt = l2.positions();

Iterator<Position<Integer>> posIterator = posIt.iterator();

System.out.println("\nStampa NodePositionList con positions()");

while(posIterator.hasNext())

System.out.print(posIterator.next() + " ");

for(int i=0; i<10; i++)

s.add(i, (i+1)*2);

System.out.println("\n\n"+s);

Iterator<Integer> it = (IndexListIterator<Integer>) s.iterator();

System.out.println("Stampa sequenza con iterator()");

while(it.hasNext())

System.out.print(it.next() + " ");

posIt = s.positions();

posIterator = posIt.iterator();

System.out.println("\nStampa sequenza con positions()");

while(posIterator.hasNext())

System.out.print(posIterator.next() + " ");

for(int i=0; i<10; i++)

s2.add(i, (i+1)*5);

System.out.println("\n\n"+s2);

it = (Iterator<Integer>) s2.iterator();

System.out.println("Stampa sequenza con iterator()");

while(it.hasNext())

System.out.print(it.next() + " ");

posIt = s2.positions();

posIterator = posIt.iterator();

System.out.println("\nStampa sequenza con positions()");

while(posIterator.hasNext())

System.out.print(posIterator.next() + " ");

for(int i=0; i<10; i++)

l.add(i, (i+1)*3);

System.out.println("\n\n"+l);

it = (IndexListIterator<Integer>) l.iterator();

System.out.println("Stampa lista con iterator()");

while(it.hasNext())

System.out.print(it.next() + " ");

}

}