Consider set_intersection_by_key overload which takes two values ranges #353

Open
jaredhoberock opened this Issue Mar 17, 2013 · 1 comment

1 participant

@jaredhoberock
A Parallel Algorithms Library member

set_intersection_by_key takes a single value input range because the semantics of set_intersection are to copy matches from only the first set. The generalization to set_intersection_by_key therefore makes an accompanying values range for the second input set meaningless.

However, sometimes what we want is to identify which keys in the second input set were matches or to copy values associated with the matches from the second input set. It doesn't seem like we can do that with the existing API.

We could extend set_intersection_by_key's existing API with these overloads:

template<typename InputIterator1,
         typename InputIterator2,
         typename InputIterator3,
         typename InputIterator4,
         typename OutputIterator1,
         typename OutputIterator2,
         typename OutputIterator3>
  thrust::tuple<OutputIterator1,OutputIterator2,OutputIterator3>
    set_intersection_by_key(InputIterator1  keys_first1,
                            InputIterator1  keys_last1,
                            InputIterator2  keys_first2,
                            InputIterator2  keys_last2,
                            InputIterator3  values_first1,
                            InputIterator4  values_first2,
                            OutputIterator1 keys_result,
                            OutputIterator2 values_result1,
                            OutputIterator3 values_result2);

template<typename InputIterator1,
         typename InputIterator2,
         typename InputIterator3,
         typename InputIterator4,
         typename OutputIterator1,
         typename OutputIterator2,
         typename OutputIterator3,
         typename Compare>
  thrust::tuple<OutputIterator1,OutputIterator2,OutputIterator3>
    set_intersection_by_key(InputIterator1  keys_first1,
                            InputIterator1  keys_last1,
                            InputIterator2  keys_first2,
                            InputIterator2  keys_last2,
                            InputIterator3  values_first1,
                            InputIterator4  values_first2,
                            OutputIterator1 keys_result,
                            OutputIterator2 values_result1,
                            OutputIterator3 values_result2,
                            Compare         comp);

These additions wouldn't be ambiguous because they have more parameters than all of the existing set_intersection_by_key functions.

@jaredhoberock
A Parallel Algorithms Library member

Greg tells me that the above interface is nearly an inner join. The difference would be the presence of a binary function which would combine matching values together. So set_inner_join_by_key is a "kernel fusion" form of set_intersection_by_key:

template<typename InputIterator1,
         typename InputIterator2,
         typename InputIterator3,
         typename InputIterator4,
         typename OutputIterator1,
         typename OutputIterator2,
         typename BinaryFunction>
  thrust::pair<OutputIterator1,OutputIterator2>
    set_inner_join_by_key(InputIterator1  keys_first1,
                          InputIterator1  keys_last1,
                          InputIterator2  keys_first2,
                          InputIterator2  keys_last2,
                          InputIterator3  values_first1,
                          InputIterator4  values_first2,
                          OutputIterator1 keys_result,
                          OutputIterator2 values_result,
                          BinaryFunction f);

template<typename InputIterator1,
         typename InputIterator2,
         typename InputIterator3,
         typename InputIterator4,
         typename OutputIterator1,
         typename OutputIterator2,
         typename BinaryFunction,
         typename Compare>
  thrust::pair<OutputIterator1,OutputIterator2>
    set_inner_join_by_key(InputIterator1  keys_first1,
                          InputIterator1  keys_last1,
                          InputIterator2  keys_first2,
                          InputIterator2  keys_last2,
                          InputIterator3  values_first1,
                          InputIterator4  values_first2,
                          OutputIterator1 keys_result,
                          OutputIterator2 values_result,
                          BinaryFunction f,
                          Compare comp);

In this way, set_intersection_by_key can be implemented via a lowering to set_inner_join_by_key by zipping values_result1 and values_result2.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment