MegaSequences.Swift

public protocol LazySequenceType      : SequenceType {}

extension LazySequence                : LazySequenceType {}
extension LazyForwardCollection       : LazySequenceType {}
extension LazyBidirectionalCollection : LazySequenceType {}
extension LazyRandomAccessCollection  : LazySequenceType {}
extension FilterSequenceView          : LazySequenceType {}
extension FilterCollectionView        : LazySequenceType {}
extension MapSequenceView             : LazySequenceType {}
extension MapCollectionView           : LazySequenceType {}
extension Zip2                        : LazySequenceType {}
extension EnumerateSequence           : LazySequenceType {}

public extension LazySequenceType {
  var array: [Generator.Element] {
    return Array(self)
  }
}

public struct LazyDropSeq<S : SequenceType> : LazySequenceType {
  
  typealias Generator = S.Generator
  
  private let seq: S
  private let n: Int
  
  public func generate() -> Generator {
    var g = seq.generate()
    for _ in 0..<n { g.next() }
    return g
  }
}

public extension LazySequenceType {
  func drop(n: Int) -> LazyDropSeq<Self> {
    return LazyDropSeq(seq: self, n: n)
  }
}

public struct LazyTakeSeq<S : SequenceType> : LazySequenceType {
  
  typealias Generator = TakeGen<S.Generator>
  
  private let seq: S
  private let n: Int
  
  public func generate() -> Generator {
    return TakeGen(g: seq.generate(), n: n)
  }
}

public struct TakeGen<G : GeneratorType> : GeneratorType {
  
  typealias Element = G.Element
  
  private var g: G
  private var n: Int
  
  mutating public func next() -> Element? {
    return --n < 0 ? nil : g.next()
  }
  
  private init(g: G, n: Int) {
    self.g = g
    self.n = n
  }
}

public extension LazySequenceType {
  func take(n: Int) -> LazyTakeSeq<Self> {
    return LazyTakeSeq(seq: self, n: n)
  }
}

public struct LazyWhileGen<G : GeneratorType> : GeneratorType {
  
  typealias Element = G.Element
  
  private var g: G
  private let condition : G.Element -> Bool
  
  mutating public func next() -> Element? {
    return g.next().flatMap {
      condition($0) ? $0 : nil
    }
  }
}

public struct LazyWhileSeq<S : SequenceType> : LazySequenceType {
  
  typealias Generator = LazyWhileGen<S.Generator>
  
  private let seq: S
  private let condition: S.Generator.Element -> Bool
  
  public func generate() -> Generator {
    return LazyWhileGen(g: seq.generate(), condition: condition)
  }
}

public extension LazySequenceType {
  func takeWhile(condition: Generator.Element -> Bool) -> LazyWhileSeq<Self> {
    return LazyWhileSeq(seq: self, condition: condition)
  }
  func takeUntil(condition: Generator.Element -> Bool) -> LazyWhileSeq<Self> {
    return LazyWhileSeq(seq: self) {!condition($0)}
  }
}

public struct JumpGen<G: GeneratorType> : GeneratorType {
  
  typealias Element = G.Element
  
  private let n: Int
  private var g: G
  
  mutating public func next() -> Element? {
    for _ in 0..<n { g.next() }
    return g.next()
  }
}

public struct HopGen<G: GeneratorType> : GeneratorType {
  
  typealias Element = G.Element
  
  private let n: Int
  private var g: G
  
  mutating public func next() -> Element? {
    defer { for _ in 0..<n { g.next() } }
    return g.next()
  }
}

public struct LazyHopSeq<S : SequenceType> : LazySequenceType {
  
  typealias Generator = HopGen<S.Generator>
  
  private let (seq, n): (S, Int)
  
  public func generate() -> Generator {
    return HopGen(n: n, g: seq.generate())
  }
}

public struct LazyJumpSeq<S : SequenceType> : LazySequenceType {
  
  typealias Generator = JumpGen<S.Generator>
  
  private let (seq, n): (S, Int)
  
  public func generate() -> Generator {
    return JumpGen(n: n, g: seq.generate())
  }
}

