设计模式之迭代器模式（Iterator）

本篇为 https://github.com/iluwatar/java-design-patterns/tree/master/Iterator 阅读笔记

意图

提供一种方法顺序访问一个聚合对象中各个元素, 而又无须暴露该对象的内部表示。

优点

1、它支持以不同的方式遍历一个聚合对象。
2、迭代器简化了聚合类。
3、在同一个聚合上可以有多个遍历。
4、在迭代器模式中，增加新的聚合类和迭代器类都很方便，无须修改原有代码。

缺点

由于迭代器模式将存储数据和遍历数据的职责分离，增加新的聚合类需要对应增加新的迭代器类，类的个数成对增加，这在一定程度上增加了系统的复杂性。

场景

1、对List迭代器进行了扩展，使其可以按类型进行迭代
2、模拟二叉排序树，迭代时采用中序遍历

迭代符合ItemType的数据项

迭代接口

public interface Iterator<T> {

    boolean hasNext();

    T next();
}

list迭代扩展

public enum  ItemType {
    ANY, WEAPON, RING, POTION
}

public class Item {
    private ItemType type;
    private String name;

    public Item(ItemType type, String name) {
        this.type = type;
        this.name = name;
    }

    @Override
    public String toString() {
        return name;
    }

    public ItemType getType() {
        return type;
    }

    public final void setType(ItemType type) {
        this.type = type;
    }

}

生成item列表，便于测试

public class TreasureChest {

    private List<Item> items;

    public TreasureChest() {
        items = new ArrayList<>();
        items.add(new Item(ItemType.POTION, "Potion of courage"));
        items.add(new Item(ItemType.RING, "Ring of shadows"));
        items.add(new Item(ItemType.POTION, "Potion of wisdom"));
        items.add(new Item(ItemType.POTION, "Potion of blood"));
        items.add(new Item(ItemType.WEAPON, "Sword of silver +1"));
        items.add(new Item(ItemType.POTION, "Potion of rust"));
        items.add(new Item(ItemType.POTION, "Potion of healing"));
        items.add(new Item(ItemType.RING, "Ring of armor"));
        items.add(new Item(ItemType.WEAPON, "Steel halberd"));
        items.add(new Item(ItemType.WEAPON, "Dagger of poison"));
    }

    public Iterator<Item> iterator(ItemType type){
        return new TreasureChestItemIterator(this,type);
    }

    public List<Item> getItems() {
        return items;
    }
}

迭代器类

public class TreasureChestItemIterator implements Iterator<Item> {

    private TreasureChest chest;
    private int idx;
    private ItemType type;

    public TreasureChestItemIterator(TreasureChest chest, ItemType type) {
        this.chest = chest;
        idx = -1;
        this.type = type;
    }

    @Override
    public boolean hasNext() {
        return findNextIdx() != -1;
    }

    @Override
    public Item next() {
        idx = findNextIdx();
        if (idx != -1){
            return chest.getItems().get(idx);
        }
        return null;
    }

    private int findNextIdx(){
        List<Item> items = chest.getItems();
        boolean found = false;
        int tempIdx = idx;
        while (!found){
            tempIdx ++;
            if (tempIdx >= items.size()){
                tempIdx = -1;
                break;
            }
            if (type.equals(ItemType.ANY) || items.get(tempIdx).getType().equals(type)){
                break;
            }
        }
        return tempIdx;
    }
}

测试

 @Test
    public void iteratorTest(){
        Iterator<Item> itemIterator = TREASURE_CHEST.iterator(ItemType.RING);
        while (itemIterator.hasNext()) {
            System.out.println(itemIterator.next().toString());
        }
    }

二叉排序树（中序遍历）

树

public class TreeNode<T extends Comparable<T>> {
    private T val;
    private TreeNode<T> left;
    private TreeNode<T> right;

    public TreeNode(T val) {
        this.val = val;
        this.right = null;
        this.left = null;
    }

    public T getVal() {
        return val;
    }

    public TreeNode<T> getLeft() {
        return left;
    }

    private void setLeft(TreeNode<T> left) {
        this.left = left;
    }

    public TreeNode<T> getRight() {
        return right;
    }

    private void setRight(TreeNode<T> right) {
        this.right = right;
    }

    public void insert(T valToInsert) {
        TreeNode<T> parent = getParentNodeOfValueToBeInserted(valToInsert);
        parent.insertNewChild(valToInsert);
    }

    private TreeNode<T> getParentNodeOfValueToBeInserted(T valToInsert) {
        TreeNode<T> parent = null;
        TreeNode<T> current = this;
        while (current != null) {
            parent = current;
            current = current.traverseOneLevelDown(valToInsert);
        }
        return parent;
    }

    private TreeNode<T> traverseOneLevelDown(T valToInsert) {
        if (this.isGreaterThan(valToInsert)) {
            return this.left;
        }
        return this.right;
    }

    private boolean isGreaterThan(T val) {
        return this.val.compareTo(val) > 0;
    }

    private void insertNewChild(T valToInsert) {
        if (this.isLessThanOrEqualTo(valToInsert)) {
            this.setRight(new TreeNode<>(valToInsert));
        } else {
            this.setLeft(new TreeNode<>(valToInsert));
        }
    }

    private boolean isLessThanOrEqualTo(T val) {
        return this.val.compareTo(val) < 1;
    }

    @Override
    public String toString() {
        return val.toString();
    }
}

中序遍历

public class BaseIterator<T extends Comparable<T>> implements Iterator<TreeNode<T>> {

    private ArrayDeque<TreeNode<T>> pathStack;

    public BaseIterator(TreeNode<T> root) {
        this.pathStack = new ArrayDeque<>();
        pushPathToNextSmallest(root);
    }

    private void pushPathToNextSmallest(TreeNode node){
        while (node != null){
            pathStack.push(node);
            node = node.getLeft();
        }
    }

    @Override
    public boolean hasNext() {
        return !pathStack.isEmpty();
    }

    @Override
    public TreeNode<T> next() {
        if (pathStack.isEmpty()){
            throw new NoSuchElementException();
        }
        TreeNode<T> next = pathStack.pop();
        pushPathToNextSmallest(next.getRight());
        return next;
    }
}

测试

 @Test
    public void treeIteratorTest(){
        TreeNode<Integer> root = buildIntegerBst();
        BaseIterator baseIterator = new BaseIterator(root);
        while (baseIterator.hasNext()){
            System.out.println(MessageFormat.format("Next node:{0}",baseIterator.next().getVal()));
        }

    }

    private TreeNode<Integer> buildIntegerBst(){
        TreeNode<Integer> root = new TreeNode<>(0);
        root.insert(3);
        root.insert(10);
        root.insert(1);
        root.insert(6);
        root.insert(14);
        root.insert(4);
        root.insert(7);
        root.insert(13);
        return root;
    }