設(shè)計模式第二章第八節(jié)

1、2.82.8、拼寫檢查和斷字處理、拼寫檢查和斷字處理 拼寫檢查和連字符點的計算也存在多種方法。因此，我們能同時希望支持多個算法。一組不同算法的集合能夠提供時間/空間/質(zhì)量選擇時的權(quán)衡，我們也希望應(yīng)該能很容易加進新的算法。因為拼寫檢查和連字符只是我們希望Lexi支持的許多潛在的文本分析中的兩種。所以，我們要盡量避免將功能與文檔結(jié)構(gòu)緊密耦合，此時這個目標甚至比格式化設(shè)計更重要。 事實上這個難題可以分成兩部分： 1）訪問需要分析的信息，而它們是被分散在文檔結(jié)構(gòu)的圖元中的；2）分析這些信息。我們將這兩部分分開對待。2.8.1、訪問分散的信息許多分析要求逐字檢查文本，而我們需要分析的文本是分散在圖元對象

2、的層次結(jié)構(gòu)中的。為了檢查在這種結(jié)構(gòu)中的文本，我們需要一個知道數(shù)據(jù)結(jié)構(gòu)中所包含圖元對象的訪問機制。一些圖元可能以連接表保存它們的子圖元，另一些可能用數(shù)組保存，還有一些可能使用更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。我們的訪問機制應(yīng)該能處理所有這些可能性。更為復(fù)雜的情況是，不同分析算法將會以不同方式訪問信息。大多數(shù)分析算法總是從頭到尾遍歷文本，但也有一些恰恰相反所以我們的訪問機制必須能容納不同的數(shù)據(jù)結(jié)構(gòu)，并且我們還必須支持不同的遍歷方法。2.8.2 封裝訪問和遍歷 假如我們的圖元的接口使用一個整型數(shù)字索引，讓客戶引用子圖元。盡管這對以數(shù)組儲存子圖元的圖元類來說是合理的，但對使用連接表的圖元類卻是低效的。圖元抽象的一個重

3、要作用就是隱藏了存儲其子圖元的數(shù)據(jù)結(jié)構(gòu)，我們可以在不影響其他類的情況下改變圖元類的數(shù)據(jù)結(jié)構(gòu)。 因而，只有圖元自己知道它所使用的數(shù)據(jù)結(jié)構(gòu)?？梢杂羞@樣的推論：圖元接口不應(yīng)該偏重于某個數(shù)據(jù)結(jié)構(gòu)。不應(yīng)該像上面這樣，即數(shù)組比使用連接表更好 我們有可能解決這個問題，并且同時支持多種遍歷方式。我們可以將多個訪問和遍歷功能直接放到圖元類中，并提供一種選擇方式，這可能是通過增加一個枚舉常量作為參數(shù)。類在遍歷過程中傳遞該參數(shù)以確保所用的是同一種遍歷方式，它們必須傳遞遍歷過程中積累的任何信息。 我們可以給Glyph的接口增加如下的抽象操作來支持這種方法：Void First (Traversal kind)Void

4、 Next()Bool IsDone()Glyph* GetCurrent()Void Insert(Glyph*) First、Next和IsDone操作控制遍歷。First初始化遍歷過程，它根據(jù)枚舉類型Traversal的參數(shù)值確定執(zhí)行何種遍歷，其值可以是CHILDREN（只遍歷圖元的直接子圖元）、PREORDER、 POSTORDER和INORDER。Next在遍歷時前進到下一個圖元。IsDone則報告遍歷是否完成。GetCurrent代替了Child操作，它訪問遍歷的當前圖元。Insert操作代替了以前的操作，它在當前位置插入給定的圖元。 一個分析可以使用如下C + +代碼實現(xiàn)對g為根

