enhance Tree support for filtering

[ktiedt]

Current grid implementation (including dojox/grid/TreeGrid) all rely on returned items always being topLevelItems that contain children. This poses a problem when you need to filter to display specific children of Tree items example:

A
--A1
----C1
----C2
--A2
----C1
----C2

If you want to search/filter for C2's existing grids require using deep:true which returns a flat result of 2 items... which the grids of course will now render as top level items (not correct)

What would be great, is if this would instead render A->A1->C2 + A->A2->C2 w/o the extraneous items --- This means modifying child arrays (typically) which gets tricky when any type of eventing mechanism comes into play

The other catch would be for complex queries C2 || A2 for example.... would now need to return A->A1->C2 A->A2->C1/C2 (because A2 was a filtered match)

I have previously implemented this my wrapping grid's call to _fetchItems, building a referenceMap of item->parentItem and then copying the children's array for parent items and modifying them as needed.... but this is obviously NOT the ideal solution (and also, not 100% effective) due to not responding well to other actions creating items and then modifying the modified children arrays and not the true array.

If any of this is too hard to follow please ping me and I'll do a more detailed (and better illustrated) example.

-Karl

[mikerobi]

I think I follow. You want a filtered tree to include all nodes which have descendants matching the filter.

That is how I would expected tree filtering to work. It would also be nice if a special class was added to the matched tree nodes, such as dgrid-tree-match.

I don't fully understand your workaround. I have not added filtering to my app yet, but this is something that I will need implement.

Have you tried collapsing non matched nodes, rather than applying a filter to the data store? This should be pretty easy (in theory) using post order tree traversal:

• visit a node
• if it does not match and all of its children are collapsed, collapse it.
• if it matches or has a non collapsed child, expand it
• repeat

When there is a data change, you do not need to walk the entire tree, you can start at the modified record and walk strait up.

As I said, this might work in theory, I will give you an update after I have tried it.

[mikerobi]

It turns out this is pretty easy to do by adding some logic to the store's query and getChildren functions.

Instead of query returning matched records, it need to return root level ancestors of the matched records. getChildren needs to filter out records that are not in the matched hierarchy. Last, you need a way to turn switch between normal behavior and filtered mode.

Here is a simple CoffeeScript example. for the Memory store.

If you need to do this for an async store you will need to implement a recursive query function.

[ktiedt]

I'm not familiar with the new Store's yet, do they not use models anymore? In dataStore's getChildren/mayHaveChildren etc was always part of the model, not the store... but your approach does sound valid...

Granted I dont read Coffeescript or have any utils to convert it, at least the description seems sound.

[mikerobi]

With the dgrid, the store is the model.

Here is an untested Javascript version of my example. I threw in some extra comments.

I am going to work on converting this into an a generic store wrapper similar to dojo.store.Observable.

[kriszyp]

I think you are on right path with nested querying in query() and in getChildren() (nested querying, not nested results). However, this solution relies on side-effect based queries (switching the store into a "filtered" mode), and the non-functinonal approach would break if you had multiple grid/trees using the same store. I believe to support this properly, the top level query needs to be passed to the getChildren function so it can utilize it as needed.

[mikerobi]

@kriszyp, your approach has an O(n^2) complexity. It will do a linear search for every record in the store. In your example, there is a noticeable delay when searching and when expanding a filtered row. My application has a much larger data set, and my implementation appears instantaneous.

The only efficient way to do this is to walk the tree from the bottom up. I do not think there is an easy way to solve the performance problem and the side effect problem, without adding a tree filter feature to the tree plugin.

It would also be nice to have a solution that efficiently work with synchronous and async stores.

I was hoping to avoid it, but I think the best solution is to add a getParents and or getParent method to the store. The tree plugin will use these methods to build it's own in memory representation of the tree. getParent would return the immediate parent and getParents would return the ancestral chain for a given record.

The advantage of getParents, is that all data needed to build the grid can be retrieved with a single ajax call. For a Memory store getParent would be better for its simplicity, but if I had to pick one, it would be getParents.

[kfranqueiro]

I agree that the earlier implementation proposed here seems overly complex. I've taken a shot at a simpler solution to this problem, which can now be seen in e345b81.

This solution involves having dgrid pass an originalQuery property to the options passed to getChildren, which includes the original top-level query used by the grid. This allows getChildren implementations to re-apply that query (e.g. mix it into its own query object) if desired. In particular, see e345b81#diff-1f6465b8f6ce01e30659f3b4fa0cf12eR215 for how the store handles this.

I'm closing this issue for now but if you have questions, feel free to ask.