begin with one quickSort

之前在學(xué)習(xí)時(shí)曾看到swift如此簡(jiǎn)潔地表達(dá)出了快排算法。

extension Array {
    var decompose : (head: Element, tail: [Element])? {
        return (count > 0) ? (self[0], Array(self[1..<count])) : nil
    }
}

func quickSort(input: [Int]) -> [Int] {
    if let (pivot, rest) = input.decompose {
        let lesser = rest.filter { $0 < pivot }
        let greater = rest.filter { $0 >= pivot }
        let a = quickSort(input: lesser) + [pivot]
        let b = a + quickSort(input: greater)
        return b
    } else {
        return []
    }
}

時(shí)雖嘆于其驚艷，但亦惑于其生澀。其實(shí)我已經(jīng)不打算講解這個(gè)算法了，但不講就沒(méi)法引出主角Sequence?？瓤龋_(kāi)課！

• 這段代碼的精髓在于數(shù)據(jù)結(jié)構(gòu)的擴(kuò)展。在extension中定義了一個(gè)可選的返回?cái)?shù)組首元素和剩余元素的屬性decompose，以此大大減少了代碼量。
• 第一次見(jiàn)filter的時(shí)候，只想說(shuō)這是啥玩意兒啊……咳，這是個(gè)過(guò)濾器。查看文檔可知其接收一個(gè)isIncluded閉包參數(shù)，此閉包用來(lái)判斷 Sequence中每個(gè)元素是否符合條件并返回bool值標(biāo)識(shí)此元素是否要被加入到方法返回值。就這樣依次過(guò)濾出數(shù)組中符合條件的元素，并返回一個(gè)這些元素組成的數(shù)組。
• 最后經(jīng)過(guò)遞歸依次完成排序，再拼接數(shù)組。

聲明：關(guān)于這段代碼網(wǎng)絡(luò)上有很多版本，有在Element處使用泛型T，如下：

var decompose : (head: T, tail: [T])? {...}

泛型T會(huì)在很多類型定義中使用，以此來(lái)接收不定類型的值（比如map，映射返回的值類型是不定的），在這個(gè)算法里完全沒(méi)有必要。還有直接將三個(gè)數(shù)組同時(shí)拼接的：

return qsortDemo(input: lesser) + [pivot] + qsortDemo(input: greater)

之前是可行的，但現(xiàn)在貌似會(huì)報(bào)錯(cuò)，暫不深入。

So what's Sequence?

在上例的快排算法中，我們用到了數(shù)組的filter方法,也提到了map方法。其實(shí)在這些我們常用的數(shù)組方法背后，有一個(gè)堅(jiān)挺的Sequence協(xié)議……這個(gè)協(xié)議與其后的Collection，Bidirectional Collection，Random Access Collection，Range Replaceable Collection，Mutable Collection（依次是集合、雙向集合、隨機(jī)訪問(wèn)集合、范圍可替代集合、可變集合協(xié)議）一起定義了所有我們能夠使用的數(shù)組方法。

序列是記錄了一組元素的列表，可以是無(wú)限或有限的，且只能迭代一次。其定義分兩部分：

protocol Sequence {
    //關(guān)聯(lián)類型，即遵守IteratorProtocol的Iterator。
    associatedtype Iterator: IteratorProtocol
    //用來(lái)構(gòu)建Iterator的函數(shù)，返回的Iterator必須與聲明的Iterator類型相同
    func makeIterator() -> Iterator
}

關(guān)于其關(guān)聯(lián)類型迭代器遵守的協(xié)議有如下定義：

protocol IteratorProtcol {
    associatedtype Element
    mutating func next() -> Element?
}

IteratorProtcol與序列協(xié)議相似，擁有一個(gè)關(guān)聯(lián)類型Element，即迭代器聲明的類型（需要迭代的類型）；next函數(shù)返回序列的下一個(gè)元素并對(duì)迭代器本身進(jìn)行修改（mutating）（使迭代器指向下一個(gè)Element）。

Let's start with LinkedList !

我們以鏈表為例來(lái)探討Sequence協(xié)議。我們可以用enum（枚舉）來(lái)定義一個(gè)鏈表：

