edit_distance.swift

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

import Foundation

enum EditOperation<Element> {
    case Insert(position: Int, value: Element)
    case Delete(position: Int, value: Element)
    case Replace(position: Int, value: Element)
    case Move(fromPosition: Int, toPosition: Int, value: Element)
}

extension Array where Element : Equatable {
    
    typealias EditStack = Array<EditOperation<Element>>
    
    // Slightly modified implementation of the Wagner–Fischer algorithm
    // https://en.wikipedia.org/wiki/Wagner–Fischer_algorithm
    func editSteps(fromArray fromArray: Array<Element>) -> EditStack {
        var editMatrix = Array<Array<EditStack>>(count: fromArray.count + 1, repeatedValue: Array<EditStack>(count: self.count + 1, repeatedValue: EditStack()))
        
        for (index, value) in fromArray.enumerate() {
            editMatrix[index + 1][0] = editMatrix[index][0]
            editMatrix[index + 1][0].append(EditOperation<Element>.Delete(position: index, value: value))
        }
        
        for (index, value) in self.enumerate() {
            editMatrix[0][index + 1] = editMatrix[0][index]
            editMatrix[0][index + 1].append(EditOperation<Element>.Delete(position: index, value: value))
        }
        
        for (fromIndex, fromElement) in fromArray.enumerate() {
            for (toIndex, toElement) in self.enumerate() {
                if (fromElement == toElement) {
                    editMatrix[fromIndex + 1][toIndex + 1] = editMatrix[fromIndex][toIndex]
                } else {
                    let deleteStack  = editMatrix[fromIndex][toIndex + 1]
                    let insertStack  = editMatrix[fromIndex + 1][toIndex]
                    let replaceStack = editMatrix[fromIndex][toIndex]
                    
                    if deleteStack.count < insertStack.count && deleteStack.count < replaceStack.count {
                        editMatrix[fromIndex+1][toIndex+1] = deleteStack
                        editMatrix[fromIndex+1][toIndex+1].append(EditOperation<Element>.Delete(position: fromIndex, value: fromElement))
                    } else if insertStack.count < replaceStack.count {
                        editMatrix[fromIndex+1][toIndex+1] = insertStack
                        editMatrix[fromIndex+1][toIndex+1].append(EditOperation<Element>.Insert(position: fromIndex, value: toElement))
                    } else {
                        editMatrix[fromIndex+1][toIndex+1] = replaceStack
                        editMatrix[fromIndex+1][toIndex+1].append(EditOperation<Element>.Replace(position: fromIndex, value: toElement))
                    }
                }
            }
        }
        
        // TODO: find pairs of inserts and deletes for the same value and turn them into moves
        
        return editMatrix[fromArray.count][self.count].reverse()
    }
    
}


let source = [1, 2, 3, 4, 6, 8]
let destination = [2, 4, 5, 6, 7, 8, 1, 9]
let steps = destination.editSteps(fromArray: source)
for step in steps {
    switch step {
    case let .Insert(position: position, value: value):
        print("Insert \(value) at \(position)")
    case let .Delete(position: position, value: value):
        print("Delete \(value) at \(position)")
    case let .Replace(position: position, value: value):
        print("Replace value at \(position) with \(value)")
    case let .Move(fromPosition: fromPosition, toPosition: toPosition, value: value):
        print("Move \(value) at \(fromPosition) to \(toPosition)")
    }
}

// Output:
//   Insert 9 at 5
//   Insert 1 at 5
//   Insert 7 at 4
//   Replace value at 3 with 5
//   Replace value at 2 with 4
//   Delete 1 at 0