Design pattern for filtering a collection of items?

Question

Imagine the typical type of application where you have a list of items with different properties. E.g. a tree-view with 100 items, each having a name, a rating, a rank-within-the-hottest-items-on-the-planet etc. Probably there are also many-to-many relationships between items and item-catalogs, or between items and item-creators etc etc.

Now this application naturally needs a filtering system. E.g. where I can construct complex filters with multiple conditions of all kinds, between data in different relationships.

The design task of writing such a filtering feature ought to be something MANY developers have done and there surely must be some kind of design pattern which is the most suitable for the task.

Anyone?

Edit: Switched to community wiki since I suspect there isn't any industry de factor pattern used for this. Question too generally formulated I guess.

Answer 1

It's a bit difficult to actually point out what you want, so I'll take my own assumptions.

1. The underlying collection should be unchanged after the filtering
2. The result is not persistent

A classic approach is the use of views. This is basically lazy programming, where you create an object which can access the original collection and knows the filter to apply but will not make any computation as long as nothing is required.

On collections, the views are often implemented with iterators, and for the filtering, of course a Strategy Pattern as already pointed out.

For example:

Collection myCollection;
Predicate myFilter;

// Nothing is computed here
View<Predicate> myView(myCollection, myFilter);

// We iterate until we find the first item in the collection that satisfies
// the Predicate, and no more, to initialize `begin`
View<Predicate>::Iterator begin = myView.begin(), end = myView.end();

The net advantage is that if you (say) only need the 10 first items, then you'll only apply the predicate as much as necessary to find those 10 first, and no more.

Also, there is no copy of the elements involved, and your view is guaranteed to be updated even if you modify myCollection, although this may affect the validity of the iterators (as usual).

The problem is that (unless you implement caching), the result is computed each time.

If you want a more persistent result, then you'd better build a new collection containing only the filtered items (or references to them). There is no general pattern here for it depends on how you want to use the 'filtered' list.

As for the Strategy Pattern suggested, you can usually build your filter by block using the Composite Pattern and then pass the object thus built as the strategy.

The Composite Pattern is especially suited to represent the result of a parsed expression for example, you might want to have a look at expressions trees to get an idea.