Swift底层进阶--017：Sequence & Collection

Sequence协议

Sequence协议是集合类型结构中的基础，是一系列相同类型的值的集合，并且提供对这些值的迭代能力。Sequence协议提供了许多强大的功能，遵循该协议的类型都可以直接使用这些功能。

迭代一个Sequence最常见的方式就是for...in循环

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：创建IndexingIterator<Array<Int>>迭代器
  • %34：当遍历元素时，调用Collection协议中的makeIterator()方法，创建了一个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：每次通过创建迭代器来访问序列中的元素

所以每次使用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：用来创建迭代器，返回一个Iterator
  • Sequence类似一个车间，而Iterator类似一条条流水线

对于Sequence协议来说，表达的既可以是一个有限的集合，也可以是一个无限的集合，它只需要提供集合中的元素，和如何访问这些元素的接口即可

案例

遵循Sequence和IteratorProtocol协议，创建一个可遍历的结构体

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需要创建一个迭代器，用来遍历当前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中继承了全部方法以外，还默认实现了很多不同的方法和协议

通过环形缓冲区的结构，来了解一下Collection协议的实现

案例1

为什么要有环形缓冲区？

例如数组，它是一个连续的线性存储空间。

假设数组内存放了B、C、D、E、F等元素，此时要将元素A插入到数组Index为0的位置，这时需要将数组内已有元素全部向后移动一个位置，再将元素A插入。

如果删除Index为0的元素，数组内的其他元素都要向前移动一个位置，以此来保证后续通过下标访问元素的正确性。

所以数组存储的元素越多，它的运行效率就越低下。这时可以设计一个环形缓冲区结构来改善效率问题。

环形缓冲区的结构，应该具有首位相连的特性。

首先定义一个head指针表示头结点，再定义一个tail指针表示尾结点。

head指向当前读取元素的索引位置，而tail指向下一个将要插入元素的空位置。

假设数组内存放了一个元素A，此时head指向Index为0的位置，tail指向Index为1的位置。

当读取元素时，将head移动到指定索引位置。

当环形缓冲区所存储的元素满了，这时tail应该指向头部，也就是Index为0的位置。

此时再插入元素X，应该插入到Index为0的位置，覆盖之前的元素A。而tail应该指向下一个Index为1的位置。

对于head的指向也是同理，读取到结尾处，自动指向头部，读取Index为0的位置，如此循环往复。

通过代码设计一个环形缓冲区结构

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：读取元素的方法

上述代码，其实就是一个简单的环形缓冲区，具备了初步的功能，但存在以下几个问题：

  • 模运算的开销是非常大的？能否替换掉
  • 当前需要频繁移动tailIndex
  • 如何判断环形缓冲区已满？使用headIndex==tailIndex可以吗？
  • 删除一个元素的逻辑是什么

如图所示，tail指针其实指向的永远都是当前空闲的节点，如果此时删除index==4的元素，逻辑是什么？

  • 定位到index==4的位置，将value设置为nil
  • 如果仅这样处理，后续再插入元素，会被插入到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)做按位与运算
  • 如果可以让当前环形缓冲的大小是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
    }
}

一个具备初步基础的环形缓冲区，还有一些功能缺陷亟待解决：

  • 无法通过下标访问元素，只能从头读取
  • 不具备遍历特性
  • 无法删除元素
案例3

遵循Collection协议，让环形缓冲区具备集合的特性

官方文档，提供了必要实现的属性和方法：

  • 定义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个元素
  • 循环append写入1-10个元素
  • 通过for...in读取元素

当遵循Collection协议实现必要属性和方法后，RingBuffer已经具备了集合特性，很多方法可以直接使用

print("集合是否为空：\(buf.isEmpty)")
print("获取集合第一个元素：\(buf.first!)")
print("读取指定下标元素：\(buf[3])")

//输出以下结果
//集合是否为空：false
//获取集合第一个元素：1
//读取指定下标元素：4
案例4

遵循RangeReplaceableCollection协议，让环形缓冲区具备删除元素的功能

首先对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循环判断nextIndex是否等于tailIndex
  • 如果不等，使用集合的swapAt方法，将nextIndex的元素和currentIndex的nil进行交换
  • 更新currentIndex为nextIndex
  • 继续通过indexAdvanced方法获取nextIndex
  • 循环往复直到nextIndex等于tailIndex为止
  • 最后将tailIndex指向-1
案例5

RangeReplaceableCollection协议还提供很多方法

例如init<S>(_ elements:)方法，有两个限制条件：

  • S必须遵循Sequence协议
  • Self.Element必须和S.Element类型相等

当遵循RangeReplaceableCollection协议，并实现init<S>(_ elements:)方法，我们可以通过字面量方式创建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到当前创建的集合中
完整代码
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)
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,088评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,715评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,361评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,099评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 60,987评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,063评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,486评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,175评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,440评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,518评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,305评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,190评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,550评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,880评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,152评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,451评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,637评论 2赞 335