设计模式 05 访问数据结构

作者 柚爸
  1. Visitor 访问者模式
  2. 练习13-1
  3. 练习13-2
  4. 练习13-3
  5. Chain of Responsibility 职责链模式
  6. 练习

Visitor 访问者模式

访问者模式用来访问一个数据结构. 虽然在刚学面向对象的时候, 说数据的自身处理和数据放在一起, 集成成为对象.

但如果要解耦的话, 实际上对象和对对象的处理, 是可以分离的, 如果将处理和对象绑在一起, 修改起来很麻烦, 如果将对对象的处理放置到对象之外, 那么就方便很多了, 只需要变更访问者, 就可以改变对对象的处理.

这里要访问的对象就是之前用过的Composite模式中的Entry对象.

重点在于编写不同的访问者. 访问者有一个抽象类叫做Visitor, 然后有具体的访问者. 而为了要让访问者可以访问自己, Entry类还要实现一个访问者接口.来看具体代码.

首先是访问者的基类Visitor:

public abstract class Visitor {

    public abstract void visit(File file);

    public abstract void visit(Directory directory);
}

这里可以看到, 访问者的关键点之一在于使用了重载的方法以适应各个类型.

然后是Element接口, 这里与Composite的不同在于要让Entry类实现Element接口, 以标志这是一个能够被Visitor模式访问的类:

public interface Element {

    void accept(Visitor visitor);

}

接口比较简单, 现在仅仅只有这两个类还看不出来有什么端倪. 现在来修改一下Entry类:

public abstract class Entry implements Element {

    ......

    //这里新增加了一个iterator方法,原理和上边的add一样, 仅能用于Directory类, 父类该方法直接抛异常是为了避免错误调用
    //这个迭代器用来在visit()方法中递归调用
    public Iterator iterator() throws FileTreatmentException {
        throw new FileTreatmentException();
    }

}

可以发现这里仅仅标上了实现接口, 但是没有实现, 由于是抽象类, 所以可以让子类去实现.

下边就来看Entry的子类是如何实现的:

public class File extends Entry {

    ......

    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this);
    }
}

public class Directory extends Entry {

    ......

    @Override
    public void accept(Visitor visitor) {
        visitor.visit(this);
    }
}

注意看, 这里很有意思, 接受访问者访问的对象, 自己调用访问者的访问自身的方法.

这样就是化被动为主动, 即对象使用访问者的方法调用自己.

现在基本上就知道大概了, 即先要有一个数据对象, 然后无论访问者的具体类型, 只要是符合Visitor类型, 就可以让其访问自己, 看ListVisitor实现类:

public class ListVisitor extends Visitor {

    public String currentdir = "";

    @Override
    public void visit(File file) {
        System.out.println(currentdir + "/" + file);
    }

    //这个方法也是递归方法, 直接访问到一棵树的所有叶子, 可以看到递归的对其中的每个Entry对象, 都调用其上的visit方法.
    @Override
    public void visit(Directory directory) {
        System.out.println(currentdir + "/" + directory);
        String savedir = currentdir;

        currentdir = currentdir + "/" + directory.getName();
        //这是递归调用, 即访问一个Directory类型的对象, 会继续递归访问. 这里实际上是Composite模式的应用.
        Iterator<Entry> iterator = directory.iterator();
        while (iterator.hasNext()) {
            Entry entry = iterator.next();
            entry.accept(this);
        }
        //这一行不起眼的也是递归, 即更改了当前的目录到新的拼接后的目录.
        currentdir = savedir;
    }
}

然后就可以来测试了, 想想看, 在Composite模式中, 每个Entry自己有打印自己列表的方法. 现在我们换了一种思路, 即使用访问者来打印:

