Add support of filters/projections for observableArrays

[SteveSanderson]

A common scenario where experience from usage of KnockoutJS can be improved is having an observableArray of elements that is not binded directly to HTML, but first projected to a set different items, or filtered by a condition.

Would be great to have something similar to:

var array = ko.observableArray([]);
var filtered = array.filter(function(item) { /* condition / });
var projection = array.select(function(item) { / selector */ });

Right now you can achieve this by using a computed observable, but this will mean that every item of resulting array will be tested against condition/selector if any item of initial collection changes, and thus whole array will be rebound, that is not effective in terms of performance.
The fact of recreation is itself crucial as it may result in the loss of state for items that were recreated, in the case it was a projection.

[SteveSanderson]

Interesting idea. I like it.

Technically you could already do it with a computed property, by using ko.utils.compareArrays to identify what has changed in the input array, and then modify the output array correspondingly. But it's not trivial or obvious, so it's a good candidate for a feature we could consider adding to the library.

[tedsteen]

+1 :)

[SteveSanderson]

Just a few notes for myself whenever I next think about this:

• A more general way of achieving this (instead of using compareArrays) would be to enhance observable arrays generally to issue "added", "deleted", and "moved" callbacks (this could be done with the existing subscribe(event) API).
  • In the first instance, this could use compareArrays internally. A future enhancement might be to intercept push, pop, shift (etc) to bypass the compareArrays operation, since we can know in advance what the diff will be.
• Once observable arrays support this, we could implement filter and map by listening for the added/deleted/moved events, then it wouldn't even involve an array diff in simple push, pop (etc) cases
• Then, we could think of arrayMappingToDomNodeChildren as just a special case of map since that is really what it is. This would eliminate most of the logic from there.

[rniemeyer]

@SteveSanderson - Ideally this would be opt-in or we would recognize that there is someone interested in the callback to avoid unnecessary calculations. If it was built into push, pop, etc., then maybe it would be somewhat less of a concern,

[mbest]

Good ideas here. I have been working on some of these in my Knockout fork. I already have it set up to post added and deleted notifications, and only when there is a subscription for them.

Regarding arrayMappingToDomNodeChildren, since it also supports plain arrays, it might be better to just leave it.

[estrizhok]

Steve, I can provide you with a working code that adds an event system you were talking about in the comment above by intercepting every standard method of array. It is based on MicrosoftAjax library, but still may be worth looking at.
I also have a filtered view implementation that uses that event system.
But I have no idea how to integrate it into KnockoutJS.

P.S. By saying 'based on MicrosoftAjax' I mean uses its naming convention and event system (addHandler).

[SteveSanderson]

Thanks! I think the implementation would be straightforward enough; it's just a matter of scheduling it alongside other priorities.

[mariusGundersen]

What is the status of this? How is it prioritized @SteveSanderson, and have you got it to work @mbest? I feel this would improve the code for simple observableArray operations, and it would be a performance improvement over plain computed, which have to recompute the entire array if only one part of it changes.

[tedsteen]

A knockout plugin that adds underscore or lodash Collection API to the observableArray would be a nice match IMO

[SteveSanderson]

OK, I've started working on this. The overall plan I have in mind is:

1. Make observable arrays smarter about diffs
   • When they change, make them able to tell you what changed
   • Possibly also allow you to register callbacks that fire when items are added or removed. Of course you could achieve this anyway by walking the changelists, but this will be more convenient in many cases.
2. Boost performance by recognizing known operations and using sparse diffs
   • If you're calling push, splice, etc., we can prepare a diff log without needing to use our differencing algorithm at all. To reduce all this to an O(1) operation, we should return sparse diffs that are the same as regular diff logs except without any { status: 'retained' } entries.
   • So, if you call myArray.push(someValue), the diff log is just [{ status: 'added', value: someValue, index: x }], and we don't need the differencing algorithm to determine that
3. PLUGIN: Build a plugin that provides efficient .map and .filter for observable arrays. I already have an implementation that minimises the number of map/filter callbacks (only called once per item ever, plus again when that item changes observably, etc.). It also provides an observable index to your map callback. It can build on the sparse diffs feature to reduce the amount of array walking.
4. FUTURE: Consider merging the map/filter plugin into KO core, as we might be able to greatly simplify arrayToDomNodeChildren and other features in terms of it.

Proposed APIs

I'd appreciate any feedback on these designs:

