Swift底層進階--017：Sequence & Collection

Sequence協議

Sequence協議是集合類型結構中的基礎唱捣，是一系列相同類型的值的集合两蟀，并且提供對這些值的迭代能力。Sequence協議提供了許多強大的功能震缭，遵循該協議的類型都可以直接使用這些功能垫竞。

迭代一個Sequence最常見的方式就是for...in循環(huán)

let numbers = [2, 4, 6, 8]

for num in numbers {
    print(num)
}

分析SIL代碼

將上述代碼生成SIL文件：swiftc -emit-sil main.swift | xcrun swift-demangle

// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @main.numbers : [Swift.Int]           // id: %2
  %3 = global_addr @main.numbers : [Swift.Int] : $*Array<Int> // users: %30, %28
  %4 = integer_literal $Builtin.Word, 4           // user: %6
  // function_ref _allocateUninitializedArray<A>(_:)
  %5 = function_ref @Swift._allocateUninitializedArray<A>(Builtin.Word) -> ([A], Builtin.RawPointer) : $@convention(thin) <τ_0_0> (Builtin.Word) -> (@owned Array<τ_0_0>, Builtin.RawPointer) // user: %6
  %6 = apply %5<Int>(%4) : $@convention(thin) <τ_0_0> (Builtin.Word) -> (@owned Array<τ_0_0>, Builtin.RawPointer) // users: %8, %7
  %7 = tuple_extract %6 : $(Array<Int>, Builtin.RawPointer), 0 // user: %28
  %8 = tuple_extract %6 : $(Array<Int>, Builtin.RawPointer), 1 // user: %9
  %9 = pointer_to_address %8 : $Builtin.RawPointer to [strict] $*Int // users: %12, %24, %19, %14
  %10 = integer_literal $Builtin.Int64, 2         // user: %11
  %11 = struct $Int (%10 : $Builtin.Int64)        // user: %12
  store %11 to %9 : $*Int                         // id: %12
  %13 = integer_literal $Builtin.Word, 1          // user: %14
  %14 = index_addr %9 : $*Int, %13 : $Builtin.Word // user: %17
  %15 = integer_literal $Builtin.Int64, 4         // user: %16
  %16 = struct $Int (%15 : $Builtin.Int64)        // user: %17
  store %16 to %14 : $*Int                        // id: %17
  %18 = integer_literal $Builtin.Word, 2          // user: %19
  %19 = index_addr %9 : $*Int, %18 : $Builtin.Word // user: %22
  %20 = integer_literal $Builtin.Int64, 6         // user: %21
  %21 = struct $Int (%20 : $Builtin.Int64)        // user: %22
  store %21 to %19 : $*Int                        // id: %22
  %23 = integer_literal $Builtin.Word, 3          // user: %24
  %24 = index_addr %9 : $*Int, %23 : $Builtin.Word // user: %27
  %25 = integer_literal $Builtin.Int64, 8         // user: %26
  %26 = struct $Int (%25 : $Builtin.Int64)        // user: %27
  store %26 to %24 : $*Int                        // id: %27
  store %7 to %3 : $*Array<Int>                   // id: %28
  %29 = alloc_stack $IndexingIterator<Array<Int>>, var, name "$num$generator" // users: %35, %49, %48, %40
  %30 = load %3 : $*Array<Int>                    // users: %33, %31
  retain_value %30 : $Array<Int>                  // id: %31
  %32 = alloc_stack $Array<Int>                   // users: %33, %35, %37
  store %30 to %32 : $*Array<Int>                 // id: %33
  // function_ref Collection<>.makeIterator()
  %34 = function_ref @(extension in Swift):Swift.Collection< where A.Iterator == Swift.IndexingIterator<A>>.makeIterator() -> Swift.IndexingIterator<A> : $@convention(method) <τ_0_0 where τ_0_0 : Collection, τ_0_0.Iterator == IndexingIterator<τ_0_0>> (@in τ_0_0) -> @out IndexingIterator<τ_0_0> // user: %35
  %35 = apply %34<Array<Int>>(%29, %32) : $@convention(method) <τ_0_0 where τ_0_0 : Collection, τ_0_0.Iterator == IndexingIterator<τ_0_0>> (@in τ_0_0) -> @out IndexingIterator<τ_0_0>
  %36 = tuple ()
  dealloc_stack %32 : $*Array<Int>                // id: %37
  br bb1                                          // id: %38

