iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

1
Modern Web

讓 TypeScript 成為你全端開發的 ACE!系列 第 46

Day 46. 通用武裝・迭代器模式 X 泛用迭代器 - Iterator Pattern Using TypeScript

https://ithelp.ithome.com.tw/upload/images/20191013/20120614OTIuHa4Eyq.png

閱讀本篇文章前,仔細想想看

泛用類別與泛用介面結合時的注意事項為何?

如果還不清楚可以看一下前一篇文章喔~

其實筆者在泛用方面的型別推論與機制並沒有討論很多(不過還是有三篇都在講一些使用泛型的細節 XD),那是因為就只是在型別系統上多了型別參數化的機制,筆者要嘛可以搬出前 20 天的文章然後冠上泛用的機制闡述各種不同的推論結果,多寫個 20 天份跟泛用型別推論機制相關的文章,不過這樣的學習效率實在是很差,所以務必要好好釐清《前線維護》《機動藍圖》篇章,方能夠駕馭 TypeScript 的進階功能,走入王道啊!

讀者云:“作者你想太多了”

那我們進入正文開始吧~

迭代器模式 Iterator Pattern

迭代器是什麼? What is Iterator?

雖然這問題可能對普遍的讀者來說應該很理所當然,不過筆者還是正規化一下迭代器的定義:

重點 1. 迭代器的定義 Definition of Iterator

專門用來巡訪(Iterate)亦或者遍歷(Traverse)目標聚合物(Collection)的內容。

小心喔 —— 迭代器這個詞也是很容易被亂用

迭代器是專門巡訪聚合物的一個物件,而聚合物就是我們所認知的 —— 陣列啊、列狀物啊、甚至是集合(Set)也是一種聚合物。

所以:

陣列或列狀物件不等於迭代器,再次強調 —— 它們是聚合物;迭代器是專門遍歷聚合物的物件。

