管理好聚集——迭代子(Iterator)模式

Posted by 李小武 on May 13, 2010

迭代子模式为遍历聚集提供了统一的接口方法,从而使得客户端不需要知道聚集的内部结构就能就能对聚集进行遍历等操作。

迭代子模式的结构

一般结构:

涉及到的角色解释:

  • 抽象迭代子(Iterator)角色:定义了遍历聚集的接口。

  • 具体迭代子(ListIterator)角色:实现了抽象迭代子接口。

  • 抽象聚集(Collection)角色:定义聚集的公共方法,并为聚集创建迭代子(Iterator)对象。

  • 具体聚集(ArrayList)角色:能够返回一个实现迭代子(Iterator)接口的迭代子实例。

  • 客户端(Client)角色:持有对聚集和迭代子实例的引用,通过迭代子对聚集进行迭代。

一个例子:

类图:

抽象迭代子(Iterator)角色:

/**
 * <b>迭代器接口。</b>
 * <p><b>详细说明:</b></p>
 * <!-- 在此添加详细说明 -->
 * 无。
 * <p><b>修改列表:</b></p>
 * <table width="100%" cellSpacing=1 cellPadding=3 border=1>
 * <tr bgcolor="#CCCCFF"><td>序号</td><td>作者</td><td>修改日期</td><td>修改内容</td></tr>
 * <!-- 在此添加修改列表,参考第一行内容 -->
 * <tr><td>1</td><td>Oliver</td><td>May 14, 2010 9:30:38 AM</td><td>建立类型</td></tr>
 *
 * </table>
 * @version 1.0
 * @author Oliver
 * @since 1.0
 */
public interface Iterator
{
    /**
     * <b>指针移动到聚集开头。</b>  
     * <p><b>详细说明:</b></p>
     * <!-- 在此添加详细说明 -->
     * 无。
     */
    void first();
    /**
     * <b>获取当前指针指向的元素。</b>  
     * <p><b>详细说明:</b></p>
     * <!-- 在此添加详细说明 -->
     * 无。
     * @return
     */
    Object next();
    /**
     * <b>是否有下一个元素。</b>  
     * <p><b>详细说明:</b></p>
     * <!-- 在此添加详细说明 -->
     * 无。
     * @return
     */
    boolean hasNext();
} 

具体迭代子(ListIterator)角色:  

public class ListIterator implements Iterator
{
    private Collection collection;

    private int index=0;

    private int size=0;

    public ListIterator(Collection collection)
    {
        this.collection=collection;
        size=collection.size();
    }
    /**
     * <b>获取聚集中当前指针指向的元素。</b>  
     * @see oliver.designpattern.iterator.Iterator#next()
     */
    public Object next()
    {
        return collection.getElement(index++);
    }
    /**
     * <b>指针移动到聚集的开头。</b>  
     * @see oliver.designpattern.iterator.Iterator#first()
     */
    public void first()
    {
        index=0;
    }
    /**
     * <b>是否有下一个元素。</b>  
     * @see oliver.designpattern.iterator.Iterator#hasNext()
     */
    public boolean hasNext()
    {
        return index<size;
    }
}

抽象聚集(Collection)角色:

/**
 * <b>抽象聚集类。</b>
 * <p><b>详细说明:</b></p>
 * <!-- 在此添加详细说明 -->
 * 无。
 * <p><b>修改列表:</b></p>
 * <table width="100%" cellSpacing=1 cellPadding=3 border=1>
 * <tr bgcolor="#CCCCFF"><td>序号</td><td>作者</td><td>修改日期</td><td>修改内容</td></tr>
 * <!-- 在此添加修改列表,参考第一行内容 -->
 * <tr><td>1</td><td>Oliver</td><td>May 14, 2010 9:27:47 AM</td><td>建立类型</td></tr>
 *
 * </table>
 * @version 1.0
 * @author Oliver
 * @since 1.0
 */
public abstract class Collection
{
    /**
     * <b>工厂方法:。</b>  
     * <p><b>详细说明:</b></p>
     * <!-- 在此添加详细说明 -->
     * 无。
     * @return 一个迭代子
     */
    public abstract Iterator iterator();

    /**
     * <b>获取聚集大小。</b>  
     * <p><b>详细说明:</b></p>
     * <!-- 在此添加详细说明 -->
     * 无。
     * @return
     */
    public abstract int size();

    /**
     * <b>获取集合元素。</b>  
     * <p><b>详细说明:</b></p>
     * <!-- 在此添加详细说明 -->
     * 无。
     * @param index
     * @return
     */
    public abstract Object getElement(int index);
}  

具体聚集(ArrayList)角色:

public class ArrayList extends Collection
{
    /**
     * 聚集数据。
     */
    private Object[] items = new Object[10];