5、結(jié)點的圖元結(jié)構(gòu)作先序遍歷：Glyph* g;For(g-Fisrst(PREORDER); !g-IsDone(); g-Next()Glyph* current=g-GetCurrent();/do some analysis我們已經(jīng)放棄了圖元接口的數(shù)字索引。這樣就不會偏重于某種數(shù)據(jù)結(jié)構(gòu)。我們也使得客戶不必自己實現(xiàn)通用的遍歷方法但是該方法仍然有一些問題。舉個例子，它在不擴展枚舉值或增加新的操作的條件下，不能支持新的遍歷方式。比方說，我們想要修改一下先序遍歷，使它能自動跳過非文本圖元。我們就不得不改變枚舉類型Traversal，使它包含TEXTUAL_PREORDER這樣的值。 2.8.3 I

6、terator類及其子類再一次提及，一個好的解決方案是封裝那些變化的概念，在這里我們指的是訪問和遍歷機制。我們引入一類稱之為iterators的對象，它們的目的是定義這些機制的不同集合。我們使用抽象類Iterator為訪問和遍歷定義一個通用的接口。由具體子類，諸如Array-Iterator和ListIterator，負責實現(xiàn)該接口以提供對數(shù)組和列表的訪問；而PreorderIterator和PostorderIterator以及類似的類在指定結(jié)構(gòu)上實現(xiàn)不同的遍歷方式。每個Iterator子類有一個它所遍歷的結(jié)構(gòu)的引用，在創(chuàng)建子類實例時，需用這個引用進行初始化。下圖展示了Iterator和它的

7、若干子類之間的關(guān)系。注意，我們在Glyph類接口中增加了一個CreateIterator抽象操作以支持Iterator。2.8.3 Iterator類及其子類 再一次提及，一個好的解決方案是封裝那些變化的概念，在這里我們指的是訪問和遍歷機制。我們引入一類稱之為iterators的對象，它們的目的是定義這些機制的不同集合。我們使用抽象類Iterator為訪問和遍歷定義一個通用的接口。由具體子類，諸如Array-Iterator和ListIterator，負責實現(xiàn)該接口以提供對數(shù)組和列表的訪問；而PreorderIterator和PostorderIterator以及類似的類在指定結(jié)構(gòu)上實現(xiàn)不同的

8、遍歷方式。每個Iterator子類有一個它所遍歷的結(jié)構(gòu)的引用，在創(chuàng)建子類實例時，需用這個引用進行初始化。下圖展示了Iterator和它的若干子類之間的關(guān)系。注意，我們在Glyph類接口中增加了一個CreateIterator抽象操作以支持Iterator。Iterator接口提供 First、Next和IsDone操作來控制遍歷。ListIterator類實現(xiàn)的First操作指向列表的第一個元素Next前進到列表的下一個元素；IsDone返回列表指針是否指向列表范圍以外；CurrentItem返回iterator所指的圖元ArrayIterator類的實現(xiàn)類似，只不過它是針對一個圖元數(shù)組的。

9、現(xiàn)在我們無需知道具體表示也能訪問一個圖元結(jié)構(gòu)的子女：GlyphGlyph* * g; g;IteratorGlyphIterator * * i=g-CreaterIterator(); i=g-CreaterIterator();for(i-First();!i-IsDone(); i-Next()for(i-First();!i-IsDone(); i-Next() GlyphGlyph* * child=i-CurrentItem(); child=i-CurrentItem();/do something with current child/do something with cur

10、rent child 在缺省情況下CreateIterator返回一個NullIterator實例。NullIterator是一個退化的Iterator，它適用于葉子圖元，即沒有子圖元的圖元。NullIterator的IsDone操作總返回true。一個有子女的圖元Glyph子類將重載CreateIterator，返回不同Iterator子類的一個實例，這依賴于保存圖元子女所用的結(jié)構(gòu)。如果Glyph的行子類在一個_children列表中保存其子類，那么它的CreateIterator操作實現(xiàn)如下：Iterator* Row:CreateIterator()return new ListIter

11、ator(_children);用于先序和中序遍歷的Iterator是用各圖元自身特定的iterator實現(xiàn)的。這些遍歷的Iterator還要保存對以它們所遍歷的結(jié)構(gòu)的根圖元的引用。它們調(diào)用結(jié)構(gòu)中圖元的CreateIterator，并用棧來保存返回的Iterator。 例如，類PreorderIterator從根圖元得到Iterator，將它初始化為指向第一個元素，然后將它壓入棧中：Void PreorderIterator:First()Void PreorderIterator:First() IteratorGlyph Iterator * * i=_root-CreateIterato

12、r(); i=_root-CreateIterator(); if(i) if(i) i-First();i-First();_iterators.RemoveAll();_iterators.RemoveAll();_iterators.Push(i);_iterators.Push(i); CurrentItem只是調(diào)用棧頂?shù)腎terator的CurrentItem操作：Glyph* PreorderIterator:CurrentItem () const return_iterators.Size()0?_iterators.Top()-CurrentItem():0; Next操作得

13、到棧頂?shù)腎terator，并且讓它的當前項創(chuàng)建一個Iterator，盡可能遍歷到圖元結(jié)構(gòu)的最遠處（因為這是一個先序遍歷）。Next將新的Iterator設(shè)置到遍歷中的第一個元素，再將它壓棧。然后Next測試最近的Iterator，如果它的IsDone操作返回true，那么我們就完成了對當前子樹（或葉子）的遍歷。本例中,Next彈出棧頂?shù)腎terator并且重復(fù)上述過程，直到發(fā)現(xiàn)下一個還沒完成的遍歷；否則，我們就完成了對整個結(jié)構(gòu)的遍歷。Void PreorderIterator:Next() Iterator* i=_iterators.Top()-CurrentItem()-CreateIte

