import UIKit

///集合类型 Collection : Sequence
///集合类型值的是那些稳定的序列，既：多次遍历能结果一致的序列
///集合中的元素可以通过索引获取到，通常是整数，不过也存在一些不透明的索引，比如字符串或者字典中
///集合中的索引值可以构成一个有限的范围，定义了集合的开始和结束
///和序列不同，集合是有限的
//Array, Dictionary, Set, String, CountableRange, UnsafeBufferPointer 都遵循Collection协议

//Mark: 自定义集合类型
//Swift中，数组可以用作栈： append, popLast
//数组用作队列： push，remove(at:0)实现，但是因为数组是连续的内存空间,所以移除非尾部元素，其他元素都要移动去填补空白，时间复杂度O(n)

//Mark:定义队列协议
//一个能够将元素出队，入队的类型
protocol Queue {
  // 在`self`中所持有的类型
  associatedtype Element
   // 将newElement入队到`self`中
  mutating func enqueue(_ newElement: Element)
  // 从`self`中出队一个元素
  mutating func dequeue() -> Element?
}

// Mark: 上述定义中，注释不能省略，它和方法名及类型一样，也是协议的一部分。这些注释用来保证协议应该有的功能。定义还省略了：时间复杂度的要求，peek操作，是否遵循Collection协议，FIFO/FOLO,

// Mark: 队列实现
//因为我们把队列的泛型占位符命名为了与协议中所要求的关联值一样的 Element，所以我们就不需要再次对它进行定义了。这个占位类型并不是一定需要被叫做 Element，我们只是随意选择的。我们也可以把它叫做 Foo，不过这样的话，我们就还需要定义 typealias Element = Foo，或者让 Swift 通过 enqueue 和 dequeue 的实现所返回的类型来进行隐式的类型推断：

///一个高效的FIFO队列，元素类型为Element
struct FIFOQueue<Element>: Queue {
  private var left: [Element] = []
  private var right: [Element] = []
  //时间复杂度:O(1)
  mutating func enqueue(_ newElement: Element) {
    right.append(newElement)
  }
  //时间复杂度: 平摊O(1) （对于数据量比较大的队列，复杂度低）
  mutating func dequeue() -> Element? {
    if left.isEmpty {
      left = right.reversed()
      right.removeAll()
    }
    return left.popLast()
  }
}

// Mark: 遵守Collection协议
//必须实现的方法
//protocol Collection: Sequence {
//  //一个表示集合中位置的类型
//  associatedtype Index: Comparable
//  //一个非空集合中首个元素的位置
//  var startIndex: Index { get }
//  // 集合中末位位置 --- 也就是最后一个有效下标值大1的位置
//  var endIndex: Index { get }
//  //给定索引之后的那个索引
//  func index(after: Index) -> Index
//  //访问特定位置的元素
//  subscript(position: Index) -> Element { get }
//}


extension FIFOQueue: Collection {
  public var startIndex: Int { return 0 }
  public var endIndex: Int { return left.count + right.count}

  public func index(after i: Int) -> Int {
    precondition(i < endIndex)
    return i + 1
  }

  subscript(position: Int) -> Element {
    precondition((0..<endIndex).contains(position))
    if position < left.endIndex {
      return left[left.count - position - 1]
    } else {
      return right[position - left.count]
    }
  }
}


var q = FIFOQueue<String>()
for x in ["1", "2", "foo", "3"] {
  q.enqueue(x)
}

for s in q {
  print(s, terminator: " ")
}

let x = q.map{ $0.uppercased()}
print(x)
let y = q.flatMap{ Int($0)}
print(y)
let z = q.filter{ $0.count > 1 }
print(z)
q.sorted()
q.joined(separator: "1")

// Mark: 遵守ExpressibleByArrayLiteral
//注意： [x,x,x,x,x] 并不一定是一个数组，它只是一个"数组字面量"，是一种写法。
extension FIFOQueue: ExpressibleByArrayLiteral {
  public init(arrayLiteral elements: Element...) {
    left = elements.reversed()
    right = []
  }
}

let queue: FIFOQueue = [1, 2, 3]

//Mark: 关联类型
//Iterator: 从Sequence集成的管理按类型。集合中的默认迭代器类型是IndexingIterator<Self>
public struct IndexingIterator<Elements: Collection>: IteratorProtocol, Sequence {
  internal let _elements: Elements
  internal var _position: Elements.Index