public extension LazySequenceType {
  func hop(n: Int) -> LazyHopSeq<Self> {
    return LazyHopSeq(seq: self, n: n)
  }
  func jump(n: Int) -> LazyJumpSeq<Self> {
    return LazyJumpSeq(seq: self, n: n)
  }
}

public struct FrameGen<G : GeneratorType> : GeneratorType {
  
  typealias Element = [G.Element]
  
  private var g: G
  private var frame: Element?
  private var n: Int
  
  mutating public func next() -> Element? {
    if frame != nil {
      return g.next().map {
        frame!.removeAtIndex(0)
        frame!.append($0)
        return frame!
      }
    } else {
      while --n >= 0, let next = g.next() {
        frame?.append(next) ?? {
          frame = [next]
          frame!.reserveCapacity(n)
          }()
      }
      return frame
    }
  }
  
  private init(g: G, n: Int) {
    self.g = g
    self.n = n
    self.frame = nil
  }
}

public struct FrameSeq<S : SequenceType> : LazySequenceType {
  
  typealias Generator = FrameGen<S.Generator>
  
  private let seq: S
  private let n: Int
  
  public func generate() -> Generator {
    return FrameGen(g: seq.generate(), n: n)
  }
}

public extension LazySequenceType {
  func frame(n: Int) -> FrameSeq<Self> {
    return FrameSeq(seq: self, n: n)
  }
}

public struct ChunkGen<G : GeneratorType> : GeneratorType {
  
  typealias Element = [G.Element]
  
  private var g: G
  private let n: Int
  
  public mutating func next() -> Element? {
    var ret: Element?
    var i = n
    while --i >= 0, let next = g.next() {
      ret?.append(next) ?? {
        ret = [next]
        ret!.reserveCapacity(n)
        }()
    }
    return ret
  }
}

public struct ChunkSeq<S : SequenceType> : LazySequenceType {
  
  typealias Generator = ChunkGen<S.Generator>
  
  private let seq: S
  private let n: Int
  
  public func generate() -> Generator {
    return ChunkGen(g: seq.generate(), n: n)
  }
}

public extension LazySequenceType {
  func chunk(n: Int) -> ChunkSeq<Self> {
    return ChunkSeq(seq: self, n: n)
  }
}

public extension SequenceType {
  func reduce(@noescape combine: (Generator.Element, Generator.Element) -> Generator.Element) -> Generator.Element? {
    var g = self.generate()
    return g.next().map {
      (var accu) in
      while let next = g.next() { accu = combine(accu, next) }
      return accu
    }
  }
}

public extension SequenceType {
  func scan<T>(var initial: T, @noescape combine: (T, Generator.Element) -> T) -> [T] {
    return self.map {
      initial = combine(initial, $0)
      return initial
    }
  }
  func scan(@noescape combine: (Generator.Element, Generator.Element) -> Generator.Element) -> [Generator.Element] {
    var accu: Generator.Element?
    return self.map {
      element in
      accu = accu.map{combine($0, element)} ?? element
      return accu!
    }
  }
}

public struct ScanGen<G : GeneratorType, T> : GeneratorType {
  
  typealias Element = T
  private let combine: (T, G.Element) -> T
  private var initial: T
  private var g: G
  
  public mutating func next() -> Element? {
    return g.next().map{
      initial = combine(initial, $0)
      return initial
    }
  }
}

public struct Scan1Gen<G : GeneratorType> : GeneratorType {
  
  typealias Element = G.Element
  private let combine: (G.Element, G.Element) -> G.Element
  private var accu: G.Element?
  private var g: G
  
  public mutating func next() -> Element? {
    return g.next().map{
      element in
      accu = accu.map{ combine($0, element) } ?? element
      return accu!
    }
  }
}

public struct LazyScanSeq<S : SequenceType, T> : LazySequenceType {
  
  typealias Generator = ScanGen<S.Generator, T>
  private let seq: S
  private let combine: (T, S.Generator.Element) -> T
  private let initial: T
  
