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 자료 구조가 본질적으로 순회하기 어려운 구조일 때 유용하다.