  init(_ elements: Elements) {
    self._elements = elements
    self._position = elements.startIndex
  }

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

//IndexDistance: 一个无符号整数类型，几乎都是Int类型，少数是Int64.代表两个索引之间的步长

//Indices: 集合的indices属性的返回值类型。它代表集合的所有有效下标的索引所组成的集合，并以升序排列。 注意： 不包含endIndex,因为endIndex代表最后一个有效索引之后的那个索引，它不是有效的下表参数
//Indices的默认类型是DefaultIndices<Self>,和slice一样，它是对原来集合类型的简单封装，并包含起始和结束索引。它需要保持对原来集合的引用，这样才能步进。 当用户在迭代索引的同事改变集合的内容的时候，可能会造成意想不到的性能问题：如果集合是写时复制，这个对于集合的额外引用将出发不必要的复制

// Mark: 索引标识集合中的一个位置，每个集合都有两个特殊的索引值，startIndex和endIndex，其中endIndex是最后一个元素之后的位置，它并不是一个有效的索引
//集合类型的Index的唯一要求： 必须实现comparable，换句话说，索引必须是有确定顺序的
//字典中键不能作为索引，因为你无法知道一个键之后的一个键是什么
//字典的索引： DictionaryIndex 类型，它是一个指向字典内部存储缓冲区的不透明值。事实上是一个Intb偏移值的封装，包含了集合类型使用者不关心的细节

// Mark: 字典中下标实现，由Dictionary定义
//struct Dictionary {
//  //...
//  subscript(key: Key) -> Value?   //返回值是可选值
//}

// Mark: 集合中索引访问的方法又Collection定义
// 返回的类型Element是一个多元组：（key:Key, value: Value）,因此对Dictionary下标访问返回的是一个键值对，而非单个Value。这也是对字典进行for循环将键值对迭代的原因
//protocol Collection {
//  //...
//  subscript(position: Index) -> Element { get } //返回值是确定值
//}


// Mark: 索引失效
//两个含义：1、 索引本身有效，但指向了另外一个元素； 2、索引本身无效
//字典中添加元素可能会导致索引失效（当字典尺寸增大到触发重新分配内存时，重新计算hash值，会触发索引失效）
//字典中移除元素必定导致索引失效

// Mark: 索引共享，集合不能区分自己的索引和一个同类型的其他索引
//索引应该是一个只存储包含位置信息的最小元素
let numbers = [1, 2, 3, 4]
let square = numbers.map {$0 * $0}
let numbersIndex = numbers.index(after: 0)  //numbers的索引
square[numbersIndex]    //共享了numbers的索引

// 索引共享是合理的，尤其是在切片上。Collection协议要求元集合的索引必须在切片上也命中同样的元素，这样一来，在切片间共享索引将会是安全的


// Mark: 索引步进
//swift3之后，向前向后移动索引的任务由集合来负责。swift2时代，用someIndex.successor()获取下一个索引，swift3之后用collection.index(after: someIndex)获取
//在原来自己管理的索引模型中，y索引必须保存对集合存储的引用，会导致集合被迭代修改时造成不必要的复制，，它带来的开销足以抵消标准库中集合的写实复制特性带来的性能改善

// Mark 自定义集合索引
//为什么不用整数作为索引，比如第N个单词？ 因为为了找到第n个单词，我们要对整个字符串进行处理（O(n)）
extension Substring {
  var nextWordRange: Range<Index> {
    let start = drop(while:{ $0 == " "})
    let end = start.index(where: {$0 == " "});
    return start.startIndex..<endIndex
  }
}

//索引要满足Comparable
struct WordsIndex: Comparable {
  fileprivate let range: Range<Substring.Index>
  fileprivate init(_ value: Range<Substring.Index>) {
    self.range = value
  }

  static func < (lhs: WordsIndex, rhs: WordsIndex) -> Bool {
    return lhs.range.lowerBound < rhs.range.lowerBound
  }

  static func == (lhs: WordsIndex, rhs: WordsIndex) -> Bool {
    return lhs.range == rhs.range
  }
}

struct Words: Collection {
  let string: Substring
  let startIndex: WordsIndex
  init(_ s: String) {
    self.init(s[...])
  }

  private init(_ s: Substring) {
    self.string = s
    self.startIndex = WordsIndex(string.nextWordRange)
  }

  var endIndex: WordsIndex {
    let e = string.endIndex
    return WordsIndex(e..<e)
  }

  subscript(index: WordsIndex) -> Substring {
    return string[index.range]
  }

  func index(after i: WordsIndex) -> WordsIndex {
    guard i.range.upperBound < string.endIndex else { return endIndex}
    let remainder = string[i.range.upperBound...]
    return WordsIndex(remainder.nextWordRange)
  }
}

// Mark: 切片
// 实现原理
struct Slice<Base: Collection>: Collection {
  typealias Index = Base.Index
  typealias SubSequence = Slice<Base>

  let collection: Base
  var startIndex: Index
  var endIndex: Index

  init(base: Base, bounds: Range<Index>) {
    collection = base
    startIndex = bounds.lowerBound
    endIndex = bounds.upperBound
  }

  func index(after i: Base.Index) -> Base.Index {
    return collection.index(after: i)
  }

  subscript(position: Index) -> Base.Element {
    return collection[position]
  }

