A Filtering Iterator

[jdporter]

I present here an iterator which applies filtering to some other iterator. You give it an iterator and a condition; it returns an iterator which produces the same sequence of values as the iterator you gave would, except those values which don't meet the condition are not returned, they are skipped.

This iterator conforms to the interface of Iterator, except that the value method can return lists of values, not just single scalars. Besides new, it implements reset, value, and is_exhausted.

The iterator you pass in should similarly implement the interface of Iterator. This "inner iterator" must implement methods reset, value, and is_exhausted. Again, its value method can return multiple values or a single value.

The condition is defined as a subroutine, passed by reference. It will receive in @_ the value(s) returned by each call to the inner iterator's value method. It should return a boolean value. This will be used to determine whether that value will be returned by the outer iterator (the one created by this class).

Let's look at the code:

{
    package Iterator::Filter;

    sub new
    {
        my $self = bless {}, shift;
        $self->{'iterator'} = shift;
        $self->{'condition'} = shift;
        $self->reset;
        $self
    }

    sub reset
    {
        my $self = shift;
        $self->{'iterator'}->reset;
        $self->_advance;
    }

    # post-condition: either 
    # a. iterator is not at end, and value is set; or
    # b. iterator is at end, and value is not set.
    sub _advance
    {
        my $self = shift;
        my @value;
        delete $self->{'value'};
        while ( !$self->{'iterator'}->is_exhausted )
        {
            @value = $self->{'iterator'}->value;
            if ( $self->{'condition'}->( @value ) )
            {
                $self->{'value'} = \@value;
                last;
            }
        }
    }

    sub value
    {
        my $self = shift;
            $self->is_exhausted and die "past end";
        my $value = $self->{'value'};
        $self->_advance;
        @$value
    }

    sub is_exhausted
    {
        my $self = shift;
        !exists $self->{'value'}
    }
}

Here's a sample application. The inner iterator returns the values in a given array, containing the integers 1 to 10. The condition returns true for those numbers which are odd. (Note that the inner iterator is created using the Iterator::Array class presented in Using Nested Iterators to find a Cross Product.)

my $fi = new Iterator::Filter
    Iterator::Array->new( [ 1 .. 10 ] ), # inner iterator
    sub { $_[0] % 2 };                   # condition

print $fi->value, "\n" until $fi->is_exhausted ;

[JadeNB]

How does this differ from Iterator::Util's igrep function?

[jdporter]

How does this differ from Iterator::Util's igrep function?

Excellent question. There is no difference, conceptually. There are some minor differences in implementation, particularly in the interface, as I discuss here. Analogously, my Interface::Array class is the same, conceptually, as Iterator::Util's iarray function. I wrote Iterator::Array, Iterator::Product, and Iterator::Filter partly as demo code, but primarly I wrote them to be transparent (or "white box") building blocks for Implementing Theta Join (select/where) using iterators. No doubt I could have used Iterator::Util instead.