Thăm quan có mục đích

Cũng có chức năng giống với iterator design pattern, dùng để duyệt qua tất cả các phần tử của một đối tượng hay một collection, tuy nhiên visitor cung cấp cho chúng ta nhiều lựa chọn hơn để quyết định sẽ làm gì với những dữ liệu sẽ được duyệt qua. Ví dụ chúng ta sẽ in thông tin của đối tượng duyệt qua hoặc lưu thông tin các đối tượng vào file một cách dễ dàng.

Bài toán thực tế

Visitor được dùng khá nhiều trong các cấu trúc dữ liệu phức tạp như dạng cây (cây thực mục, BTree, TreeMap, ..) hay dạng dữ liệu đồ thị. Trong phạm vi bài viết này, chúng ta sẽ nói đến dạng dữ liệu đồ thị (Graph) nhé.

Đồ thị được cấu tạo bởi các đỉnh, các đỉnh này có mối liên hệ với nhau, nghĩa là từ một đỉnh ta có thể thăm quan được tất cả các đỉnh có liên hệ với nó.

Chúng ta không thể nào sử dụng vòng for kiểu này:

for(Vertex vertex : graph.getVertexts()) {
    // làm gì đó với vertex
}

Vì mỗi đỉnh lại có mối liên hệ với nào đó với các đỉnh còn lại, nếu dùng vòng for kiểu này chúng ta sẽ bị lặp qua các đỉnh đã được duyệt rồi.

Mục tiêu ra đời

  • Visitor ra đời nhằm giải quyết các hạn chế của iterator, nó giúp chúng ta không cần quan tâm đến điểm bắt đầu và điều kiện kết thúc, từ đó chúng ta sẽ chỉ cần tập trung vào xử lý nghiệp vụ mà thôi. Ví dụ với đồ thị, chúng ta có thể bắt đầu từ bất cứ điểm nào và tham quan cho đến khi nào hết các đỉnh có mối quan hệ thì thôi.
  • Chúng ta cũng có thể tạo ra nhiều lớp visitor khác nhau và sử dụng chúng mà không làm thay đổi bất kì thông tin hay cấu trúc của lớp chứa dữ liệu. Ví dụ chúng ta có thể tạo ra các lớp visitor khác nhau để tham quan các đỉnh của đồ thị nhưng lớp đồ thị sẽ chẳng cần thay đổi gì cả.

Mô hình tiêu chuẩn

Mô hình tiêu chuẩn của một visitor design pattern bao gồm:

  1. Visitor: là interface cơ sở chưa hàm visit để thăm quan các phần tử.
  2. ConcreteVisitor: là các lớp cài đặt cụ thể tương ứng từng nghiệp vụ mà chúng ta muốn xử lý phần tử được thăm quan.
  3. ObjectStructure: là lớp chứa các phần tử cần được thăm quan.
  4. Element: là các phần tử được thăm quan
  5. Client: là lớp khởi tạo visitor và cung cấp cho lớp ObjectStructure

Ví dụ

Quay trở lại với vi dụ đồ thị, chúng ta sẽ sử dụng visitor để thăm quan tấn cả các đỉnh, bắt đầu từ một đỉnh bất kì nhé. Trước hết, hãy thiết kế lớp một chút.

Sơ đồ lớp

Sơ đồ lớp bao gồm:

  1. Visitor: chức năng giống như trong mô hình tiêu chuẩn
  2. PrintVisistor: in ra các phần tử được thăm quan
  3. CacheVisitor: lưu lại thông tin các phần tử được thăm quan vào cache
  4. Graph: là lớp đại diện cho đồ thị
  5. Vertext: là lớp đại diện cho mỗi đỉnh của đồ thị

Cài đặt

Để bài viết không bị dài và nhàm chán, mình sẽ chỉ đưa một ít code vào đây, ví dụ đầy đủ, các bạn có thể tham khảo tại đây nhé.

Đầu tiên là visitor interface:

public interface Visitor<E> {

    void visit(E element);  

}

Sau đó là 2 lớp PrintVisitor và CacheVisitor:

public class PrintVisitor<K, V> implements Visitor<Vertex<K, V>> {
    @Override
    public void visit(Vertex<K, V> element) {
        System.out.print(element + " => ");
    }
}

public class CacheVisitor<K, V> implements Visitor<Vertex<K, V>> {

    private final List<Vertex<K, V>> buffer = new LinkedList<>();

    @Override
    public void visit(Vertex<K, V> element) {
        buffer.add(element);
    }
}

Tiếp theo là lớp Graph và hàm thăm quan tất cả các đỉnh của nó:

public class Graph<K, V> {

    private final Map<K, Vertex<K, V>> vertexByKey;

    // Các đỉnh và các mỗi liên kết
    private final Map<Vertex<K, V>, List<Vertex<K, V>>> adjVertices;

    public void depthFirstTraversal(K rootKey, Visitor<Vertex<K, V>> visitor) {
        Stack<Vertex<K, V>> stack = new Stack<>();
        Vertex<K, V> root = getRootByKey(rootKey);
        if(root != null)
            stack.add(root);
        Set<K> visited = new HashSet<>();
        while(stack.size() > 0) {
            Vertex<K, V> vertex = stack.pop();
            if(!visited.contains(vertex.key)) {
                visited.add(vertex.key);
                vertex.accept(visitor);
                for(Vertex<K, V> v : adjVertices.get(vertex)) {
                    stack.push(v);
                }
            }
        }
    }
}

Cuối cùng, việc sử dụng sẽ chỉ đơn giản thế này:

Graph<String, Integer> graph = new Graph<>();
graph.addVertex("Bob", 1);
graph.addVertex("Alice", 2);
graph.addVertex("Mark", 3);
graph.addVertex("Rob", 4);
graph.addVertex("Maria", 5);
graph.addEdge("Bob", "Alice");
graph.addEdge("Bob", "Rob");
graph.addEdge("Alice", "Mark");
graph.addEdge("Rob", "Mark");
graph.addEdge("Alice", "Maria");
graph.addEdge("Rob", "Maria");
System.out.println(graph);

Visitor<Vertex<String, Integer>> printVisitor = new PrintVisitor<>();
graph.breadthFirstTraversal(printVisitor);
System.out.println();

Visitor<Vertex<String, Integer>> cacheVisitor = new CacheVisitor<>();
graph.depthFirstTraversal(cacheVisitor);
System.out.println(((CacheVisitor)cacheVisitor).getBuffer());

Tổng kết

Visitor là một trong những design pattern tương đối quan trọng để xử lý các cấu trúc dữ liệu phức tạp. Vòng for nên phù hợp với những tập dữ liệu nhỏ và có điều kiện kết thúc cụ thể. Nhưng với visitor, chúng ta sẽ có khả năng xử lý được những tập dữ liệu lớn hơn rất nhiều như các database vẫn đang làm cho chúng ta. Hãy sử dụng nó khi bạn không muốn dùng hoặc không yêu thích vòng for nhé.