reorder_iterator : iterator_adaptor

From: Toon Knapen (toon.knapen_at_[hidden])
Date: 2001-11-24 08:24:21

I frequently need to have access to entries in a sequence in a different 
order, depending on the context, as the order in which they are stored.

For this purpose I use a customised iterator_adaptor which takes as 
input a random-access iterator to the sequence and an iterator that
specifies the order by which I will access them.

It's different from the permutation iterator (mentioned in the OOPSLA
article, not in boost though AFAIK ;-( that the relative order can 
change and even the same entry can appear multiple times.

If others would be interested in this functionality ...
you can find the code with a small test in attachment.

toon


#include <boost/iterator_adaptors.hpp>

namespace boost {

  template < typename OrderIt >
  struct reorder_iterator_policies : public default_iterator_policies
  {
    reorder_iterator_policies(OrderIt order_it) 
      : order_it_( order_it ) 
    {}

    template < class Base >
    void initialize(Base& base)
    {
      base += *order_it_;
    }

    template <class IteratorAdaptor>
    void increment(IteratorAdaptor& x)
    { 
      std::iterator_traits< OrderIt >::value_type current = *order_it_;
      x.base() += *++order_it_ - current;
    }

    template <class IteratorAdaptor>
    void decrement(IteratorAdaptor& x)
    {
      std::iterator_traits< OrderIt >::value_type current = *order_it_;
      x.base() += *--order_it_ - current;
    }

    template <class IteratorAdaptor, class DifferenceType>
    void advance(IteratorAdaptor& x, DifferenceType n)
    { 
      std::iterator_traits< OrderIt >::value_type current = *order_it_;
      x.base() += *(order_it_ += n) - current;
    }

    template <class IteratorAdaptor1, class IteratorAdaptor2>
    typename IteratorAdaptor1::difference_type
    distance(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
    { return *(y.policies().order_it_) - *(x.policies().order_it_); }

    template <class IteratorAdaptor1, class IteratorAdaptor2>
    bool equal(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
    { return x.policies().order_it_ == y.policies().order_it_; }
  
    OrderIt order_it_;
  };

  /// generate an iterator that will access the elements
  /// behind the random-access iterator RAIt in the
  /// order specified by the OrderIt iterator.
  /// preconditions:
  /// The OrderIt::value_type will be used in iterator arithmetic
  template < typename RAIt, typename OrderIt >
  struct reorder_iterator_generator
  {
    typedef iterator_adaptor
    < RAIt,
      reorder_iterator_policies< OrderIt > 
    > type;
  };

  template < class RAIt, typename OrderIt >
  inline typename reorder_iterator_generator< RAIt, OrderIt >::type
  make_reorder_iterator(RAIt base, OrderIt order)
  {
    typedef typename reorder_iterator_generator< RAIt, OrderIt >::type result_t;
    return result_t( base, order );
  }

}


#include <utilities/reorder_iterator.hpp>
#include <vector>
#include <numeric>
#include <iostream>

int main()
{
  using namespace boost;
  int i = 0;

  typedef std::vector< int > sequence;

  static const int size = 100;
  sequence up( size );
  std::iota( up.begin(), up.end(), 0 );

  sequence order( size );
  std::iota( order.begin(), order.end(), 0 );
  std::reverse( order.begin(), order.end() );

  typedef reorder_iterator_generator< sequence::iterator, sequence::iterator >::type reorder_type;
  reorder_type begin = make_reorder_iterator( up.begin(), order.begin() );
  reorder_type it = begin;
  reorder_type end = make_reorder_iterator( up.begin(), order.end() );

  std::cout << "just iterate over all entries following the given order\n";
  for(; it != end ; ++it ) {
    std::cout << *it << " ";
  }
  std::cout << "\n\n";

  std::cout << "iterate forward with stride 2\n";
  it = begin;
  for(i = 0; i < 50 ; ++i, it+=2 ) {
    std::cout << *it << " ";
  }
  std::cout << "\n\n";

  std::cout << "iterate backward\n";
  it = begin + (size - 1);
  assert( it != begin );
  for( ; it != begin ; --it ) {
    std::cout << *it << " ";
  }
  std::cout << "\n\n";

  std::cout << "iterate backward with stride 2\n";
  it = begin + (size - 1);
  for(i = 0 ; i < 50 ; ++i, it-=2 ) {
    std::cout << *it << " ";
  }
  std::cout << "\n\n";
}