public class Main {
    public static void main(String[] args) {
        try {
            //和Composite模式中一样的目录结构
            Directory rootdir = new Directory("root");
            Directory bindir = new Directory("bin");
            Directory tmpdir = new Directory("tmp");
            Directory usrdir = new Directory("usr");
            rootdir.addEntry(bindir).addEntry(tmpdir).addEntry(usrdir);
            bindir.addEntry(new File("vi", 10000));
            bindir.addEntry(new File("latex", 20000));
            Directory yukidir = new Directory("yuki");
            Directory hanakodir = new Directory("hanako");
            Directory tomuradir = new Directory("tomura");
            usrdir.addEntry(yukidir).addEntry(hanakodir).addEntry(tomuradir);
            yukidir.addEntry(new File("diary.html", 100));
            yukidir.addEntry(new File("Composite.java", 200));
            hanakodir.addEntry(new File("memo.tex", 300));
            tomuradir.addEntry(new File("game.doc", 400));
            File file = new File("iunk.mail", 500);
            tomuradir.addEntry(file);

            //不再使用Entry对象的方法
            //rootdir.printList();

            Visitor visitor = new ListVisitor();

            visitor.visit(rootdir);

            rootdir.accept(visitor);

        } catch (FileTreatmentException e) {
            System.out.println(e);
        }
    }
}

visitor.visit(rootdir); 和 rootdir.accept(visitor); 这两行代码的效果是一样的, 一个是从访问者发起访问, 一个是从数据对象自己接受访问. 然后最终都是进入到访问的visit方法中进行操作.

因此只需要更换一个访问者, 就可以进行完全不同的操作, 但数据对象完全不需要修改代码, 只有创建访问者的代码需要修改.

这里的互相调用还是比较复杂的, 要理解的是, 只有一个访问者, 这个访问者对于每个数据对象, 都通过数据对象的visitor()访问了一遍. 每个数据结构都只调用一次accept()方法, 即接受了一次访问者的访问.

访问者则每次根据不同类型的对象, 进行不同的处理(直接显示还是递归访问).

Visitor模式有如下几点思考:

  1. 除了访问者 – 被访问者之外, 还有处理方法这个抽象, 只不过处理方法在例子中被写死在了visit方法里(实际上是在Entry类中的那些toString()方法), 如果单独将处理方法抽象出来, 就更复杂
  2. 采用了双重分发的思路, 可以发现visitor.visit()是访问者访问数据, entry.accept()是上一个方法的反向处理, 即自己来接受一个访问者对象. 双重分发一般用在两个类共同决定实际进行的处理时, 这也增加了复杂度, 但是提高了灵活性.
  3. 为何如此复杂, 是为了将处理从数据结构中分离出来, 所以必然要提供一个接口, 用于便利的访问一个数据结构. 将处理分离出来之后, 为了显示目录, 我们完全可以删除Entry内部的那一些toString()和printList()方法, 改成仅仅向外返回数据即可. 访问者根据数据结构的关系, 就可以进行访问. 以后如果要编写新的数据结构, 就可以完全无需编写具体处理方法.
  4. 开闭原则, 对扩展开放, 对修改关闭. 如果想要给数据结构添加新的功能, 在没有引入访问者模式之前, 只能修改数据结构自己的方法, 有了访问者之后, 添加新功能也无需修改数据结构自身, 这就是访问者解耦的一大特点.

在现实中, 一旦要自己制作一个数据结构, 比如数据库中取出对象的列表, 就要想到可能会使用访问者模式. 此外对于嵌套的数据结构, 访问者模式经常和Composite模式以及Iterator模式搭配使用.

谈谈我自己的心得, 访问者模式, 就是让数据结构需要具备一个接口, 与访问者的方法一起构成双重分发, 然后在访问者的方法内部编写实际处理程序. 这样无论来自数据结构内外部, 都走双重分发, 最终找到对应的访问者.

如果不使用双重分发, 站在访问者的角度可以访问结构, 但是反过来就比较麻烦了.

练习 13-1 编写一个查找所有html文件的功能

思路很简单, 不断的递归访问, 遇到html文件, 就将其加入一个列表, 然后显示出来.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class FileFindVisitor extends Visitor {

    private String suffix;

    private List<File> files = new ArrayList<>();


    public FileFindVisitor(String suffix) {
        this.suffix = suffix;
    }

    //访问到文件的时候, 将文件记录到数组中
    @Override
    public void visit(File file) {
        if (file.getName().endsWith(suffix)) {
            files.add(file);
        }
    }

    //访问的如果是目录, 对其递归的调用所有的方法
    @Override
    public void visit(Directory directory) {

        Iterator<Entry> entryIterator = directory.iterator();
        while (entryIterator.hasNext()) {
            entryIterator.next().accept(this);
        }
    }

    public Iterator<File> iterator() {
        return files.iterator();
    }
}

