begin with one quickSort
之前在学习时曾看到swift如此简洁地表达出了快排算法。
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 []
}
}
时虽叹于其惊艳，但亦惑于其生涩。其实我已经不打算讲解这个算法了，但不讲就没法引出主角Sequence。咳咳，开课！
- 这段代码的精髓在于数据结构的扩展。在extension中定义了一个可选的返回数组首元素和剩余元素的属性
decompose，以此大大减少了代码量。 - 第一次见filter的时候，只想说这是啥玩意儿啊……咳，这是个过滤器。查看文档可知其接收一个
isIncluded闭包参数，此闭包用来判断Sequence中每个元素是否符合条件并返回bool值标识此元素是否要被加入到方法返回值。就这样依次过滤出数组中符合条件的元素，并返回一个这些元素组成的数组。 - 最后经过递归依次完成排序，再拼接数组。
声明：关于这段代码网络上有很多版本，有在Element处使用泛型T，如下：
var decompose : (head: T, tail: [T])? {...}
泛型T会在很多类型定义中使用，以此来接收不定类型的值（比如map，映射返回的值类型是不定的），在这个算法里完全没有必要。还有直接将三个数组同时拼接的：
return qsortDemo(input: lesser) + [pivot] + qsortDemo(input: greater)
之前是可行的，但现在貌似会报错，暂不深入。
So what's Sequence?
在上例的快排算法中，我们用到了数组的filter方法,也提到了map方法。其实在这些我们常用的数组方法背后，有一个坚挺的Sequence协议……这个协议与其后的Collection，Bidirectional Collection，Random Access Collection，Range Replaceable Collection，Mutable Collection（依次是集合、双向集合、随机访问集合、范围可替代集合、可变集合协议）一起定义了所有我们能够使用的数组方法。
序列是记录了一组元素的列表，可以是无限或有限的，且只能迭代一次。其定义分两部分：
protocol Sequence {
//关联类型，即遵守IteratorProtocol的Iterator。
associatedtype Iterator: IteratorProtocol
//用来构建Iterator的函数，返回的Iterator必须与声明的Iterator类型相同
func makeIterator() -> Iterator
}
关于其关联类型迭代器遵守的协议有如下定义：
protocol IteratorProtcol {
associatedtype Element
mutating func next() -> Element?
}
IteratorProtcol与序列协议相似，拥有一个关联类型Element，即迭代器声明的类型（需要迭代的类型）；next函数返回序列的下一个元素并对迭代器本身进行修改（mutating）（使迭代器指向下一个Element）。
Let's start with LinkedList !
我们以链表为例来探讨Sequence协议。我们可以用enum（枚举）来定义一个链表：
//indirect关键字意味着我们将要在此类型内部使用LinkedListNode<T>;
indirect enum LinkedListNode<T> {
case value(element: T, next: LinkedListNode<T>
case end
}
现在，我们得到了一个链表，可以通过一个元素来得到下一个元素的链表。但是，我们还不能对这个链表使用枚举（enum）、循环（比如for）、映射（map）、或者过滤（filter）等功能。
如果我们让此链表遵循sequence协议的话，它就获取了使用上述功能的资格，就像我们在视图控制器里使用表格的协议来达成一些特定的功能一样。
extension LinkedListNode: Sequence {
func makeIterator() -> ??? {
return ???
}
}
之前我们了解到sequence协议中有一个非可选的方法makeIterator，这意味着我们必须在遵循协议时实现这个方法来构造迭代器。在这时，我们还不知道需要返回什么关联类型，但不用担心，我们会把这个问题解决。
在实现sequence协议时，我们不知道声明何种迭代器来作为关联类型，但我们知道这个关联类型与IteratorProtcol息息相关。我们必须先实现这个协议看看：
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
}
}
}
这个时候，我们已知的就是IteratorProtcol需要关联链表中的元素类别，以及我们会使用next来返回链表中下一个这种类别的元素。由于我们并不知道我们需要什么类别的元素，所以必须使用泛型T来构建这个自由的选择空间。与此同时，我们需要实现协议中的非可选方法next，我们知道链表可以只有一项或有很多项，这就意味着next需要返回可选的T。
这时我们需要关注的就是???。它是Sequence协议需要的关联类型，也是需要遵循IteratorProtocol的一个迭代器。我们使用何种类型的迭代器来完成迭代操作，就意味着我们需要实现哪种类型的迭代。链表迭代器（LinkedListIterator，因为我们在拿链表做实验）正是我们需要的啊。但是单迭代器的返回是没有意义的，我们需要知道它将迭代何种类型，很显然我们不知道（因为那是链表被实例化后才可以推断出的），所以使用泛型T。于是我们可以得出???-->LinkedListIterator<T>。即完整的实现sequence协议需要以下代码：
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 {
//用于指出迭代器当前处于序列何处的状态变量，它指向链表当前节点。
var current: LinkedListNode<T>
//实现next需要的功能。
mutating func next() -> T? {
switch current {
case let .value(element, next):
current = next
return element
case .end:
return nil
}
}
}
就这样，我们已经得到了一个遵循着Sequence协议的链表。现在你可以使用for loop、filter或者map...（很多功能，自己脑补吧）...来操作这个链表。
See this mysterious iterator
上面我们已经定义了一个LinkedListNode<T>类型的链表。我们通过实例化一个存放三个元素A,B,C的链表来探讨迭代器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)
当然，下面这种形式也能创建同样的链表，如果你喜欢这样写的话（虽然这样看起来更有链表的样子）：
let linkedList = LinkedListNode<String>.value(element: "A", next: LinkedListNode<String>.value(element: "B", next: LinkedListNode<String>.value(element: "C", next: LinkedListNode<String>.end)))
现在我们就可以用linkedList来创建一个Iterator了：
var iterator = linkedList.makeIterator();
由上面遵循的sequence协议可知，我们创建出的Iterator包含有指向链表头的指针，即current变量。我们可以通过调用iterator.next来返回链表首元素A，这时，current会通过IteratorProtocol更新以指向下一个元素：
var element: Any?
repeat {
//把当前迭代器指向的元素赋值给element。
element = iterator.next()
//repeat依次打印出A、B、C
if let _ = element
{print(element!)}
} while ((element as? String) != nil)
Add functions to our LinkedList
如果我们需要某些操作，比如查询链表中符合某条件元素的个数。这很简单，使用filter选出元素组成数组，再调用count计数：
let numberOfAdmins = users.filter({ $0.isAdmin }).count
我们何不直接扩展sequence协议，添加count方法，这样我们就能这样写了：
//是不是比上面的写法好看多了。。。。
let numberOfAdmins = users.count({ $0.isAdmin })
那我们就尝试扩展一下sequence协议吧。为了实现这个想法，我们需要在extension 中定义一个count 方法：
extension Sequence {
//我们已经知道的是需要返回一个Int值
func count(...) -> Int {
var count = 0
//逻辑实现
return count
}
}
首先要知道我们希望的形式是users.count({ $0.isAdmin })，这样一来我们可以参考filter的形式（最前面快排算法中提到），使其接收一个isIncluded闭包参数并返回bool值判断是否加入元素到返回序列。闭包中需要使用序列中的元素，也就是我们链表中的元素。上面讲迭代器时我们知道可以通过iterator.element来访问这些元素。那么，当当！我们的参数部分就完成了：
func count(_ isIncluded: (Iterator.Element) -> Bool) -> Int {...}
接下来就只需要处理count，使其返回为符合条件的值个数。我们知道filter筛选元素就是通过接收到的这个闭包参数完成的。所以我们需要获取所有元素，并依次通过isIncluded来标记它们：
//此处self即是调用此方法的链表
for element in self{
//满足我们自己所写条件时标记一次
if isIncluded(element){
count += 1
}
}
到这里我们的count方法已经完成，并且可以调用了。全部实现及调用如下：
//实现
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
}
}
//调用
let countOfA = linkedList.count({$0 == "A"})
//等价于
let countOfA = linkedList.filter({$0 == "A"}).count
