Consider complementing the set operations with relational algebra algorithms #206

Open
jaredhoberock opened this Issue Aug 2, 2012 · 0 comments

Comments

Projects
None yet
1 participant
Owner

jaredhoberock commented Aug 2, 2012

For example, natural join:

template<typename InputIterator1, typename InputIterator2, typename OutputIterator2>
OutputIterator set_natural_join(InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result);

template<typename InputIterator1, typename InputIterator2, typename OutputIterator2, typename Compare>
OutputIterator set_natural_join(InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result,
                                Compare comp);

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

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

With these semantics:

template<typename InputIterator1, typename InputIterator2, typename InputIterator3, typename InputIterator4, typename OutputIterator1, typename OutputIterator2>
tuple<OutputIterator1, OutputIterator2, OutputIterator3>
  set_natural_join_by_key(InputIterator1 keys_first1, InputIterator1 keys_last1, InputIterator2 values_first1,
                          InputIterator3 keys_first2, InputIterator3 keys_last2, InputIterator4 values_first2,
                          OutputIterator1 keys_result, OutputIterator2 values_result1, OutputIterator2 values_result2)
{
  InputIterator3 keys2_restart = keys_first2;
  InputIterator4 values2_restart = values_first2;

  for(; keys_first1 != keys_last1; ++keys_first1, ++values_first1)
  {
    keys_first2 = loop2_restart;
    values_first2 = values2_restart;
    for(; keys_first2 != keys_last2; ++keys_first2, ++values_first2)
    {
      if(*keys_first1 < *keys_first2)
      {
        break;
      }
      else if(*keys_first2 < *keys_first1)
      {
        loop2_restart = keys_first;
        ++loop2_restart;

        values2_restart = values2_first;
        ++values2_restart;
      }
      else
      {
        *keys_result = *keys_first;
        *values_result1 = *values_first1;
        *values_result2 = *values_first2;

        ++keys_result;
        ++values_result1;
        ++values_result2;
      }
    }
  }

  return make_tuple(keys_result, values_result1, values_result2);
}

Something like set_natural_join might make implementing an algorithm like outer_product practical.

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