14、rator(); i-First(); _iterators.push(i); while(_iterators.Size()&_iterators.Top()_IsDone(0) delete _iterators.Pop(); _iterators.Top()-Next(); Iterator類層次結(jié)構(gòu)是怎樣允許我們不改變圖元類而增加新的遍歷方式的如PreorderIterator所示，我們只需創(chuàng)Iteraror子類，并給它增加一個新的遍歷算法即可。2.8.4 Iterator模式 Iterator模式描述了那些支持訪問和遍歷對象結(jié)構(gòu)的技術(shù)，它不僅可用于組合結(jié)構(gòu)也可用于集合。該模式

15、抽象了遍歷算法，對客戶隱藏了它所遍歷對象的內(nèi)部結(jié)構(gòu)。 Iterator模式再一次說明了怎樣封裝變化的概念，有助于我們獲得靈活性和復(fù)用性。盡管如此， Iteration問題的復(fù)雜性還是令人吃驚的，Iterator模式包含了比我們這里考慮的更多的細微差別和權(quán)衡。2.8.5 遍歷和遍歷過程中的動作 現(xiàn)在我們有了遍歷圖元結(jié)構(gòu)的方法，可以進行檢查拼寫和支持連字符。 首先我們要決定將分析的責任放在什么位置上。我們可以在Iterator類中作分析，將分析和遍歷有機結(jié)合起來。但因為不同的分析通常需要相同的遍歷方式。所以如果我們能區(qū)別遍歷和遍歷過程中所執(zhí)行動作之間的差別的話，就可以得到更多的靈活性和潛在復(fù)用性。

16、這是因為，對于不同的分析而言，我們可以復(fù)用相同的Iterator集合。 因此，我們應(yīng)當將分析和遍歷分開，那么將分析責任放到什么地方呢？ 我們知道有許多種分析可以做，每一種分析將在不同的遍歷點做不同的事情。根據(jù)分析的種類，有些Glyph比其他的圖元更具重要性。如果作拼寫檢查和連字符分析，我們要考慮的是字符型的圖元，而不是像行和位圖圖形這樣的圖元。如果我們作顏色分割，我們要考慮的是可見的圖元，而不是不可見圖元。因此，不同的分析過程必然是分析不同的圖元。 因而一個給定的分析必須能區(qū)別不同種類的圖元。很明顯的一種做法是將分析能力放到圖元類本身。針對每一種分析，我們?yōu)镚lyph類增加一個或多個抽象操作，

17、并且根據(jù)它們在分析中所起作用，在Glyph子類中實現(xiàn)這些操作。但這種方法存在兩個問題： 1、我們每增加了一種新的分析，都必須改變每一個圖元類。 2、隨著新的分析功能的增加，Glyph的接口會越來越大。眾多的分析操作會逐漸模糊基本的Glyph接口，從而很難看出圖元的主要目的是定義和結(jié)構(gòu)化那些有外觀和形狀的對象這些接口完全被淹沒了。2.8.6 封裝分析 所有跡象表明，我們需要在一個獨立對象中封裝分析方法，就像我們以前多次做過的那樣。我們可以將一個給定的分析封裝在一個類中，并把該類的實例和合適的Iterator結(jié)合起來使用。這個Iterator負責將該實例攜帶到所遍歷結(jié)構(gòu)的每一個圖元中。這樣分析對象

