jamesarosen/ember-cpm — pull request #28 by cibernox (2014-04-14 10:11:57+00:00)
Title: [WIP] New arrayComputed "inRange" && plan to create a bound filter CP

This is a work in progress, but I want to place it here because is a pretty complex goal and I would like to ear opinions, specially about naming or signature of the methods.

Recently in my job I solved a performance problem building a complex `arrayComputed` CP. I had a collection of transactions, ordered by date, and I wanted to be able to filter which of those transactions are within a time frame selected by the user.

`Ember.computed.filter` was not enough because my time window is bound. Ember's arrayComputed properties that have as dependencies other keys beyond its `dependentKey` are completely recalculated when those properties change, and that was a absolute performance killer because I had other CPs watching changes on this one, an others on them, until everything ends in a D3 chart :bomb: :gun: :fire: :fire_engine:

I solved the problem `Ember.computed.sort` as inspiration I build a CP that sets some observers on the property names that define the bounds of the range, and each time the bounds change I reevaluate things to add/remove elements one-at-a-time. Worked like a charm.

My initial solution had a flaw. It only works if the array inside `dependentKey` was already sorted, so this PR is an attempt to generalize this solution. I also included an option to consider the range exclusive and another to filter by the element itself rather than by a property.

Examples:

```js
// Filter by the object itself. Using '@this' as keyword.
//
var Obj = Ember.Object.extend({
selection: EmberCPM.Macros.inRange('objects', '@this', 'rangeStart', 'rangeEnd')
});

var obj = Obj.create({
objects: Ember.A([1,4,7,2,8,7,3,6,9,8,2,5,2]),
rangeStart: 3,
rangeEnd: 7
});

// Filter by a property in the object. Pass the property's name in the 2nd argument.
//
var Obj = Ember.Object.extend({
selection: EmberCPM.Macros.inRange('objects', 'num', 'rangeStart', 'rangeEnd')
});

var obj = Obj.create({
objects: Ember.A([
{num: 1, index: 0},
{num: 4, index: 1},
{num: 7, index: 2},
{num: 2, index: 3},
{num: 8, index: 4},
{num: 7, index: 5},
{num: 3, index: 6},
{num: 6, index: 7},
{num: 9, index: 8},
{num: 8, index: 9},
{num: 2, index: 10},
{num: 5, index: 11},
{num: 2, index: 12}
]),
rangeStart: 3,
rangeEnd: 7
});
```

It adds/removes items and and reacts to changes in the bounds of the range perfectly, but there is a lot of room for improvement in the algorithm. I've already designed a solution that stores an array in the instanceMeta that works as a bitmap to optimize things.

But then I realized that what **I was writing was a specific case of a more generic problem**: Having filters that react to changes in other secondary properties without recompute the whole CP.

So, now I am changing my approach to a more ambitious goal:

I'm creating `Ember.computed.boundFilter` CP that reacts to changes in other properties. The name `boundFilter` maybe is not the best.

Possible signatures:

1. `Ember.computed.boundFilter(dependentKey, filterFunction, otherKey1, otherKey2, ...)`
It is nice because is backwards compatible with `Ember.computed.filter`, and maybe it could be accepted in ember's core by that reason.

2. `Ember.computed.boundFilter(dependentKey, otherKey1, otherKey2, ..., filterFunction)`
Its nice because it reads better. It might be backwards compatible if somehow I manage to read the size of the arguments and take decisions based on that.

Algorithm basics:

1. `initialize` function creates an array of rejected elements in the instanceMeta.
2. Each time a item is added, it passes through the `filterFunction`. If satisfies the filter function it makes it into the CP. It it doesn't, it is added in the array of rejectedElements
3. Each time an item is removed, it is removed from that `rejectedElements` as well if necessary.
4. Changes in the keys other than the `dependentKey` makes to check which elements of the `rejectedElements` now satisfy the `filterFunction` and which elements of the array do not satisfy it anymore.
5. The order of the elements is preserved. This means that if the source array contains `[1,7,2,9,5,2,8,2,9]` and we filter elements bigger than 4 the resultant array needs to be `[7,9,5,8,9]`

So, in a nutshell, my plan is:

1. Write a `boundFilter` arrayComputed property that handles changes in keys other than its `dependentKey` with one-at-a-time semantics.
2. Rewrite my `inRange` CP to use internally the `boundFilter` property.
3. See how easy is to optimize my `inRange` CP for cases where you know in advance that the source array is sorted, which is a common use case, and allows to perform a much lighter computation.
4. My intuition says that in order to make 3, I'll need to extract another very basic (and probably private) CP, maybe called `_baseBoundFilter`, and use implement `boundFilter`/`inRange` using that primitive. Maybe it could end being a `_boundArrayComputed`. If it is generic enough, but that would need a lot of work and review by the people in ember's core that are more expert than me in CP's.

There is still a lot of work to do here, but I prefer to make it public now.
Do not pay much attention to current implementation. Ignore comments in spanish too :sweat_smile: