Skip to main content

Add Filter interface to java.util

37 replies [Last post]
roytmana
Offline
Joined: 2003-06-29

Please add a simple Filter interface to java.util and filtering method to Collection class

It is one of those simple universally useful interfaces like Comparable which really should be in java.utils
As it is people just keep creating in in every project or framework

public interface Filter {
public boolean test(T testObject);
}

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
jessewilson
Offline
Joined: 2003-06-14

Filtering in batch like this is useful in a lot of cases. But another approach is to create a 'live' filter of the collection. This way, when the original collection changes, the filtered collection changes to match.

Glazed Lists does this for Lists. So you can do something like this:
[code]
EventList original = new BasicEventList();
original.add("A");
original.add("B");
original.add("C");

FilterList noVowels = new NoVowelsFilterList(original);
/* noVowels now contains { "B", "C" } */

original.add("D");
original.add("E");
/* noVowels now contains { "B", "C", "D" } */
[/code]
Of course, I'm biased to think this is great because I'm a Glazed Lists developer.
http://www.publicobject.com/glazedlists/

kcpeppe
Offline
Joined: 2003-06-15

> This would be a nice addition.
>
> ----------------------------------
> [b]package java.util;
>
> public interface Filter {
> public boolean accept( T t );
> }[/b]
> ----------------------------------
> * Addition to java.util.Collections
>
> [b]public void filterList( java.util.List,
> java.util.Filter );[/b]
>
> Remove items that do not match the filter
>
> [b]public java.util.Collection filter(
> java.util.Collection, java.util.Filter )[/b]
>
> Return a new Collection containing only items that
> match the filter.
>
> [b]public java.util.Iterator iterator(
> java.util.Collection, java.util.Filter );[/b]
>
> Iterate only accepted items.

Interesting... but why pass in the collections?

On iteration, IME, it is typical that one takes an object out of a collection (using an iterator) and then may or may not apply some homogenous process to it depending upon some interal state. Why not just pass this processing and have the collection apply it? I guess what I'm saying is... this is a good start on working towards the arguement fo closures..

Slightly different topic but non the less related.

viper_wolf
Offline
Joined: 2004-06-03

My first thought on the itterator was to modify the Collection interface to add iterator( Fitler ). But then that would effect pre existing classes using the interface. So I moved the iterator to Collections.

However, it is defenatly not needed. By simply adding the method

[b]Collection filter( Collection, Filter )[/b]

would allow coding a filtered iterator with

[b]Collections.filter( object, filter ).iterator( )[/b]

The iterator method was added stricktly for the convenience of the developer. Since the addition of a Filter interface would be for convenience, I figured it was worth including the iterator method as well.

tsinger
Offline
Joined: 2003-06-10

Adding new methods
[code]public class Collections {
public static List filteredList(List originalList, Filter filter) {
/* ... */
}
public static Set filteredSet(Set originalSet, Filter filter) {
/* ... */
}
}[/code]
would be the most intuitive solution.

Tom

dgreenbean
Offline
Joined: 2003-12-08

> Is it good software engineering to have the container
> held responsible for the addition of items outside
> its interface?

The example I gave above for the list of positive Integers was just an example for using Filter. You are probably right about doing this with a PositiveInteger class. So, in creating such a class, it might make sense to write (will not actually work):
[code]public class FilteredInteger extends Integer implements Filter {
public boolean filter(Integer i) {
return true;
}
public FilteredInteger(int i) {
super(i);
if (!filter(this))
throw new NumberFormatException("foo");
}
public FilteredInteger(String s) {
super(s);
if (!filter(this))
throw new NumberFormatException("foo");
}
}[/code]
This way, defining a positive Integer can be done either as a public subclass of FilteredInteger or as an anonymous subclass of it for temporary use. What is great about the Filter interface is that it has so many uses. You can also use Filters as you suggested before:
[code]Filter f = new Filter() {
public boolean filter(Integer i) {
return i.intValue >= 0;
}
};
List lst = ...; // some list of integers
List pos = new ArrayList;
for (Integer i : lst) if (filter(i)) pos.add(i); else ;[/code]
The point I am getting at is that both of these approaches are equally valid. The former is very extensible and great for abstractions. The latter is extremely useful for manipulating complex data sets and rules for extracting that data.

