jflinter/dwifft

Swift Diff

dwifft's Issues

Deleted and Inserted indexes not being tested

Hi,

I've noticed that the unit tests are not asserting correctly that insertion and deletions happens at the expected indexes. Expectations were only being fulfilled but not asserted.
I've also took the chance to refactor the Unit test to improve the readability and to separate them by test domain.
I've already open a PR #51 with the proposed changes.

Thanks

Unnecessary double assignment in CollectionViewDiffCalculator:processChanges

This assignment is probably unnecessary and was left after a copy & paste from TableViewDiffCalculator https://github.com/jflinter/Dwifft/blob/master/Dwifft/Dwifft%2BUIKit.swift#L145

[Performance] It takes 7s to calculate 500 object

It takes 7s to calculate 500 object
The Object is a custom class, with properties and some other methods,
will spend much time than using Int or String as T

SingleSection Calculators don't support changing view after init

I'm upgrading Dwifft to 0.6.3, and had a breakage I didn't expect from the release notes. Our code creates the SingleSectionTableViewDiffCalculator with a dummy UITableView, and then during viewDidLoad it swaps in the "real" table view.

I'm changing our code to eliminate the dummy view, but I think it'd be a good idea to change the public API of the calculators to disallow changing the view, because I've also run into bugs where changing the tableView doesn't invalidate the calculator's state and it subsequently triggers a crash from UIKit (ex: asking the new tableView to delete a row that it's not actually displaying, but the previous tableView was).

It looks like SingleSectionCollectionViewDiffCalculator has the same potential bug.

Minimum iOS deployment target?

Hi, the podspec in this repository states that the iOS deployment target is '8.0, but the Cocoapods specs states that the minimum target is iOS 9.0. This is making it impossible for me to use 0.4 in my iOS 8 project! Not sure where the right place to fix this is.

Add tree-diffing algorithm to efficiently compute table view section changes

Ideally, it would be nice to be able to calculate diffs for 2 (or, really, N)-dimensional arrays. This would allow animated section + row changes for UITableView/UICollectionView.

I think the work for this looks something like:

• Implement a functional N-ary tree class, and code to convert an array to such a representation.
• Use a tree-diffing algorithm to compute the diff between two such trees. http://www.sciencedirect.com/science/article/pii/S0304397505000174 seems like a good place to start here.
• This previous step will need to have the added wrinkle that the diff must be constrained to a maximum "depth" of 2, since otherwise the individual transformation steps must either map to a UITableView section or row insertion.
• Once the diff is obtained, update TableViewDiffCalculator to transform the diff steps into a series of animated updates.

Usage with ReactiveCocoa

I love Dwifft but I would love even more to use it with ReactiveCocoa to help reduce code complexity in my collection view controllers even more.

Currently, I have a helper class that takes an instance of SignalProducer<[[T]]> where T: Equatable (so it works with the differ). Every time the signal producer emits a new value:

        self.data.producer.observeOn(UIScheduler()).on(next: { [unowned self] in
            guard let collectionView = self.collectionView else { return }
            for (index, element) in $0.enumerate() {
                if index == self.diffCalculators.count {
                    let calculator = CollectionViewDiffCalculator<T>(collectionView: collectionView, initialRows: element)
                    calculator.sectionIndex = index
                    self.diffCalculators.append(calculator)
                } else {
                    let calculator = self.diffCalculators[index]
                    calculator.rows = element
                }
                for index in self.data.value.count..<(self.diffCalculators.count >= self.data.value.count ? self.diffCalculators.count : self.data.value.count) {
                    self.diffCalculators.removeAtIndex(index)
                }
            }
        })
            .takeUntil(self.willDeallocSignal())
            .start()

Here, while enumerating through my 2d array, if a diff calculator doesn't exist yet, one is created and added to my storage array, diffCalculators. If one does exist, the rows property is set. Afterwards, I loop through the remaining sections and remove them.

Unfortunately, I've been incredibly unsuccessful in getting this to work. Time after time I get a The number of sections contained in the collection view after the update (1) must be equal to the number of sections contained in the collection view before the update (0), plus or minus the number of sections inserted or deleted (0 inserted, 0 deleted).' and I can't tell if that's in my logic or if I'm using Dwifft wrong.

