airspeedswift

/// Brian Kernighan's article in Beautiful Code talks about the minimalist regex matcher written by 
/// Rob Pike for their Practice of Programming book as "one of the best examples of recursion that I 
/// have ever seen, and it shows the power of C pointers".
///
/// Swift strings don't use pointers, and the original code relied heavily on the last character of a 
/// C string being `\0`, but you can reproduce many of the nice aspects of the original C code using a 
/// combination of slicing and `dropFirst`, the `first` function that returns an optional you can then  
/// compare to a non-optional character, and the Swift 1.2 `if...let...where`
///
/// In theory no string copying should be happening since the slices are just a subrange view on the

airspeedswift

// adapted from original, which was (c) 2015 Nate Cook, licensed under the MIT license
//
// Fisher-Yates shuffle as protocol extensions

import Darwin

extension CollectionType where Index: RandomAccessIndexType {
    /// Return a copy of `self` with its elements shuffled
    func shuffle() -> [Generator.Element] {
        var list = Array(self)

airspeedswift

func tellJoke(name: String, character: Character) {
    let punchline = name.filter { $0 != character }
    let n = name.count - punchline.count
    
    let joke = """
        Q: Why does \(name) have \(n) \(character)'s in their name?
        A: I don't know, why does \(name) have \(n) \(character)'s in their name?
        Q: Because otherwise they'd be called \(punchline).
        """
    print(joke)

airspeedswift

struct MyReversed<Base: BidirectionalCollection> {
    let base: Base
}

extension MyReversed: Collection {
    public enum Index: Comparable {
        case element(Base.Index)
        case end

airspeedswift

public struct SubSliceView<C: CollectionType>: Sliceable {
    let collection: C
    let bounds: Range<C.Index>

    public var startIndex: C.Index { return bounds.startIndex }
    public var endIndex: C.Index { return bounds.endIndex }
    
    public subscript(idx: C.Index) -> C.Generator.Element

airspeedswift

// Swift 4.0 (and 3.2 as well!)

struct LazySplit<Base: Collection>: Collection
    where Base.Element: Equatable,
          Base.SubSequence: Collection
{
    struct Index: Comparable {
        let start, end: Base.Index
        static func ==(lhs: Index, rhs: Index) -> Bool { return lhs.start == rhs.start }
        static func < (lhs: Index, rhs: Index) -> Bool { return lhs.start < rhs.start }

airspeedswift

// ideally we would define this inside the tree struct
private class _Node<T: Comparable> {
    var _value: T
    var _left: _Node<T>? = nil
    var _right: _Node<T>? = nil
    
    init(value: T) { _value = value }
}

airspeedswift

// this particular API/implementation for demonstration only,
// not necessarily quite what will be proposed
extension Collection where SubSequence == Self {
    /// Drop n elements from the front of `self` in-place,
    /// returning the dropped prefix.
    mutating func dropPrefix(_ n: IndexDistance) -> SubSequence {
        // nature of error handling/swallowing/trapping/optional
        // returning here TBD...
        let newStart = index(startIndex, offsetBy: n)
        defer { self = self[newStart..<endIndex] }

airspeedswift

extension Array where Element: Comparable
{
    mutating func mergesortInPlace() {
        
        var tmp: [Generator.Element] = []
        tmp.reserveCapacity(numericCast(self.count))
        
        func merge(lo: Int, _ mi: Int, _ hi: Int) {
            tmp.removeAll(keepCapacity: true)
            tmp.extend(self[lo..<hi])

airspeedswift

extension RangeReplaceableCollection
  where
  // Index: RandomAccessIndexType → Self: RandomAccessCollection
  Self: RandomAccessCollection,
  // still need this, until generics allow constraints to guarantee
  // this is the case for all collections...
  SubSequence.Iterator.Element == Iterator.Element {
    // mutating in-place operations should be imperative verb phrases,
    // so let's rename this stablySort