欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

设计模式之迭代器模式(Iterator)

程序员文章站 2024-03-22 09:14:46
...

设计模式之迭代器模式(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;
    }