Any suggestions?

SingleSectionTableViewDiffCalculator setting animations doesn't work

Need to have the underlying table dif animations set. Perhaps:

public final class SingleSectionTableViewDiffCalculator<Value: Equatable> {

    /// The table view to be managed
    public weak var tableView: UITableView?

    /// All insertion/deletion calls will be made on this index.
    public let sectionIndex: Int

    /// You can change insertion/deletion animations like this! Fade works well.
    /// So does Top/Bottom. Left/Right/Middle are a little weird, but hey, do your thing.
  public var insertionAnimation = UITableViewRowAnimation.automatic {
    didSet {
      internalDiffCalculator.insertionAnimation = insertionAnimation
    }
  }
  
  public var deletionAnimation = UITableViewRowAnimation.automatic {
    didSet {
      internalDiffCalculator.deletionAnimation = deletionAnimation
    }
  }

... more code

I think the results of diff should have indices while some items just moved to a new position

After comparing ["a", "b", "c", "d"] to ["c", "b", "a"] we should know how to transform the first array into the second and vice versa. I mean we should get something like this:

{
  $0.moveTo(2)
  $1.same()
  $2.moveTo(0)
  $3.delete()
}

So that it's possible to move a UITableViewCell to a new position when needed.

Crash with SingleSectionTableViewDiffCalculator

Hi!
We have started receiving some Crashlytics crash reports in our production app recently. And they all point to some bizarre issue with Dwifft. Now the app has 2k daily active users and the crash happened only 4 times now, so it is not terribly common. None of the QA teams have been able to reproduce it and neither have I. However it happened to three different users.

The crash always happens when setting new rows for the Dwifft SingleSectionTableViewDiffCalculator. We are using the latest version of Dwifft available via Cocoapods.

Basically this is what we get:

Fatal Exception: NSInternalInconsistencyException
attempt to insert row 20 into section 0, but there are only 10 rows in section 0 after the update

Part of the stack trace:

Fatal Exception: NSInternalInconsistencyException
0  CoreFoundation                 0x1becc1ea4 __exceptionPreprocess
1  libobjc.A.dylib                0x1bde91a50 objc_exception_throw
2  CoreFoundation                 0x1bebd7a2c +[_CFXNotificationTokenRegistration keyCallbacks]
3  Foundation                     0x1bf6c61d0 -[NSAssertionHandler handleFailureInMethod:object:file:lineNumber:description:]
4  UIKitCore                      0x1ec19e150 -[UITableView _endCellAnimationsWithContext:]
5  UIKitCore                      0x1ec1b70a0 -[UITableView endUpdates]
6  Dwifft                         0x101669340 TableViewDiffCalculator.processChanges(newState:diff:) (Dwifft+UIKit.swift:45)
7  Dwifft                         0x101668cdc specialized AbstractDiffCalculator.sectionedValues.setter (AbstractDiffCalculator.swift:78)
8  Dwifft                         0x10166a308 specialized SingleSectionTableViewDiffCalculator.rows.setter (<compiler-generated>)
9  Dwifft                         0x101669be8 SingleSectionTableViewDiffCalculator.rows.setter (<compiler-generated>)

This is how dwifft is configured:

