Iterator Pattern Opgaver

Forudsætninger: Det forudsættes at man har kendskab til packages. Det vil ligeledes være en fordel at man har kendskab til indre klasser, da Iterator Pattern bekvemt lader sig realisere ved anvendelse af disse. Det er dog ikke strengt nødvendigt, da implementation med indre klasser er placeret til sidst i et afsnit for sig.

 

 

	Motivation
Iterere	Når man arbejder med en collection, kan det i visse situationer være nyttigt at iterere (gennemløbe) elementerne - f.eks. hvis man skal beregne den samlede alder af en række personer.
	Hvis vi f.eks. har en linket liste af personer, kan vi beregne deres samlede alder med følgende:
	Der kan være mange objekter i kæden før det sidste element. Vi vil indskrænke os til ét, der vil være en instans af følgende klasse:
Source 1: Iteration af collection med for-løkke	ArrayList<Person> personer; ... int samletAlder = 0; for (int i=0; i<personer.size(); i++) samletAlder += personer.get(i).getAlder();
	En ukompliceret løsning - men der er et problem!
	Problemet er: Hvor skal denne kode stå?
Stærk kobling til collection	Umiddelbart skal den vel stå i klienten. Det betyder at vi får en stærk kobling til ArrayList. Som koden er lavet, skal collection'en være en ArrayList for at den kan håndteres af klienten. At der er tale om instanser af Person er også en kobling, men den slipper vi ikke for, da den følger af, at vi vil beregne den samlede alder af personer i en collection. En tredie ting, er at det er klienten som holder styr på hvor i den linkede liste vi er kommet til - dvs. klienten er fuldt ud klar over at vi arbejder med en listestruktur i containeren. (Det er muligt at anvende en foreach løkke i eksemplet, men vi har valgt ikke at gøre det, for at problematisere situationen).
	Disse betragtninger får os til at ønske et mere dynamisk design; hvor klienten kun ved, at der er tale om personer, og har et mere abstrakt forhold til at gennemløbe collection'ens elementer.
	Problem
	Vi ønsker at kunne iterere en collections elementer uden et konkret kenskab til hvilken slags collection der er tale om, og uden at skulle holde styr på hvor vi er kommet til.
	Løsning
	Den første idé man kunne få, ville være at udstyre vores collection med en række metoder, som vi kunne nøjes med at kalde. Metoderne kunne f.eks. være:
	boolean next() Object current()
