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

// A simple linked list using enums:
enum List<Element> {
    case End
    indirect case Node(Element, List<Element>)
    
    func cons(x: Element) -> List<Element> {
        return .Node(x, self)
    }
}

airspeedswift

enum Color { case R, B }

indirect enum Tree<Element: Comparable> {
    case Empty
    case Node(Color,Tree<Element>,Element,Tree<Element>)
    
    init() { self = .Empty }
    
    init(_ x: Element, color: Color = .B,
        left: Tree<Element> = .Empty, right: Tree<Element> = .Empty)

airspeedswift

struct LazilyFlattenedRandomAccessCollection<C: CollectionType where C.Index: RandomAccessIndexType> {

    let collections: [C]
    
    var count: Int {
        return collections.reduce(0) { (total: Int, next: C) -> Int in
            total + numericCast(next.count)
        }
    }
    

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

/*:

You used to be able to do this:

    [anything].map(toString)

but then String() replaced toString,
which meant you had to write

    [anything].map { String($0) }

airspeedswift

extension SequenceType where Generator.Element: Equatable {
    /// Checks every element in a sequence is equal to a given element
    func all(element: Generator.Element) -> Bool {
        return !contains { $0 != element }
    }

    /// Checks no element in a sequence is equal to a given element
    func none(element: Generator.Element) -> Bool {
        return !contains(element)
    }

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

// works for any index type
extension CollectionType {
    var mid: Index {
        return advance(startIndex,
            distance(startIndex,endIndex) / 2
        )
    }
}

// and specialize for random-access index types

airspeedswift

extension Range where T: RandomAccessIndexType {
    var mid: T {
        return startIndex.advancedBy(
            startIndex.distanceTo(endIndex) / 2
        )
    }
}

extension Sliceable