    private var dataModel: [AppNotification] = []
    private var diffCalculator: SingleSectionTableViewDiffCalculator<AppNotification>?
    ...
    override func viewDidLoad() {
        ...
        diffCalculator = SingleSectionTableViewDiffCalculator<AppNotification>(tableView: self.tableView, initialRows: [], sectionIndex: 0)
        diffCalculator?.insertionAnimation = .top
        diffCalculator?.deletionAnimation = .middle
        ...
    }

The crash happens when we fetch the data from network, prepare and then store it to the dataModel property and then set the self.diffCalculator?.rows = self.dataModel.

Any ideas on what could be the reason for this?

Demo Usage in Readme

I think it would help people trying to integrate this repo in a project a lot if there was a sample use case.

Redundant Conformance on Protocol Equatable

Jack,

I'm getting an error on Dwift.swift line 131 under xCode 9GM, after Swift 4 conversion

public static func diff<Section: Equatable, Value: Equatable>(lhs: SectionedValues<Section, Value>, rhs: SectionedValues<Section, Value>) -> [SectionedDiffStep<Section, Value>]

and I'm certainly not smart enough to fix it without breaking everything. Any help greatly appreciated.

Thank in advance

Docs link SSL cert issue

Just a heads up, getting this when I visit the https version of your docs linked in the readme:

Direct access to Diff<T>

Maybe I'm missing something, but is there a more direct way of getting into the diff other than through Array.apply(_:) and the various UIKit extensions? Looking at the public API, DiffStep<T> is exposed but the properties in Diff<T> are not; so maybe this is a mistake? If so, I can provide a PR.

I'm asking this because I have a use case that requires consuming the diff results on a lower-level layer that hides the diff'ing implementation from the UI.

Using Dwifft with custom class

I am using Dwifft with a custom class and I am not getting the expected result.
It seems that the issue is because some of the variables of the class are changed.
In order to avoid that I wanted to exclude these unwated property. I hence added the following function but Dwiff nevel calls it. How Dwiff test equality between two objects?

static func == (lhs: Slide, rhs: Slide) -> Bool {
    return lhs.markdown == rhs.markdown
}

Swift 4.2/Xcode 10 support

I have noticed, that Dwifft cannot be compiled in Xcode 10 and Swift 4.2. Main issues are:

1. UITableViewRowAnimation renamed to UITableView.RowAnimation.
2. UITableViewStyle renamed to UITableView.Style.
3. UIApplicationLaunchOptionsKey renamed to UIApplication.LaunchOptionsKey .
4. Some other details in example app and test dependencies.

How would you execute the transition to Swift 4.2? Do you think the changes need to be backward compatible? I can see few difficult issues to fix if you required the backward compatibility.

I am willing to help with the transition.

Does not work with tableView with sections.

Adding support for isEqual completion handler

How hard would it be to add a completion handler for the diff function so the values don't have to be equatable? A library called Diff does this.

For example:

        [1,2,3].diff([3,4,5]) { (old, new) -> Bool in
            return old == new
        }

This would allow me to pass an array of custom models and only check if certain values are equal.

Thanks,
Joe

Update podspec for Swift 3?

Do you update the podspec for Swift 3?

Mismatch between pod spec and Cocoapods Specs repository

When trying to install Dwifft through Cocoapods in an app that has iOS 8 as the minimum deployment target, I get the following error:

[!] Unable to satisfy the following requirements:

- `Dwifft (~> 0.4)` required by `Podfile`
- `Dwifft (~> 0.4)` required by `Podfile`

Specs satisfying the `Dwifft (~> 0.4)` dependency were found, but they required a higher minimum deployment target.

Initially I thought Dwifft's deployment was higher than iOS 8, but when I checked the Podspec here in this repository, I saw that it has iOS 8 as the minimum deployment version. Nevertheless problems persisted.

However, when I add Dwifft in my Podfile as follows:

