Swift Array diff

Dado dos matrices, donde uno es el antiguo set de valores y el otro los nuevos valores, quiero encontrar el "diff" de esas dos matrices, tales actualizaciones a la matriz original se pueden representar como:

enum CollectionChange<T: SequenceType> { case Initial(T) case Update(T, deletions: [Int], insertions: [Int], modifications: [Int]) } 

Estoy intentando build una versión más simple de esto donde el object de cambios se basa en la igualdad de objects, en lugar de índices como RAC-MutableCollectionProperty (para el cual el código está aquí y cuál podría ser el bit de código más complicado que tengo visto en un time; no hay documentation que no ayude).

También es importante para este proyecto la capacidad de poder observar los cambios en una matriz a cualquier nivel de granularidad. Por ejemplo, una matriz unidimensional, que restringe T a Equatable , es un caso de uso relativamente fácil. Puede, como RAC-MutableCollectionProperty crear algún tipo de tabla que describa los cambios, comprobando la igualdad en los objects. Sin embargo, una vez que se llega a usar matrices bidimensionales y más profundas, se vuelve un poco más complicado porque no solo tiene que diferenciar los elementos en el nivel más bajo sino también describir las eliminaciones a nivel de sección. En la práctica, nunca más de 2D arrays es realmente necesario, pero sería bueno tener una solución que funcione independientemente de la profundidad de la matriz. No estoy necesariamente buscando una solución (aunque sería fantástica), realmente cualquier apuntador y soluciones de alto nivel sobre cómo abordar este problema.

Una forma en la que he pensado observar múltiples niveles de matriz es escribir una function diferente que funcione en matrices unidimensionales y build una propiedad tal que:

 let property: MutableCollectionProperty<MutableCollectionProperty<Int>> 

donde la propiedad verificará si su tipo genérico es de su tipo. Tendría que cambiar la descripción de los cambios a algo más cercano a

 enum Changes<T> { case Initial(T) case Update(T, deletions: [NSIndexPath], insertions: [NSIndexPath], modifications: [NSIndexPath]) } 

o tal vez algo como

 enum Changes<T> { case Initial(T) case UpdateSections(sections: [T], deletions:[Int], insertions: [Int], modifications: [Int]) case UpdateIndexes(T, deletions: [Int], insertions: [Int], modifications: [Int]) } 

Estos son solo mis pensamientos preliminares, estoy abierto a cualquier solución o sugerencia.

BOUNTY EDIT:

La recompensa se otorgará a alguien que pueda proporcionar una solución que tenga los siguientes parameters:

  • Deje que x y y sean dos matrices rápidas
  • Ambas matrices de tipo T: Equatable
  • ambos arrays pueden ser de cualquier profundidad
  • la profundidad de x == la profundidad de y

se puede generar un set de cambios donde un set de cambios describe:

  • qué elementos se han eliminado de la x a y (por índice)
  • qué elementos se han insertado en y que no estaban en x (por índice)
  • qué elementos se han movido yendo de x a y (por índice)

Los cambios solo deben describirse en el nivel más bajo de la matriz (no hay necesidad de preocuparse por la inserción y eliminación de segmentos más altos, aunque realmente se ganaría la repetición de 300 con eso), pero los índices de cambio deben indicar la ruta del índice nested.

Por ejemplo, si la matriz es una matriz 3d y se elimina un object en la array[0][5][2] , el cambio de índice resultante debe ser una matriz [0, 5, 2] . Esa matriz describe una sola eliminación y todas las deleciones serían del tipo [[Int]] .

Editar:

Estoy eliminando el requisito de que las matrices sean de cualquier profundidad. Digamos que son simplemente arrays 1d.

A partir de Swift 2.2, esto es imposible. Usted da los siguientes requisitos:

  • Ambas matrices de tipo T: Equatable
  • ambos arrays pueden ser de cualquier profundidad