bb1:                                              // Preds: bb3 bb0
  %39 = alloc_stack $Optional<Int>                // users: %45, %42, %46
  %40 = begin_access [modify] [static] %29 : $*IndexingIterator<Array<Int>> // users: %42, %44
  // function_ref IndexingIterator.next()
  %41 = function_ref @Swift.IndexingIterator.next() -> A.Element? : $@convention(method) <τ_0_0 where τ_0_0 : Collection> (@inout IndexingIterator<τ_0_0>) -> @out Optional<τ_0_0.Element> // user: %42
  %42 = apply %41<Array<Int>>(%39, %40) : $@convention(method) <τ_0_0 where τ_0_0 : Collection> (@inout IndexingIterator<τ_0_0>) -> @out Optional<τ_0_0.Element>
  %43 = tuple ()
  end_access %40 : $*IndexingIterator<Array<Int>> // id: %44
  %45 = load %39 : $*Optional<Int>                // user: %47
  dealloc_stack %39 : $*Optional<Int>             // id: %46
  switch_enum %45 : $Optional<Int>, case #Optional.some!enumelt: bb3, case #Optional.none!enumelt: bb2 // id: %47

main函數：

%29：創(chuàng)建IndexingIterator<Array<Int>>迭代器

%34：當遍歷元素時，調用Collection協議中的makeIterator()方法蛀序，創(chuàng)建了一個IndexingIterator

bb1函數：

%41：通過IndexingIterator.next()方法來不斷拿到元素

所以平常寫的for...in是不存在的欢瞪，它僅是一個語法糖

源碼分析

打開Collection.swift文件

public struct IndexingIterator<Elements: Collection> {
  @usableFromInline
  internal let _elements: Elements
  @usableFromInline
  internal var _position: Elements.Index

  @inlinable
  @inline(__always)
  /// Creates an iterator over the given collection.
  public /// @testable
  init(_elements: Elements) {
    self._elements = _elements
    self._position = _elements.startIndex
  }

  @inlinable
  @inline(__always)
  /// Creates an iterator over the given collection.
  public /// @testable
  init(_elements: Elements, _position: Elements.Index) {
    self._elements = _elements
    self._position = _position
  }
}

extension IndexingIterator: IteratorProtocol, Sequence {
  public typealias Element = Elements.Element
  public typealias Iterator = IndexingIterator<Elements>
  public typealias SubSequence = AnySequence<Element>

  @inlinable
  @inline(__always)
  public mutating func next() -> Elements.Element? {
    if _position == _elements.endIndex { return nil }
    let element = _elements[_position]
    _elements.formIndex(after: &_position)
    return element
  }
}

IndexingIterator是一個接收泛型的結構體

IndexingIterator遵循IteratorProtocol和Sequence兩個協議

打開Sequence.swift文件

IteratorProtocol：一次提供一個序列值的類型，它和Sequence協議是息息相關的

Sequence：每次通過創(chuàng)建迭代器來訪問序列中的元素

所以每次使用for..in的時候徐裸，其實都使用這個集合的迭代器來遍歷當前集合或序列中的元素

找到IteratorProtocol協議的定義

public protocol IteratorProtocol {
  /// The type of element traversed by the iterator.
  associatedtype Element

  mutating func next() -> Element?
}

Element：關聯類型遣鼓，取決于實現該協議的提供者

next：使用mutating修飾的next方法，返回一個element

找到Sequence協議的定義

public protocol Sequence {
  /// A type representing the sequence's elements.
  associatedtype Element

  /// A type that provides the sequence's iteration interface and
  /// encapsulates its iteration state.
  associatedtype Iterator: IteratorProtocol where Iterator.Element == Element

  __consuming func makeIterator() -> Iterator

  var underestimatedCount: Int { get }

  func _customContainsEquatableElement(
    _ element: Element
  ) -> Bool?

  __consuming func _copyToContiguousArray() -> ContiguousArray<Element>

