LevenshteinEditDistance.swift

//
//  LevenshteinEditDistance.swift
//
//  Created by Guilherme Rambo on 01/09/16.
//  Based on https://gist.github.com/shergin/a6dba6ee5ae3b9ecb16c
//  Copyright © 2016 Guilherme Rambo. All rights reserved.
//

import Foundation

enum EditOperation<Element> {
    case delete(index: Int)
    case insert(index: Int, element: Element)
    case replace(index: Int, element: Element)
    case none
    
    var distance: Int {
        switch self {
        case .none:
            return 0
        default:
            return 1
        }
    }
}

class EditOperationChain<Element> {
    typealias ConcreteEditOperation = EditOperation<Element>
    typealias ConcreteEditOperationChain = EditOperationChain<Element>
    
    private(set) var current: ConcreteEditOperation
    private(set) var previousChain: ConcreteEditOperationChain? = nil
    private(set) var distance: Int = 0
    
    init(current: ConcreteEditOperation, previousChain: ConcreteEditOperationChain? = nil) {
        self.current = current
        self.previousChain = previousChain
        
        self.distance = (self.previousChain?.distance ?? 0) + current.distance
    }
}


class Matrix<Value> {
    
    private(set) var columns: Int
    private(set) var rows: Int
    
    private var backstage: [Value?]
    
    init(columns: Int, rows: Int) {
        self.columns = columns
        self.rows = rows
        self.backstage = Array(repeating: nil, count: columns * rows)
    }
    
    subscript(column: Int, row: Int) -> Value? {
        get {
            return self.backstage[self.columns * row + column]
        }
        set {
            self.backstage[self.columns * row + column] = newValue
        }
    }
}


class MinimumEditDistanceCalculator<Element: Equatable> {
    typealias ConcreteEditOperation = EditOperation<Element>
    typealias ConcreteEditOperationChain = EditOperationChain<Element>
    
    var before: [Element]
    var after: [Element]
    var matrix: Matrix<EditOperationChain<Element>>!
    
    init(before: [Element], after: [Element]) {
        self.before = before
        self.after = after
    }
    
    func solve() -> [EditOperation<Element>] {
        let matrix = Matrix<ConcreteEditOperationChain>(columns: self.before.count + 1, rows: self.after.count + 1)
        
        matrix[0, 0] = ConcreteEditOperationChain(
            current: .none
        )
        
        // Deletions
        if self.before.count > 0 {
            for i in 1...self.before.count {
                matrix[i, 0] = ConcreteEditOperationChain(
                    current: .delete(index: 0/*i - 1*/),
                    previousChain: matrix[i - 1, 0]
                )
            }
        }
        
        // Insertions
        if self.after.count > 0 {
            for j in 1...self.after.count {
                matrix[0, j] = ConcreteEditOperationChain(
                    current: .insert(index: 0/*j - 1*/, element: self.after[j - 1]),
                    previousChain: matrix[0, j - 1]
                )
            }
        }
        
        if self.before.count > 0 && self.after.count > 0 {
            for i in 1...self.before.count {
                for j in 1...self.after.count {
                    
                    if self.before[i - 1] == self.after[j - 1] {
                        matrix[i, j] = matrix[i - 1, j - 1]
                        continue
                    }
                    
                    let variants = [
                        matrix[i - 1, j]!,  // deletion
                        matrix[i, j - 1]!,  // insertion
                        matrix[i - 1, j - 1]!  // substitution
                        ] as [ConcreteEditOperationChain]
                    
                    let distances = variants.map { $0.distance }
                    let minimumIndex = distances.index(of: distances.min()!)!
                    let minimumEditChain = variants[minimumIndex]
                    
                    var editChain: ConcreteEditOperationChain? = nil
                    switch minimumIndex {
                    case 0:
                        // Deletion
                        editChain = ConcreteEditOperationChain(current: .delete(index: j), previousChain: minimumEditChain)
                        break
                    case 1:
                        // Insertion
                        editChain = ConcreteEditOperationChain(current: .insert(index: j - 1, element: self.after[j - 1]), previousChain: minimumEditChain)
                        break
                    case 2:
                        // Substitution
                        editChain = ConcreteEditOperationChain(current: .replace(index: j - 1, element: self.after[j - 1]), previousChain: minimumEditChain)
                        break
                    default:
                        assertionFailure()
                    }
                    
                    matrix[i, j] = editChain
                }
            }
        }
        
        var currentChain: ConcreteEditOperationChain? = matrix[self.before.count, self.after.count]
        
        var editOperations: [ConcreteEditOperation] = []
        
        while currentChain != nil {
            let editOperation = currentChain!.current
            
            switch editOperation {
            case .none:
                break
            default:
                editOperations.insert(editOperation, at: 0)
                break
            }
            
            currentChain = currentChain!.previousChain
        }
        
        return editOperations
    }
}

Valeu (Y)