burrows-wheeler-transform.swift

// Playground - noun: a place where people can play

import UIKit

// MARK: Utilities
func take<T>(slice: Slice<T>, num: Int) -> Slice<T> {
    let n = (num < slice.count) ? num : slice.endIndex
    return slice[0..<n]
}

func drop<T>(slice: Slice<T>, num: Int) -> Slice<T> {
    let n = (num < slice.count) ? num : slice.endIndex
    return slice[n..<slice.endIndex]
}

func rotate<T>(slice: Slice<T>, count: Int) -> Slice<T> {
    return drop(slice, count) + take(slice, count)
}

// MARK: Burrows-Wheeler Transform
func encode(s: String, mark: String) -> String {
    let string = s + mark
    let range = (0..<countElements(string))
    
    let encoded = range.map    { rotate(Slice(string), $0) }
                       .sorted { String($0) < String($1) }
                       .map    { $0.last! }
    
    return String(encoded)
}

func decode(s: String, mark: String) -> String? {
    let range = 0..<countElements(s)
    let table = Array(count: countElements(s), repeatedValue:"")

    return reduce(range, table) { t, _ in
        return map(Zip2(t, s)) { String($1) + $0 }
              .sorted          { $0 < $1         }
    }.filter {
        $0.hasSuffix(mark)
    }.first
}

let mark    = "$"
let string  = "BANANA"
let encoded = encode(string, mark)    // ANNB$AA
let decoded = decode(encoded, mark)   // BANANA$

More about Burrows–Wheeler transform:

Tom Stuart's lightning talk
Wikipedia