  __consuming func _copyContents(
    initializing ptr: UnsafeMutableBufferPointer<Element>
  ) -> (Iterator,UnsafeMutableBufferPointer<Element>.Index)
  
  func withContiguousStorageIfAvailable<R>(
    _ body: (UnsafeBufferPointer<Element>) throws -> R
  ) rethrows -> R?  
}

Element：關聯類型

Iterator：遵循IteratorProtocol協議重贺，并且有一個限制條件骑祟，Iterator和Sequence里面的Element類型必須相同

makeIterator：用來創(chuàng)建迭代器，返回一個Iterator

Sequence類似一個車間气笙，而Iterator類似一條條流水線

對于Sequence協議來說次企，表達的既可以是一個有限的集合，也可以是一個無限的集合潜圃，它只需要提供集合中的元素缸棵，和如何訪問這些元素的接口即可

案例

遵循Sequence和IteratorProtocol協議，創(chuàng)建一個可遍歷的結構體

struct LGSequence: Sequence {
    typealias Element = Int
    var arrayCount: Int

    init(_ count: Int) {
        self.arrayCount = count
    }

    func makeIterator() -> LGIterator{
        return LGIterator(self)
    }
}

struct LGIterator: IteratorProtocol {
    typealias Element = Int
    let seq: LGSequence
    var count = 0

    init(_ sequence: LGSequence) {
        self.seq = sequence
    }

    mutating func next() -> Int? {
        guard count < self.seq.arrayCount else {
            return nil
        }

        count += 1
        return count
    }
}

let seq = LGSequence.init(10)

for element in seq{
    print(element)
}

//輸出以下內容
//1
//2
//3
//4
//5
//6
//7
//8
//9
//10

LGSequence .arrayCount：提供一個Int類型的數據

LGSequence.init：初始化arrayCount

LGSequence.makeIterator：Sequence需要創(chuàng)建一個迭代器谭期，用來遍歷當前Sequence中的元素堵第，每次遍歷只會調用一次

LGIterator.init：提供一個構造方法吧凉，需要傳遞LGSequence

LGIterator.next，讓當前count做自增操作踏志，遍歷Sequence中的元素阀捅。當count小于LGSequence.arrayCount進行遍歷，否則返回nil終止遍歷针余。next方法在符合遍歷條件的情況下會調用多次

由此可見Sequence和Iterator兩者之間的關系

Collection協議

Collection協議遵循Sequence協議饲鄙，除線性遍歷以外，集合中的元素也可以通過下標索引的方式被獲取到圆雁。和序列不同忍级，集合類型不能是無限的。

上面提到的IndexingIterator結構體摸柄，接收泛型Elements遵循了Collection協議颤练，_position: Elements.Index提供了當前元素的Index

打開Collection.swift文件既忆，找到Collection協議的定義

public protocol Collection: Sequence {
  // FIXME: ideally this would be in MigrationSupport.swift, but it needs
  // to be on the protocol instead of as an extension
  @available(*, deprecated/*, obsoleted: 5.0*/, message: "all index distances are now of type Int")
  typealias IndexDistance = Int  

  // FIXME: Associated type inference requires this.
  override associatedtype Element

  associatedtype Index: Comparable

  var startIndex: Index { get }

  var endIndex: Index { get }

  associatedtype Iterator = IndexingIterator<Self>

  override __consuming func makeIterator() -> Iterator

  associatedtype SubSequence: Collection = Slice<Self>
  where SubSequence.Index == Index,
        Element == SubSequence.Element,
        SubSequence.SubSequence == SubSequence

  @_borrowed
  subscript(position: Index) -> Element { get }

  subscript(bounds: Range<Index>) -> SubSequence { get }

  associatedtype Indices: Collection = DefaultIndices<Self>
    where Indices.Element == Index, 
          Indices.Index == Index,
          Indices.SubSequence == Indices
        
  var indices: Indices { get }

  var isEmpty: Bool { get }

  var count: Int { get }

  func _customIndexOfEquatableElement(_ element: Element) -> Index??

  func _customLastIndexOfEquatableElement(_ element: Element) -> Index??

  func index(_ i: Index, offsetBy distance: Int) -> Index

  func index(
    _ i: Index, offsetBy distance: Int, limitedBy limit: Index
  ) -> Index?

