Skip to content

Instantly share code, notes, and snippets.

View airspeedswift's full-sized avatar

Ben Cohen airspeedswift

View GitHub Profile
@airspeedswift
airspeedswift / spellcheck.swift
Last active June 21, 2024 07:57
A simple spelling corrector in Swift
// Swift version of the spelling checker described in http://norvig.com/spell-correct.html
import Foundation
let alphabet = "abcdefghijklmnopqrstuvwxyz"
/// Given a word, produce a set of possible edits with one character
/// transposed, deleted, replaced or a rogue character inserted
func edits(_ word: String) -> Set<String> {
@airspeedswift
airspeedswift / rbtree.swift
Created April 15, 2024 05:01
Red black tree in Swift 5.10
indirect enum Tree<Element: Comparable> {
enum Color { case R, B }
case empty
case node(Color, Tree<Element>, Element, Tree<Element>)
init() { self = .empty }
init(
@airspeedswift
airspeedswift / list.swift
Created March 23, 2024 18:48
A Basic Noncopyable Singly Linked List in Swift
// To run this code on a Mac with Xcode installed:
// Download the latest toolchain from https://www.swift.org/download/#trunk-development-main and install it
// From a command line:
// export TOOLCHAINS=`plutil -extract CFBundleIdentifier raw -o - /Library/Developer/Toolchains/swift-latest.xctoolchain/Info.plist`
// xcrun swiftc -parse-as-library -enable-experimental-feature NoncopyableGenerics -enable-experimental-feature MoveOnlyPartialConsumption -Xfrontend -disable-round-trip-debug-types -enable-experimental-feature BorrowingSwitch linkedlist.swift
struct Box<Wrapped: ~Copyable>: ~Copyable {
private let pointer: UnsafeMutablePointer<Wrapped>
@airspeedswift
airspeedswift / Swift57RedBlackTree.swift
Created June 28, 2022 19:51
Swift red/black persistent tree
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,
////===--- EitherCollection.swift - A collection of two different types -----===//
////
//// This source file is part of the Swift.org open source project
////
//// Copyright (c) 2014 - 2020 Apple Inc. and the Swift project authors
//// Licensed under Apache License v2.0 with Runtime Library Exception
////
//// See https://swift.org/LICENSE.txt for license information
//// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
////
////===--- EitherSequence.swift - A sequence type-erasing two sequences -----===//
////
//// This source file is part of the Swift.org open source project
////
//// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
//// Licensed under Apache License v2.0 with Runtime Library Exception
////
//// See https://swift.org/LICENSE.txt for license information
//// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
////
/// Conform references types for use in the COW wrapper to this protocol
protocol Cowable: class {
/// Make a new unique instance of `copied`
static func makeUnique(_ copied: Self) -> Self
}
/// A wrapper that turns a Cowable reference type into a value-semantic
/// type with access to all of its properties
@dynamicMemberLookup
extension Sequence {
func count(where p: (Element)->Bool)->Int {
return reduce(0) { p($1) ? $0 + 1 : $0 }
}
}
let fn: ((Int) -> Bool) -> Int = [1,2,3].count
let n = fn { $0<2 }
print(n) // 1
@airspeedswift
airspeedswift / Bounded.swift
Created October 26, 2018 04:33
Bound a sequence with a start and end marker
struct BoundedSequence<Base: Sequence> {
let _base: Base
}
extension BoundedSequence {
struct Iterator {
enum State { case starting, iterating, ended }
var _state: State
var _iterator: Base.Iterator
}
@airspeedswift
airspeedswift / usort.swift
Created August 16, 2018 00:50
Unsafe stable mergesort
extension UnsafeMutableBufferPointer {
public mutating func merge(
using aux: UnsafeMutableBufferPointer<Element>,
_ lo: Int, _ mid: Int, _ hi: Int,
by isOrderedBefore: (Element, Element) -> Bool
) {
assert(hi <= self.endIndex)
assert(self.count == aux.count)
let from = self.baseAddress!, to = aux.baseAddress!