  public func generate() -> Generator {
    return ScanGen(combine: combine, initial: initial, g: seq.generate())
  }
}

public struct LazyScan1Seq<S : SequenceType> : LazySequenceType {
  
  typealias Generator = Scan1Gen<S.Generator>
  private let seq: S
  private let combine: (S.Generator.Element, S.Generator.Element) -> S.Generator.Element
  
  public func generate() -> Generator {
    return Scan1Gen(combine: combine, accu: nil, g: seq.generate())
  }
}

public extension LazySequenceType {
  func scan<T>(initial: T, combine: (T, Generator.Element) -> T) -> LazyScanSeq<Self, T> {
    return LazyScanSeq(seq: self, combine: combine, initial: initial)
  }
  func scan(combine: (Generator.Element, Generator.Element) -> Generator.Element) -> LazyScan1Seq<Self> {
    return LazyScan1Seq(seq: self, combine: combine)
  }
}

public struct PaddedZipGenerator<G0: GeneratorType, G1: GeneratorType> : GeneratorType {
  
  typealias E0 = G0.Element
  typealias E1 = G1.Element
  
  typealias Element = (E0?, E1?)
  
  private var (g0, g1): (G0?, G1?)
  
  public mutating func next() -> PaddedZipGenerator.Element? {
    let e0: E0? = g0?.next() ?? {g0 = nil; return nil}()
    let e1: E1? = g1?.next() ?? {g1 = nil; return nil}()
    return (e0 != nil || e1 != nil) ? (e0, e1) : nil
  }
}

public struct PaddedZip<S0: SequenceType, S1: SequenceType> : LazySequenceType {
  
  typealias Generator = PaddedZipGenerator<S0.Generator, S1.Generator>
  
  private let (s0, s1): (S0, S1)
  
  public func generate() -> PaddedZip.Generator {
    return PaddedZipGenerator(g0: s0.generate(), g1: s1.generate())
  }
}

public func zipWithPadding<S0: SequenceType, S1: SequenceType>(s0: S0, _ s1: S1) -> PaddedZip<S0, S1> {
  return PaddedZip(s0: s0, s1: s1)
}

public extension SequenceType {
  func all(@noescape condition: Generator.Element -> Bool) -> Bool {
    for el in self {
      if !condition(el) { return false }
    }
    return true
  }
}

public struct SpecEnumerateGen<Base : CollectionType> : GeneratorType {
  
  typealias Element = (Base.Index, Base.Generator.Element)
  
  private var eG: Base.Generator
  private let sI: Base.Index
  private var i: Base.Index!
  
  public mutating func next() -> Element? {
    i = i?.successor() ?? sI
    return eG.next().map { (i, $0) }
  }
  
  private init(g: Base.Generator, i: Base.Index) {
    self.eG = g
    self.sI = i
    self.i = nil
  }
}

public struct SpecEnumerateSeq<Base : CollectionType> : LazySequenceType {
  
  typealias Generator = SpecEnumerateGen<Base>
  private let col: Base
  public func generate() -> Generator {
    return SpecEnumerateGen(g: col.generate(), i: col.startIndex)
  }
}

public extension CollectionType {
  func specEnumerate() -> SpecEnumerateSeq<Self> {
    return SpecEnumerateSeq(col: self)
  }
}

public extension CollectionType {
  func indicesOf(@noescape predicate: Generator.Element -> Bool) -> [Index] {
    var ret: [Index] = []
    for (index, value) in self.specEnumerate() {
      if predicate(value) { ret.append(index) }
    }
    return ret
  }
}

public extension CollectionType where Generator.Element : Equatable {
  func indicesOf(match: Generator.Element) -> [Index] {
    var ret: [Index] = []
    for (index, value) in self.specEnumerate() {
      if value == match { ret.append(index) }
    }
    return ret
  }
}

public struct LazyIndGen<Base : CollectionType> : GeneratorType {
  
  typealias Element = Base.Index
  
  private var eG: Base.Generator
  private let sI: Base.Index
  private var i: Base.Index!
  private let pred: Base.Generator.Element -> Bool
  