  func distance(from start: Index, to end: Index) -> Int

  func _failEarlyRangeCheck(_ index: Index, bounds: Range<Index>)

  func _failEarlyRangeCheck(_ index: Index, bounds: ClosedRange<Index>)

  func _failEarlyRangeCheck(_ range: Range<Index>, bounds: Range<Index>)

  func index(after i: Index) -> Index

  func formIndex(after i: inout Index)
}

Collection協議建立在Sequence協議上驱负，除了從Sequence中繼承了全部方法以外，還默認實現了很多不同的方法和協議

通過環(huán)形緩沖區(qū)的結構患雇，來了解一下Collection協議的實現

案例1

為什么要有環(huán)形緩沖區(qū)跃脊？

例如數組，它是一個連續(xù)的線性存儲空間苛吱。

假設數組內存放了B酪术、C、D翠储、E绘雁、F等元素，此時要將元素A插入到數組Index為0的位置援所，這時需要將數組內已有元素全部向后移動一個位置庐舟，再將元素A插入。

如果刪除Index為0的元素住拭，數組內的其他元素都要向前移動一個位置挪略，以此來保證后續(xù)通過下標訪問元素的正確性。

所以數組存儲的元素越多滔岳，它的運行效率就越低下杠娱。這時可以設計一個環(huán)形緩沖區(qū)結構來改善效率問題。

環(huán)形緩沖區(qū)的結構谱煤，應該具有首位相連的特性摊求。

首先定義一個head指針表示頭結點，再定義一個tail指針表示尾結點刘离。

head指向當前讀取元素的索引位置睹簇，而tail指向下一個將要插入元素的空位置奏赘。

假設數組內存放了一個元素A，此時head指向Index為0的位置太惠，tail指向Index為1的位置磨淌。

當讀取元素時，將head移動到指定索引位置凿渊。

當環(huán)形緩沖區(qū)所存儲的元素滿了梁只，這時tail應該指向頭部，也就是Index為0的位置埃脏。

此時再插入元素X搪锣，應該插入到Index為0的位置，覆蓋之前的元素A彩掐。而tail應該指向下一個Index為1的位置构舟。

對于head的指向也是同理，讀取到結尾處堵幽，自動指向頭部狗超，讀取Index為0的位置，如此循環(huán)往復朴下。

通過代碼設計一個環(huán)形緩沖區(qū)結構

struct RingBuffer<Element>{
    
    var _buffer: ContiguousArray<Element?>
    
    var headIndex: Int = 0
    var tailIndex: Int = 0
    
    init(_ count: Int) {
        _buffer = ContiguousArray<Element?>.init(repeating: nil, count: count)
    }
    
    mutating func append(_ value: Element) {
        _buffer[tailIndex % _buffer.count] = value
        tailIndex += 1
    }
    
    mutating func pop() -> Element? {
        let result = _buffer[tailIndex % _buffer.count]
        headIndex += 1
        
        return result
    }
}

_buffer：定義為ContiguousArray類型努咐，ContiguousArray提供了和Array完全相同的功能，而Array的底層也使用了ContiguousArray結構來存儲數據殴胧。如果我們不需要與OC交互渗稍，使用ContiguousArray會更加高效

init：使用ContiguousArray的init(repeating: nil, count: count)初始化_buffer，指定_buffer的count大小团滥，全部使用nil填充

append：存儲元素的方法

pop：讀取元素的方法

上述代碼竿屹，其實就是一個簡單的環(huán)形緩沖區(qū)，具備了初步的功能灸姊，但存在以下幾個問題：

模運算的開銷是非常大的拱燃？能否替換掉

當前需要頻繁移動tailIndex

如何判斷環(huán)形緩沖區(qū)已滿？使用headIndex==tailIndex可以嗎厨钻？

刪除一個元素的邏輯是什么

如圖所示扼雏，tail指針其實指向的永遠都是當前空閑的節(jié)點，如果此時刪除index==4的元素夯膀，邏輯是什么诗充？

定位到index==4的位置，將value設置為nil

如果僅這樣處理诱建，后續(xù)再插入元素蝴蜓，會被插入到7的位置，這樣顯然不合理，因為前面仍有空閑位置