As far as limiting what goes into a Collection, the Sets already will only store unique data as part of their definition. This is a constraint that is not dependant on the data itself, but rather how the data relates to the other data contained in the Collection. Similarly, you could say that you want to constrain a list so that you cannot add any number more than twice the highest number already in the list:
[code]public class WeirdList extends FilteredArrayList {
int max = Integer.MIN_VALUE;
public boolean filter(Integer i) {
if (i.intValue() > max * 2) return false;
if (i.intValue() > max) max = i.intValue();
return true;
}
}[/code]
Properly abstracted, this is an example of something someone may actually need to do, and it cannot be done simply by restricting the datatype. It can be done afterwards by using the class method, but that would potentially mean iterating over millions of unneccessary elements millions of times (~10^12+ operations that can be avoided). I am exaggerating a bit, but the fact is that a class method is useful for some cases, and a separate WierdList class is necessary for others. In addition, this is yet another way that Filter can be used.

To reiterate, all of these uses are valid in different contexts, and they all use the same Filter interface.

dwdunham
Offline
Joined: 2010-10-07

In addition to hasNext(), you'll also have problems with remove(). If you advance the wrapped iterator to see if additional matches exist, that iterator will no longer point at the last item returned by next(). That means your remove() would have to something other than simply delegate to the wrapped iterator's remove().

dgreenbean
Offline
Joined: 2003-12-08

I don't think that:
[code]public interface Filterable {
public boolean filter(T t);
}[/code] Will clutter the API any more than the 3 implementations of every type of Collection. I personally will rarely, if ever, use half of the Collections, but I am glad that they are available in case I ever do need them.

The Filterable interface (or with some other name) seems to be a very welcome addition by those who have posted examples of how they would use it. Moreover, everyone's example so far can make use of this interface in their context. Assuming this is generally true for most programmers requiring this functionality (yet to be determined), the addition is an appropriate abstraction of the problem at hand.

The question really should be: Can anyone think of an example of a way they would want to filter information that would not be possible using this interface?

mgrev
Offline
Joined: 2003-08-12

Gili, look at it from this angle instead. It's like the Comparator interface, but filters out/in something rather than to specify some order of things as a Comparator does.

For instance a Filter can specify what objects should be in/not in a list just as a Comparator would make it possible to sort that list.

Without a Comparator interface you would have to subclass everything you wanted to sort, today you have to subclass it to filter out/in stuff, which is not supported sometimes.

Another angle: It's aggregation of logic rather than imposing logic via inheritance.

And we are talking a few bytes when it comes to how much it will bloat the download/API...

Cheers,
Mikael Grev

roytmana
Offline
Joined: 2003-06-29

Collections or not this interface is useful for any situation where you need to delegate decision making to something. Whether it is for collection filtering or any other conditional logic. If Comparable is part of java.utils I do not see why Filter (or whatever name you like) should not be.

Filtered collections wrappers are not trivial (performance) I would be happy with
static Collection Collections.filter(Collection c)
to begin with

roytmana
Offline
Joined: 2003-06-29

sorry hit post too soon

I meant

class Collections {

public static Collection filter(Collection, Filter)

public static Iterator filter(Iterator, Filter)
}

retain() and remove() methods would be nice too plus

david_hall
Offline
Joined: 2003-06-12

As someone else pointed out, there are already third party libraries that contain this functionality. Of these, jga supports generics already.

You might be interested in this:

http://jga.sf.net/docs/AddingAlgorithms.shtml

which documents how to use the jga algorithms and functors with the 1.5 forloop syntax.

Dave Hall
http://jga.sf.net
http://jroller.com/page/dhall

dgreenbean
Offline
Joined: 2003-12-08

> As someone else pointed out, there are already third
> party libraries that contain this functionality.

I guess the question here is whether it makes sense to have this in the standard library instead of a third party library. I would propose that it would only make sense to have the functionality in the standard library if it would make sense to define portions of the standard library using the functionality. In other words: Does anyone know if the implementation of the standard library uses a Filter-like design anywhere?

> http://jga.sf.net/docs/AddingAlgorithms.shtml

Thanks for the pointer. This does look like a very good solution to this and other problems. It is fairly lightweight, but provides a host of functions for this sort of thing. Pending whether anyone has a response to my question above, I would venture that this library is all I would need for any of my programs.

