Lexi's Leetcode solutions

[design pattern] iterator pattern

Posted on: August 22, 2013

Iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container’s elements. The iterator pattern decouples algorithms from containers; in some cases, algorithms are necessarily container-specific and thus cannot be decoupled. It provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

这个模式可以保证不同的容器统一用一个interface来traverse,比如正常用for的话,array的traverse要用arr[i],arrayList的要用get(i),map更是得map.entrySet.get..,各种syntax不同,所以即使对每个element干的事儿一样,traverse也要写三遍,太麻烦了。如果用iterator,所有traverse统一用next()就行了。具体iterator是怎么next()的,自己再在容器里面写(大不了就三个容器都implement MyContainer,全写一遍next()函数对于该容器是怎么取下一个的。反正一劳永逸,next()一旦定义了,以后任何client都可以随便用)。其实对于ArrayList, Map之类这么长用的,java已经都给写好了iterator (e.g. List list = new List(); Iterator it = list.iterator();)。下面是例子:

  1. Container要implement Iterable<Type>
  2. Container里面写个implement Iterator<Type> 的iterator inner class
  3. Container里要有个iterator() method用来生成一个iterator
  4. Inner iterator class里面implement next(), hasNext()两个method.
public class TreeInPreOrderIterable implements Iterable<TreeNode> {
  private TreeNode root;
  private class TreeIterator implements Iterator<TreeNode> {
    Stack<TreeNode> stack;
    private TreeIterator(TreeNode root) {
      stack = new Stack<TreeNode>();
      if (root != null)
        stack.push(root);
    }
    @Override
    public TreeNode next() {
      if (hasNext()) {
        TreeNode pop = stack.pop();
        if (pop.right != null)
          stack.push(pop.right);
        if (pop.left != null) 
          stack.push(pop.left);
        return pop;
      } else {
        throw new NoSuchElementException(); 
      }
    }
    @Override
    public boolean hasNext() {
      return !stack.isEmpty();
    }
  }
  @Override
  public Iterator<TreeNode> iterator() {
    return new TreeIterator(this.root);
  }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: