repmin.swift

// 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)"
        }
    }
}