    /**
     * 当前指针。
     */
    private int currentIndex=0;

    /**
     * <b>向聚集中添加元素。</b>  
     * <p><b>详细说明:实现了聚集大小自动增长</b></p>
     * <!-- 在此添加详细说明 -->
     * 无。
     * @param item
     */
    public void add(Object item)
    {
        if(currentIndex>=items.length)
        {
            Object[] newItems = new Object[items.length+10];
            System.arraycopy(items,0,newItems,0,items.length);
            items=newItems;
        }
        items[currentIndex]=item;
        currentIndex++;
    }

    /**
     * <b>iterator。</b>  
     * @see oliver.designpattern.iterator.Collection#iterator()
     */
    @Override
    public Iterator iterator()
    {

        return new ListIterator(this);
    }
    /**
     * <b>获取聚集大小。</b>  
     * <p><b>详细说明:</b></p>
     * <!-- 在此添加详细说明 -->
     * 无。
     * @return
     */
    public int size()
    {
        return items.length;
    }
    public Object getElement(int index)
    {
        if(index<items.length)
            return items[index];
        else
            throw new IndexOutOfBoundsException();
    }
}  

客户端(Client)角色:

import junit.framework.TestCase;
public class ExternalIteratorTest extends TestCase
{
    /**
     * <b>外禀迭代子测试。</b>  
     * <p><b>详细说明:</b></p>
     * <!-- 在此添加详细说明 -->
     * 无。
     */
    public void testExternalIterator()
    {
        ArrayList list = new ArrayList();
        for(int i=0;i<10;i++)
            list.add(i);
        Iterator it=list.iterator();
        while(it.hasNext())
        {
            System.out.println(it.next());
        }
    }
}  

内禀子,外禀子?

内禀子:

聚集本身不提供访问其内部元素的方法,只有通过聚集内部的迭代子来遍历聚集,这时迭代子是个内部类,是聚集的一部分。

外禀子:

聚集本身提供访问其内部元素的方法,可以通过外部的迭代子来遍历聚集,这时迭代子是个外部类,只维持对聚集的一个引用。

显然,我们上面的例子是一个外禀迭代。

java内部的ArrayList类用的是一个内禀子迭代子。

在jdk中,ArrayList类继承抽象类AbstractList,而在AbstractList中,有一个内部类Itr:

private class Itr implements Iterator<E> {
    /**
     * Index of element to be returned by subsequent call to next.
     */
    int cursor = 0;
    /**
     * Index of element returned by most recent call to next or
     * previous.  Reset to -1 if this element is deleted by a call
     * to remove.
     */
    int lastRet = -1;
    /**
     * The modCount value that the iterator believes that the backing
     * List should have.  If this expectation is violated, the iterator
     * has detected concurrent modification.
     */
    int expectedModCount = modCount;
    public boolean hasNext() {
        return cursor != size();
    }
    public E next() {
        checkForComodification();
        try {
            E next = get(cursor);
            lastRet = cursor++;
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }
    public void remove() {
        if (lastRet == -1)
            throw new IllegalStateException();
        checkForComodification();
        try {
            AbstractList.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        cursor = index;
    }
    public boolean hasPrevious() {
        return cursor != 0;
    }
    public E previous() {
        checkForComodification();
        try {
            int i = cursor - 1;
            E previous = get(i);
            lastRet = cursor = i;
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }
    public int nextIndex() {
        return cursor;
    }
    public int previousIndex() {
        return cursor-1;
    }
    public void set(E e) {
        if (lastRet == -1)
            throw new IllegalStateException();
        checkForComodification();
        try {
            AbstractList.this.set(lastRet, e);
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    public void add(E e) {
        checkForComodification();
        try {
            AbstractList.this.add(cursor++, e);
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

 

内禀子VS外禀子

迭代子有一个很重要的属性就是当前聚集的指针,有了当前的指针,才能进行迭代。如果几个客户端同时迭代一个聚集,假如聚集的迭代子是外禀子,这个是没有问题的,几个客户端持有每个外禀子的独立指针。但是如果聚集的迭代子是内禀子,问题就出现了:几个客户端同时持有内禀子的指针,并且同时对指针进行操作,就不能正常的对集合进行遍历。

使用外禀迭代子的一个重要理由是它可以被几个不同的方法和对象共享和控制,使用内禀子的优点是它不破坏对聚集的封装。

java的设计师在设计AbstractList的时候在聚集定义了内部类Itr作为迭代子,也就是说,设计师不希望客户端随意更换迭代子。

项目源码下载:http://cid-2c8a0dc7c1eb1d71.skydrive.live.com/self.aspx/soft/Design%20Pattern/Iterator.7z