viper_wolf
Offline
Joined: 2004-06-03

> In other words: Does anyone know if the implementation
> of the standard library uses a Filter-like design
> anywhere?

Yes, in the IO package they use filters. The filters there are extremly specific, one in the util would be very generic.

[b]java.io.FileFitler[/b]

[b]java.io.FilenameFitler[/b]

Are both used by the File class for filtering the list of child files it returns. Could even replace java.io.FileFilter with a java.util.Filter.

[b]java.io.File.listFiles( java.util.Filter )[/b]

could easily work to provide more functinality to a new java.util.Filter interface but would not be required.

wingetr
Offline
Joined: 2004-01-19

To keep backward compatibility, have the following definitions:
[code]
package java.util;

public interface Filter
{
public boolean accept(T object);
}
[/code]
[code]
package java.io;

public interface FileFilter extends Filter {}
[/code]

Now regarding javax.swing.filechooser.FileFilter. Why was this made an abstract class instead of an interface? There is _zero_ code - just two abstract methods.

If I were to rewrite it, it would be
[code]
package javax.swing.filechooser;

public interface FileFilter extends java.io.FileFilter
{
public String getDescription();
}
[/code]

However, changing to an interface could break some existing code. In that case

[code]
package javax.swing.filechooser;

public abstract class FileFilter implements java.io.FileFilter
{
public abstract String getDesciption();
}
[/code]

I would like to see java.io.FilenameFilter tied to this new proposed java.util.Filter, but can't see how.

Also, all methods that currently accept java.io.FileFilter or javax.swing.filechooser.FileFilter should allow for [i]any[/i] java.util.Filter

viper_wolf
Offline
Joined: 2004-06-03

This would be a nice addition.

----------------------------------
[b]package java.util;

public interface Filter {
public boolean accept( T t );
}[/b]
----------------------------------
* Addition to java.util.Collections

[b]public void filterList( java.util.List, java.util.Filter );[/b]

Remove items that do not match the filter

[b]public java.util.Collection filter( java.util.Collection, java.util.Filter )[/b]

Return a new Collection containing only items that match the filter.

[b]public java.util.Iterator iterator( java.util.Collection, java.util.Filter );[/b]

Iterate only accepted items.

monika_krug
Offline
Joined: 2004-10-14

Your API is confusing. One filter method permits the other one reject the elements that match the criteria.

Monika.

viper_wolf
Offline
Joined: 2004-06-03

In practice, they would both remove. A List has functionality to remove the items from it. A Collection does not. So to filter a collection, unless you can cast it to List first which may or may not be possable, you must create a new one with the items removed you do not want. On the other hand a list can be mutated without creating a new List object. That was the reasoning behind the 2 methods.

monika_krug
Offline
Joined: 2004-10-14

Thanks, now I get it.

Monika.

vikstar
Offline
Joined: 2004-04-23

Is it good software engineering to have the container held responsible for the addition of items outside its interface?

For example, the List example that is also featured in this thread accepts only positive integers via the Filter mechanism. This is misleading because List is said to hold Integers and not a specific subset of the Integers. If you want to only add positive integers, it should be the responsibility of the class/method that uses this container to filter-out non positive Integers.

If you need the container itself to have the responsibility of descrimitating which objects it can hold then this should be reflected in the interface. So you should have something along the lines of List, although not practical in this example, it does illustrate my meaning.

If you need to sometimes add positive Integers and othertimes negative Integers or any Integers then, under the Filter mechanism you would make a change to the Filter that is used, or swap which Filter is used depending on your need. This ties back to what I meantioned before about the class/method that uses the container must have the responsibility of deciding what is added to the container.

mgrev
Offline
Joined: 2003-08-12

You would have a FilterableList that accepts a Filter, not a common List.

Filters can also be combined, say a filter that accepts positive integers and one that only accepts even integers could be implemented and chosen at runtime. That's hard to do with inheritance since it is 'combined' at compile time.

Cheers,
Mikael grev

rickcarson
Offline
Joined: 2004-03-04

I like it, but my natural inclination was to apply it to an Iterator... eg something like...

public interface Filter {
public boolean accept(Object o);
}