使用的时候完全无需更改任何Entry代码, 直接使用:

    FileFindVisitor fileFindVisitor = new FileFindVisitor(".html");

    rootdir.accept(fileFindVisitor);

    for (Iterator<File> it = fileFindVisitor.iterator(); it.hasNext(); ) {
        System.out.println(it.next());
    }

练习 13-2 完全通过访问者来计算大小, 而不是通过数据结构的getSize()方法

由于也是仅仅只有File才具有size, Directory对象的大小是通过file计算出来的, 所以可以编写一个递归的方法. 这里自己还思考了一下, 数据结构采用何种设计模式或者说具体的结构, 也决定了如何编写访问者的方法.

这个方法不难, 由于Composite模式的实现, 还是递归调用然后求和就可以了:

import java.util.Iterator;

public class SizeVisitor extends Visitor {

    private int size = 0;

    @Override
    public void visit(File file) {
        this.size += file.getSize();
    }

    @Override
    public void visit(Directory directory) {
        for (Iterator<Entry> entries = directory.iterator(); entries.hasNext(); ) {
            entries.next().accept(this);
        }
    }

    public int getSize() {
        return size;
    }
}

调用很简单:

    SizeVisitor sizeVisitor = new SizeVisitor();

    rootdir.accept(sizeVisitor);

    System.out.println(sizeVisitor.getSize());

习题 13-3

这个很简单, 就是在Directory和File类上再套了一层, 也算作一种数据类型.

import java.util.ArrayList;

public class ElementArrayList implements Element {

    private ArrayList<Entry> entries = new ArrayList<>();

    public void add(Entry entry) {
        entries.add(entry);
    }

    //依然是递归访问
    @Override
    public void accept(Visitor visitor) {
        for (Entry entry : entries) {
            entry.accept(visitor);
        }
    }
}

使用:

    Directory root1 = new Directory("root1");
    root1.addEntry(new File("diary.html", 10));
    root1.addEntry(new File("index.html", 20));

    Directory root2 = new Directory("root2");
    root2.addEntry(new File("diary.html", 1000));
    root2.addEntry(new File("index.html", 2000));

    ElementArrayList elementArrayList = new ElementArrayList();

    elementArrayList.add(root1);
    elementArrayList.add(root2);
    elementArrayList.add(new File("etc.html", 1234));

    elementArrayList.accept(new ListVisitor());

Chain of Responsibility 职责链模式

职责链模式就是外部需求过来的时候, 如果不知道由哪个对象进行处理, 就需要将多个对象组成一条职责链, 然后按照这个链条一个一个的找过去, 直到能找到能处理的类.

使用这个方法, 可以解耦请求方和处理方之间的强耦合关系, 让双方都成为各自可以复用的组件. 另外看到链, 可以想到链式调用.

例子使用了一个问题类Trouble, 一个解决问题的抽象类 Support, 以及只能解决部分问题的四个实现类.

先看Trouble类, 一个很简单的POJO:

public class Trouble {

    private int number;

    public Trouble(int number) {
        this.number = number;
    }

    public int getNumber() {
        return number;
    }

    @Override
    public String toString() {
        return "Trouble{" +
                "number=" + number +
                '}';
    }
}

然后是抽象类Support, 用于解决问题的基类:

public abstract class Support {

    private String name;

    private Support next;

    public Support(String name) {
        this.name = name;
    }

    public Support setNext(Support next) {
        this.next = next;
        return next;
    }

    //这是一种模板模式, 即算法在抽象类中规定好了.
    //这里先尝试用当前对象进行解决问题, 如果不行, 就将其交给下一个对象
    public final void support(Trouble trouble) {
        if (resolve(trouble)) {
            done(trouble);
        } else if (next != null) {
            next.support(trouble);
        } else {
            fail(trouble);
        }
    }