• someArray.trackDiffs() enables diff tracking on an observable array. It means it maintains a snapshot of current contents so that, on each change, it's possible to produce a diff.
  • Calling trackDiffs multiple times on the same object is allowed (and makes no difference) so any code that wants to use these diffs can safely call it.
  • You can also supply callbacks (someArray.trackDiffs({ add: ..., remove: ... })) if you want to work in terms of individual item additions and removals rather than diff logs. That will be more convenient for many developers.
• someArray.getDiff() returns a sparse diff log to describe the current change on that observable array
  • This is only applicable while an array mutation is in progress, i.e., during a .subscribe(...) callback or during the evaluation of a computed property that depends on someArray. We erase the diff log at the end of valueHasMutated so any removed objects can be GCed, so calling it at other times returns an empty diff log ([]).
  • The sparse diff log is calculated lazily and cached until the end of the current valueHasMutated process, so there's no perf cost to code that doesn't use this.
  • If the mutation was a known operation like push etc., the sparse diff log is prebuilt in O(1) time without using the differencing algorithm. But if it was an unknown operation, or you just replaced the array contents completely, then we have no choice but to use the diff algorithm to satify getDiff calls (the result is still cached, though).

Example usage:

    someArray.trackDiffs();
    someArray.subscribe(function(items) {
        var diffs = someArray.getDiff(); // Usually done in O(1)
        // Now do something with the diff log
    });

Or:

    someArray.trackDiffs();
    ko.computed(function() {
        var diffs = someArray.getDiff(); // Usually done in O(1). On first run returns empty array as there were no changes
        // Now do something with the diff log
    });

Or:

    someArray.trackDiffs({
        add: function(item, newIndex) {
             // Do stuff with item
        },
        remove: function(item, oldIndex) {
             // Do stuff with item
        }
    });

As for the map/filter plugin, the APIs are pretty obvious:

• someArray.map(function(item) { return transform(item) }) returns an observable containing an array representing the transformed version of each item
  • If you add new items, we map then and update the output, without remapping any existing items
  • If you remove items, we remove them from the output without any remapping
  • If you move items, we move them in the output without any remapping
  • If your transform code refers to observables on each item, then we auto-update the output when those observables change.
• someArray.filter(function(item) { return predicate(item) }) returns an observable containing an array containing a subset of the input items, i.e., those for which your callback returns a trueish value.
  • If you add new items, we apply the filter and possibly add them to the output, without refiltering any existing items
  • If you remove items, we remove them from the output without any refiltering
  • If you move items and they are included in the output, we move them in the output without any refiltering
  • If your filter callback refers to observables on each item, then we auto-update the filter result when those observables change (possibly adding or removing the item in the output)