另外,樹狀資料結構(Tree)也是一種聚合物,只是組織成樹狀結構,但是巡訪模式就有分前序(Preorder)、中序(Inorder)以及後序(Postorder),不過還有一個是層級巡訪(Level-order)的模式,但個人覺得不太算常使用的巡訪模式,所以覺得還好。(可參見 Tree Data Structure

貼心小提示

事實上,樹狀資料結構的尋訪演算法,筆者還是大概講一下細節與各自的優勢,讀者有空可以自己想想看。

深度優先尋訪(Depth-First Search)專門以尋訪子樹(Child Tree)為優先,比較適合解『找不找得到路徑』(Finding the existence of the path)相關問題,譬如迷宮的尋訪。

  • 其中深度優先尋訪演算法就有再分前序、中序與後序
  • 樹狀結構如果越深,演算法的耗費時間可能會越久。

層級優先尋訪(Breadth-First Search)專門以層級(Level)為優先,比較適合解『最短路徑』(Finding the shortest path)相關問題,譬如 LinkedIn 上,人脈的維度(Degree)—— 你的朋友和你的關係是第一度人際關係(1st Degree)、你朋友的朋友與你是第二度人際關係(2nd Degree)等等,依此類推。

  • 其中層級優先尋訪就只有層級尋訪演算法一種而已。
  • 樹狀結構如果越廣,演算法耗費時間可能越久。

重點 2. 迭代器 Iterator V.S. 聚合物 Collection

聚合物(Collection)泛指常見的聚合型資料結構,不限列狀、環狀、樹狀或者是圖(Graph)。

迭代器則是負責巡訪聚合物的物件,而非聚合物本身。

有些讀者可能想說:“恩... 可是我們不是有 forwhile 迴圈協助我們迭代一些列表行資料嗎?我們真的有需要用到迭代器這種東西嗎?”

筆者答:“因為你不可能只會遇到普通串列的格式(如陣列型別),但你可能也會遇到樹狀資料結構 —— 如果把樹狀的巡訪情形邏輯,再分成上述的前序、中序與後序,你可能也會使用 if...else... 等等語法去寫出很龐大一片不同的 for 迴圈巡訪演算法,除了程式碼可再利用性差東西塞在一起要維護起來也挺麻煩的。”

以上所謂的程式碼可再利用性差 —— 讀者請仔細想想:

https://ithelp.ithome.com.tw/upload/images/20191012/20120614oDlWqTHnrP.png

如果別的地方也會需要用類似的遍歷演算法,一種就是 Copy-Paste 方式搬移,另一種可以採用過往筆者介紹的策略模式來解決,抽換掉遍歷演算法。

不過本篇要介紹的是針對這一類,需要遍歷不同的資料結構型態,更適合的一種設計模式 —— 迭代器模式

迭代器模式 Iterator Pattern

資深的讀者應該隱約猜出筆者想要講的重點,筆者就速速把迭代器模式要達到的效果交代一下:

重點 3. 迭代器模式 Iterator Pattern

迭代器模式的主要目的在於不需要知曉任意聚合物的細節,就可以依序遍歷內含的每一個元素

也就是說,我們可以宣告統一的產出迭代器的介面(Iterator Generator Interface),而任何互相毫無關聯甚至是實作上天差地遠的聚合物,都可以藉由實踐該介面,產出同樣功能的迭代器,達到泛用的效果。

讀者看不懂,沒關係,因為設計模式這種東西光看定義能夠領會的人(除非你有經歷過)應該也不到兩成,原著也只有說明第一句話:

不需要知曉任意聚合物的細節,就可以依序遍歷內含的每一個元素 - 出自《Design Patterns — Elements of Reusable Object-Oriented Software》

筆者必須澄清:重點 3 的第二段不是出自原著,而是筆者為了因應 TypeScript 的使用情形,才寫出來的額外補充片段。

迭代器模式下的角色

根據本篇每一個重點的描述,角色看起來很明確只有兩個:迭代器(Iterator)以及聚合物(Collection)。

不過,事實上這裡有一個很細微、不知道讀者有沒有注意到的點:

(...重點 3 第二段前面略)而任何互相毫無關聯甚至是實作上天差地遠的聚合物,都可以藉由實踐該介面,產出同樣功能的迭代器,達到泛用的效果。

“產出”這兩字的關鍵 —— 超級重要,暗示隱藏的背後角色還有一個產出迭代器的介面(Iterator Generator Interface)。

也就是說,我們除了迭代器的介面到底長什麼樣子外,聚合物也必須實作另一個功能 —— 專門產出對應的迭代器 —— 這不很像之前講過的 Factory Method 模式

所以筆者宣告兩個介面 —— Iterator 以及 Iterable 這兩種分別代表 —— 迭代器的介面,以及可被迭代的聚合物必須實踐的介面

https://ithelp.ithome.com.tw/upload/images/20191012/201206144gQFMnSOcU.png

所以筆者簡單實作陽春版迭代器~!

https://ithelp.ithome.com.tw/upload/images/20191012/20120614nZN5JKCVS6.png

讀者可能看到上面的程式碼心想:“搞什麼嘛!普通的陣列不是單純用 for 迴圈迭代就好了嗎? —— 難道作者耍我嗎?”

不!不!不!並不是這樣的,筆者當然要先舉簡單的例子給讀者看,讓讀者先熟悉實踐迭代器模式的基本過程而已,讀者忍一下~

史上最基本的迭代器的關聯圖呈現如圖一。

https://ithelp.ithome.com.tw/upload/images/20191012/20120614t9qkO1ycO9.png
圖一:迭代器模式分成兩個部分 —— 一是迭代器本身的介面,另一個是對任意的聚合物實踐 Iterable 介面,也就是工廠方法負責產出該聚合物的迭代器

要使用聚合物的迭代器非常簡單。(以下程式碼輸出結果如圖二)

https://ithelp.ithome.com.tw/upload/images/20191012/20120614WjdD4gXqgj.png

https://ithelp.ithome.com.tw/upload/images/20191012/20120614XIsUBLyzW7.png
圖二:順利地迭代普通陣列的值

迭代器模式的優勢

接下來筆者要解釋為何迭代器模式很好用。前一篇筆者有展示過一個鏈結串列的實踐過程 —— GenericLinkedList<T> 類別。

https://ithelp.ithome.com.tw/upload/images/20191012/20120614PJLVRoKDPh.png

普通情況下,要迭代這個 GenericLinkedList,我們可能必須手動這樣寫:

https://ithelp.ithome.com.tw/upload/images/20191012/20120614cPDSGUeeeH.png

不過我們希望這個 GenericLinkedList 也可以產出和 Iterator 同樣介面的迭代器,這樣一來,除了基本的陣列 MyArray 外,如果是 GenericLinkedList 也可以用相同的迭代器介面去遍歷裡面的內容。

一種寫法是直接讓 GenericLinkedList 再去實踐 Iterable 這個介面,另一種則是在宣告一個子類別繼承 GenericLinkedList 並實踐 Iterable 介面:

https://ithelp.ithome.com.tw/upload/images/20191012/20120614IMgGNmbKlo.png

貼心小提示

筆者在很遙遠的陣列型別篇章有講到:空陣列由於內部沒有任何型別可以參考,因此 TypeScript 無法判斷 [] 型別為 Array<T> 中的 T 為何,因此必須積極註記。

筆者來寫一個函式 foreach<T>,專門接受 Iterator<T> 型別還有一個回呼函式,進行迭代的動作:

https://ithelp.ithome.com.tw/upload/images/20191012/20120614nh9dil3mV0.png

記得,foreach 之所以要有型別參數變成泛用函式的理由是因為要能夠接收各種不同型別的 Iterator 物件。

以下的程式碼就來測測看 foreach<T> 這個函式。(測試結果如圖三)

https://ithelp.ithome.com.tw/upload/images/20191012/20120614lGWBI7LAZE.png

https://ithelp.ithome.com.tw/upload/images/20191012/20120614xGygHKUnnK.png
圖三:這個行為在設計模式原著又有一個名稱 —— 多型巡訪(Polymorphic Iteration)

以上的 foreach<T>,儘管來源是不同的聚合物,但是我們卻可以用同一個迭代方式去遍歷每一個元素,這個被稱為多型巡訪。(多 Fancy 的名稱)

另外,你也可以發現我們不用在擔心說還要特定幫 LinkedList 相關的類別還要想著怎麼寫 while 迴圈去做迭代 —— 這個邏輯本身被 NormalIterator<T> 給做掉了

重點 4. 迭代器模式的優勢 Advantage of Using Iterator Pattern

不需要管聚合物的結構如何,我們都可以藉由迭代器模式的操作下,統一所有聚合物的迭代方式 —— 又名多型巡訪(Polymorphic Iteration)。

你也不需要再去為不同的聚合物宣告迭代的方式,因為這些邏輯都被迭代器模式給做掉了

其實迭代器模式,講直白點主要就是把聚合物內部的結構隱藏在該聚合物類別裡 —— 綁定 Iterable<T> 介面負責去宣告建構統一的迭代器介面而已。

筆者繼續延伸:假設我們也有二元樹 BinaryTree 這種資料結構。

https://ithelp.ithome.com.tw/upload/images/20191012/20120614BQNQZapdig.png

筆者知道以上的 BinaryTree 是過度簡化的版本,不過就將就一下給大家看建造一顆二元樹的過程。另外,忘記存取方法(Access Methods)請參考這一篇

https://ithelp.ithome.com.tw/upload/images/20191013/20120614kO4R2zVoji.png

以上的程式碼建造的樹之結構如圖四。

https://ithelp.ithome.com.tw/upload/images/20191012/201206141x1ylyiygm.png
圖四:這是按照上面的程式碼建構出來的 BinaryTree 的長相

平常如果你想要遍歷樹狀資料結構,我們又還分前序、中序與後序 —— 筆者本篇以*前序(Preorder)走訪模式*為例,根據圖四,前序走訪的順序剛好是從 TreeNode 之數字 1 走到數字 10。

所以我們可以這麼做 —— 將 BinaryTree<T> 實踐 Iterable<T> 介面,然後創建出前序走訪過後的迭代器

https://ithelp.ithome.com.tw/upload/images/20191013/20120614XrcSzauNAi.png

以下是比較普通使用 preorderTraversal 的手法,比對建立迭代器然後套入剛剛筆者定義的 foreach<T> 函式:

https://ithelp.ithome.com.tw/upload/images/20191013/20120614uw9X9nVquz.png

測試結果都是印出 1 ~ 10 這些數字。(如圖五)

https://ithelp.ithome.com.tw/upload/images/20191013/20120614c1CnrpxFpW.png
圖五:筆者一再地印證,就算資料結構再複雜,我們都可以在外面使用相同的 Iterator<T> 提供的功能,達到多型巡訪這個很酷的功能

以下的關聯圖(圖六)展示的就是將剛剛 MyArray<T>IterableLinkedList<T> 以及 BinaryTree<T> 這三種看似不可能用同個介面巡訪的方式 —— 藉由迭代器模式統一下來。

https://ithelp.ithome.com.tw/upload/images/20191013/20120614DC7mDgWsJt.png
圖六:就算你用再複雜的聚合物,我們都可以達到統一巡訪的模式

小結

這一篇不用說,花最多時間就是在畫圖上...

不過筆者大致上把該 Cover 的東西都大概講述完畢了,接下來還要其他泛用型別的應用~


上一篇
Day 45. 通用武裝・泛用類別與介面 X 終極組合第二彈 - Ultimate Combo of Generic Class & Interface
下一篇
Day 47. 通用武裝・泛型應用 X 結合 ES2015+ - TypeScript Generics with ES2015+ Features
系列文
讓 TypeScript 成為你全端開發的 ACE!51

1 則留言

0
ch_lute
iT邦新手 5 級 ‧ 2020-02-14 13:22:53

IsDone()應該是 return this.currentItem == null ?

我要留言

立即登入留言