//indirect關(guān)鍵字意味著我們將要在此類型內(nèi)部使用LinkedListNode<T>;
indirect enum LinkedListNode<T> {
    case value(element: T, next: LinkedListNode<T>
    case end
}

現(xiàn)在，我們得到了一個(gè)鏈表，可以通過(guò)一個(gè)元素來(lái)得到下一個(gè)元素的鏈表。但是，我們還不能對(duì)這個(gè)鏈表使用枚舉（enum）、循環(huán)（比如for）、映射（map）、或者過(guò)濾（filter）等功能。

如果我們讓此鏈表遵循sequence協(xié)議的話，它就獲取了使用上述功能的資格，就像我們?cè)谝晥D控制器里使用表格的協(xié)議來(lái)達(dá)成一些特定的功能一樣。

extension LinkedListNode: Sequence {
    func makeIterator() -> ??? {
        return ???
    }
}

之前我們了解到sequence協(xié)議中有一個(gè)非可選的方法makeIterator，這意味著我們必須在遵循協(xié)議時(shí)實(shí)現(xiàn)這個(gè)方法來(lái)構(gòu)造迭代器。在這時(shí)，我們還不知道需要返回什么關(guān)聯(lián)類型，但不用擔(dān)心，我們會(huì)把這個(gè)問(wèn)題解決。

在實(shí)現(xiàn)sequence協(xié)議時(shí)，我們不知道聲明何種迭代器來(lái)作為關(guān)聯(lián)類型，但我們知道這個(gè)關(guān)聯(lián)類型與IteratorProtcol息息相關(guān)。我們必須先實(shí)現(xiàn)這個(gè)協(xié)議看看：

struct ???: IteratorProtocol {

    var current: LinkedListNode<T>

    mutating func next() -> T? {
        switch current {
        case let .value(element, next):
            current = next
            return element
        case .end:
            return nil
        }
    }
}

這個(gè)時(shí)候，我們已知的就是IteratorProtcol需要關(guān)聯(lián)鏈表中的元素類別，以及我們會(huì)使用next來(lái)返回鏈表中下一個(gè)這種類別的元素。由于我們并不知道我們需要什么類別的元素，所以必須使用泛型T來(lái)構(gòu)建這個(gè)自由的選擇空間。與此同時(shí)，我們需要實(shí)現(xiàn)協(xié)議中的非可選方法next，我們知道鏈表可以只有一項(xiàng)或有很多項(xiàng)，這就意味著next需要返回可選的T。

這時(shí)我們需要關(guān)注的就是???。它是Sequence協(xié)議需要的關(guān)聯(lián)類型，也是需要遵循IteratorProtocol的一個(gè)迭代器。我們使用何種類型的迭代器來(lái)完成迭代操作，就意味著我們需要實(shí)現(xiàn)哪種類型的迭代。鏈表迭代器（LinkedListIterator，因?yàn)槲覀冊(cè)谀面湵碜鰧?shí)驗(yàn)）正是我們需要的啊。但是單迭代器的返回是沒(méi)有意義的，我們需要知道它將迭代何種類型，很顯然我們不知道（因?yàn)槟鞘擎湵肀粚?shí)例化后才可以推斷出的），所以使用泛型T。于是我們可以得出???-->LinkedListIterator<T>。即完整的實(shí)現(xiàn)sequence協(xié)議需要以下代碼：