  public mutating func next() -> Element? {
    while let next = eG.next() {
      i = i?.successor() ?? sI
      if pred(next) {return i}
    }
    return nil
  }
  
  init(g: Base.Generator, i: Base.Index, predicate: Base.Generator.Element -> Bool) {
    self.eG = g
    self.sI = i
    self.i = nil
    self.pred = predicate
  }
}

public struct LazyIndsOfSeq<Base : CollectionType> : LazySequenceType {
  
  typealias Generator = LazyIndGen<Base>
  private let col: Base
  private let pred: Base.Generator.Element -> Bool
  public func generate() -> Generator {
    return LazyIndGen(g: col.generate(), i: col.startIndex, predicate: pred)
  }
}

public extension CollectionType where Self : LazySequenceType {
  func indicesOf(predicate: Generator.Element -> Bool) -> LazyIndsOfSeq<Self> {
    return LazyIndsOfSeq(col: self, pred: predicate)
  }
}

public struct LazyIndEqGen<Base : CollectionType where Base.Generator.Element : Equatable> : GeneratorType {
  
  typealias Element = Base.Index
  
  private var eG: Base.Generator
  private let sI: Base.Index
  private var i: Base.Index!
  private let el: Base.Generator.Element
  
  public mutating func next() -> Element? {
    while let next = eG.next() {
      i = i?.successor() ?? sI
      if next == el {return i}
    }
    return nil
  }
  
  init(g: Base.Generator, i: Base.Index, element: Base.Generator.Element) {
    self.eG = g
    self.sI = i
    self.i = nil
    self.el = element
  }
}

public struct LazyIndsOfEqSeq<Base : CollectionType where Base.Generator.Element : Equatable> : LazySequenceType {
  
  typealias Generator = LazyIndEqGen<Base>
  private let col: Base
  private let el: Base.Generator.Element
  public func generate() -> Generator {
    return LazyIndEqGen(g: col.generate(), i: col.startIndex, element: el)
  }
}

public extension CollectionType where Self : LazySequenceType, Generator.Element : Equatable {
  func indicesOf(element: Generator.Element) -> LazyIndsOfEqSeq<Self> {
    return LazyIndsOfEqSeq(col: self, el: element)
  }
}

public extension SequenceType where Generator.Element : Hashable {
  func uniques() -> [Generator.Element] {
    var prevs: Set<Generator.Element> = []
    return self.filter {
      el in
      defer { prevs.insert(el) }
      return !prevs.contains(el)
    }
  }
  func freqs() -> [Generator.Element:Int] {
    var ret: [Generator.Element:Int] = [:]
    for el in self { ret[el] = ret[el]?.successor() ?? 1 }
    return ret
  }
}

public struct UniquesGen<G : GeneratorType where G.Element : Hashable> : GeneratorType {
  
  typealias Element = G.Element
  
  private var prevs: Set<Element>
  private var g: G
  
  public mutating func next() -> Element? {
    while let next = g.next() {
      if !prevs.contains(next) {
        prevs.insert(next)
        return next
      }
    }
    return nil
  }
}

public struct UniquesSeq<S : SequenceType where S.Generator.Element : Hashable> : LazySequenceType {
  typealias Generator = UniquesGen<S.Generator>
  private let seq: S
  public func generate() -> Generator {
    return UniquesGen(prevs: [], g: seq.generate())
  }
}

public extension LazySequenceType where Generator.Element : Hashable {
  func uniques() -> UniquesSeq<Self> {
    return UniquesSeq(seq: self)
  }
}

public struct DropWhileGen<G : GeneratorType> : GeneratorType {
  
  typealias Element = G.Element
  private let predicate: Element -> Bool
  private var nG: G!
  private var oG: G
  
  init(g: G, predicate: Element -> Bool) {
    self.nG = nil
    self.oG = g
    self.predicate = predicate
  }
  
  public mutating func next() -> Element? {
    guard nG == nil else { return nG.next() }
    while let next = oG.next() {
      if !predicate(next) {
        nG = oG
        return next
      }
    }
    return nil
  }
}