    protected abstract boolean resolve(Trouble trouble);

    protected void done(Trouble trouble) {
        System.out.println(trouble + " is resolved by " + this);
    }

    protected void fail(Trouble trouble) {
        System.out.println("No Supporter can resolve " + trouble);
    }

}

这个类很关键, 这也是一种模板, 即给定了解决办法, 另外还有一个setNext()方法用于注册成一个链条, 注意其中返回的是next, 这就很有意思, 可以链式注册.

然后是四个实现类, 由于算法很清晰, 沿着链条一个一个调用, 所以实现类重点就在于实现 resolve() 方法:

//不解决问题的类永远返回false
public class NoSupport extends Support {

    public NoSupport(String name) {
        super(name);
    }

    @Override
    protected boolean resolve(Trouble trouble) {
        return false;
    }
}
//这个类仅解决小于指定数字的问题
public class LimitSupport extends Support {

    private int limit;

    public LimitSupport(String name, int limit) {
        super(name);
        this.limit = limit;
    }

    @Override
    protected boolean resolve(Trouble trouble) {
        if (trouble.getNumber() < limit) {
            return true;
        } else {
            return false;
        }
    }
}
//只解决奇数问题的类
public class OddSupport extends Support {
    public OddSupport(String name) {
        super(name);
    }

    @Override
    protected boolean resolve(Trouble trouble) {
        return trouble.getNumber() % 2 != 0;
    }
}
//只解决指定编号的问题
public class SpecialSupport extends Support {

    private int number;

    public SpecialSupport(String name, int number) {
        super(name);
        this.number = number;
    }

    @Override
    protected boolean resolve(Trouble trouble) {
        return trouble.getNumber() == number;
    }
}

类很简单, 如何使用是关键, 首先要注册成一个链条, 然后从链条的头部开始调用resolve方法:

public class Main {

    public static void main(String[] args) {
        //创建各种解决问题的对象
        Support a = new NoSupport("a");
        Support b = new LimitSupport("b", 3);
        Support c = new SpecialSupport("c", 5);
        Support d = new OddSupport("d");
        Support e = new SpecialSupport("e", 8);

        //串成一个链, 注意我们的方法里返回next, 很巧妙
        a.setNext(b).setNext(c).setNext(d).setNext(e);

        //然后来解决问题
        for (int i = 0; i < 10; i++) {
            //从链条的第一个方法开始调用解决问题的方法
            a.support(new Trouble(i));
        }
    }
}

这个模式可以有效的弱化发出请求和处理者之间的关系, 不使用该模式的话, 就必须要知道具体能够解决问题的类.

此外在串起链条的时候有顺序, 可以将一些通用的处理程序尽量靠前, 这样整体效率会提升.

这个模式会导致处理的问题比直接处理会慢, 不过是以提高灵活性为代价的.

虽然之前我很少听过这个职责链, 但是一旦学了之后, 发现这个模式用途很广泛的. 像浏览器中的事件传播和处理, 就是采用了职责链模式.

练习

习题 14-1 这是一个鼠标点击的职责链.

我想了一下, 鼠标在屏幕上的点击, 由于鼠标是I/O设备, 其点击的位置必定是先由操作系统捕获.

然后操作系统应该会去看屏幕当前的位置是被那个应用程序占据, 然后按照操作系统的规则将控制权交给给这个应用程序.

应用程序接到这个事件消息之后, 肯定也会按照点击的位置来看需要具体谁来处理这个事件.

不过我看答案, 控件里保存的是父窗口, 然后事件如果不被处理, 会一层一层向上传播, 这果然就是浏览器的事件捕获机制.


习题 14-2

这个我看了答案才意识到, 按键之后的结果不同, 实际上就说明控件对于按键事件处理的方式不同, 能够移动到其他控件就说明交给了父窗口, 否则就会自行去处理, 这就很有意思


习题 14-3

由于support要对外暴露, 用于解决问题, 所以是public权限. 而protect方法主要是用于解决问题的类内部解决问题, 所以用protect就可以了.

习题 14-4

这个只要使用一个while(next!=null)就可以了