Skip to content

Instantly share code, notes, and snippets.

Ben Cohen airspeedswift

View GitHub Profile
@airspeedswift
airspeedswift / NonemptyCollection.swift
Created Dec 17, 2016
Non-empty collection in Swift
View NonemptyCollection.swift
protocol NonemptyCollection: Collection {
var first: Iterator.Element { get }
}
enum NonemptyIndex<Base: Collection>: Comparable {
case head
case tail(Base.Index)
static func ==(lhs: NonemptyIndex, rhs: NonemptyIndex) -> Bool {
switch (lhs,rhs) {
@airspeedswift
airspeedswift / mergesort.swift
Last active Jan 3, 2017
Swift 3 Merge Sort
View mergesort.swift
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
@airspeedswift
airspeedswift / RBTree.swift
Created Oct 4, 2015
red black tree updated for 2.1b2
View RBTree.swift
private enum ListNode<Element> {
case End
indirect case Node(Element, next: ListNode<Element>)
func cons(x: Element) -> ListNode<Element> {
return .Node(x, next: self)
}
}
public struct ListIndex<Element> {
@airspeedswift
airspeedswift / list.swift
Last active Oct 31, 2015
Swift Singly Linked List
View list.swift
private enum ListNode<Element> {
case End
indirect case Node(Element, tag: Int, next: ListNode<Element>)
/// Computed property to fetch the tag. .End has an
/// implicit tag of zero.
var tag: Int {
switch self {
case .End: return 0
case let .Node(_, tag: n, _):
@airspeedswift
airspeedswift / MyArray.swift
Last active Nov 22, 2016
Array using ManagedBuffer
View MyArray.swift
private class MyArrayBuffer<Element>: ManagedBuffer<Int,Element> {
func clone() -> MyArrayBuffer<Element> {
return self.withUnsafeMutablePointerToElements { elements -> MyArrayBuffer<Element> in
return MyArrayBuffer<Element>.create(self.allocatedElementCount) { newBuf in
newBuf.withUnsafeMutablePointerToElements { newElems->Void in
newElems.initializeFrom(elements, count: self.value)
}
return self.value
@airspeedswift
airspeedswift / mergesort.swift
Last active Jan 20, 2017
Stable Swift merge sort
View mergesort.swift
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
airspeedswift / list.swift
Last active Nov 3, 2019
indirect enum List as CollectionType
View list.swift
// 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
airspeedswift / rbt.swift
Created Jul 22, 2015
Red Black Tree with indirect and pattern matching for Swift 2.0b4
View rbt.swift
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)
View lazilyflattenedcollection.swift
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
airspeedswift / shuffle.swift
Last active Feb 2, 2018 — forked from natecook1000/shuffle.swift
Fisher-Yates shuffle as protocol extension on any random-access collection
View shuffle.swift
// 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)
You can’t perform that action at this time.