next	Med et kald af next kan vi bevæge os ét element frem i listen. Ved gentagne gange at kalde next vil vi kunne gennemløbe samtlige elementer i containeren. Metoderen returnerer boolsk, om man er flyttet frem til det næste element (true), eller der ikke var flere (false).
Before first	Bemærk i den forbindelse at vi ved iterationens start befinder os før det første element (eng.: before first). Det kan måske synes mærkeligt at vælge en sådan start-placering, hvor der ikke er noget element — vi starter så at sige ude over "kanten". Det skyldes at iterationen rent programmeringsmæssig bliver meget enklere, da vi så blot kan anvende en simpel whileløkke til et gennemløb:
Source 2: Bekvem while-løkke	while (personer.next()) { ... }
	Første gang next kaldes, vil man blive placeret ved det første element, og metoden vil returnere true (hvis der er ellers er nogen elementer i collection'en). Når alle elementer er itereret igennem vil next returnerer false, og løkken vil terminere.
current	Dernæst kan vi kalde current, for at aflæse det element som vi er kommet til. I eksemplet ovenfor ville current returnere den instans af Person som vi var kommet til.
	Disse metoder kaldes i almindelighed "iterator-metoder", fordi de understøtter iteration.
	Løsningen med iterator-metoder på en collection er for så vidt udemærket. Den virker, og vi opnår en løsere kobling til collection'en i forbindelse med iterationen af dens elementer. Der er blot et problem!
Kun én klient	Problemet er, at kun én klient af gangen kan iterere på elementerne i collection'en. Hvis flere klienter samtidig vil iterere over collection'ens elementer, vil den ikke være i stand til at skelne mellem hvor de to klienter er kommet til, da den ikke ved hvem der kalder dens iterator-metoder.
Iterator- objekt	Løsningen er nogenlunde intuitiv. Hvis det itererende i containeren kun kan håndtere én klient, skal vi blot have flere itererende "dele". Disse itererende dele, blive egne objekter, som bruges til at iterere på containeren. Det betyder at iterator-metoderne ikke længere findes i collection'ens interface, men i det itererende objekts interface: Iterator-objektet.
Fabriks-metode	Det er nu Iterator-objektets opgave at være itererende mellemled mellem klient og collection, men hvorfra får klienten et Iterator-objekt? Klienten kunne selv instantiere det, men det vil normalt betyde, at klienten skal have et konkret kendskab til collection'en. Derfor vælger man i stedet at lade collection'en instantiere iteratoren, med en fabriksmetode som klienten kalder.
	Med uafhængige iteratorer kan et vilkårligt antal klienter nu iterere på collection'en, blot de hver har deres eget Iterator-objekt.
	Klassediagram
	I Iterator Pattern kalder man generelt collection'en: Aggregatet:
Figur 1: Klasse-diagrammet
	Interaktion
	Interaktionen forløber i to dele:
Figur 2: Gentagne kald af current og next
	Efter klienten har fået en iterator fra ConAggregate, foregår resten af interaktionen med iteratoren. Det er her illustreret hvordan klienten gentagne gange kalder next og current for at aflæse det aktuelle element. Fra det sidste kald af next får klienten besked om, at der ikke er flere elementer (next returnerer false).
	Implementation
	Iterator-metoderne er normalt simple at implementere. Det væsentligste implementations-problem er normalt forholdet mellem ConIterator og ConAggregate.
Adgang til data i Aggregatet	Iteratoren har generelt brug for at kunne tilgå Aggregates datakerne meget konkret - ofte mere end vi ønsker at andre objekter skal kunne. Dette kan realiseres med en package! (vi skal dog senere se hvordan det mere elegant kan laves med indre klasser).
Protected	Man placerer de to interfaces og de to (eller flere) realiseringer i en package. Dernæst lader man Aggregates get-metoder være protected. På den måde sikrer man sig at iteratoren kan kalde dem, men at klienten ikke kan.
Bryde indkapsling	Man kan evt. lade Aggregatets datakerne være protected; hvilket ofte gør iteratoren simplere. Det er ikke så "kriminelt" som det umiddelbart lyder, da indkapslingen trods alt kun er brudt i forhold til de andre klasser i dens package.
	Robust iterator
	En iterator er robust; hvis den kan tåle at Aggregatet ændrer sig under iterationen. Det vil sige, at iteratoren kan håndtere, at der indsættes eller fjernes elementer fra containeren mens den er igang med at iterere.
Sletning er det største problem	Disse ændringer kan være mere eller mindre kritiske for en iterator. Hvis aggregatet er implementeret med f.eks. en linket liste, vil indsættelse af elementer normalt ikke give nogen problemer, mens sletning kan være fatalt. Tænk f.eks. på den situation hvor en iterator er ved at gennemløb en linket liste, og containeren vælger at slette iteratorens aktuelle element - i den situation kan iteratoren står med et element der ikke længere er en del af listen, og hvor next ikke fører nogen steder hen.
Observer Pattern	De fleste robuste iteratorer er afhængige af at være registreret hos Aggregatet, som så vil oplyse iteratoren om ændringer, og evt. justerer iteratorens tilstand (dvs. hvor den er kommet til). En sådan opdatering vil bekvemt kunne laves med Observer Pattern, men det vil nornalt stadig være en udfordring for iteratoren at forholde sig til en sådan ændring; hvis den vedrører det aktuelle element. Robuste iteratorer er normalt vanskelige at lave, og ses ikke så ofte.
	Eksterne og interne iteratorer
Ekstern	En iterator som klienten styrer, ved at kalde diverse iterator-metoder, kaldes en ekstern iterator. Det er eksterne iteratorer vi har lagt op til i det foregående, og langt de fleste iteratorer i den virkelige verden er eksterne iteratorer.
Intern	En intern iterator styrer selv iterationen. Klienten giver iteratoren en "operation" som skal udføres på alle elementer i Aggregatet. Iteratoren gennemløber selv Aggregatets elementer og udfører/kalder operationen, der normalt vil være en metode i et objekt som iteratoren har modtaget fra klienten. Denne konstruktion anvendes også i forbindelse med Visitor Pattern.
	Eksempel: Array af integers
	Lad os konstruere et simpelt eksempel hvor Aggregatets datakerne er et array af integers. Vi vil se dette eksempel, først med en ekstern iterator og dernæst med en intern iterator.
	Bemærk, at vi i de følgende eksempler med integers, arbejder direkte med tallene og ikke med objekter. Det skyldes at vi gerne vil bruge heltal for at gøre det enklere, men samtidig ikke komplicere eksemplerne ved at forholde os til problematikken i Java, med at integers ikke er objekter.
	Ekstern iterator
	Vi vil først se hvordan vi kan lave en ekstern iterator til ArrayAggregate:
Figur 3: Klassediagram med ekstern iterator
	Vi vælger at placere de to interfaces og de to realiseringer i en package array, idet vi gør de to get-metoder protected, da de er tiltænkt ArrayIterator - og i særdeleshed ikke klienten.
	Lad os først se Aggregates interface og realisering:
Source 3: Aggregate	package array; public interface Aggregate { public Iterator createIterator(); }
Source 4: ArrayAggregate	package array; public class ArrayAggregate implements Aggregate { private int[] array; public ArrayAggregate(int[] array) { this.array = array; } public Iterator createIterator() { return new ArrayIterator(this); } protected int get( int index ) { return array[index]; } protected int size() { return array.length; } }
	get- og size-metoderne giver iteratorer den fornødne adgang til Aggregatet.
	Lad os dernæst se iteratorens interface og realisering:
Source 5: Iterator	package array; public interface Iterator { public boolean next(); public int current(); }
Source 6: ArrayIterator	package array; public class ArrayIterator implements Iterator { private ArrayAggregate aggregate; private int index; public ArrayIterator( ArrayAggregate aggregate ) { this.aggregate = aggregate; index = -1; // before first (eg. first == 0) } public boolean next() { if (index + 1 < aggregate.size()) { index++; return true; } else return false; } public int current() { return aggregate.get(index); } }
	next sikrer sig at den ikke "falder ud over kantet" - med andre ord, at det nye index vil svare til et element i Aggregatet.
	Bemærk at ArrayIterator ikke er en public klasse. I modsætning til den anden realisering: ArrayAggregate er det ikke nødvendigt at foretage instantiering udenfor klassen, ej heller have referencer af typen ArrayIterator, da vi altid kan bruge refernecer af det mere abstrakte Iterator-interface.
	Endelig har vi en testanvendelse. Bemærk at vi har lavet en inddeling, der præciserer hvad der udgør klienten i vores test:
Source 7: Klient anvender iterator	import array.*; public class Main { public static void main(String[] args) { int[] list = { 2, 3, 5, 7, 11, 13, 17, 19 }; Aggregate aggregate = new ArrayAggregate(list); // Klient start Iterator iterator = aggregate.createIterator(); while (iterator.next()) System.out.print(iterator.current() + " "); System.out.println(); // Klient slut } } 2 3 5 7 11 13 17 19
	Bemærk hvordan vi tilstræber at arbejde med abstrakte referencer.
	Intern iterator
	Lad os nu i stedet se, hvordan vi kan lave en intern iterator til vores ArrayAggregate:
Figur 4: Klassediagram med intern iterator
	Den grå baggrundsfarve i klassediagrammet, markerer de klasser der ikke skal ændres fra det foregående eksempel med den eksterne iterator.
	Alle ovenstående klasser (pånær Client) placeres i en package: array.
Aggregatet	De to Aggregate-klasser vil vi anvende uforandret, fordi det ikke betyder noget for Aggregate om iteratorerne er interne eller eksterne.
Iteratoren	Derimod er det nødvendigt at ændre Iterator-klasserne. De skal nu have en iterate-metode, der selvstændigt kan gennemløbe elementerne i aggregatet. Dermed er det iteratoren der styrer selve iterationen. Til gengæld er det ikke den som bestemmer hvad der skal ske med de enkelte elementerne under gennemløbet. Denne funktionalitet lægges ud i en andet objekt — en IteratorMethod.
Funktionali- teten	iterate-metoden tager en IteratorMethod som parameter, og gennemløber aggregatets elementer. For hvert element kalder den operation-metoden, som udfører den ønskede funktionalitet på elementet.
Ændringer	At operation returnerer et element gør det teknisk muligt for os at lave implementationer der ændrer elementerne i aggregatet. Ellers ville dette kræve at elementet var en instans af en mutabel klasse; hvilket vi ikke altid kan regne med. I vores eksempel med integers er det i særdeleshed nødvendigt, da parameteren til operation-metoden er en value-parameter og ikke et objekt.
	Lad os se et eksempel på en realisering af IteratorMethod:
Udskriver element	import array.*; class Printer implements IteratorMethod { public int operation( int element ) { System.out.print( element + " " ); return element; } }
	Funktionaliteten består i at udskrive elementet. I samspil med iterate-metoden får vi udskrevet samtlige elementer i aggregatet — rækkefølgen bestemmes af iterate-metoden.
	Lad os se implementationen af ArrayIterator:
iterate-metoden gennemløber elementerne	package array; class ArrayIterator implements Iterator { private ArrayAggregate aggregate; public ArrayIterator( ArrayAggregate aggregate ) { this.aggregate = aggregate; } public void iterate( IteratorMethod method ) { for ( int i=0; i<aggregate.size(); i++ ) aggregate.set( i, method.operation( aggregate.get( i ) ) ); } }
	Bemærk i øvrigt, at vi har udvidet ArrayAggregate med en set-metode for at muliggøre det tredie skridt (I figur 4, har vi dog undladt at markere ArrayAggregate som ny/ændret klasse, da denne tilføjelse er så ubetydelig i omfang).
	Implementation med indre klasser
	Eftersom packages og indre klasser er konstruktioner der har visse fællestræk, kan vi i stedet basere iteratorens adgang til aggregatet på indre klasser. Som vi skal se, er dette en mere elegant løsning, da koblingen mellem iteratoren og aggregatet er så stærk og så ensidigt går den ene vej.
	Da en package ikke vil spille en væsentlig rolle i forbindelse med vores anvendelse af indre klasser, vil vi fjerne package array, og i stedet placere klasserne på samme niveau som vores testanvendelse. Dette betyder ikke, at man ikke kan/bør anvende en package, men at vi vil koncentrere os om en løsning med indre klasser.
	Først gør vi Iterator til et indre interface i Aggregate,
	public interface Aggregate { public Iterator createIterator(); public interface Iterator { public boolean next(); public int current(); } }
	og ArrayIterator gøres til en indre klasse i ArrayAggregate:
	public class ArrayAggregate implements Aggregate { private int[] array; public ArrayAggregate( int[] array ) { this.array = array; } public Iterator createIterator() { return new ArrayIterator(); } private int get( int index ) { return array[ index ]; } private int size() { return array.length; } private class ArrayIterator implements Iterator { private int index; public ArrayIterator() { index = -1; // before first (eg. first == 0) } public boolean next() { if ( index + 1 < size() ) { index++; return true; } else return false; } public int current() { return get( index ); } } }
	Man bemærker at både AggregateIterator, get- og size-metoden nu kan gøres private (idet vi stadig antager at get- og size-metoderne kun er tiltænkt iteratoren), og at det som en konsekvens af den indre klasse, ikke længere er nødvendigt for iteratoren at have en reference til aggregatet.
	Vores testanvendelse (Main.java) skal kun ændres på et punkt:
	Aggregate.Iterator iterator = aggregate.createIterator();
	idet vi nu skal angive klasse-stien indtil det indre interface Iterator.
	Iteratorer i Java
	Vi vil i det følge se nærmere på Java's egne iteratorer.
	java.util.Enumeration
Nærmest deprecated	Det er måske en overdrivelse at betegne Enumeration som deprecated (forældet), men det anbefales at man primært anvender Iterator, som vi skal se om lidt. Inden da, vil vi dog først se nærmere på den lidt "mindre" iterator Enumeration — mindre i den forstand at interfacet har færre metoder end Iterator.
Figur 5: Enumeration interfacet
	Enumeration er kun understøttet af fabriksmetoder i Directory-, Hashtable- og Vector-klasserne; hvoraf Hashtable vel nærmest selv er deprecated.
String- Tokenizer	Reelt er det eneste interessante ved Enumeration, at StringTokenizer realiserer den. Dermed bliver Enumeration-interfacets metoder til iterator-metoder direkte i StringTokenizer's interface. Der er dermed ikke tale om Iterator Pattern, da der ikke er noget selvstændigt Iterator-objekt.
	Vil man have en Enumerator til at iterere på en vilkårlig Collection-klasse kan det godt lade sig gøre, men man er nød til at bruge en statisk fabriksmetode i Collections-klassen:
	Enumeration Collections.enumeration( Collection c )
	Som nævnt bør man nok undgå Enumeration, og i stedet bruge Iterator:
	java.util.Iterator
	Som nævnt er Iterator's interface lidt større - én metode større!
Figur 6: Iterator interfacet
	To af metoderne hedder blot noget andet end i Enumeration-interfacet, det eneste nye er muligheden for at slette det aktuelle element - dvs. det element som senest er blevet returneret af nextElement-metoden.
	I modsætning til Enumeration, har alle Collection-klasser en fabriksmetode der returnerer en Iterator:
	Iterator iterator()
	java.util.ListIterator
	Klasserne: LinkedList, ArrayList og Vector tilbyder en udvidet iterator - en ListIterator. Disse klasser har alle (LinkedList har dog kun den første) fabriksmetoderne:
	ListIterator listIterator() ListIterator listIterator( int index )
	der returner en sådan iterator.
	Metoden der tager en parameter, returnerer en iteratorer, der arbejder med den del af listen, der starter ved det pågældende index.
	Som det ses i figur 6, består udvidelsen i to dele: Den giver mulighed for at iterere baglæns, og giver mulighed for enten at tilføje eller erstatte elementer.
	Varianter
	Cursor Varianten
En iterator, der ikke kan iterere	Man kunne kalde en Cursor: "En iterator, der ikke kan iterere (selv)". En Cursor er i virkeligheden blot en positions-wrapper. Selve Cursor-objektet indeholder information om en position i Aggregatet, og klienten bruger Cursor'en som et slags bogmærke, klienten giver til Aggregatet hver gang den kalder en af iterator-metoderne. Aggregatet bruger Cursor'en til at afgøre hvor iterationen er nået til, og har mulighed for at justere positionen i Cursor'en.
Figur 7: Klasse-diagram for Cursor-varianten
	Bemærk at Cursor'en ikke har noget behov for at kende Aggregate.
	En typisk interaktion kunne forløbe som det er vist i følgende sekvensdiagram:
Figur 8: Sekvens-diagram for Cursor-varianten
	Man ser hvordan Cursor'en sendes med i hvert kald af iterator-metoderne, som i Cursor-varianten befinder sig i Aggregates interface. Bemærk hvordan Aggregatet i udførelsen af next sender to requests til Cursor'en: Først en request med henblik på at checke om positionen kan tælles én op, og dernæst en request om at gøre det.
	Relationer til andre patterns
	Visitor Pattern
	IteratorMethod-klassen, i den interne iterator, ligner meget Visitor-klassen i Visitor Pattern. I begge tilfælde overlader man det til et andet objekt at bestemme "hvad der skal ske".