  subscript(bounds: Range<Base.Index>) -> Slice<Base> {
    return Slice(base: collection, bounds: bounds)
  }
}

// Slice是默认的子序列类型，最好考虑用集合本身作为SubSequence来使用：这样可以减轻学习者的负担，只需要理解单个类型就可以了，不过让集合和切片使用不同的类型，可以有效p避免内存管理
//编译器将会通过基于范围的下标访问返回的类型，来推断SubSequence的类型
extension Words {
  subscript(range: Range<WordsIndex>) -> Words {
    let start = range.lowerBound.range.lowerBound
    let end = range.upperBound.range.upperBound
    return Words(string[start..<end])
  }
}


// Mark: 切片与原集合共享索引： Collection协议还有一个正式的要求： 切片的索引可以和元集合的索引互换使用
//集合类型和它的切片有用相同的索引。只要集合和它的切片在切片被创建后没有改变，切面中某个索引位置上的元素，应当也存在于原集合中同样的索引位置上



// 泛型PrefixIterator
struct PrefixIterator<Base: Collection>: IteratorProtocol, Sequence {
  let base: Base
  var offset: Base.Index
  init(_ base: Base) {
    self.base = base
    self.offset = base.startIndex
  }

  mutating func next() -> Base.SubSequence? {
    guard offset != base.endIndex else { return nil }
    base.formIndex(after: &offset)
    return base.prefix(upTo: offset)
  }
}

// Mark: 双向索引集合： BidirectionCollection 协议，只增加了一个方法：index(before:)
extension BidirectionalCollection {
  public var last: Element? { //Collection也提供了last属性，这种方式是从前面一个一个往后找，时间复杂度为O(n)
    return isEmpty ? nil : self[index(before: endIndex)]
  }
}

// Bidirection 还提供suffix，removeLast和reversed功能
//reversed并不是直接反转集合，而是返回一个延时加载的表达式：
extension BidirectionalCollection {
  //返回集合中元素的逆序表示方式似乎数组
  //-复杂度O(1)
  public func reversed() -> ReversedCollection<Self> {
    return ReversedCollection<Self>(self)O(1) //逆序集合会持有原来的集合，并且使用逆向索引。集合将所有遍历方法逆序，既：向前变为向后，向后变为向前
  }
  //虽然持有原来集合，但是会触发写时复制，对原集合的修改不会影响逆序集合
}

// Mark: 随机存取集合， RandomAccessCollection协议，提供了高效的元素存取方式，可以在常数时间内跳转至任意位置。要做到这一点，必须满足两点：
//1、可以以任意距离移动索引，2、测量任意两个索引之间的距离，两者都需要O(1)的复杂度
//RandomAccessCollection以更严格的方式重新声明了关联的indices和SubSequence类型，这两个类型自身必须可以随机存取，其他并没有更多的要求

// 和BidirectionCollection的区别： BidirectionCollection 使用index(_:offsetBy:)操作以渐进式访问下一个索引，直到找到目标索引为止。时间复杂度会随着距离增加而增加，而在RandomAccessCollection中可以在两个索引之间进行移动


// Mark: 可变集合： MutableCollection，相对于Collection，只增加了一个要求： 下标访问方法subscript必须提供setter方法

//extension FIFOQueue: MutableCollection {
//  public var startIndex: Int { return 0}
//  public var endIndex: Int { return left.count + right.count}
//  func formIndex(after i: inout Int) {
//    return i + 1
//  }
//
//  subscript(position: Int) -> Element {
//    get {
//      precondition((0..<endIndex).contains(position), "out of bouds")
//      if position < left.endIndex {
//        return left[left.count - position - 1]
//      } else {
//        return right[position - left.count]
//      }
//    }
//    set {
//      precondition((0..<endIndex).contains(position), "out of bounds")
//      if position < left.endIndex {
//        left[left.count - position - 1] = newValue
//      } else {
//        return right[position - left.count] = newValue
//      }
//    }
//  }
//}

// //在标准库中只有Array满足MutableCollection协议，允许修改元素值，但是不允许修改元素的长度或者元素的顺序

// Mark: 添加，移除元素：RangeReplaceableCollection协议
//该协议有两个要求： 1、一个空的s初始化方法 --- 在反省函数中很有用，因为它允许一个函数创建相同类型的空集合。 2、replaceSubrange(_:with:)方法 --- 接受一个范围和用来替换的集合
//RangeReplaceableCollection协议展示了协议扩展的强大能力，只需要实现一个超级灵活的replaceSubrange方法，即可引申出以下方法：
// (1)append(_:)和append（conentOf:）--- 将endIndex..<endIndex(空范围)替换为一个或多个元素
// (2)remove(at:)和removeSubrange(_:) --- 将i..<i或者subRange替换为空集合
// (3)insert(at:) 和insert(contentOf:at:) --- 将i..<或者某个位置的空范围替换单个或多个元素
// (4)removeAll 将startIndex..<endIndex替换为空集合

//extension FIFOQueue: RangeReplaceableCollection {
//  mutating func replaceSubrange<C, R>(_ subrange: R, with newElements: __owned C) where C : Collection, R : RangeExpression, Element == C.Element, Self.Index == R.Bound {
//    right = left.reversed() + right
//    left.removeAll()
//    right.replaceSubrange(subrange, with: newElements)
//  }
//}



// Mark: 组合能力：以上四种集合：双向索引集合，随机存取集合，可变集合，范围替换集合可以随意组合：例如MutableRangeReplaceableBidirectionalSlice。标准库中有十二种不同类型的集合，它们是三种遍历方式（向前，向后和随机存取）以及四种变更方式（不变，可变，范围可替换，可变且范围可替换）的组合