 /*
 
-Uses code from https://github.com/moderngpu/moderngpu which has the following license:
+Adapted from https://github.com/moderngpu/moderngpu which has the following license:
 
 > Copyright (c) 2016, Sean Baxter
 > All rights reserved.

}


template<typename launch_arg_t = empty_t,
  typename a_it, typename b_it, typename comp_t>
mem_t<int2> inner_join(a_it a, int a_count, b_it b, int b_count,
  comp_t comp, context_t& context) {

  // Compute lower and upper bounds of a into b.
  mem_t<int> lower(a_count, context);
  mem_t<int> upper(a_count, context);
  sorted_search<bounds_lower, launch_arg_t>(a, a_count, b, b_count,
    lower.data(), comp, context);
  sorted_search<bounds_upper, launch_arg_t>(a, a_count, b, b_count,
    upper.data(), comp, context);

  // Compute output ranges by scanning upper - lower. Retrieve the reduction
  // of the scan, which specifies the size of the output array to allocate.
  mem_t<int> scanned_sizes(a_count, context);
  const int* lower_data = lower.data();
  const int* upper_data = upper.data();

  mem_t<int> count(1, context);
  transform_scan<int>([=]MGPU_DEVICE(int index) {
    return upper_data[index] - lower_data[index];
  }, a_count, scanned_sizes.data(), plus_t<int>(), count.data(), context);

  // Allocate an int2 output array and use load-balancing search to compute
  // the join.
  int join_count = from_mem(count)[0];
  mem_t<int2> output(join_count, context);
  int2* output_data = output.data();

  // Use load-balancing search on the segmens. The output is a pair with
  // a_index = seg and b_index = lower_data[seg] + rank.
  //
  // **libgdf changes**
  //  - tuple<int> lower -> tuple<int, int> lower
  //    to workaround error with 1-tuple
  auto k = [=]MGPU_DEVICE(int index, int seg, int rank, tuple<int, int> lower) {
    output_data[index] = make_int2(seg, get<0>(lower) + rank);
  };
  // **libgdf changes**
  //  - make_tuple(lower_data) -> make_tuple(lower_data, lower_data)
  //    to workaround error with 1-tuple
  transform_lbs<launch_arg_t>(k, join_count, scanned_sizes.data(), a_count,
    make_tuple(lower_data, lower_data), context);

  return output;
}


template<typename launch_arg_t = empty_t,
  typename a_it, typename b_it, typename comp_t>
mem_t<int2> left_join(a_it a, int a_count, b_it b, int b_count,
    comp_t comp, context_t& context) {

    // Compute lower and upper bounds of a into b.
    mem_t<int> lower(a_count, context);
    mem_t<int> upper(a_count, context);
    sorted_search<bounds_lower, launch_arg_t>(a, a_count, b, b_count,

        return upper_rev_data[index] == lower_rev_data[index];
    }, b_count, matches.data(), plus_t<int>(), matches_count.data(), context);

    // Prepare output
    append_count = from_mem(matches_count)[0];
    return matches;
}



template<typename launch_arg_t = empty_t,
         typename a_it, typename b_it, typename comp_t>
mem_t<int2> inner_join(a_it a, int a_count, b_it b, int b_count,
                       comp_t comp, context_t& context)
{
    _join_bounds bounds = compute_join_bounds(a, a_count, b, b_count, comp, context);
    int join_count;
    mem_t<int> scanned_sizes = scan_join_bounds(bounds, a_count, b_count, context, true,
                                                join_count);
    mem_t<int2> output = compute_joined_indices(bounds, scanned_sizes, a_count,
                                                join_count, context, true);
    return output;
}


template<typename launch_arg_t = empty_t,
         typename a_it, typename b_it, typename comp_t>
mem_t<int2> left_join(a_it a, int a_count, b_it b, int b_count,
                      comp_t comp, context_t& context)
{
    _join_bounds bounds = compute_join_bounds(a, a_count, b, b_count, comp, context);
    int join_count;
    mem_t<int> scanned_sizes = scan_join_bounds(bounds, a_count, b_count, context, false,
                                                join_count);
    mem_t<int2> output = compute_joined_indices(bounds, scanned_sizes, a_count,
                                                join_count, context, false, 0);
    return output;
}

template<typename launch_arg_t = empty_t,
  typename a_it, typename b_it, typename comp_t>
mem_t<int2> outer_join(a_it a, int a_count, b_it b, int b_count,
                       comp_t comp, context_t& context)
{
    _join_bounds bounds = compute_join_bounds(a, a_count, b, b_count, comp,
                                              context);
    int join_count;
    mem_t<int> scanned_sizes = scan_join_bounds(bounds, a_count, b_count, context, false,
                                                join_count);
    int append_count;
    mem_t<int> matches = outer_join_count_matches(a, a_count, b, b_count,
                                                  comp, context, append_count );
    mem_t<int2> output = compute_joined_indices(bounds, scanned_sizes, a_count,
                                                join_count, context, false, append_count);
    outer_join_append_right(output.data(), matches, append_count, join_count,
                            context);
    return output;
}


struct join_result_base {
    virtual ~join_result_base() {}
    virtual void* data() = 0;