所以應該依次把5茎匠、6的位置向前移動格仲，再將tail的指向-1，這樣才能保證tail指向的是將要填充的空間

模運算替換為位運算

在objc_msgSend源碼中诵冒，查找緩存時凯肋，通過sel & mask來計算緩存的index，此時mask的取值范圍必須滿足2^n - 1的條件才能成立

所以有這么一個表達式：x % y = x % (y - 1)汽馋，其中y的取值為2^n侮东，一個數對2^n取模相當于一個數和(2^n - 1)做按位與運算

如果可以讓當前環(huán)形緩沖的大小是2^n，就可以直接通過與運算的方式來計算index

例如：2^n豹芯，此時n等于3

2^3 = 8悄雅，轉為二進制1000，(2^3 - 1)轉為二進制0111

x/8相當于x右移3位：x >> 3铁蹈，此時得到的是商宽闲。被移掉的3位即為余數

2^n轉為二進制，首位是1握牧，后面跟n個0容诬，即：1……n個0

2^n - 1轉為二進制，首位是0我碟，后面跟n個1放案，即：0……n個1

x/2^n 等同于x右移n位：x >> n

故此x & (2^n - 1)可以得到被移掉的n位姚建，即為余數

明白上述公式矫俺，假設_buffer的容量是2^n大小，即可使用位運算代替模運算掸冤。

在官方源碼中厘托，有這樣一段方法：

extension FixedWidthInteger {
    @inlinable
    func nextPowerOf2() -> Self {
        guard self != 0 else {
            return 1
        }
        return 1 << (Self.bitWidth - (self - 1).leadingZeroBitCount)
    }
}

定義FixedWidthInteger協議的擴展，實現nextPowerOf2方法稿湿，找到距一個值最近的2的n次方數

Self：代表當前類型铅匹，當前類型是Int，Self代表的就是Int饺藤。當前類型是Double包斑，Self代表的就是Double。一般用作返回值類型

bitWidth：代表當前類型有多少二進制位涕俗，例如Int類型有64個二進制位

leadingZeroBitCount：代表當前值轉為二進制罗丰，有多少前導零。例如Int類型的8再姑，二進制1000萌抵，Int為64位，所以它的前導零為60

測試nextPowerOf2方法的正確性

如果x為3，距離3最近的2的n次方數是多少绍填？

測試結果：距離3最近的2的n次方數是4

如果x為5

測試結果：距離5最近的2的n次方數是8

案例2

使用nextPowerOf2方法霎桅，讓位運算代替模運算

改造init方法，將傳入的count值讨永，找的距它最近的2的n次方數滔驶，將其設置為_buffer的容量大小

init(_ count: Int) {
    let tmp = count.nextPowerOf2()
    _buffer = ContiguousArray<Element?>(repeating: nil, count: tmp)
}

定義mask計算屬性，設置掩碼_buffer.count - 1

var mask: Int{
    return _buffer.count - 1
}

定義兩個方法卿闹，用于控制headIndex和tailIndex的指向

mutating func advanceTailIndex(by: Int){
    self.tailIndex = (self.tailIndex + by) & self.mask
}

mutating func advanceHeadIndex(by: Int){
    self.headIndex = (self.headIndex + by) & self.mask
}

改造存儲元素的append方法

mutating func append(_ value : Element){
    self._buffer[self.tailIndex] = value
    self.advanceTailIndex(by: 1)

    if self.headIndex == self.tailIndex {
        fatalError("out of bounds")
    }
}

改造讀取元素的pop方法

mutating func pop() -> Element?{
    let result = _buffer[self.headIndex]
    self.advanceHeadIndex(by: 1)
    return result
}

完整代碼如下：

struct RingBuffer<Element>{

    var _buffer: ContiguousArray<Element?>

    var headIndex: Int = 0
    var tailIndex: Int = 0

    var mask: Int{
        return _buffer.count - 1
    }

    init(_ count: Int) {
        let tmp = count.nextPowerOf2()
        _buffer = ContiguousArray<Element?>(repeating: nil, count: tmp)
    }

    mutating func advanceTailIndex(by: Int){
        self.tailIndex = (self.tailIndex + by) & self.mask
    }