public struct DropWhileSeq<S : SequenceType> : LazySequenceType {
  
  typealias Generator = DropWhileGen<S.Generator>
  
  private let predicate: Generator.Element -> Bool
  private let seq: S
  
  public func generate() -> Generator {
    return DropWhileGen(g: seq.generate(), predicate: predicate)
  }
}

public extension LazySequenceType {
  func dropWhile(predicate: Generator.Element -> Bool) -> DropWhileSeq<Self> {
    return DropWhileSeq(predicate: predicate, seq: self)
  }
}

public struct ZipWithGen<G0: GeneratorType, G1: GeneratorType, T> : GeneratorType {
  
  typealias Element = T
  private let combine: (G0.Element, G1.Element) -> T
  
  private var g0: G0
  private var g1: G1
  
  public mutating func next() -> Element? {
    if let e0 = g0.next(), e1 = g1.next() {
      return combine(e0, e1)
    } else {
      return nil
    }
  }
}

public struct ZipWithSeq<S0: SequenceType, S1: SequenceType, T> : LazySequenceType {
  
  typealias Generator = ZipWithGen<S0.Generator, S1.Generator, T>
  private let combine: (S0.Generator.Element, S1.Generator.Element) -> T
  
  private let s0: S0
  private let s1: S1
  
  public func generate() -> Generator {
    return ZipWithGen(combine: combine, g0: s0.generate(), g1: s1.generate())
  }
}

public func zipWith<
  S0: SequenceType, S1: SequenceType, T
  >(s0: S0, _ s1: S1, combine: (S0.Generator.Element, S1.Generator.Element) -> T)
  -> ZipWithSeq<S0, S1, T> {
    return ZipWithSeq(combine: combine, s0: s0, s1: s1)
}

public struct InterposeElGen<G : GeneratorType> : GeneratorType {
  
  typealias Element = G.Element
  
  private let element: Element
  private var g: G
  private let n: Int
  private var count: Int
  
  init(n: Int, g: G, element: Element) {
    self.n = n
    self.count = n
    self.element = element
    self.g = g
  }
  
  public mutating func next() -> Element? {
    return --count < 0 ? {count = n; return element}() : g.next()
  }
}

public struct InterposeElSeq<S : SequenceType> : LazySequenceType {
  
  typealias Generator = InterposeElGen<S.Generator>
  
  private let element: Generator.Element
  private let n: Int
  private let seq: S
  
  public func generate() -> Generator {
    return InterposeElGen(n: n, g: seq.generate(), element: element)
  }
}

public extension LazySequenceType {
  func interpose(element: Generator.Element) -> InterposeElSeq<Self> {
    return InterposeElSeq(element: element, n: 1, seq: self)
  }
  func interpose(element: Generator.Element, n: Int) -> InterposeElSeq<Self> {
    return InterposeElSeq(element: element, n: n, seq: self)
  }
}

public struct InterposeColGen<G : GeneratorType, C: CollectionType where G.Element == C.Generator.Element> : GeneratorType {
  
  typealias Element = G.Element
  
  private let col: C
  private var g: G
  private let n: Int
  private var count: Int
  private var colG: C.Generator
  
  private init(col: C, g: G, n: Int) {
    self.n = n
    self.count = n + 1
    self.col = col
    self.g = g
    self.colG = self.col.generate()
  }
  
  public mutating func next() -> Element? {
    return --count <= 0 ? {
      colG.next() ?? {
        count = n
        colG = col.generate()
        return g.next()
        }()}() : g.next()
  }
}

public struct InterposeColSeq<S : SequenceType, C: CollectionType where S.Generator.Element == C.Generator.Element> : LazySequenceType {
  
  typealias Generator = InterposeColGen<S.Generator, C>
  
  private let col: C
  private let n: Int
  private let seq: S
  
  public func generate() -> Generator {
    return InterposeColGen(col: col, g: seq.generate(), n: n)
  }
}

