Swift Array diff

Question

Gegeben zwei Arrays, wobei eins die alte Menge von Werten und das andere die neuen Werte ist, möchte ich das "Diff" dieser zwei Arrays finden, so dass Aktualisierungen des ursprünglichen Arrays wie folgt dargestellt werden können:

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

ich versuche, eine einfachere Version von this, wo die Änderungen zu bauen Objekt gebaut basiert auf Objektgleichheit, ist anstelle von Indizes als RAC-MutableCollectionProperty (für die der Code here ist und was vielleicht der komplizierteste Bit sein, Code habe ich schon lange gesehen, keine Dokumentation hilft nicht).

Auch wichtig für dieses Projekt ist die Fähigkeit, Änderungen an einem Array auf jeder Granularitätsebene beobachten zu können. Beispielsweise ist ein eindimensionales Array, das T auf Equatable beschränkt, ein relativ einfacher Anwendungsfall. Sie können als eine Art Tabelle erstellen, die die Änderungen beschreibt und auf Gleichheit der Objekte prüft. Wenn Sie jedoch erst einmal zweidimensionale Arrays verwenden, wird es etwas kniffliger, da Sie nicht nur die Elemente auf der untersten Ebene unterscheiden müssen, sondern auch die Entfernungen auf der Ebene der Schnitte beschreiben. In der Praxis ist nicht mehr als 2D-Arrays wirklich notwendig, aber es wäre nett, eine Lösung zu haben, die unabhängig von der Array-Tiefe funktioniert. Ich bin nicht unbedingt auf der Suche nach einer Lösung (obwohl das fantastisch wäre), wirklich nur irgendwelche Hinweise und High-Level-Lösungen, wie Sie dieses Problem anzugehen.

Ein Weg, dachte ich habe von mehreren Array-Ebenen zu beobachten ist eine diffing Funktion zu schreiben, die auf eindimensionale Arrays arbeitet und eine Eigenschaft zu konstruieren, so dass:

let property: MutableCollectionProperty<MutableCollectionProperty<Int>> 

, wo die Eigenschaft, wenn seine generische überprüfen würde Typ ist von seinem eigenen Typ. Ich würde die Änderungen Beschreibung etwas ändern müssen näher an

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

oder vielleicht wie etwas

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]) 
} 

Dies sind nur meine Vorüberlegungen obwohl, ich bin für jede Lösung oder einen Vorschlag offen.

BOUNTY EDIT:

Die Prämie an jemanden vergeben werden, die eine Lösung, die die folgenden Parameter angegeben zur Verfügung stellen kann:

• Es seien x und y sein, zwei schnellen Array
• beide Arrays vom Typ T: Equatable
• beide Arrays können
• die Tiefe x von jeder Tiefe sein == die Tiefe y

eine Änderung Satz kann erzeugt werden, wo ein Wechselsatz beschreibt:

• , die Elemente aus der x zu y (durch Index) gelöscht wurden
• die Elemente in y dass eingefügt wurden nicht in x (durch Index) waren
• bewegt, welche Elemente von x zu y (durch Index)

Wandel wurden s müssen nur auf der niedrigsten Ebene des Arrays beschrieben werden (keine Notwendigkeit, sich über die Einfügung & Entfernung von höheren Segmenten zu kümmern, obwohl Sie wirklich verdienen die 300 rep mit diesem), aber ändern Indizes müssen den verschachtelten Index Pfad angeben. Wenn das Array beispielsweise ein 3D-Array ist und ein Objekt bei array[0][5][2] gelöscht wurde, sollte die resultierende Indexänderung ein Array sein [0, 5, 2]. Dieses Array beschreibt eine einzelne Löschung und alle Löschungen würden vom Typ [[Int]] sein.

Edit:

ich die Forderung der Arrays Entfernen von beliebiger Tiefe zu sein. Nehmen wir an, dass es sich einfach um 1d-Arrays handelt.

Answer 1

Ab Swift 2.2 ist dies unmöglich. Sie geben die folgenden Anforderungen:

• beiden Arrays vom Typ T: Equatable
• beide Arrays jeder Tiefe

Aber die Fähigkeit, sein können eine eingeschränkte Ausdehnung auf ein neues Protokoll konform zu machen sind nur planned for Swift 3.0 , so können Sie jetzt nicht extension Array where Element: Array<Equatable> konform zu Equatable Protokoll machen. Dies bedeutet, dass nur 1D-Arrays vom Typ T: Equatable sein können.

EDIT:

Im Grunde, was Sie tun müssen, ist, einen Algorithmus zu schreiben, die Longest common subsequence problem löst.Für 1D-Arrays können Sie Dwifft Bibliothek verwenden, die das Problem in der folgenden Art und Weise löst:

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 
    } 
} 

Answer 2

Ich bin nicht sicher, das alle Anforderungen erfüllt Ihre Prämie, aber ich werde einige Code, den ich für die Berechnung Arrays Unterschiede verwenden schreiben:

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) 
} 

Mein spezifischen Anwendungsfall ist Unterschiede zur Berechnung eines UITableView zu aktualisieren, wozu ich auch die folgenden:

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() 
     } 
    } 

}