batmanjs/batman — pull request #774 by pushrax (2013-07-18 20:52:09+00:00)
Title: Smarter sorted sets and iterator binding, part 1

First, these changes were made:

- Event emitters that fire `itemsWereAdded` and `itemsWereRemoved` (i.e. sets and hashes) have `isCollectionEventEmitter` set on them to differentiate
- Sets have `insert` and `at` methods (gross, but it needs to stay until we refactor sets to become lists/vectors)
- Sorted sets fire `itemWasMoved` when an item's sort value is changed
- Various other sorted set refactorings

These changes allow for optimizations to sorted sets:

- Adding N items to a sorted set of length M causes them to be inserted with O(N log M) efficiency
- Removing N items from a set of length M is also O(N log M)
- Changing an element's sort value in a set of length M causes it to be resorted in O(log M)
- Determining the index of an item in a set of length M is O(log M)

Doing these explicit sort operations results in having a record of which indexes were moved where, allowing for these optimizations to iterator bindings:

- Adding items to any set causes nodes for just those items to be built within a document fragment, and then moved into place. If the set is sorted, the nodes are moved into sorted order.
- Removing items from any set causes their nodes to just be deleted.
- Reordering a sorted set by changing an element's sorted value just moves nodes into the correct position.

Still to do:

- Another algorithm for speeding up mass reordering was written, but it's a bit contrived and I'll be including it in another pull request. It's the one that uses a longest increasing subsequence algorithm to determine the diff between the sorted and unsorted sets, to determine the minimum operations to update the DOM.
- Real benchmarks.
- Decide on the heuristic to use in `SetSort::_handleItemsAdded`. This is going to be entirely dependent on benchmarks, since the native JS sort function is going to be faster at some point just due to it being native (my initial guess is commented in this PR for reference).

Did some of this with @xthexder, and some with @jahfer.
@nickjs @kristianpd @SoapyIllusions for an initial review

This should be a fix for #762