• You can chain as many map and filter calls as you like, because they return objects that have map and filter functions (but not other observable array functions like push, etc., because the output is readonly - it's effectively a computed observable)

Does this sound good? I'll submit a pull request that implements this soon.

[thelinuxlich]

+1 for this!

[mbest]

@SteveSanderson I'll look over your very detailed description soon. In the meantime, I want to share the work I did on this: https://github.com/mbest/knockout/compare/array-change-tracking

[NikGovorov]

@SteveSanderson, @mbest it would be great to support custom comparison function, as mentioned here #937, what do you think?

[rniemeyer]

Minor feedback that I have on this design:

• I think that it would be nice to fit the add/remove/etc. callbacks in by optionally allowing the ability to subscribe to an observableArray on a corresponding topic (like the current beforeChange subscriptions).
• As far as naming goes, I feel that diffs feel a bit foreign in this type of API. Maybe just trackChanges and getChanges?

[gvas]

map() and filter() should also have an optional second argument which would be used as the this value for the callback function. The Array's prototype object in ES5 also supports that argument for its map() and filter() methods, it would be easier to remember only one signature.

[mbest]

We should also export the computedArray class that's used for the return value of map and filter. I personally would find that useful by itself.

[mariusGundersen]

I want to add reduce and reduceRight to the list of built in functions. With reduce you don't need to recalculate all the items when a new item is pushed to the end of the array: only the last item needs to be run through the reduce function with the original array as the other input argument. The same would be true for reduceRight, but when an item is shifted onto the front of the array.

[SteveSanderson]

Thanks for all the feedback!

Ryan - agreed - have used those names.

Michael - thanks for pointing me to your take on this. I've taken a bunch of your ideas from that code and adapted the APIs a bit to produce what I hope has a few extra advantages. Then I built sparse diffing on top of that. In particular the differences are:

• Since it's only really clear what changes we're talking about during a mutation, my updated API ensures you can only ask about changes during a mutation. This also avoids the oddness of saying that all items are 'added' if you ask about changes before there were any - now a diff can only be obtained in response to a change, so always contains the change description you'd expect.
• This also has the significant benefit that there's no need to retain change lists in memory indefinitely, so now the GC can reclaim objects that were removed from the array immediately, instead of having to wait until the next mutation when the changelist is changed.
• It's not necessary to make many changes to observableArray.js or compareArrays.js, because the additional features can be layered on from an external file
• The use of sparse diffs means we can compute changelists in O(1) for known operations. It also largely takes care of the "I only want to know about added/deleted items" use case in that when walking a sparse changelist you only encounter modified items. However if we feel there's a strong case for an explicit "just tell me about added items" API then we could add that easily.

Now with all this, I've also built a plugin called knockout.projections.js (not included in this pull request) which implements fast map/filter functionality (fast in the sense that it updates the output in O(1) in many cases, thanks to the sparse diffs). I'm entirely open to baking this into KO core, but maybe we should let the community play with it as a plugin first. Any thoughts on that?

map() and filter() should also have an optional second argument which would be used as the this value for the callback function

Good point - we can ensure that is the case.

I want to add reduce and reduceRight to the list of built in functions.

I'll check out how much extra code this adds to knockout.projections.js and either implement it there, or provide a suggestion on how the sparse diff feature makes it very cheap to implement this.

[SteveSanderson]

Actually, after further consideration, I'm wondering if Michael's "subscribe"-based API for receiving array changes might be a bit cleaner and more consistent with our other patterns. It eliminates both trackChanges and getChanges, and means you can no longer get into the erroneous situation of asking for changes on an array that isn't tracking them.

I've added a further commit that means this pull request now follows that API pattern. Usage:

myArray.subscribe(function(changes) { /* ... */ }, target, 'arrayChange');

One slight drawback is that it isn't so obvious how to get the current array contents inside your subscription callback. The way to do it of course is just to evaluate myArray(), but arguably it's not totally obvious.

On balance I suspect this is better than the trackChanges/getChanges approach because there's no longer any need to explain that you can only call getChanges from inside a subscribe callback, and after you have already called trackChanges. That was all kind of weird.

Now, this is a fairly low-level API that we probably wouldn't expect most developers to use anyway. The primary use case is really to enable "projections"-type plugins and possibly also for internal use inside KO. If it turns out that developers do use this a lot, we could consider adding a myArray.subscribeArrayChanges(function() { }) shorthand helper, just so you don't have to pass three params to myArray.subscribe. No need to do that right now though.

[rniemeyer]

I prefer the subscribe based API, as it fits nicely with our existing functionality.

[evanworley]

A massive +1 for this feature in general, my use of observable arrays is falling down due to compareArrays and arrayMappingToDomNodeChildren grinding to a halt when my observable array grows to thousands of elements.

Also I'd prefer the subscribe approach. I think the natural array methods such as push, and splice should get the benefits of understanding the details of the change to the array.

[SteveSanderson]

This is excellent - thanks very much Michael! These are really great improvements.

[milutinovici]

This looks fantastic. I use map/filter/reduce extensively, and think that it should be added to the core as soon as possible. Please consider adding 'some/every' method as well.

[lovedota]

Hi
If the some item in the ObservableArray is Observable, can ObservableArray track these item if they are changed.
I am working with JQGrid CustomBindings and using MBest function to do with this. If we can get the changed items, it will be good to use $element.setRowData(value[rowId], itemObjectChange); in JQGrid.
bindingAttributes.dataSource.subscribeArrayChanged(
function (value) { //Add New Item
//var index = ko.utils.arrayIndexOf(viewModelData, newValue);
$element.addRowData(value[rowId], ko.unwrap(value));
},
function (value) { //Remove New Item
$element.delRowData(value[rowId]);
if ($selectAllCheckBox.is(":checked") && dataSource().length === 0) {
$selectAllCheckBox.removeAttr("checked");
}
},
//NEED a callback to check if some item with Observable Property has changed
);

[brigand]

@lovedota please use formatting and indentation. It makes everything a lot easier to read.

---

Hi
If the some item in the ObservableArray is Observable, can ObservableArray track these item if they are changed.

I am working with JQGrid CustomBindings and using MBest function to do with this. If we can get the changed items, it will be good to use $element.setRowData(value[rowId], itemObjectChange); in bindingAttributes.dataSource.subscribeArrayChanged

bindingAttributes.dataSource.subscribeArrayChanged(

function (value) { //Add New Item
    $element.addRowData(value[rowId], ko.unwrap(value));
},

function (value) { //Remove New Item
    $element.delRowData(value[rowId]);
    if ($selectAllCheckBox.is(":checked") && dataSource().length === 0) {
        $selectAllCheckBox.removeAttr("checked");
    }
},
//NEED a callback to check if some item with Observable Property has changed 
);

[cryo-warden]

The arrayChange subscription functionality has allowed us to implement a two-way-binding mapBind(mapFn, inverseMapFn) method, similar to map, which allows its return value (a ko.observableArray) to be modified and to propagate changes back to the source ko.observableArray, using the inverseMapFn to determine the correct value to add into the source array.

So we can do this:

var a = ko.observableArray([1, 2, 3]);
var b = a.mapBind(function (x) {
    return x * 10;
}, function (y) {
    return y / 10;
});

// b is an observableArray with value [10, 20, 30]

b.push(40, 50, 60);

// a now contains [1, 2, 3, 4, 5, 6]

a.push(7, 8, 9);

// b now contains [10, 20, 30, 40, 50, 60, 70, 80, 90]

It also works with arrays containing objects, with some caveats. You shouldn't rely on mapFn returning two equal values for the same input value if you're creating a new object as your return value, of course. Nothing really surprising though.

[casdevs]

+1 for this feature, missed it a lot until now!

@SteveSanderson: on your blog, you stated 'Coming soon: A powerful new plugin, built using arrayChange, for efficiently processing chains of maps and filters on observable arrays. Just as soon as I get permission to publish it :)'

Is there any chance to get knockout.projections.js and test this plugin at the moment, or can you estimate how long it will take until it will be published?

[casdevs]

does anyone know when the mentioned knockout.projections.js plugin will be released? Steven seems too busy to answer my question at the moment, and I need the functionality of projected/efficiently filtered computed arrays very soon, otherwise I have to develop something for myself. Are there any problems with the plugin I could help solving (testing, API discussion etc.)?
Thanks and with regards,
Stefan

[tedsteen]

I'm also eagerly waiting for this feature

[mbest]

I don't know any more than you.

[SteveSanderson]

Hey, sorry for the lack of responsiveness since v3.0.0 was released! My wife gave birth last week, so as you can guess I'm off work and pretty focused on home stuff right now and for the next week or so.

There have been a few emails flying round in my team trying to confirm it's all clear to publish knockout.projections (which is fully built, tested, and ready to go, and works really nicely!) to GitHub. I don't anticipate any problem with going ahead with open-sourcing it, so hopefully by the time I'm back at work the lawyers will have given approval.

[casdevs]

Steven, thank you very much for explaining the status of the plugin. Looking forward to see it on github in the near future.
And of course, congratulations on the arrival of your baby child - I wish you all the best with your new family member!

[mbest]

@SteveSanderson, congratulations. Your wife needs the rest, so it's great you're taking the time off.

[SteveSanderson]

I got the all-clear to publish knockout-projections :) See https://github.com/SteveSanderson/knockout-projections/

