Skip to content

Instantly share code, notes, and snippets.

@lldong
Last active August 29, 2015 14:10
Show Gist options
  • Save lldong/ad6b6944e55147f688db to your computer and use it in GitHub Desktop.
Save lldong/ad6b6944e55147f688db to your computer and use it in GitHub Desktop.
// 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$
@lldong
Copy link
Author

lldong commented Nov 29, 2014

More about Burrows–Wheeler transform:

Tom Stuart's lightning talk
Wikipedia

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment