startupthekid - 1 year ago 82

Swift Question

Given two arrays, where one is the old set of values and the other is the new values, I want to find the "diff" of those two arrays such updates to the original array can be represented as:

`enum CollectionChange<T: SequenceType> {`

case Initial(T)

case Update(T, deletions: [Int], insertions: [Int], modifications: [Int])

}

I'm trying to build a simpler version of this where the changes object is built based on object equality, instead of indexes as

`RAC-MutableCollectionProperty`

Also important for this project is the ability to be able to observe changes to an array at any level of granularity. For example, a one-dimensional array, restricting

`T`

`Equatable`

`RAC-MutableCollectionProperty`

One way I've thought of to observe multiple array levels is to write a diffing function that works on single dimensional arrays and construct a property such that:

`let property: MutableCollectionProperty<MutableCollectionProperty<Int>>`

where the property would check if its generic type is of it's own type. I'd have to change the changes description to something closer to

`enum Changes<T> {`

case Initial(T)

case Update(T, deletions: [NSIndexPath], insertions: [NSIndexPath], modifications: [NSIndexPath])

}

or maybe something like

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

}

These are just my preliminary thoughts though, I'm open to any solution or suggestion.

BOUNTY EDIT:

The bounty will be awarded to someone who can provide a solution that given the following parameters:

- Let x and y be two swift array
- both arrays of type
`T: Equatable`

- both arrays can be of any depth
- the depth of x == the depth of y

a change set can be generated where a change set describes:

- which elements have been deleted from the x

to y (by index) - which elements have been inserted into y that

weren't in x (by index) - which elements have been moved going from x

to y (by index)

Changes only have to be described at the lowest level of the array (no need to worry about insertion & removal of higher segments, although you'd

For example, if the array is a 3d array and an object at

`array[0][5][2]`

`[0, 5, 2]`

`[[Int]]`

Edit:

I'm removing the requirement of the arrays being of any depth. Let's say that they're simply 1d arrays.

Answer Source

As of Swift 2.2, this is impossible. You give the following requirements:

- both arrays of type
`T: Equatable`

- both arrays can be of any depth

But the ability to make a constrained extension conform to a new protocol is only planned for Swift 3.0, so right now you can't make `extension Array where Element: Array<Equatable>`

conform to `Equatable`

protocol. This means that only 1d arrays can be of of type `T: Equatable`

.

**EDIT:**

Basically what you need to do is to write an algorithm that solves Longest common subsequence problem. For 1d arrays you can use Dwifft library which solves the problem in the following way:

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