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

}