Iterator vs Visitor, Pull vs Push
名詞界定
Iterator Pattern
也叫做
Generator, Sequence, Stream
等。
Java
里面有
Iterator Interface
，大家應該比較熟悉，不再贅述。
?
完整的具有
Visitor
和
Visited (Visitable)
兩個部分的
Visitor Pattern
的使用并不廣泛。
簡單的只有
Visitor
部分的
Simple Visitor Pattern
比較常見，比如
Callback, Interceptor, Filter
，
Functor, Selector, Extractor
等，都可以看作是
Simple Visitor Pattern
。
它們都只有
Visitor
部分，而沒有
Visited
部分。或者說他們的
Visitor
需要處理的
Visited Object
通常只有一種通用數據類型，所以不需要專門提出來一個
Visited
Interface -- accept(visitor)
。
?
這種情況和
Observer
Pattern
很相似。不過這也不奇怪，很多
Design
Pattern
都是非常類似的，有的幾乎只有名字不同。
為了避免不必要的口舌之爭后，這么說吧，
Visitor
和
Observer
的側重點不同。
Visitor
一般來說是
Visit
一個集合，通常在一個遍歷算法中密集完成，獲取的信息（
Node Object
）之間一般都有密切關聯，比如父子關系，兄弟關系。
而
Observer
Patten
則是監聽一個長期運行的系統，零零散散地不定期地運行，獲取的信息之間不存在密切聯系，或者說，沒什么關系。比如訂閱的報紙到了，訂購的牛奶到了。
?
費了半天口舌，澄清各種可能的誤會，我們繼續
Iterator vs Visitor
之旅。
Iterator Pattern
和
Simple Visitor Pattern
處理的問題領域幾乎是重合的。它們面對的共同問題模型的組成部分如下：
(1)
有一個算法
Algorithm
，通常是遍歷算法（
Traversal
）。而且通常是復雜的數據結構，
Tree
、
Graph
等結構的遍歷算法。
(2)
算法的使用者，需要和算法的每一步遇到的
Node Object
進行交流。
?
所不同的是，
Iterator
是一種主動模型，
Pull
模型，
Ask and Get
。
Iterator
聽候用戶的調遣。
Vistor
是一種被動模型，
Push
模型，
Plugin /
callback
模型，
Push and
Pray and Wait
。
Visitor
聽候算法的調遣。
?
Iterator
相當于算法公司的一名業務人員，代表公司和用戶打交道。用戶并不需要深入到算法公司內部。
而
Visitor
相當于用戶派出的代表，深入到算法公司內部，由算法公司安排訪問行程。
?
Iterator
的典型使用方法是：
iterator = traversal.getIterator();
item = iterator.next();
do some thing with item
?
Vistor
的典型使用方法是
visitor = new Visitor(){
? ..
visit(item) { do something with item }
};
traversal.traverse(visitor);
?
一個典型的例子是
StAX
和
SAX
和兩種操作
XML
的方式。
（參見
http://www.xmlpull.org/
，關于
StAX
的典型用法，網上有些經典文章，本文不再贅述。請使用
StAX
XMLPull XML
等關鍵字進行搜索）
StAX
就是一個典型的
Pull Model, Iterator Pattern
。
而
SAX
是
Push Model, Simple Visitor Pattern
(Event Listener)
。（如果較真，你當然可以把它叫做
Oberver Pattern
）。
?
另外一個有趣的例子是
DOM
Traversal
。
W3
的
DOM Level 2
規范定義了
DOM Traversal
。
http://www.w3.org/TR/2000/REC-DOM-Level-2-Traversal-Range-20001113/traversal.html
DocumentTraversal, TreeWalker,
NodeIterator, NodeFilter
。
?
DOM Traversal
主要是一個
Iterator Pattern
，
TreeWalker, NodeIterator
都是
Iterator
；但
DOM Traversal
同時也是一個簡單的
Visitor Pattern
——
NodeFiter
可以作為簡單的
Visitor
被注入到
Traversal
算法里面，對遇到的每個
Node
進行過濾。
不過，這個
NodeFiter
的
method name
比較有意思，叫做
accept
。而我們知道
Visitor Pattern
的
Visited Object
具有一個
accept
方法。不過，不要誤會。這個
NodeFilter
仍然是一個
Visitor
。這里的
Accept
的意思就是
Intercept, Filter
。
用法是這樣。
NodeIterator iterator =
DocumentTraversal.createNodeIterator(…NodeFilter …)
?
按照我的設想，這個
API
設計，還可以有另外的思路。把
Filter
加在
Iterator
身上，而不是加在
Traversal
算法身上。因為
Iterator Pattern
很容易地做到這一點。
NodeIterator iterator = New
FilteredIterator(
??
DocumentTraversal().createNodeIterator() , … NodeFilter …);
?
這樣，
DOM
Traversal
就是一個純粹的
Iterater
Pattern
了。
特性比較
Iterator
屬于問答模式，或者說消費者
/
生產者模式。
如果消費者不問不要，生產者就不答不給。
Iterator
的使用者完全掌握了主動權，是控制舞步節奏的領舞者，隨時可以中止這場問答游戲。
Iterator
的用法本身就是
Lazy
的，一問一答，遍歷算法停在那里恭候
Iterator
使用者的調遣。
?
Visitor
則完全是被動的，
Visitor
的提供者
/
使用者把
Visitor
扔到
Traversal
算法里面，然后運行算法，同時祈禱并等候算法的完成（
Push and Wait
），完全失去了控制權，只能等待算法整個完成或者中止，才能重新拿到控制權。
Vistor
的用法很難做到
Lazy
，算法必須提供一些機制，接受
Visitor
每一步調用發出的指令，進行相應的策略選擇。
換句話說，
Visitor
Pattern
里面的算法必須做出相應的
Lazy
支持，而且
Visitor
必需積累前面步驟的狀態，然后判斷這次調用中發出什么樣的指令。
?
比如，有這樣一個需求：遍歷一棵樹，搜集到前
5
個名字是
Apple
的
Node
。然后返回這
5
個
Node
。假設樹遍歷算法已經有了。
這時候采用
Iterator
Pattern
視線起來很容易。不再多說。
Visitor Pattern
則需要：
Vistor
使用一個集合來保存每次遇到的名字是
Apple
的
Node
，每次都判斷是否已經找到了
5
個，如果已經找到，那么發出一個
Stop Signal
給算法。
如果遍歷算法不接受這種指令怎么辦？
只好等待算法完成。或者實在等不及，預計到后面還有上萬個
Node
需要遍歷，那么就干脆
throw new RuntimeException(),? throw new Throwable()
。
也許算法并沒有聰明到捕獲這些
Exception
。那么這個
Trick
就成功了。外面使用一個
Try Catch
捕獲這個
Exception
。不過，這是
Very Very Bad Smell
。
?
Iterator
的應用場景是這樣：
我
在商品定購目錄上看到一個公司有我感興趣的產品系列。于是我打電話給該公司，要求派一個銷售代表來。銷售代表上門之后，從包里拿出一個一個的產品給你看，
我看了幾個，沒什么滿意的，于是打了個哈欠說，今天就先到這里吧，下次再說。打發了銷售代表，我就轉身去做自己的事情了。
我的地盤，我做主。這就是
Iterator
Pattern
的理念。
?
Vistior
的應用場景是這樣：
我
在商品定購目錄上看到一個公司有我感興趣的產品系列。于是我上門拜訪該公司，公司給我安排了一場產品性能展示，我看了幾個之后，沒有什么滿意的，于是我
說，我肚子疼，想先回去了。遇到好心的公司代表，當然說，身體要緊，慢走。遇到固執的公司代表，一定會說，對不起，我們公司有自己的工作流程，完成產品演
示之前，產品廳的門鎖是打不開的。我只好勃然大怒，吵吵嚷嚷（
throw exception
），期待能夠殺出重圍，這時候，假設該公司的保安系統反映比較靈敏（
try catch every visitor exception
），就會有幾個保安跑過來，把我按在椅子上繼續聽講。
入鄉隨俗，客隨主便。別人的地盤，別人做主。這就是
Visitor Pattern
的理念。
?
Iterator Pattern
的優勢當然不僅如此。這只是個特殊的例子。
更常見的是，
Iterator
Pattern
能夠支持基于
Iterator
的很多算法。
比如，
Functional
Programming
的
Map, Reduce,
Filter
等函數都是接受一個
Iterator
(Sequence, List, Stream
等
)
。
Map, Filter
等函數還可以組合成一個新的
Iterator
。這個組合可以一直下去。
當然，
Visitor
也是可以組合的。但是限制嚴格，缺乏擴展性。
?
比如這樣一個需求：
有
T1
和
T2
兩棵樹。首先遍歷
T1
的
10
個
Node
，如果發現
Apple
，那么摘下來，然后繼續遍歷，如果
10
步都沒有發現
Apple
，那么切換到
T2
；遍歷
T2
的規則也是如此，
10
步之內發現目標，就繼續，否則就切換到
T1
。
Iterator Pattern
實現起來很簡單。相當于我是買方，情勢是買方市場，我可以讓兩個公司的銷售代表同時到我的公司來，我可以同時接待他們，讓他們各自按順序展示自己的產品。
Visitor Pattern
怎么做？情勢是賣方市場，我巴巴地跑上門去，看
T1
公司的產品展示，看了
10
個之后說，請送我到
T2
公司的產品展示現場，我看
10
個之后，再回來。
?
一個用戶可以同時使用多個算法的
Iterator
；但是用戶的一個
Visitor
只能同時進入一個算法。
這就是兩者核心理念的不同。
實現難度
讀者說了，
Iterator
這么方便，你就使用
Iterator
好了，說這么多干什么。
如果別人提供了
Iterator
，我當然會使用。
?
現在的問題是，假設你是算法公司的成員。你是提供
Visitor Pattern
的
API
，還是
Iterator
Pattern
的
API
？
Visitor Pattern
的實現比較簡單。自己知道自己公司的內部組織結構，一個一個的遍歷，并傳遞給
Visitor
就行了。
Iterator Pattern
的實現難度，可以說，那是相當的大。
內部數據結構簡單的數組、鏈表好說，做一個類似于
Closure, Context, Continuation
的保存了當前調用步驟（數組索引，或者當前指針）和調用環境（內部數據集）的結構，返回給用戶就可以了。用戶每次調用
iterator.next
，
iterator
就把索引或指針向后移動一下。
如果是內部數據復雜的
Tree,
Graph
結構，就相當復雜了。比如是遍歷一棵樹，而且這棵樹的
Node
里面沒有
Parent
引用，那么
Iterator
必須自己維護一個棧把前面的所有的
Parent Node
都保存起來。當用戶調用
iterator.next
的時候，
iterator
就必須檢查自己當前的狀態，如果所有的
Child Node
都走完了，那么就要返回到上面的
Parent
，繼續檢查。
而在
Visitor
Pattern
里面，這個算法的實現簡直是小菜一碟，只要一個簡單的遞歸就夠了。計算機會自動幫你分配和管理運行棧，保存前面的
Parent Node
，執行返回的時候，這個
Parent Node
又自動交還給你。
Coroutine
有沒有簡單的方法來實現
Iterator
Pattern API
呢？如同實現
Visitor
Pattern API
那樣容易？
幸福得象花兒一樣。簡單得像
Visitor
一樣。能不能那樣？
?
聰明的人們把目光轉向了
Coroutine
。
Coroutine
本來是一個通用的概念。表示幾個協同工作的程序。
比如，消費者
/
生產者，你走幾步，我走幾步；下棋對弈，你一步我一步。
由于協同工作的程序通常只有
2
個，而且這兩個程序交換的數據通常只有一個。于是人們就很容易想到用
Coroutine
來實現
Iterator
。
這里面
Iterator
就是
Coroutine
里面的生產者
Producer
角色，數據提供者。所以，也叫做
Generator
。
每次
Iterator
程序就是等在那里，一旦用戶（消費者
Consumer
角色）調用了
iterator.next, Iterator
就繼續向下執行一步，然后把當前遇到的內部數據的
Node
放到一個消費者用戶能夠看到的公用的緩沖區（比如，直接放到消費者線程棧里面的局部變量）里面，然后自己就停下來（
wait
）。然后消費者用戶就從緩沖區里面獲得了那個
Node
。
這樣
Iterator
就可以自顧自地進行遞歸運算，不需要自己管理一個棧，而是迫使計算機幫助它分配和管理運行棧。于是就實現了幸福得像花兒一樣，簡單得像
Visitor
一樣的夢想。
?
比如，這樣一段代碼，遍歷一棵二叉樹。
public class TreeWalker : Coroutine {
??? private TreeNode _tree;
??? public TreeWalker(TreeNode tree) { _tree?= tree; }
??? protected override Execute() {
??????? Walk(_tree);
??? }
??? private void Walk(TreeNode tree) {
??????? if (tree != null) {
???????????
Walk(tree.Left);
???????????
Yield(tree);
???????????
Walk(tree.Right);
??????? }
??? }
}
?
其中的
Yield
指令是關鍵。意思是，首先把當前
Node
甩到用戶的數據空間，然后自己暫停運行（類似于
java
的
thread yield
方法或者
object.wait
方法），把自己當前運行的線程掛起來，這樣虛擬機就為自己保存了當前的運行棧（
context
）。
有人說，這不就是
continuation
嗎？
對。只是
Coroutine
這里多了一個產生并傳遞數據的動作。
實現原理如果用
Java
Thread
表示大概就是這樣。當然下面的代碼只是一個示意。網上有具體的
Java Coroutine
實現，具體代碼我也沒有看過，想來實現原理大致如此。
?
public class TreeIterator implements
Iterator{
??
TreeWalker walker;
???
// start the walker thread ..
??
Object next(){
???? walker.notify();
???? // wait for a while so that walker can
continue run
???? return walker.currentNode;
?? }
}
?
class TreeWalker implements Runnable{
??? TreeNode currentNode;
???
TreeWarker(root){?
?
??currentNode = root;
}
void run(){
? walk(curentNode);
}
?
private void
Walk(TreeNode tree) {
??????? if (tree != null) {
???????????
Walk(tree.Left);
currentNode = tree;
this.wait();
Walk(tree.Right);
??????? }
??? }
}
?
我們看到，
Iterator
本身是一個
Thread
，用戶也是一個
Thread
。
Iterator Thread
把數據傳遞給
User Thread
。
說實話，我寧可自己維護一個
Stack
，也不愿意引入
Coroutine
這類
Thread Control
的方式來實現
Iterator
。
總結
千言萬語一句話。
Iterator
是好的，但不是免費的。