Swift Array diff

Question

Biorąc pod uwagę dwie tablice, gdzie jeden jest starym zestawem wartości, a drugi to nowe wartości, chcę znaleźć "różnicę" tych dwóch tablic, takie aktualizacje oryginalnej tablicy można przedstawić jako:

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

Próbuję zbudować prostszą wersję this gdzie sprzeciwu zmiany jest zbudowany w oparciu o równości obiektu, zamiast indeksów jak RAC-MutableCollectionProperty jest (dla których kod jest here i co może być najbardziej skomplikowany bit kod, który widziałem od dłuższego czasu, żadna dokumentacja nie pomaga).

Ważnym elementem tego projektu jest także możliwość obserwowania zmian w tablicy na dowolnym poziomie szczegółowości. Na przykład tablica jednowymiarowa, ograniczająca zakres od T do Equatable, jest stosunkowo łatwym przypadkiem użycia. Możesz, jako RAC-MutableCollectionProperty, zbudować tabelę opisującą zmiany, sprawdzając równość obiektów. Jednak gdy przejdziesz do korzystania z tablic dwuwymiarowych i głębiej, staje się to trochę trudniejsze, ponieważ nie tylko musisz odróżniać elementy na najniższym poziomie, ale także opisywać przeprowadzanie na poziomie sekcji. W praktyce nie więcej niż tablice 2D są naprawdę potrzebne, ale dobrze byłoby mieć rozwiązanie działające niezależnie od głębokości tablicy. Niekoniecznie szukam rozwiązania (choć byłoby to fantastyczne), naprawdę tylko wszelkie wskazówki i rozwiązania na wysokim poziomie, jak podejść do tego problemu.

Jednym ze sposobów myślałem o obserwować wiele poziomów tablicy jest napisać funkcję diffing który działa na pojedynczych wymiarowych tablic i skonstruować własności takie, że:

let property: MutableCollectionProperty<MutableCollectionProperty<Int>> 

którym nieruchomość byłoby sprawdzić, czy jej nazwę rodzajową typ jest tego samego typu. Musiałabym zmienić opis zmian do czegoś bliżej

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

czy może coś jak

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

Są to tylko moje wstępne przemyślenia jednak jestem otwarty na wszelkie rozwiązania lub sugestii.

BOUNTY Edycja:

Bounty otrzyma do kogoś, kto może stanowić rozwiązanie Biorąc pod uwagę następujące parametry:

• Niech X i Y są dwa szybkimi tablicy
• oba układy typu T: Equatable
• obie tablice mogą być dowolnej głębokości
• głębokość x == głębokość y

zespół zmiany mogą być generowane w której zestaw zmiana opisuje:

• elementy, które zostały usunięte z X Y (o wskaźniku)
• elementy, które zostały wprowadzone do Y, że nie były w x (o wskaźniku)
• elementy, które zostały przeniesione począwszy od x do y (wskaźnikiem)

Zmiana s tylko muszą być opisane na najniższym poziomie macierzy (nie musisz się martwić wstawianiu & usuwania wyższych segmentów, chociaż tak naprawdę uzyskasz naprawdę z tego 300 rep), ale zmienne indeksy muszą wskazywać zagnieżdżoną ścieżkę indeksu.

Na przykład, jeśli tablica jest tablicą 3d, a obiekt o numerze array[0][5][2] został usunięty, wynikiem zmiany indeksu powinna być tablica [0, 5, 2]. Ta tablica opisuje pojedynczą delecję, a wszystkie usunięcia będą miały typ [[Int]].

Edit:

jestem usunięcie wymogu tablic będących dowolnej głębokości. Powiedzmy, że są to po prostu tablice 1d.

Answer 1

Od Swift 2.2 jest to niemożliwe. podać następujące wymagania:

• obie tablice typu T: Equatable
• obie tablice mogą być dowolnej głębokości

ale zdolność dokonać ograniczone rozszerzenie zgodne z nowego protokołu jest tylko planned for Swift 3.0 , więc teraz nie możesz ustawić extension Array where Element: Array<Equatable> zgodnie z protokołem Equatable. Oznacza to, że tylko tablice 1d mogą być typu T: Equatable.

EDIT:

zasadzie to, co trzeba zrobić, to napisać algorytm, który rozwiązuje Longest common subsequence problem.Dla 1d tablic można użyć Dwifft biblioteki, która rozwiązuje ten problem w następujący sposób:

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

nie jestem pewien, to spełnia wszystkie wymagania Bounty, ale będę pisać jakiś kod używać do obliczania różnic tablice:

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

Mój przypadek szczególny ma zastosowanie do obliczania różnic zaktualizować UITableView, dla których celem mam także następujące:

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

}