    mutating func advanceHeadIndex(by: Int){
        self.headIndex = (self.headIndex + by) & self.mask
    }

    mutating func append(_ value : Element){
        self._buffer[self.tailIndex] = value
        self.advanceTailIndex(by: 1)

        if self.headIndex == self.tailIndex {
            fatalError("out of bounds")
        }
    }

    mutating func pop() -> Element?{
        let result = _buffer[self.headIndex]
        self.advanceHeadIndex(by: 1)
        return result
    }
}

一個具備初步基礎的環(huán)形緩沖區(qū)瓜浸，還有一些功能缺陷亟待解決：

無法通過下標訪問元素，只能從頭讀取

不具備遍歷特性

無法刪除元素

案例3

遵循Collection協議比原，讓環(huán)形緩沖區(qū)具備集合的特性

官方文檔插佛，提供了必要實現的屬性和方法：

定義startIndex和endIndex屬性，表示集合起始和結束位置

定義一個只讀的下標操作符

實現一個index(after:)方法量窘，用于在集合中移動索引位置

定義RingBuffer擴展雇寇，遵循Collection協議

extension RingBuffer: Collection{
    var startIndex: Int{
        return self.headIndex
    }

    var endIndex: Int{
        return self.tailIndex
    }

    subscript(position: Int) -> Element {
        get{
            return self._buffer[position]!
        }
        set{
            self._buffer[position] = newValue
        }
    }

    func index(after i: Int) -> Int {
        return (i + 1) & self.mask
    }
}

實現startIndex和endIndex屬性

實現subscript(position:)方法，通過下標讀寫指定位置的元素

實現index(after:)方法蚌铜，移動索引位置

對上述代碼進行測試：

var buf = RingBuffer<Int>.init(9)

for i in 1...10{
    buf.append(i)
}

for element in buf{
    print(element)
}

//輸出以下結果
//1
//2
//3
//4
//5
//6
//7
//8
//9
//10

初始化init方法傳入9锨侯，距離9最近的2的n次方數是16，實際上_buffer的容量大小是16冬殃，最大可存儲15個元素

循環(huán)append寫入1-10個元素

通過for...in讀取元素

當遵循Collection協議實現必要屬性和方法后囚痴，RingBuffer已經具備了集合特性，很多方法可以直接使用

print("集合是否為空：\(buf.isEmpty)")
print("獲取集合第一個元素：\(buf.first!)")
print("讀取指定下標元素：\(buf[3])")

//輸出以下結果
//集合是否為空：false
//獲取集合第一個元素：1
//讀取指定下標元素：4

案例4

遵循RangeReplaceableCollection協議审葬，讓環(huán)形緩沖區(qū)具備刪除元素的功能

首先對RingBuffer結構體深滚，添加indexAdvanced方法，返回指定位置移動后的index

func indexAdvanced(index: Int, by: Int) -> Int{
    return (index + by) & self.mask
}

定義RingBuffer擴展涣觉，遵循RangeReplaceableCollection協議

extension RingBuffer: RangeReplaceableCollection{

    init() {
        self.init(16)
    }

    mutating func remove(at position: Int) -> Element {
        var currentIndex = position

        guard let element = self._buffer[currentIndex] else {
            fatalError("not fount element")
        }

        switch currentIndex {
            case self.headIndex:
                self.advanceHeadIndex(by: 1)
                self._buffer[currentIndex] = nil
            default:
                self._buffer[currentIndex] = nil
                var nextIndex = self.indexAdvanced(index: currentIndex, by: 1)

                while nextIndex != self.tailIndex {
                    self._buffer.swapAt(currentIndex, nextIndex)
                    currentIndex = nextIndex
                    nextIndex = self.indexAdvanced(index: currentIndex, by: 1)
                }

                self.advanceTailIndex(by: -1)
        }

        return element
    }
}

實現remove方法

如果將要刪除的currentIndex位置不存在元素痴荐，輸出錯誤提示

如果currentIndex等于headIndex

將headIndex指向+1

將currentIndex的元素置為nil

如果currentIndex不等于headIndex

將currentIndex的元素置為nil

調用indexAdvanced方法獲取nextIndex（下一個位置）

通過while循環(huán)判斷nextIndex是否等于tailIndex

