intersperse.swift

struct InterspersedSequence<S: Sequence>: Sequence, IteratorProtocol {
    var separator: S.Element
    var iterator: S.Iterator
    
    enum State {
        case separator
        case element(nextElement: S.Element?)
    }
    
    var state: State
    
    init(sequence: S, separator: S.Element) {
        self.iterator = sequence.makeIterator()
        self.separator = separator
        
        self.state = .element(nextElement: iterator.next())
    }
    
    mutating func next() -> S.Element? {
        switch state {
            case .separator:
                if let x = iterator.next() {
                    state = .element(nextElement: x)
                    return separator
                } else {
                    return nil
                }
            case .element(let nextElement):
                state = .separator
                return nextElement
        }
    }
}

extension Sequence {
    func interspersing(_ separator: Element) -> InterspersedSequence<Self> {
        return InterspersedSequence(sequence: self, separator: separator)
    }
}

extension Collection {
    func interspersed(_ separator: Element) -> [Element] {
        var newArray: [Element] = []
        guard !isEmpty else {
            return newArray
        }
        newArray.reserveCapacity(2 * count - 1)
        newArray.append(first!)
        
        var i = index(after: startIndex)
        while i != endIndex {
            newArray.append(separator)
            newArray.append(self[i])
            formIndex(after: &i)
        }
        return newArray
    }
}