Filtering contents of NSOutlineView

Question

I have set up an NSOutlineView with DataSource.

The data being fed to the NSOutlineView is basically a custom-node tree, with each node (let's call this PPDocument) featuring 2 basic properties (there are much more, but that's the essential part) :

• label (what is displayed)
• children (an array of children nodes)

When my Filter field (an NSSearchField actually) changes, I call for a reloadData on the Outline view.

So, I decided to plug the whole filtering into the datasource like this:

- (NSInteger)outlineView:(NSOutlineView *)outlineView numberOfChildrenOfItem:(PPDocument*)doc {
    if (doc==nil) return [[[[APP documentManager] documentTree] groups] count]; // Root
    else
    {
        if ([[[APP fileOutlineFilter] stringValue] isEqualToString:@""]) // Unfiltered
            return [doc noOfChildren];
        else
            return [doc noOfChildrenFiltered:[[APP fileOutlineFilter] stringValue]];
    }
}

- (id)outlineView:(NSOutlineView *)outlineView child:(NSInteger)index ofItem:(PPDocument*)doc {
    if (doc == nil) return [[[APP documentManager] documentTree] groups][index]; // Root
    else
    {
        if ([[[APP fileOutlineFilter] stringValue] isEqualToString:@""]) // Unfiltered
            return [doc childAtIndex:index];
        else
            return [doc childAtIndex:index filtered:[[APP fileOutlineFilter] stringValue]];
    }
}

And the 3 main "filtering" functions :

- (NSArray*)filteredChildren:(NSString*)filter
{
    NSMutableArray* ret = [[NSMutableArray alloc] initWithObjects: nil];

    if (([self.label contains:filter]) && ([self.children count]==0)) return @[self];

    for (PPDocument* d in _children)
    {
        NSArray* filtered = [d filteredChildren:filter];

        if ([filtered count]>0)
        {
            PPDocument* newDoc = [d copy];
            newDoc.children = [filtered mutableCopy];
            [ret addObject:newDoc];
        }
    }

    return ret;
}

- (NSInteger)noOfChildrenFiltered:(NSString*)filter
{
    NSArray* filtered = [self filteredChildren:filter];

    return [filtered count];
}

- (PPDocument*)childAtIndex:(NSInteger)index filtered:(NSString*)filter {
    NSArray* filtered = [self filteredChildren:filter];

    return (PPDocument*)(filtered[index]);
}

However, it doesn't seem to be working right (+ the isGroupItem: function suddenly started throwing EXC_BAD_ACCESS errors).

Any ideas? Is there any obvious error you notice?

Answer 1

Your -filteredChildren: method doesn't seem right to me.

First, it should never return itself as one of its children (filtered or not). It also doesn't seem like it should be making copies of the children nodes.

I think this should work:

- (NSArray*)filteredChildren:(NSString*)filter
{
    NSIndexSet* indexes = [_children indexesOfObjectsPassingTest:BOOL ^(PPDocument* child, NSUInteger idx, BOOL *stop){
        if (child.children.count)
            return [[child filteredChildren:filter] count] > 0;
        return [child.label contains:filter];
    }];
    return [_children objectsAtIndexes:indexes];
}

The problem with this approach, though, is that you're building the list of filtered children for every query of an item. NSOutlineView warns that the data source methods will be called frequently and must be efficient. For example, it asks the number of children of an item and you construct the array of filtered children, which necessitates building the array of the filtered children of those children, etc., in order to determine if a child should be present because it has children that survive filtering. Then it asks how many children one of those children has, and you have to rebuild that entire subtree.

When I have done this, I have my node class track both the children and the filtered children in persistent arrays. Each node also has to track the current filter.

One approach is to keep them always in sync. Any change made to the children array needs to be reflected in the filtered children, too. That is, if you add a child and it passes the filter, you add it to the filtered children in the corresponding position. If you remove a child, it needs to be removed from the filtered children array, too.

Another approach is to treat the filtered children array as a cache. Any modification of the child array invalidates that cache. Any time the filtered children array is requested, it is recomputed if it's invalid.

Either way, when a node detects that its filtered children array has changed or may have changed (i.e. the cache has been invalidated) from being empty to non-empty or vice versa, it needs to inform its parent. That's because its emptiness affects whether the parent keeps it in the parent's filtered children list.

In the first approach where the filtered children array is constantly maintained, you need a method to set the filter. That should both update the filtered children of the current node and also pass the new filter down to all the children. In the second approach, the last-used filter is part of the cache. You test if the filter has changed when the filtered children array is requested. If it has, then that's the equivalent of the cache having been invalidated, so you recompute it.