I'll write a more detailed blog post when I get a chance, but for now, those of you who've been keen to try this out will be able to make sense of it. Let me know if you have questions, and especially if you discover any issues!

Thanks.

[milutinovici]

Nice one Steve, will try it out.

[casdevs]

thanks Steve, I'm looking forward to trying this out.

[evanworley]

@SteveSanderson - Thank you for this! Does this rely on knockout 3.0.0's arrayChange functionality, for the "efficient" part? It looks like it does from the source, so perhaps you should add that to the README?

[SteveSanderson]

Evan - yes it does.

On Tuesday, November 26, 2013, Evan Worley wrote:

@SteveSanderson https://github.com/SteveSanderson - Thank you for this!
Does this rely on knockout 3.0.0's arrayChange functionality, for the
"efficient" part?

—
Reply to this email directly or view it on GitHubhttps://github.com//pull/695#issuecomment-29319087
.

[jgoodsen]

This looks hellasweet! Can't wait to go refactor some of that logic out of my app code now!

[rosieks]

@SteveSanderson, @mbest - could you add links to knockout-projections, knockout-es5 and knockout.punches to plugin section on knockoutjs.com?

[ghost]

@coryandrew1988 - you mentioned a mapBind(mapFn, inverseMapFn) that you were able to build off this. Is this code available anywhere? Seems like a useful addition to knockout-projections.

(Overall, I am hoping that this will be useful for <select multiple> binding scenarios against many-to-many data models.)

[cryo-warden]

@MrAndMrsK Sorry for the late response. The code (written years ago, so it might need some updates) can be found here.

[JasonKleban]

@coryandrew1988 Thanks! (from MrAndMrsK)