Patience Implementation in Swift

patience.swift

import UIKit

struct DiffLine: CustomDebugStringConvertible {

    enum DiffLineType {
        case equal
        case remove
        case add
        case replace
    }

    let textA: String
    let textB: String
    let type: DiffLineType

    var debugDescription: String {
        switch type {
        case .equal:
            return textA
        case .remove:
            return "--- \(textA)"
        case .add:
            return "+++ \(textB)"
        case .replace:
            return "+++ \(textB)"
        }
    }
}

class PatienceStrategy {

    typealias DiffFallback = ([String], [String]) -> [DiffLine]

    let linesA: [String]
    let linesB: [String]

    let fallback: DiffFallback

    init(linesA: [String], linesB: [String], diffFallback: @escaping DiffFallback ) {
        self.linesA = linesA
        self.linesB = linesB
        self.fallback = diffFallback
    }

    struct Slice {
        let a_low: Int
        let a_high: Int
        let b_low: Int
        let b_high: Int

        var a_range: CountableRange<Int> {
            return a_low..<a_high
        }

        var b_range: CountableRange<Int> {
            return b_low..<b_high
        }

        func isNotEmpty() -> Bool {
            return (a_low < a_high) && (b_low < b_high)
        }
    }

    class Match {
        var prev: Match?
        var next: Match?

        let a_line: Int
        let b_line: Int

        init(a_line: Int, b_line: Int){
            self.a_line = a_line
            self.b_line = b_line
        }
    }

    typealias registerLine = (Int, Int, Int, Int)

    func unique_matching_lines(slice: Slice) -> [Match] {
        var counts = [String: registerLine]()

        slice.a_range.forEach { position in
            var register = counts[linesA[position]] ?? (0, 0, Int.max, Int.max)
            register.0 += 1
            register.2 = min(position, register.2)
            counts[linesA[position]] = register
        }

        slice.b_range.forEach { position in
            var register = counts[linesB[position]] ?? (0, 0, Int.max, Int.max)
            register.1 += 1
            register.3 = min(position, register.3)
            counts[linesB[position]] = register
        }

        let results = counts.filter { (key, value)  in
            return ((value.0 == 1) && (value.1 == 1))
        }.sorted { itemA, itemB in
            return itemA.value.2 < itemB.value.2
        }.map { key, value in
            return Match(a_line: value.2, b_line: value.3)
        }

        return results
    }

    func patience_sort(matches: [Match]) -> Match? {

        var stacks = [Match]()

        matches.forEach{ match in
            let i = binary_search(stacks: stacks, match: match)

            if i >= 0 {
                match.prev = stacks[i]
            }

            stacks.append(match)
        }
        var match: Match? = stacks.last
        guard match != nil else { return nil }

        while let newMatch = match?.prev {
            newMatch.prev?.next = match
            match = newMatch.prev
        }

        return match
    }

    func binary_search(stacks: [Match], match: Match) -> Int {
        var low = -1
        var high = stacks.count

        while ((low + 1) < high) {
            let mid: Int = (low + high) / 2
            if stacks[mid].b_line < match.b_line {
                low = mid
            } else {
                high = mid
            }
        }
        return low
    }

    func fallback_diff(slice: Slice) -> [DiffLine] {
        let sublinesA = Array(linesA[slice.a_range])
        let sublinesB = Array(linesB[slice.b_range])
        return self.fallback(sublinesA, sublinesB)
    }

    func diff(slice: Slice) -> [DiffLine] {

        var match = self.patience_sort(matches: self.unique_matching_lines(slice: slice))

        if match == nil {
            return self.fallback_diff(slice: slice)
        }

        var lines = [DiffLine]()

        var a_line = slice.a_low
        var b_line = slice.b_low


        repeat {

            let a_next = (match != nil) ? match!.a_line : slice.a_high
            let b_next = (match != nil) ? match!.a_line : slice.b_high

            let subslice = Slice(a_low: a_line, a_high: a_next, b_low: b_line, b_high: b_next)
             lines.append(contentsOf: self.diff(slice: subslice))
            if match == nil {
                return lines
            }

            lines.append(.init(textA: linesA[(match?.a_line ?? 0)], textB: linesB[(match?.b_line ?? 0)], type: .equal))

            a_line = (match?.a_line ?? 0)  + 1
            b_line = (match?.b_line ?? 0) + 1
            match = match?.next

        } while(match != nil)
     return lines
    }

    func patience() {

        let firstSlice = Slice(a_low: 0, a_high: linesA.count, b_low: 0, b_high: linesB.count)
        let lines = self.diff(slice: firstSlice)

        lines.forEach { line in
            print(line)
        }
    }


}


extension String {
    func lines() -> [String] {
        return self.components(separatedBy: .newlines)
    }
}

func execute(valueA: String, valueB: String) {
    let linesA = valueA.lines()
    let linesB = valueB.lines()

    let strategy = PatienceStrategy(linesA: linesA, linesB: linesB) { blockA, blockB in
        var lines = [DiffLine]()
        (0..<max(blockA.count, blockB.count)).forEach { numberLine in
            guard blockA.count > numberLine else { lines.append(DiffLine(textA: "", textB: blockB[numberLine], type: .add)) ; return }
            guard blockB.count > numberLine else { lines.append(DiffLine(textA: blockA[numberLine], textB: "", type: .remove)) ; return }
            lines.append(DiffLine(textA: blockA[numberLine], textB: blockB[numberLine], type: (blockA[numberLine] == blockB[numberLine]) ? .equal : .replace))
        }
        return lines
    }

    strategy.patience()
}

let a = """
aaa
bbb
cccc
DDDDD
e
"""


let b = """
aaa
bb
ccccCCC
e
"""
execute(valueA: a, valueB: b)