public class FilteredIterator extends Iterator {
private Iterator myIterator;
private Filter myFilter;
public FilteredIterator(Collection col) {
// should check if col is null etc
myIterator = col.iterator();
}
public FilteredIterator(Iterator iteratorToWrap) {
myIterator = iteratorToWrap;
}
public Object next() {
while (myIterator.hasNext()) {
Object o = myIterator.next()
if (myFilter.accept(o)) {
return o;
}
}
// what to return? We ran off the end of the iterator!
}
}

Anyways, the best thing is: no generics! ;-)

Astute observers will note that the hasNext() contract has been violated.

To solve that, probably you have to 'check ahead' and 'preload' the next object which the filter will accept. Which raises optimisation issues (such as Hotspot not precompiling constructors?).

eg

...
Object next;
public boolean hasNext() {
return (next != null);
}
public Object next() {
Object obToReturn = next;
// loop as above, but don't return o, set next = o;
...
return obToReturn;
}

I'm not sure what would happen to your Filter if the list contained several different types...

Whereas with my one you could take a list which contained both Integers and Doubles, and use different Filters to get each of them...

eg

class IntegerFilter implements Filter {
public boolean accept(Object o) {
return (o instanceof Integer);
}
}

with obvious extensions into things like filtering over a range (though you do of course need to use instanceof and casting... oh the humanity!).

dgreenbean
Offline
Joined: 2003-12-08

> I like it, but my natural inclination was to apply it
> to an Iterator... eg something like...

I would tend to disagree here, as I tend to think of an Iterator as performing only the task of iterating over a Collection, not choosing which information is in the Collection as well. The laziness of the filter that is implied in your statement can be attained in the implementation of the Collection, rather than the Iterator.

> Anyways, the best thing is: no generics! ;-)

Generics are wonderful! ;-)

> Astute observers will note that the hasNext()
> contract has been violated.

Another reason that it would make sense to do this in the Collection. As far as the Iterator should be concerned, if there are no more elements in the list that satisfy the condition, hasNext() should be false. Properly implemented, this can be the case:
When calling hasNext(), the Collection that the Iterator is tied to checks the next element against the filter. If it passes, then return true. Otherwise, check the next element until there are no more.

> To solve that, probably you have to 'check ahead' and
> 'preload' the next object which the filter will
> accept. Which raises optimisation issues (such as
> Hotspot not precompiling constructors?).

It should not be more than O(n) where n is the number of elements in the Collection, removing efficiency as a factor.

> I'm not sure what would happen to your Filter if
> the list contained several different types...
>
> Whereas with my one you could take a list which
> contained both Integers and Doubles, and use
> different Filters to get each of them...

This is a detail that can be worked out with careful use of generics. The idea is that you would need to ensure that T is the same for List and Filter. It is true that if you let T be Object, you will need to use casts and instanceof in your filter method. Generics remove this obstacle.

cowwoc
Offline
Joined: 2003-08-24

-1

Unless you can make the case that there is a filter interface that universally pleases all people and contributes more than it harms in the form of "extra API clutter" then I would have to disagree. It already seems pretty clear from the above posts that everyone wants a filter interface, but everyone wants it in a different context. In such a case, it would seem to me, it is quite appropriate for everyone to define their own interface that suits their specific context.

PS: I'm not trying to shoot down your idea for the sake of it. I honestly hope I am wrong and your idea can go through, but let's just say I am skeptical and I've yet to be convinced.

Gili

rickcarson
Offline
Joined: 2004-03-04

D'oh! Of coruse the constructors need to take a Filter as a parameter and set myFilter to that Filter, etc. My bad. :)

dog
Offline
Joined: 2003-08-22

Aren't you really asking for standard interfaces and methods to implement

do, select, collect, reject, and others (Smalltalk)

also (with some overlap here)

mapcar, remove-if-not, remove-if, reduce, and others (Lisp)

Jakarta commons already has these implemented but it would be better if these were part of the java.util package.

Besides filter.. this could also be useful

public interface Transform {
public T transform(T object);
}

and maybe variable parameter versions to support reduce like operations or mapcars over various collections?

ssteadman
Offline
Joined: 2004-08-10

Actually, I suggest something like this:

public interface Filter {

/**
* Returns true if the object should be included in the filtered result.
*/
boolean include (Object value);

}