 pod 'Dwifft', :git => '[email protected]:jflinter/Dwifft.git'

it just works™.

This got me thinking that maybe there is a mismatch between the current Podspec in this repository and the Podspec that is published to the CocoaPods specs repo. Looking at spec for Dwifft in the CocoaPods Specs repo, this seems to indeed be the case:

...
"platforms": {
    "ios": "9.0"
  },
...

Could it be that the minimum deployment target was changed after pushing the spec to the CocoaPods Specs repo? In that case, bumping the version number and pushing again would suffice.

Support moves

First off, great library! I've struggled with this issue for years and have always fallen back to an NSFetchedResultsController or just calling reloadData.

I watched your meetup video about Dwifft 0.6 online, and saw you mentioned having support for move operations for 1.0, which would be rad! I just wanted to make you aware of the Android implementation of this functionality (if you aren't already) - maybe you can take some inspiration from it, since it supports moves, inserts, and deletes. I think it's a different algorithm than the one you're using, but might be useful. The docs say it uses two passes of the Myers Difference Algorithm (which I believe is the same LCS algorithm you're using?) in order to detect the moves, since it can't be done in a single pass.

https://developer.android.com/reference/android/support/v7/util/DiffUtil.html

Keep up the good work!

Crash in CollectionViewDiffCalculator

Hi,

my app sometimes crashes when updating the CollectionView. Unfortunately I'm not able to reproduce the crashes, but the same code (using the TableViewDiffCalculator) works without problems for my tableviews.

I'm using pagination and want to eliminate possible duplicates - hence the diff function here.

// strongSelf is from a guard clause in the callback
let diff = strongSelf.itemList.diff(newItems)
strongSelf.itemList.append(contentsOf: strongSelf.itemList.apply(diff))

the didset iss correctly triggered with the append

var itemList: Array<Item> = [] {
    didSet {
      self.diffCalculator?.rows = itemList
    }
  }

Relevant crashlog:

#0. Crashed: com.apple.main-thread
0  libsystem_kernel.dylib         0x181562014 __pthread_kill + 8
1  libsystem_pthread.dylib        0x18162a450 pthread_kill + 112
2  libsystem_c.dylib              0x1814d63e0 abort + 140
3  libsystem_malloc.dylib         0x1815a6a38 _nano_vet_and_size_of_live + 330
4  libsystem_malloc.dylib         0x1815a8bf0 _nano_malloc_check_clear + 392
5  libsystem_malloc.dylib         0x1815a7b3c nano_malloc + 44
6  libsystem_malloc.dylib         0x1815962c4 malloc_zone_malloc + 172
7  CoreFoundation                 0x18246615c _CFRuntimeCreateInstance + 312
8  CoreFoundation                 0x182551604 __CFStringCreateImmutableFunnel3 + 2116
9  CoreFoundation                 0x18247034c CFStringCreateCopy + 504
10 CoreFoundation                 0x1825519f0 _CFStringCreateWithFormatAndArgumentsAux2 + 256
11 CoreFoundation                 0x182575b98 _CFLogvEx2Predicate + 156
12 CoreFoundation                 0x182575eec _CFLogvEx3 + 408
13 Foundation                     0x18305c454 _NSLogv + 132
14 Foundation                     0x182f8335c NSLog + 32
15 Foundation                     0x18301f76c -[NSAssertionHandler handleFailureInMethod:object:file:lineNumber:description:] + 64
16 UIKit                          0x188ce90e8 -[UICollectionView _endItemAnimationsWithInvalidationContext:tentativelyForReordering:animator:] + 13428
17 UIKit                          0x188cecc34 -[UICollectionView _endUpdatesWithInvalidationContext:tentativelyForReordering:animator:] + 92
18 UIKit                          0x188cecf14 -[UICollectionView _performBatchUpdates:completion:invalidationContext:tentativelyForReordering:animator:] + 384
19 UIKit                          0x188cecd74 -[UICollectionView _performBatchUpdates:completion:invalidationContext:tentativelyForReordering:] + 96
20 UIKit                          0x188ceccf8 -[UICollectionView _performBatchUpdates:completion:invalidationContext:] + 84
21 UIKit                          0x1885c71c0 -[UICollectionView performBatchUpdates:completion:] + 64
22 Dwifft                         0x100f1439c CollectionViewDiffCalculator.rows.setter (Dwifft+UIKit.swift)

Any idea what could be happening here?

Swift 3 Support?

Is there any Swift 3 support?

Podspec claims wrong version of swift

Podspec sets a SWIFT_VERSION of 3.0.1 even though the latest release adds Swift4 support.

Also, I don't think setting that actually does anything in the resulting project that cocoapods generates, at least as of cocoapods 1.3.x (it overrides your setting to the latest version supported by xcode)

Release 0.10.0 to improve Swift package manager support

Hello, thank you for the awesome library!

We depend on it on one of our libraries and recently we migrated to SPM. We currently need to reference (master) branch or commit (6fec2b), which does not work well for library dependecies – there are even some issues with SPM.

Could you please just tag the current master HEAD 0.10.0? (The patch version is required.)

Error on Carthage build -> DwifftTests

error: overriding instance method must be as accessible as its enclosing type.

Errors are on:

• insertRows
• deleteRows
• insertItems
• deleteItems

I have cloned the repo, built it and ran the tests with no problem. However it always fails the perform the Carthage build.

Support for Set<Equatable> collection type

There is a bunch of cases where we need to compare two sets of data and deal with their diff but here we forced to convert these collections to arrays and obviously use a heavier algorithm to deal with them. This can be achieved with the basic Swift Set operations like subtracting but I would really like to see such option in this library.

Question from the Slow Lane

@jflinter,

First thank you for this brilliant library. Like many, I have been struggling with the problems your code solves for years, first in ObjC and now Swift. Previously TLIndexPathTools has been my library of choice but it is in ObjC and I would love to transition over.

But, I have a request...(it's for yet another demo).

I am struggling with insertions and deletions and I can't seem to figure out how they work using Dwifft. Can you point me to (or put up) another multiSection viewController example that has the traditional NavBar Edit button that would enable drag and drop, deletions (and, stretch request, inserts) so slow learners like me can see exactly how to wire up Dwifft+UIKit?

I get the didSet but I can't seem to get a handle on all the rest of what Dwifft can really do. I am assuming that SectionedValues IS the one and only model. Is that the case?

Thank you in advance

Support for reload instead of delete+insert

I'm exploring using a different animation for reloading a row, for that I would need Dwifft to call reloadItems instead of deleteItems and insertItems.

My first guess is that a adding a naive support for reloads would just require checking for the intersection between deletes and inserts in processChanges(newState:diff:).

What do you think?

EXC_BAD_ACCESS in thread

Xcode Version 7.1.1 (7B1005)

My code is like this:

dispatch_async(queue) {
    let s1 = get_a_string()
    let s2 = get_another_string()

    // size of a and b is about 1000
    let a = s1!.characters.split { $0 == "\n" }.map(String.init)
    let b = s2!.characters.split { $0 == "\n" }.map(String.init)

    let diff = a.diff(b) // crash in Array::diffFromIndices
}

public for idx and value in DiffStep

Is there any reason these fields are not public

[RFC] Make `Dwifft` an enum, not a struct

It looks like Dwifft is only used as a namespace:
https://github.com/jflinter/Dwifft/blob/master/Dwifft/Dwifft.swift#L79

The problem with a struct is that it can be instantiated, Dwifft(). This isn't a problem now, since there are no instance members, but it is a bit awkward.

Changing this to enum Dwifft (with 0 cases) provides the same effect of namespacing, except you cannot instantiate an enum. 😄

See also:

• https://www.natashatherobot.com/swift-enum-no-cases/
• http://ericasadun.com/2016/07/18/dear-erica-no-case-enums/

Small buildTable Refactor idea

To prevent any future mistakes that might slip by PR review in the only spot Dwifft uses Unsafe*, could I make a PR to get the len of the args instead of passing the len in? Future xrefs to it can't pass something wrong in for the len https://github.com/jflinter/Dwifft/blob/master/Dwifft/Dwifft.swift#L281

// BEFORE
let table = MemoizedSequenceComparison.buildTable(lhs, rhs, lhs.count, rhs.count)
-->
// AFTER
let table = MemoizedSequenceComparison.buildTable(lhs, rhs)

// BEFORE
static func buildTable(_ x: [T], _ y: [T], _ n: Int, _ m: Int) -> [[Int]] {
-->
// AFTER
static func buildTable(_ x: [T], _ y: [T]) -> [[Int]] {
n = x.count
m = y.count
...

Dwifft 0.3 Is Not Available in the CocoaPods Spec Repo

According to the releases on GitHub, 0.3 is the latest version, but only versions up to 0.2 are available via CocoaPods (see: https://cocoapods.org/pods/Dwifft). A Podfile like this will reproduce the issue.

pod 'Dwifft', '0.3'

The likely solution to this issue is running pod trunk push Dwifft.podspec.

DiffCalculator for NSTableView

Hey,

I would like to refactor your current iOS offerings to include OSX support - NSTableView and perhaps NSCollectionView.

Would that be ok? And if so, have you any preference on how you would like it done?

Chris

tvOS scheme

Hey do you mind adding a tvOS scheme to the project? There shouldn't be any reason that it won't work out of the box that I can think of. Thanks!

*** Skipped building Dwifft due to the error:
Dependency "Dwifft" has no shared framework schemes for any of the platforms: tvOS

Release 0.9 to CocoaPods

Please release 0.9 to CocoaPods

Broken for 'release' config using CocoaPods

Seems something is fishy here... It compiles fine using the standard Debug xcconfig, but throws some missing symbol errors when trying to use Release.

I repro'd in a clean project using the Example app source so repro steps are:

• Download repro project
• Hit run and notice errors
• Edit the scheme to flip run back to using Debug
• Run again and notice no errors

The only difference I can see is you're linking the example app locally versus using a pod / carthage.

Undefined symbols for architecture i386:
  "__TFC6Dwifft22AbstractDiffCalculator5valuefT11atIndexPathV10Foundation9IndexPath_q_", referenced from:
      __TTSf4g_g_n___TFC10DwifftPods24StuffTableViewController9tableViewfTCSo11UITableView12cellForRowAtV10Foundation9IndexPath_CSo15UITableViewCell in StuffTableViewController.o
      __TTSf4g_g_n___TFC10DwifftPods29StuffCollectionViewController14collectionViewfTCSo16UICollectionView13cellForItemAtV10Foundation9IndexPath_CSo20UICollectionViewCell in StuffCollectionViewController.o
      __TTSf4g_g_n___TFC10DwifftPods25EventsTableViewController9tableViewfTCSo11UITableView12cellForRowAtV10Foundation9IndexPath_CSo15UITableViewCell in EventsTableViewController.o
  "__TFC6Dwifft22AbstractDiffCalculator5valuefT10forSectionSi_x", referenced from:
      __TToFC10DwifftPods24StuffTableViewController9tableViewfTCSo11UITableView23titleForHeaderInSectionSi_GSqSS_ in StuffTableViewController.o
      __TTSf4g_gs_g_n___TFC10DwifftPods29StuffCollectionViewController14collectionViewfTCSo16UICollectionView33viewForSupplementaryElementOfKindSS2atV10Foundation9IndexPath_CSo24UICollectionReusableView in StuffCollectionViewController.o
      __TTSf4d_n_n___TFC10DwifftPods25EventsTableViewController9tableViewfTCSo11UITableView23titleForHeaderInSectionSi_GSqSS_ in EventsTableViewController.o
  "__TFC6Dwifft22AbstractDiffCalculator15numberOfObjectsfT9inSectionSi_Si", referenced from:
      __TToFC10DwifftPods24StuffTableViewController9tableViewfTCSo11UITableView21numberOfRowsInSectionSi_Si in StuffTableViewController.o
      __TToFC10DwifftPods29StuffCollectionViewController14collectionViewfTCSo16UICollectionView22numberOfItemsInSectionSi_Si in StuffCollectionViewController.o
      __TFC10DwifftPods25EventsTableViewController9tableViewfTCSo11UITableView21numberOfRowsInSectionSi_Si in EventsTableViewController.o
      __TToFC10DwifftPods25EventsTableViewController9tableViewfTCSo11UITableView21numberOfRowsInSectionSi_Si in EventsTableViewController.o
  "__TFC6Dwifft22AbstractDiffCalculator16numberOfSectionsfT_Si", referenced from:
      __TToFC10DwifftPods24StuffTableViewController16numberOfSectionsfT2inCSo11UITableView_Si in StuffTableViewController.o
      __TToFC10DwifftPods29StuffCollectionViewController16numberOfSectionsfT2inCSo16UICollectionView_Si in StuffCollectionViewController.o
      __TFC10DwifftPods25EventsTableViewController16numberOfSectionsfT2inCSo11UITableView_Si in EventsTableViewController.o
      __TToFC10DwifftPods25EventsTableViewController16numberOfSectionsfT2inCSo11UITableView_Si in EventsTableViewController.o
  "__TFC6Dwifft22AbstractDiffCalculators15sectionedValuesGVS_15SectionedValuesxq__", referenced from:
      __TFC10DwifftPods24StuffTableViewController7shufflefT_T_ in StuffTableViewController.o
      __TFC10DwifftPods29StuffCollectionViewController7shufflefT_T_ in StuffCollectionViewController.o
      __TTSf4g_n___TFC10DwifftPods25EventsTableViewControllers12buttonPushesGSaV10Foundation4Date_ in EventsTableViewController.o
      __TTSf4n_g___TFFC10DwifftPods25EventsTableViewController11viewDidLoadFT_T_U_FCSo5TimerT_ in EventsTableViewController.o
ld: symbol(s) not found for architecture i386
clang: error: linker command failed with exit code 1 (use -v to see invocation)

Exemple: fatal error: swapping a location with itself is not supported

this happens on launching the exemple

CollectionViewDiffCalculator crashes every time

Fix taken from here: http://stackoverflow.com/questions/25265183/collectionview-performbatchupdates-crash

if oldRows.isEmpty {
collectionView?.reloadData()
} else {
collectionView?.performBatchUpdates({ () -> Void in
self.collectionView?.insertItemsAtIndexPaths(insertionIndexPaths)
self.collectionView?.deleteItemsAtIndexPaths(deletionIndexPaths)
}, completion: nil)
}

Issues with Storyboards causing dwifft to update incorrectly.

I have an issue with the storyboard, I have a view model which exposes an array that powers a table view and it fetches and updates the calculator.

Unfortunatly as the table view loads from the storyboard things like set bounds reload the data and eventually the view model comes back with the data.

If it does it quickly enougth it crashes.

Why? Because a set bounds call could occur the same time the data is loaded.

So the table view reloads with the latest data and the network call also tries to tell the calculator to update it.

So what are some solutions:

• A quick one is to compare the sizes of the section data to dwifft's and update, not sure how stable this is.
• I directly use the rows property from the swifft calculator so I have the last data from when the table was last updated.

What do you think ?

Separating into 2 libs

I think you should separate Dwifft.swift and Dwifft+UIKit.swift, because, as you said, maybe only Dwifft+UIKit.swift is actually useful for people. By doing that, I'd be easier to explain what the it does.
Dwifft is very useful and neat, but it has one major problem: It took me a whole paragraph to understand what could be explained with

Automatic updates of UITableView with animations in Swift 🔶

What are your thoughts?

watchOS Scheme

Tested on watchOS and everything works fine.

Call to `beginUpdates` should occur before modifying the table's source data

I've been getting errors from within some unit test code that uses TableViewDiffCalculator. From view controller code that's invoked whenever backing data has changed...

vehicles.producer.startWithNext { vehicles in
    self.diffCalculator.rows = vehicles.sort()
}

...an exception like this is thrown when diffCalculator.rows is set:

failed: caught "NSInternalInconsistencyException", "Invalid update: invalid number of rows in section 0. The number of rows contained in an existing section after the update (5) must be equal to the number of rows contained in that section before the update (5), plus or minus the number of rows inserted or deleted from that section (5 inserted, 0 deleted) and plus or minus the number of rows moved into or out of that section (0 moved in, 0 moved out)."

After looking into this, my understanding is that tableView.beginUpdates() and tableView.endUpdates() require the table's dataSource to be modified in between the two calls, or at least in the same block. This is what Apple's documentation seems to suggest:

At the conclusion of a block—that is, after endUpdates returns—the table view queries its data source and delegate as usual for row and section data. Thus the collection objects backing the table view should be updated to reflect the new or removed rows or sections.

Sure enough, if I surround my self.diffCalculator.rows = ... call with update methods...

vehicles.producer.startWithNext { vehicles in
    self.tableView.beginUpdates()
    self.diffCalculator.rows = vehicles.sort()
    self.tableView.endUpdates()
}

...no exception is thrown, since update methods can be nested, and only the outer set triggers the actual insertions/deletions to the table.

My proposal to fix this would be to move Dwifft's beginUpdates call to a willSet observer, so that the initial number of rows is calculated before rows is changed, or to encourage wrapping rows modifications with update methods, like I did above.

I think this bug is being missed in the Dwifft tests because insertRowsAtIndexPaths and deleteRowsAtIndexPaths are being overridden. What's confusing to me is why I'm noticing this in testing, but not when my application is being run, but regardless, let me know what you think!

Keep contentOffset when data has been changed

I've researched a lot regards to fix contentOffset after table dataSource has been updated. I couldn't find a way to do it with Dwifft. When diffCalculator.row = self.data is invoked with new values (in my case, new values will be added at front of previous data), it changes contentOffset. I attempted to use tableView.setContentOffset(offset, animated: false) after providing new data to diffCalculator which didn't work. Also, when new values (in this case, append to previous data) are added while scrolling, scroll somehow jumps on and off at some weird position. I also noticed, when same values were set to diffCalculator, it treated there were diff. I'd appreciate any advices. Thanks

Proposed significant optimization for common cases

Great work with Dwifft. Thanks for it.

One challenge with the LCS algorithm is that it is O(m*n) in both CPU and memory consumption. Though this isn't a problem in practice when the size of the arrays is moderate, it becomes a problem when the arrays are large.

Anything that can be done to reduce the size of the arrays passed to the LCS algorithm has very beneficial results.

This approach, which I've used in the past in another language, is to essentially trim off the matching prefixes and suffixes from the arrays passing only the "middle" of the array to the LCS algorithm.

Of course, if there is a change at both the head and tail of the array, this optimization has no benefit. In the common case, though, the benefit is huge.

Based on the guidelines, I thought it would be good to discuss the idea before opening a PR. Nevertheless, it may be easiest to just see the code.

In my previous implementation, I also added change beyond what I've proposed here to pick an upper bound on m*n work factor. When that limit is exceeded, a reloadData is really the best approach.

Swift 2/Xcode 7 Support

I've converted the framework to compile in Xcode 7, with Swift 2: master...natestedman:swift2

I suppose that Swift 2 changes the Xcode 7 pbxproj changes are separate concepts, but Xcode really really likes making those project file changes. I tried to keep the commits atomic though, so they could be split out if desired. I don't believe it's possible to open a pull request for a new branch, so I'm creating this as an issue since it's incompatible with Swift 1.2.

On a separate branch, I made additional changes that remove the LCS and Diff classes and replace them with extensions of Array, constrained to Element: Equatable: natestedman/Dwifft@swift2...swift2-extension

It might be possible to make the extensions more generic by having CollectionType extended instead, but I'd need to look into that more.

Blocking up the main thread. Some public API adjustments.

I attempted to implement Dwift with a library called CollapsableTable.

I planned to make so many changes to Dwift, I decided to pull each file out individually and work on it in isolation. So you'll notice the library is actually called Difter (in attached file) at the moment.

The public API of Dwift recommends the use of a table view calculator, which takes the table view and does some magical stuff to it. This was taking a bit too much control away from me, so I wanted to avoid using it.

The changes are quite extensive so I didn't want to issue a pull request for it until I get some feedback on what you think about the approach.

If the data model is 500 items or more, the main thread gets blocked up. Take a look at the attached code and run the Example Xcode scheme.

I've put a loading screen in place.

CollapsableDifter.zip

Swift 4 main thread warning

Main thread warning in this code.

/// You can change insertion/deletion animations like this! Fade works well.
    /// So does Top/Bottom. Left/Right/Middle are a little weird, but hey, do your thing.
    public var insertionAnimation = UITableViewRowAnimation.automatic, deletionAnimation = UITableViewRowAnimation.automatic

    override fileprivate func processChanges(newState: SectionedValues<Section, Value>, diff: [SectionedDiffStep<Section, Value>]) {
        guard let tableView = self.tableView else { return }
        tableView.beginUpdates()
        self._sectionedValues = newState
        for result in diff {
            switch result {
            case let .delete(section, row, _): tableView.deleteRows(at: [IndexPath(row: row, section: section)], with: self.deletionAnimation)
            case let .insert(section, row, _): tableView.insertRows(at: [IndexPath(row: row, section: section)], with: self.insertionAnimation)
            case let .sectionDelete(section, _): tableView.deleteSections(IndexSet(integer: section), with: self.deletionAnimation)
            case let .sectionInsert(section, _): tableView.insertSections(IndexSet(integer: section), with: self.insertionAnimation)
            }
        }
        tableView.endUpdates()
    }
}

Improving performance

Hi, I'm learning different diffing algorithms, and I would like to give them benchmarks. Here is my benchmark https://github.com/onmyway133/DeepDiff#among-different-frameworks. I'm running on real device iPhone 6.

With 2000 items and 100 deletions, 200 insertions, Dwifft runs in 150 seconds. If I increase number of items to 10000+ items, then it just hangs for over half an hour. The item is just UUID string, but in real scenarios, custom objects with complex Equatable will suffer from slow performance.

Do you plan to improve the performance?