Chapter 4 - Iterator Pattern
기본 아이디어
Iterator 패턴은 복합 객체 요소를 복합 객체의 구현을 노출시키지 않으면서 순회할 수 있는 방벙를 제공해준다.
Iterator의 실체화 코드
public final class ArrayIterator implements Iterator
{
private int position = 0;
private final Object[] items;
/**
* Create and <code>ArrayIterator</code>.
* @param items the array whose elements will be returned,
* in turn, by each {@link #next} call.
*/
public ArrayIterator(Object[] items){ this.items = items; }
public boolean hasNext()
{
return ( position < items.length );
}
public Object next()
{
if( position >= items.length )
throw new NoSuchElementException();
return items[ position++ ];
}
public void remove()
{
throw new UnsupportedOperationException(
"ArrayIterator.remove()");
}
/** Not part of the Iterator interface, returns the data
* set in array form. A clone of the wrapped array
* is actually returned, so modifying the returned array
* will not affect the iteration at all.
*/
public Object[] toArray()
{
return (Object[]) items.clone();
}
}
- Iterator 패턴을 원소를 특정 순서로 순회하도록 실체화할 수도 있다. 자료 구조의 내부 구현을 노출시키지 않으면서 순회할 수 있는 방법을 제공하는 것이 Iterator 패턴의 의도이면, 순회의 순서는 편의 따라 구현하면 된다.
- Iterator가 내부 자료 구조를 수정할 수도 있다. 하지만 이러한 경우 Iterator가 내부 잘 구조를 망치치 않도록 주의해야 한다.
단순한 이진 코드를 Passive와 Active Iterator를 구현한 코드
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import javax.print.DocFlavor.STRING;
public class Tree
{
private Node root = null;
private static class Node
{
public Node left, right;
public Object item;
public Node( Object item )
{
this.item = item;
}
}
// A Passive (internal) iterator
public interface Examiner
{
public void examine( Object currentNode );
}
public void traverse( Examiner client )
{
traverseInOrder( root, client );
}
private void traverseInOrder(Node current, Examiner client)
{
if( current == null)
return;
traverseInOrder(current.left, client);
client.examine (current.item );
traverseInOrder(current.right, client);
}
public void add( Object item )
{
if( root == null )
root = new Node( item );
else
insertItem( root, item );
}
//-------------------------------------------------------------
// An Active (external) iterator
//
public Iterator iterator()
{
return new Iterator() //자바는 interface의 익명 impemetation이 가능한다. C#는 불가
{
private Node current = root;
private LinkedList stack = new LinkedList();
public Object next()
{
while( current != null )
{
stack.addFirst( current );
current = current.left;
}
if(stack.size() != 0 )
{
current = (Node)( stack.removeFirst() );
Object toReturn=current.item;
current = current.right;
return toReturn;
}
throw new NoSuchElementException();
}
public boolean hasNext()
{
return !(current==null && stack.size()==0);
}
public void remove()
{
throw new UnsupportedOperationException();
}
};
}
private void insertItem( Node current, Object item )
{
if(current.item.toString().compareTo(item.toString())>0)
{
if( current.left == null )
current.left = new Node(item);
else
insertItem( current.left, item );
}
else
{
if( current.right == null )
current.right = new Node(item);
else
insertItem( current.right, item );
}
}
public static void main( String[] args )
{
Tree t = new Tree();
t.add("D");
t.add("B");
t.add("F");
t.add("A");
t.add("C");
t.add("E");
t.add("G");
Iterator i = t.iterator();
//Active Iterator를 사용
while( i.hasNext() )
System.out.print( i.next().toString() );
System.out.println("");
//Passive Itrerator를 사용
t.traverse( new Examiner()
{
public void examine(Object o)
{
System.out.print( o.toString() );
}
}
);
System.out.println("");
}
}
트리를 방문하는 Active(External Iterator)를 구현한다고 생각해보자. Tree 클래스의 iterator() 메소드 는 트리의 각 노드를 중위(inorder) 순위로 방문하는 java.utiil.iterator를 반환한다. 이 코드는 매우 불분명하다. 알고리즘은 단순하지만 이해하기 어렵고 작성하기도 어렵다. (트리를 순회할 때 부모 노드를 기억하기 위해 스택을 사용)
하지만 Passive Iterator는 단순한 재귀 함수이며 작성하기 쉽다. TraverseInOrder 메소드는 Passive Iterator의 구현을 보여준다. 이 재귀 순회 알고리즘은 각 노드를 Examiner 객체에 차례로 전달할 뿐이다. 트리의 모든 노드를 Examiner 익명 인터페이스를 구현해서 다음과 같이 출력할 수 있다.
정리
- External Iterator 혹은 Active Iterator는 자신이 순회하는 자료 구조와 분리되어 있다.
- Passive Iterator는 혹은 Internal Iterator 객체를 생성하는 대신 자료 구조 내부에 순회 메커니즘을 구현한다.
- Passive Iterator는 혹은 Internal Iterator 자료 구조가 본질적으로 순회하기 어려운 구조일 때 유용하다.