18、可以在每個遍歷點做一些分析工作。在遍歷過程中，分析者積累它所感興趣的信息如下圖所示。 該方法的基本問題在于：分析對象怎樣才能不使用類型測試或強制類型轉(zhuǎn)換也能正確對待各種不同的圖元。我們不希望SpellingChecker包含類似如下的(偽)代碼：Void SpellingChecker:Check (GlyphVoid SpellingChecker:Check (Glyph* * glyph) glyph) Character Character* * c; c;RowRow* * r; r;ImageImage* * I; I;if(c=dynamic_castCharacterif(c=

19、dynamic_cast(glyph)(glyph)/analyze the character/analyze the characterelse if(r=dynamic_castRowelse if(r=dynamic_cast(glyph)(glyph)/prepare to analyze rs children/prepare to analyze rs childrenelse if(i=dynamic_castImage else if(i=dynamic_cast(glyph)(glyph)/do nothing/do nothing 這段代碼相當拙劣。它依賴于比較高深的像類

20、型的安全轉(zhuǎn)換這樣的能力，并且難以擴展。無論何時當我們改變Glyph類層次時，都要記住修改這個函數(shù)。事實上，這也是面向?qū)ο笳Z言力圖消除的那種代碼。 我們?nèi)绾伪苊膺@種不成熟的方式呢？我們在Glyph類中添加如下代碼時會發(fā)生什么：void CheckMe (SpellingChecker&)void CheckMe (SpellingChecker&) 我們在每一個Glyph子類中定義CheckMe如下：Void GlyphSubclass:checkMe (SpellingChecker& Void GlyphSubclass:checkMe (SpellingChecke

21、r& checker)checker)Checker.CheckGlyphSubclass(this);Checker.CheckGlyphSubclass(this); 當調(diào)用CheckMe時，當前是哪一個特定Glyph子類是知道的畢竟，我們在使用它的操作。相對應(yīng)的，SpellingChecker類的接口包含每一個Glyph子類的類似于CheckGlyphSubclass的操作：Class SpellingCheckerPublic:SpellingChecker();virtual void CheckCharacter(Character*);virtual void check

22、Row(Row*);virtual void CheckImage(Image*);/.and so forthlist& GetMisspellings();Protected;virtual bool IsMisspelled(const char *);Private:char_currentWordMAX_WORD_SIZE;List_misspellings;SpellingChecker的檢查字符圖元的操作可能像如下所示：我們已經(jīng)在Character類中定義了一個特殊的GetCharCode操作。拼寫檢查者能夠處理特定子類的操作，而無需類型檢查或轉(zhuǎn)換這讓我們可以分別對待各個

23、對象。CheckCharacter將字母字符累積在_CurrentWord數(shù)組中。當碰到像下劃線這樣的非字母字符時，它使用IsMisspelled操作去檢查_CurrentWord中單詞的拼寫。如果該單詞拼寫錯誤， CheckCharacter將它加到拼錯單詞的列表中。然后必須清空數(shù)組_CurrentWord ，以便檢查下一個單詞。當遍歷結(jié)束后，你可以通過GetMisspellings操作遍歷拼寫錯誤的單詞的列表。 現(xiàn)在，我們以拼寫檢查器為參數(shù)調(diào)用每個圖元的CheckMe操作，來實現(xiàn)對圖元結(jié)構(gòu)的遍歷。這使得拼寫檢查器SpellingChecker可以有效區(qū)分每個圖元，并不斷推進檢查器以檢查下面

24、的內(nèi)容。SpellingChecker spellingChecker;Composition* c;/Glyph*g;PreorderIterator i(c);For(i.First();!i.IsDone();i.Next()g=i.CurrentItem();g-CheckMe(spellingChecker); 這種方法適合于找出拼寫錯誤，但怎樣才能幫助我們?nèi)ブС侄喾N分析呢？看上去有點像我們每增加一種新的分析，就不得不為Glyph及其子類增加一個類似于CheckMe(SpellingChecker &)的操作。如果我們堅持每一個分析對應(yīng)一個獨立的類的話，事實確實如此。但是沒有

25、理由說我們不能給所有分析類型一個相同的接口。應(yīng)該允許我們多態(tài)使用各種分析。也就是說，我們應(yīng)能夠用一個有通用參數(shù)的與分析無關(guān)的操作來替代像CheckMe(SpellingChecker &)這樣表示特定分析的操作。2.8.7 Visitor類及其子類我們使用術(shù)語訪問者（v i s i t o r）來泛指在遍歷過程中“訪問”被遍歷對象并做適當操作的一類對象。本例中我們使用一個Visitor類來定義一個訪問結(jié)構(gòu)中圖元的接口。Class visitorpublic;:virtual void VisitCharacher(Character*)virtual void VisitRow(Row*)Virtual void VisitImage(Image*)/and so forth; 訪問者的具體子類做不同的分析，例如，我們可以用一個SpellingCheckingVisitor子類來檢查拼寫；用HyphenationVisitor子類做連字符分析。SpellingCheckingVisitor可以就像我們上面的SpellingChecker那樣來實現(xiàn)，只是操作名要反映通用的訪問者的類接口。例如，CheckCharacter應(yīng)該改成VisitCharacter。既然CheckMe對于訪問者并不合適，因為訪問者不檢查任何東