如果不等，使用集合的swapAt方法官册，將nextIndex的元素和currentIndex的nil進行交換

更新currentIndex為nextIndex

繼續(xù)通過indexAdvanced方法獲取nextIndex

循環(huán)往復直到nextIndex等于tailIndex為止

最后將tailIndex指向-1

案例5

RangeReplaceableCollection協議還提供很多方法

例如init<S>(_ elements:)方法生兆，有兩個限制條件：

S必須遵循Sequence協議

Self.Element必須和S.Element類型相等

當遵循RangeReplaceableCollection協議，并實現init<S>(_ elements:)方法膝宁，我們可以通過字面量方式創(chuàng)建RingBuffer

extension RingBuffer: ExpressibleByArrayLiteral{
    typealias ArrayLiteralElement = Element

    init(arrayLiteral elements: ArrayLiteralElement...) {
        self.init(elements)
    }
}

var buf = [1, 2, 3, 4, 5, 6]

for element in buf{
    print(element)
}

//輸出以下結果：
//1
//2
//3
//4
//5
//6

通過源碼可以看到init<S>(_ elements:)方法由系統自動實現了鸦难，打開RangeReplaceableCollection.swift文件

@inlinable
public init<S: Sequence>(_ elements: S) where S.Element == Element {
  self.init()
  append(contentsOf: elements)
}

先調用了self.init方法

然后將elements直接append到當前創(chuàng)建的集合中

完整代碼

extension FixedWidthInteger {
    @inlinable
    func nextPowerOf2() -> Self {
        guard self != 0 else {
            return 1
        }
        return 1 << (Self.bitWidth - (self - 1).leadingZeroBitCount)
    }
}

struct RingBuffer<Element>{

    var _buffer: ContiguousArray<Element?>

    var headIndex: Int = 0
    var tailIndex: Int = 0

    var mask: Int{
        return _buffer.count - 1
    }

    init(_ count: Int) {
        let tmp = count.nextPowerOf2()
        _buffer = ContiguousArray<Element?>(repeating: nil, count: tmp)
    }

    mutating func advanceTailIndex(by: Int){
        self.tailIndex = (self.tailIndex + by) & self.mask
    }

    mutating func advanceHeadIndex(by: Int){
        self.headIndex = (self.headIndex + by) & self.mask
    }

    func indexAdvanced(index: Int, by: Int) -> Int{
        return (index + by) & self.mask
    }

    mutating func append(_ value : Element){
        self._buffer[self.tailIndex] = value
        self.advanceTailIndex(by: 1)

        if self.headIndex == self.tailIndex {
            fatalError("out of bounds")
        }
    }

    mutating func pop() -> Element?{
        let result = _buffer[self.headIndex]
        self.advanceHeadIndex(by: 1)
        return result
    }
}

extension RingBuffer: Collection{
    var startIndex: Int{
        return self.headIndex
    }

    var endIndex: Int{
        return self.tailIndex
    }

    subscript(position: Int) -> Element {
        get{
            return self._buffer[position]!
        }
        set{
            self._buffer[position] = newValue
        }
    }

    func index(after i: Int) -> Int {
        return (i + 1) & self.mask
    }
}

extension RingBuffer: RangeReplaceableCollection{

    init() {
        self.init(16)
    }

    mutating func remove(at position: Int) -> Element {
        var currentIndex = position

        guard let element = self._buffer[currentIndex] else {
            fatalError("not fount element")
        }

        switch currentIndex {
            case self.headIndex:
                self.advanceHeadIndex(by: 1)
                self._buffer[currentIndex] = nil
            default:
                self._buffer[currentIndex] = nil
                var nextIndex = self.indexAdvanced(index: currentIndex, by: 1)

                while nextIndex != self.tailIndex {
                    self._buffer.swapAt(currentIndex, nextIndex)
                    currentIndex = nextIndex
                    nextIndex = self.indexAdvanced(index: currentIndex, by: 1)
                }

                self.advanceTailIndex(by: -1)
        }

        return element
    }
}

extension RingBuffer: ExpressibleByArrayLiteral{
    typealias ArrayLiteralElement = Element

    init(arrayLiteral elements: ArrayLiteralElement...) {
        self.init(elements)
    }
}