PolylineEncoding.swift

import CoreLocation
import UIKit

extension CLLocationCoordinate2D {
    init() {
        self.init(latitude: 0, longitude: 0)
    }

    static var invalidCoordinate: CLLocationCoordinate2D {
        return kCLLocationCoordinate2DInvalid
    }

    var isValid: Bool {
        return CLLocationCoordinate2DIsValid(self)
    }
}

func encodedPolyline(coordinates: [CLLocationCoordinate2D]) -> String {
    let initialValue = (array: [Double](), previousCoordinate: CLLocationCoordinate2D())
    return coordinates.reduce(initialValue, combine: { (memo, coordinate) in
        let (array, previousCoordinate) = memo
        let deltaLatitude = coordinate.latitude - previousCoordinate.latitude
        let deltaLongitude = coordinate.longitude - previousCoordinate.longitude
        return (array + [deltaLatitude, deltaLongitude], coordinate)
    }).array.map { delta -> String in
        var encoded = ""
        var value = Int(round(delta * 1e5))
        if value < 0 {
            value = ~(value << 1)
        } else {
            value = value << 1
        }
        while value >= 0x20 {
            let char = (0x20 | (value & 31)) + 63
            encoded.append(UnicodeScalar(char))
            value >>= 5
        }
        let char = value + 63
        encoded.append(UnicodeScalar(char))
        return encoded
    }.reduce("", +)
}

func decodedPolyline(encodedString: String) -> [CLLocationCoordinate2D] {
    struct IntCoordinate {
        init() {

        }

        init(_ latitude: Int, _ longitude: Int) {
            self.latitude = latitude
            self.longitude = longitude
        }

        let latitude: Int = 0
        let longitude: Int = 0

        func addDeltas(deltaLatitude: Int, _ deltaLongitude: Int) -> IntCoordinate {
            return IntCoordinate(latitude + deltaLatitude, longitude + deltaLongitude)
        }

        var coordinate: CLLocationCoordinate2D {
            return CLLocationCoordinate2D(latitude: Double(latitude) * 1e-5, longitude: Double(longitude) * 1e-5)
        }
    }

    struct Memo {
        let coordinates: [CLLocationCoordinate2D] = []
        let lastCoordinate: IntCoordinate? = nil
        let prevOrdinate: Int? = nil
        let result: Int = 0
        let shift: Int = 0

        func addCoordinateByDeltas(deltaLatitude: Int, _ deltaLongitude: Int) -> Memo {
            let newCoordinate = (lastCoordinate ?? IntCoordinate()).addDeltas(deltaLatitude, deltaLongitude)
            return Memo(coordinates: coordinates + [newCoordinate.coordinate], lastCoordinate: newCoordinate, prevOrdinate: nil, result: 0, shift: 0)
        }

        func updateOrdinate(newOrdinate: Int) -> Memo {
            return Memo(coordinates: coordinates, lastCoordinate: lastCoordinate, prevOrdinate: newOrdinate, result: 0, shift: 0)
        }

        func updateResultShift(newResult: Int, _ newShift: Int) -> Memo {
            return Memo(coordinates: coordinates, lastCoordinate: lastCoordinate, prevOrdinate: prevOrdinate, result: newResult, shift: newShift)
        }
    }

    return reduce(encodedString.utf8, Memo()) { (memo, codeUnit) in
        let value = Int(codeUnit) - 63

        let result = memo.result | ((value & 0x1F) << memo.shift)
        let shift = memo.shift + 5
        if value < 0x20 {
            let newOrdinate = result & 1 != 0 ? ~(result >> 1) : (result >> 1)
            if let prevOrdinate = memo.prevOrdinate {
                return memo.addCoordinateByDeltas(prevOrdinate, newOrdinate)
            } else {
                return memo.updateOrdinate(newOrdinate)
            }
        } else {
            return memo.updateResultShift(result, shift)
        }
    }.coordinates
}

// MARK: - Testing

func approximatelyEqual(a: CLLocationDegrees, b: CLLocationDegrees) -> Bool {
    return abs((a - b) * 1e5) < 1
}

func approximatelyEqual(a: [CLLocationCoordinate2D], b: [CLLocationCoordinate2D]) -> Bool {
    if a.count != b.count {
        return false
    }

    for (ai, bi) in Zip2(a, b) {
        if !approximatelyEqual(ai.latitude, bi.latitude) || !approximatelyEqual(ai.longitude, bi.longitude) {
            return false
        }
    }

    return true
}

let locations = [
    CLLocationCoordinate2D(latitude: 38.5, longitude: -120.2),
    CLLocationCoordinate2D(latitude: 40.7, longitude: -120.95),
    CLLocationCoordinate2D(latitude: 43.252, longitude: -126.453),
]
encodedPolyline(locations) == "_p~iF~ps|U_ulLnnqC_mqNvxq`@"
approximatelyEqual(decodedPolyline("_p~iF~ps|U_ulLnnqC_mqNvxq`@"), locations)

let locations2 = [
    CLLocationCoordinate2D(latitude: 51.55921, longitude: -0.14029),
    CLLocationCoordinate2D(latitude: 51.55931, longitude: -0.14014),
    CLLocationCoordinate2D(latitude: 51.55684, longitude: -0.13840),
    CLLocationCoordinate2D(latitude: 51.55334, longitude: -0.14089),
    CLLocationCoordinate2D(latitude: 51.55149, longitude: -0.14108),
    CLLocationCoordinate2D(latitude: 51.55102, longitude: -0.14061),
    CLLocationCoordinate2D(latitude: 51.54743, longitude: -0.14145),
    CLLocationCoordinate2D(latitude: 51.54618, longitude: -0.14183),
    CLLocationCoordinate2D(latitude: 51.54431, longitude: -0.14145),
    CLLocationCoordinate2D(latitude: 51.54352, longitude: -0.14177),
    CLLocationCoordinate2D(latitude: 51.53891, longitude: -0.14248),
    CLLocationCoordinate2D(latitude: 51.53809, longitude: -0.14192),
    CLLocationCoordinate2D(latitude: 51.53638, longitude: -0.14031),
    CLLocationCoordinate2D(latitude: 51.53512, longitude: -0.13905),
    CLLocationCoordinate2D(latitude: 51.53248, longitude: -0.13935),
    CLLocationCoordinate2D(latitude: 51.53079, longitude: -0.13875),
    CLLocationCoordinate2D(latitude: 51.52610, longitude: -0.13862),
    CLLocationCoordinate2D(latitude: 51.52597, longitude: -0.13937),
]
encodedPolyline(locations2) == "aduyHxkZS]lN{IzTpNpJd@|A}AlUfDxFjAtJkA|C~@x[lCbDoBtIaIzF{FnOz@pIwBh\\YXtC"
approximatelyEqual(decodedPolyline("aduyHxkZS]lN{IzTpNpJd@|A}AlUfDxFjAtJkA|C~@x[lCbDoBtIaIzF{FnOz@pIwBh\\YXtC"), locations2)