Pero la capacidad de hacer que una extensión restringida cumpla con un nuevo protocolo solo está planificada para Swift 3.0 , por lo que en este momento no puede hacer la extension Array where Element: Array<Equatable> Equatable protocolo Equatable . Esto significa que solo las matrices 1d pueden ser del tipo T: Equatable .

EDITAR:

Básicamente, lo que debe hacer es escribir un algorithm que resuelva el problema de subsecuencia común más largo . Para arrays 1d puede usar la biblioteca Dwifft que resuelve el problema de la siguiente manera:

 public extension Array where Element: Equatable { public func diff(other: [Element]) -> Diff<Element> { let table = MemoizedSequenceComparison.buildTable(self, other, self.count, other.count) return Array.diffFromIndices(table, self, other, self.count, other.count) } private static func diffFromIndices(table: [[Int]], _ x: [Element], _ y: [Element], _ i: Int, _ j: Int) -> Diff<Element> { if i == 0 && j == 0 { return Diff<Element>(results: []) } else if i == 0 { return diffFromIndices(table, x, y, i, j-1) + DiffStep.Insert(j-1, y[j-1]) } else if j == 0 { return diffFromIndices(table, x, y, i - 1, j) + DiffStep.Delete(i-1, x[i-1]) } else if table[i][j] == table[i][j-1] { return diffFromIndices(table, x, y, i, j-1) + DiffStep.Insert(j-1, y[j-1]) } else if table[i][j] == table[i-1][j] { return diffFromIndices(table, x, y, i - 1, j) + DiffStep.Delete(i-1, x[i-1]) } else { return diffFromIndices(table, x, y, i-1, j-1) } } } internal struct MemoizedSequenceComparison<T: Equatable> { static func buildTable(x: [T], _ y: [T], _ n: Int, _ m: Int) -> [[Int]] { var table = Array(count: n + 1, repeatedValue: Array(count: m + 1, repeatedValue: 0)) for i in 0...n { for j in 0...m { if (i == 0 || j == 0) { table[i][j] = 0 } else if x[i-1] == y[j-1] { table[i][j] = table[i-1][j-1] + 1 } else { table[i][j] = max(table[i-1][j], table[i][j-1]) } } } return table } } 

No estoy seguro de que cumpla todos tus requisitos de recompensas, pero publicaré un código que utilizo para calcular las diferencias de las matrices:

 func arrayInsertionDeletionAndNoopIndexes<T: Equatable>(objects: [T], originalObjects: [T]) -> ([Int], [Int], [Int]) { let insertions = objects.filter({ !originalObjects.contains($0) }).map({ objects.index(of: $0)! }) let noops = originalObjects.filter({ objects.contains($0) }).map({ originalObjects.index(of: $0)! }) let deletions = originalObjects.filter({ !objects.contains($0) }).map({ originalObjects.index(of: $0)! }) return (insertions, deletions, noops) } func arrayInsertionDeletionAndNoopIndexPaths<T: Equatable>(objects: [T], originalObjects: [T], section: Int = 0) -> ([IndexPath], [IndexPath], [IndexPath]) { let (insertions, deletions, noops) = arrayInsertionDeletionAndNoopIndexes(objects: objects, originalObjects: originalObjects) let insertionIndexPaths = insertions.map({ IndexPath(row: $0, section: section) }) let deletionIndexPaths = deletions.map({ IndexPath(row: $0, section: section) }) let noopIndexPaths = noops.map({ IndexPath(row: $0, section: section) }) return (insertionIndexPaths, deletionIndexPaths, noopIndexPaths) } 

Mi caso de uso específico es para calcular diferencias para actualizar una UITableView , para lo cual también tengo lo siguiente:

 extension UITableView { func insertAndDeleteCellsForObjects<T: Equatable>(objects: [T], originalObjects: [T], section: Int = 0) { let (insertions, deletions, _) = arrayInsertionDeletionAndNoopIndexPaths(objects: objects, originalObjects: originalObjects, section: section) if insertions.count > 0 || deletions.count > 0 { beginUpdates() insertRows(at: insertions, with: .automatic) deleteRows(at: deletions, with: .automatic) endUpdates() } } }