public Class SubCollection extends AbstractCollection {
Collection base;
Filter filter;

public SubCollection (Collection b, Filter f){
this.base = b
this.filter = f;
}

...

/**
* Returns an iterator for the SubCollection.
*/
public Iterator iterator () {
return new FilterIterator(base.iterator(), filter);
}

}

Then you can have SubList and SubMap classes...

tsinger
Offline
Joined: 2003-06-10

Generally I'm not against this RFE, because I like light-weight interfaces ;)

But I don't get it, what exactly you intent with such an interface, especially in the combination with collections.

Tom

dgreenbean
Offline
Joined: 2003-12-08

Here's a simple example of something that could be useful (make a list that requires all of its elements are positive). What I like about this is that you add the constraint when building the list, but "client" code (with respect to the list) does not affect anything other than the [code]filter(T t)[/code] method.

In addition to this example, you could allow the elements to be added to the list, but then have a method that extracts only those that satisfy the condition. Either of these can be useful in complex applications, when you want your code to be as intuitive as possible.

[code]
public interface Filter {public boolean filter (T t);}
----------------------------------------------------------
import java.util.List;
public interface FilteredList extends List,Filter{}
----------------------------------------------------------
import java.util.ArrayList;
public class FilteredArrayList extends ArrayList implements FilteredList {
public boolean filter(T t) {return true;}
public boolean add(T t) {
if (filter (t)) return super.add (t);
return false;
}
}
----------------------------------------------------------
import java.util.Iterator;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class FilterTemp {
public static void main(String[] args) throws IOException {
String s;
FilteredArrayList pos = new FilteredArrayList () {
public boolean filter(Integer i) {
return i.intValue() > 0;
}
};
System.out.println("Give me a number: ");
BufferedReader in = new BufferedReader(
new InputStreamReader(System.in));
while ((s = in.readLine()) != null && !s.equals("")) {
pos.add(Integer.parseInt(s));
System.out.println("Give me a number: ");
}
System.out.println("\n\nAll positive numbers:\n");
for (Integer i : pos) System.out.println(i);
}
}
[/code]

jzacker
Offline
Joined: 2004-12-06

I would prefer this whole idea go into a static method in java.util.Collections (doesn't that seem like the right place for it?).

[i]static public Collection filter(Collection c, Filter filter)[/i]

The Collection parameter obviously remains unchanged. The return value is a non-null Collection of Objects that met the filter criteria.

dgreenbean
Offline
Joined: 2003-12-08

That would make sense for the latter suggestion I made, where you would filter a preexisting list. My hope was to convey that that would not be the only use for this, and that, in fact, many different uses can be discovered, each for a different purpose.

Your proposal would be very helpful in situations where storing the original data is important. Mine would be useful in cases where only the filtered information will be used and efficiency is important. I would also like to throw out there the situations where you might be filtering something that is not a Collection. In these cases your suggestion would not necessarily scale as well.

dgreenbean
Offline
Joined: 2003-12-08

+1 I can't tell you how many times I have implemented this same interface in my code.

yishai
Offline
Joined: 2003-11-16

+1. Now that we have generics, it makes sense. Pre-generics it wouldn't have.

mgrev
Offline
Joined: 2003-08-12

+1

A always have one of those in my projects.

accept() is normally the method name though..

jwenting
Offline
Joined: 2003-12-02

ever heard of the instanceof operator and the equals method?
Doesn't seem your filter interface would ever be implemented to do much more than two provide already.

monika_krug
Offline
Joined: 2004-10-14

Probably the interface would often be implemented using instanceof or equals. But why are you saying this? The interface is useful. One can implement a Collection class with a method filteredList that takes a Filter as a paramter and filters according to its criteria.

[code]public class MyList extends ArrayList
{
/* ... */
public MyList filteredList(Filter filter)
{
MyList newList = new MyList;
for (E e: this)
{
if (filter(e)) newList.add(e);
}
}
}[/code]
Monika.

jwenting
Offline
Joined: 2003-12-02

Because each and every time something is added just because it might be useful to someone the language grows and grows.

Already there are complaints that Java is way too fat for its own good.
Just because something is used frequently doesn't mean it should be part of the core language...

monika_krug
Offline
Joined: 2004-10-14

This is not to be added to the language, but to the library. There are thousands of classes and interfaces in the library, this one will certainly not harm anyone. It's not in java.lang, so unless someone import java.util.*, there won't be name clashes in existing code.

Monika.