indirect enum LinkedListNode<T> {
    case value(element: T, next: LinkedListNode<T>
    case end
}
  
extension LinkedListNode: Sequence {
    func makeIterator() -> LinkedListIterator<T> {
        //returns current
        return LinkedListIterator(current: self)
    }
}

struct LinkedListIterator<T>: IteratorProtocol {
    //用于指出迭代器當(dāng)前處于序列何處的狀態(tài)變量，它指向鏈表當(dāng)前節(jié)點(diǎn)。
    var current: LinkedListNode<T>
    //實(shí)現(xiàn)next需要的功能。
    mutating func next() -> T? {
        switch current {
        case let .value(element, next):
            current = next
            return element
        case .end:
            return nil
        }
    }
}

就這樣，我們已經(jīng)得到了一個(gè)遵循著Sequence協(xié)議的鏈表?，F(xiàn)在你可以使用for loop、filter或者map...（很多功能，自己腦補(bǔ)吧）...來(lái)操作這個(gè)鏈表。

See this mysterious iterator

上面我們已經(jīng)定義了一個(gè)LinkedListNode<T>類型的鏈表。我們通過(guò)實(shí)例化一個(gè)存放三個(gè)元素A,B,C的鏈表來(lái)探討迭代器Iterator：

let linkedList = LinkedListNode<String>.value(element: "A", next: secondNode)
let secondNode = LinkedListNode<String>.value(element: "B", next: thirdNode)
let thirdNode = LinkedListNode<String>.value(element: "C", next: LinkedListNode<String>.end)

當(dāng)然，下面這種形式也能創(chuàng)建同樣的鏈表，如果你喜歡這樣寫(xiě)的話（雖然這樣看起來(lái)更有鏈表的樣子）：

let linkedList = LinkedListNode<String>.value(element: "A", next: LinkedListNode<String>.value(element: "B", next: LinkedListNode<String>.value(element: "C", next: LinkedListNode<String>.end)))

現(xiàn)在我們就可以用linkedList來(lái)創(chuàng)建一個(gè)Iterator了：

var iterator = linkedList.makeIterator();

由上面遵循的sequence協(xié)議可知，我們創(chuàng)建出的Iterator包含有指向鏈表頭的指針，即current變量。我們可以通過(guò)調(diào)用iterator.next來(lái)返回鏈表首元素A，這時(shí)，current會(huì)通過(guò)IteratorProtocol更新以指向下一個(gè)元素：

var element: Any?
repeat {
     //把當(dāng)前迭代器指向的元素賦值給element。
     element = iterator.next()
     //repeat依次打印出A、B、C
     if let _ = element
     {print(element!)}
} while ((element as? String) != nil)

Add functions to our LinkedList

如果我們需要某些操作，比如查詢鏈表中符合某條件元素的個(gè)數(shù)。這很簡(jiǎn)單，使用filter選出元素組成數(shù)組，再調(diào)用count計(jì)數(shù)：

let numberOfAdmins = users.filter({ $0.isAdmin }).count

我們何不直接擴(kuò)展sequence協(xié)議，添加count方法，這樣我們就能這樣寫(xiě)了：

//是不是比上面的寫(xiě)法好看多了。。。。
let numberOfAdmins = users.count({ $0.isAdmin })

那我們就嘗試擴(kuò)展一下sequence協(xié)議吧。為了實(shí)現(xiàn)這個(gè)想法，我們需要在extension 中定義一個(gè)count 方法：

extension Sequence {
//我們已經(jīng)知道的是需要返回一個(gè)Int值
    func count(...) -> Int {
        var count = 0
        //邏輯實(shí)現(xiàn)
        return count
    }
}

首先要知道我們希望的形式是users.count({ $0.isAdmin })，這樣一來(lái)我們可以參考filter的形式（最前面快排算法中提到），使其接收一個(gè)isIncluded閉包參數(shù)并返回bool值判斷是否加入元素到返回序列。閉包中需要使用序列中的元素，也就是我們鏈表中的元素。上面講迭代器時(shí)我們知道可以通過(guò)iterator.element來(lái)訪問(wèn)這些元素。那么，當(dāng)當(dāng)！我們的參數(shù)部分就完成了：

func count(_ isIncluded: (Iterator.Element) -> Bool) -> Int {...}

接下來(lái)就只需要處理count，使其返回為符合條件的值個(gè)數(shù)。我們知道filter篩選元素就是通過(guò)接收到的這個(gè)閉包參數(shù)完成的。所以我們需要獲取所有元素，并依次通過(guò)isIncluded來(lái)標(biāo)記它們：

//此處self即是調(diào)用此方法的鏈表
for element in self{
    //滿足我們自己所寫(xiě)條件時(shí)標(biāo)記一次
    if isIncluded(element){
       count += 1
    }
}

到這里我們的count方法已經(jīng)完成，并且可以調(diào)用了。全部實(shí)現(xiàn)及調(diào)用如下：

//實(shí)現(xiàn)
extension Sequence{
    
    func count(_ isIncluded:(Iterator.Element) -> Bool) -> Int{
        
        var count = 0
        for element in self{
            print(self)
            if isIncluded(element){
                count += 1
            }
        }
        return count
    }
}
//調(diào)用
let countOfA = linkedList.count({$0 == "A"})
//等價(jià)于
let countOfA = linkedList.filter({$0 == "A"}).count

Happy ending

• 感謝不可數(shù)的愛(ài)提供技術(shù)引導(dǎo)及支持，推薦大家關(guān)注其MVVM Github項(xiàng)目。