Swift Array diff

Учитывая два массива, где один из них - это старый набор значений, а другой - новые значения, я хочу найти "diff" этих двух массивов, такие обновления для исходного массива могут быть представлены как:

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

Я пытаюсь создать более простую версию этого, где объект изменений строится на основе равенства объектов, а не индексов как RAC-MutableCollectionProperty (для которого код здесь и какой может быть самый сложный бит кода, который я видел за время, никакая документация не помогает).

Также важно, чтобы этот проект мог наблюдать изменения в массиве на любом уровне детализации. Например, одномерный массив, ограничивающий T до Equatable, является относительно простым вариантом использования. Вы можете, как RAC-MutableCollectionProperty создать какую-то таблицу, описывающую изменения, проверяя равенство на объектах. Однако, как только вы приступите к использованию двумерных массивов и глубже, это становится немного сложнее, потому что вам не только нужно различать элементы на самом низком уровне, но также описывать абзацы на уровне разделов. На практике, действительно, не больше 2D-массивов, но было бы неплохо иметь решение, которое работает независимо от глубины массива. Я не обязательно ищу решение (хотя это было бы фантастически), на самом деле просто любые указатели и решения высокого уровня о том, как подойти к этой проблеме.

Один из способов, с помощью которого я мог наблюдать несколько уровней массива, - написать функцию, которая работает на одномерных массивах, и построить свойство, которое:

let property: MutableCollectionProperty<MutableCollectionProperty<Int>>

где свойство проверяет, является ли его общий тип его собственным типом. Мне нужно будет изменить описание изменений на что-то ближе к

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

или, может быть, что-то вроде

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

Это только мои предварительные мысли, хотя я открыт для любого решения или предложения.

BOUNTY EDIT:

Награда будет вручена тому, кто может предоставить решение, которое дает следующие параметры:

Пусть x и y - два быстрых массива
оба массива типа T: Equatable
оба массива могут иметь любую глубину
глубина x == глубина y

может быть сгенерирован набор изменений, где описывается набор изменений:

какие элементы были удалены из x к y (по индексу)
какие элементы были вставлены в y, не были в x (по индексу)
какие элементы были перемещены из x к y (по индексу)

Изменения должны быть описаны только на самом низком уровне массива (не нужно беспокоиться о вставке и удалении более высоких сегментов, хотя вы действительно зарабатываете 300 репатов с этим), но изменяйте индексы должны указывать путь вложенного указателя.

Например, если массив представляет собой 3D-массив и объект в array[0][5][2] был удален, результирующее изменение индекса должно быть массивом [0, 5, 2]. Этот массив описывает одно удаление, и все удаления будут иметь тип [[Int]].

Edit:

Я удаляю требование наличия массивов любой глубины. Скажем, что это просто 1d массивы.

Ответ 1

С Swift 2.2 это невозможно. Вы даете следующие требования:

оба массива типа T: Equatable
оба массива могут иметь любую глубину

Но возможность создания ограниченного расширения соответствует новому протоколу, это только для Swift 3.0, поэтому прямо сейчас вы не можете сделать extension Array where Element: Array<Equatable> соответствовать Equatable. Это означает, что только 1d массивы могут иметь тип T: Equatable.

EDIT:

В основном вам нужно написать алгоритм, который решает Самая длинная общая проблема подпоследовательности. Для 1d массивов вы можете использовать библиотеку Dwifft, которая решает проблему следующим образом:

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

Ответ 2

Я не уверен, что это отвечает всем вашим требованиям к бонусам, но я выложу код, который я использую для вычисления разностей массивов:

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

Моим конкретным вариантом использования является вычисление различий для обновления UITableView, для чего у меня также есть следующее:

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

}