public extension LazySequenceType {
  func interpose<C: CollectionType where C.Generator.Element == Generator.Element>(elements: C) -> InterposeColSeq<Self, C> {
    return InterposeColSeq(col: elements, n: 1, seq: self)
  }
  func interpose<C: CollectionType where C.Generator.Element == Generator.Element>(elements: C, n: Int) -> InterposeColSeq<Self, C> {
    return InterposeColSeq(col: elements, n: n, seq: self)
  }
}

public extension SequenceType where Generator.Element: SequenceType {
  func transposeAndPad() -> [[Generator.Element.Generator.Element]] {
    var g = self.generate()
    return g.next().map {
      var gens = GeneratorSequence(g).map{$0.generate()}
      return $0.map { fEl in [fEl] + gens.indices.map{gens[$0].next() ?? fEl}}
      } ?? [[]]
  }
}

public struct InterDigGen<G0 : GeneratorType, G1 : GeneratorType where G0.Element == G1.Element> : GeneratorType {
  
  typealias Element = G0.Element
  
  private var g0: G0
  private var g1: G1
  
  private let aN: Int
  private let bN: Int
  
  private var count: Int
  
  public mutating func next() -> Element? {
    for (--count;;count = aN) {
      if count >= bN {return count < 0 ? g1.next() : g0.next()}
    }
  }
}

public struct InterDigSeq<S0 : SequenceType, S1 : SequenceType where S0.Generator.Element == S1.Generator.Element> : LazySequenceType {
  
  typealias Generator = InterDigGen<S0.Generator, S1.Generator>
  
  private let s0: S0
  private let s1: S1
  
  private let aN: Int
  private let bN: Int
  
  public func generate() -> Generator {
    return InterDigGen(g0: s0.generate(), g1: s1.generate(), aN: aN - 1, bN: -bN, count: aN)
  }
}

public func interdig<
  S0 : SequenceType, S1 : SequenceType where
  S0.Generator.Element == S1.Generator.Element
  >(s0: S0, _ s1: S1) -> InterDigSeq<S0, S1> {
    return InterDigSeq(s0: s0, s1: s1, aN: 1, bN: 1)
}

public func interdig<
  S0 : SequenceType, S1 : SequenceType where
  S0.Generator.Element == S1.Generator.Element
  >(s0: S0, _ s1: S1, s0Len: Int, s1Len: Int) -> InterDigSeq<S0, S1> {
    return InterDigSeq(s0: s0, s1: s1, aN: s0Len, bN: s1Len)
}

public extension SequenceType where Generator.Element: SequenceType {
  func everyOf() -> [[Generator.Element.Generator.Element]] {
    var seqGen = self.generate()
    return seqGen.next().map {
      let fSeq = Array($0)
      return GeneratorSequence(seqGen).everyOf().flatMap {
        lSeq in fSeq.map{ [$0] + lSeq }
      }
    } ?? [[]]
  }
}

public extension SequenceType where Generator.Element: CollectionType {
  func everyOf() -> [[Generator.Element.Generator.Element]] {
    var seqGen = self.generate()
    return seqGen.next().map {
      fSeq in AnySequence{seqGen}.everyOf().flatMap {
        lSeq in fSeq.map{ [$0] + lSeq }
      }
    } ?? [[]]
  }
}

public struct SplitAtGen<G : GeneratorType> : GeneratorType {
  
  typealias Element = [G.Element]
  private let isSplit: G.Element -> Bool
  private var g: G
  
  mutating public func next() -> Element? {
    var ret: Element?
    while let next = g.next() {
      ret?.append(next) ?? {ret = [next]}()
      if isSplit(next) { return ret }
    }
    return ret
  }
}

public struct SplitSeq<S : SequenceType> : LazySequenceType {
  
  typealias Generator = SplitAtGen<S.Generator>
  private let seq: S
  private let isSplit: S.Generator.Element -> Bool
  
  public func generate() -> Generator {
    return SplitAtGen(isSplit: isSplit, g: seq.generate())
  }
}

public extension LazySequenceType {
  func splitAt(isSplit: Generator.Element -> Bool) -> SplitSeq<Self> {
    return SplitSeq(seq: self, isSplit: isSplit)
  }
}