permutation_iterator needs unit tests

[GoogleCodeExporter]

The problem of dispatching gather/scatter to and from different spaces
needs to be solved comprehensively with copy + permutation_iterator.

Here's a prototypical implementation:

// all three spaces match
gather(Space result,
       Space map,
       Space input)
{
  copy(make_permutation_iterator(map, input),
       result)
}

// spaces differ in at least one place
gather(Space1 result,
       Space2 map,
       Space3 input)
{
  // bring the map & input to Space1
  // one of these is potentially a no-op
  bring_range_to_space<Space1> map1(map);
  bring_range_to_space<Space1> input1(input);

  gather(result, map1, input1);
}

Original issue reported on code.google.com by jaredhoberock on 31 Oct 2009 at 7:38

[GoogleCodeExporter]

Original comment by jaredhoberock on 31 Oct 2009 at 7:40

• Added labels: Type-Enhancement
• Removed labels: Type-Defect

[GoogleCodeExporter]

Implementing gather is actually nastier than I thought.  For one thing, gather's
interface is defined incorrectly.

gather's interface is:

template<typename ForwardIterator , typename InputIterator , typename
RandomAccessIterator >
void    thrust::gather (ForwardIterator first, ForwardIterator last, 
InputIterator map,
RandomAccessIterator input)

The output range comes first, unlike every other Thrust algorithm.  So it can't 
be
implemented directly with permutation_iterator + thrust::copy because we don't 
know
the end of the input range (i.e., map_last).  Nor can we gather to an 
ostream_iterator.

We have ForwardIterators, so we can at least find the size of the range, n.  
This is
inelegant, but we could implement gather with copy_n.

Anyway, what I think we should do is implement detail::copy_n. Instead of a 
bunch of
differently spaced flavors, we should do it with the bring_range_to_space trick 
I
mentioned above.  I think this could collapse a lot of the copy backend.

Incidentally, probably all of our primitive device kernels should be XXX_n() 
rather
than XXX().  If all we accept are RandomAccessIterators, the end of the range is
redundant.

Original comment by jaredhoberock on 1 Nov 2009 at 7:17

[GoogleCodeExporter]

r721 adds permutation_iterator

changing summary to permutation_iterator needs unit tests, ARBing Nathan

Original comment by jaredhoberock on 20 Jan 2010 at 8:10

• Changed title: permutation_iterator needs unit tests

[GoogleCodeExporter]

resolved by r738

Original comment by wnbell on 24 Jan 2010 at 3:46

• Changed state: Fixed