Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
// This accompanies http://chris.eidhof.nl/posts/repmin-in-swift.html
import UIKit
// Unfortunately, we need Box
public class Box<T> {
public let unbox: T
public init(_ value: T) { self.unbox = value }
}
enum Tree {
case Node(Box<Tree>, Box<Tree>)
case Leaf(Int)
}
func minimum(t: Tree) -> Int {
switch t {
case .Node(let l, let r):
return min(minimum(l.unbox), minimum(r.unbox))
case .Leaf(let x):
return x
}
}
func replaceAllLeaves(t: Tree, newValue: Int) -> Tree {
switch t {
case .Node(let l, let r):
return .Node(Box(replaceAllLeaves(l.unbox, newValue)),Box(replaceAllLeaves(r.unbox, newValue)))
case .Leaf(_):
return .Leaf(newValue)
}
}
func repMinHelper(t: Tree) -> (minimum: Int, build: Int -> Tree) {
switch t {
case .Node(let l, let r):
let (lMin, lBuild) = repMinHelper(l.unbox)
let (rMin, rBuild) = repMinHelper(r.unbox)
return (min(lMin,rMin), { x in .Node(Box(lBuild(x)), Box(rBuild(x))) })
case .Leaf(let value):
return (value, { x in .Leaf(x) })
}
}
func repMin(t: Tree) -> Tree {
let (min, builder) = repMinHelper(t)
return builder(min)
}
func node(l: Tree, r: Tree) -> Tree {
return .Node(Box(l), Box(r))
}
let tree = node(node(.Leaf(1), .Leaf(2)), .Leaf(3))
repMin(tree)
extension Tree: Printable {
var description: String {
switch self {
case let .Node(l, r):
return "(\(l.unbox.description), \(r.unbox.description))"
case let .Leaf(i):
return "\(i)"
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment