[boost] filter_iterator bidirectional traversal patch

12 Dec 2004

      Hi boosters-

A couple of days ago I started a thread asking about the rationale for
making filter_iterator only a  forward traversal iterator. I presented 
some arguments for making filter_iterator bidirectional instead. As some
people seemed to be convinced that this was OK, I took the liberty of
creating a patch.

Oddly enough, the work had almost been completed already -- all that
was needed was to make the category bidirectional. Here's the patch:

*** filter_iterator.hpp.orig  Thu Aug 12 10:13:06 2004
--- filter_iterator.hpp Sun Dec 12 11:24:05 2004
***************
*** 33,39 ****
                      typename iterator_traversal<Iterator>::type
                    , bidirectional_traversal_tag
                  >
!               , forward_traversal_tag
                , use_default
              >::type
          > type;
--- 33,39 ----
                      typename iterator_traversal<Iterator>::type
                    , bidirectional_traversal_tag
                  >
!               , bidirectional_traversal_tag
                , use_default
              >::type
          > type;

Here's the test program I used to verify it:

#include <iostream>
#include <list>

#include <boost/iterator/filter_iterator.hpp>
#include <boost/iterator/reverse_iterator.hpp>

// simple filter that returns true for even numbers:
struct filter {
   typedef int argument_type;

   bool operator()(argument_type iArg);
};

bool filter::operator()(argument_type iArg)

{
   return (iArg & 1) == 0;
}

// Simple functions that traverse a sequence and print them:
template<typename It>
void traverse_forward(It iBegin, It iEnd)

{
   while (iBegin != iEnd) {
      std::cout << *iBegin << "\n";

      ++iBegin;
   }
}

template<typename It>
void traverse_backward(It iBegin, It iEnd)

{
   while (iBegin != iEnd) {
      --iEnd;

      std::cout << *iEnd << "\n";
   }
}

// Show that boost::filter_iterator won't make a forward iterator into a
// bidirectional one.
typedef boost::filter_iterator<filter, std::istream_iterator<int> > ii;

enum {
   result = boost::is_convertible<
                   boost::iterator_traversal<ii>::type
                 , boost::bidirectional_traversal_tag
                >::value
};

BOOST_STATIC_ASSERT(!result);

int main (void)

{
   std::list<int>    l;

   for (int i = 0; i < 10; ++i)
      l.push_back(i);

   typedef boost::filter_iterator<filter, std::list<int>::iterator> fi;

   fi    b, e;

   b = boost::make_filter_iterator(filter(), l.begin(), l.end());
   e = boost::make_filter_iterator(filter(), l.end(), l.end());

   std::cout << "Using filter_iterator:\n";

   std::cout << "\nEven numbers forward:\n";
   traverse_forward(b, e);

   std::cout << "\nEven numbers backward:\n";
   traverse_backward(b, e);

   // Show that filter_iterator works with reverse_iterator:
   typedef boost::reverse_iterator<fi> ri;

   std::cout << "\nUsing reverse_iterator with a filter_iterator:\n";

   std::cout << "\nEven numbers backward:\n";
   traverse_forward(ri(e), ri(b));

   std::cout << "\nEven numbers forward:\n";
   traverse_backward(ri(e), ri(b));
}

Here's the expected output:

Using filter_iterator:

Even numbers forward:
0
2
4
6
8

Even numbers backward:
8
6
4
2
0

Using reverse_iterator with a filter_iterator:

Even numbers backward:
8
6
4
2
0

Even numbers forward:
0
2
4
6
8

Bob

[boost] filter_iterator bidirectional traversal patch

Bob Bell