tmp.cpp

tmp.cpp

template <typename RandIter1, typename RandIter2,
            typename Comp, typename Proj1, typename Proj2,
        HPX_CONCEPT_REQUIRES_(
            hpx::traits::is_random_access_iterator<RandIter1>::value &&
            hpx::traits::is_random_access_iterator<RandIter2>::value)>
        std::pair<RandIter1, RandIter2>
        find_half_point(RandIter1 first1, RandIter1 last1,
            RandIter2 first2, RandIter2 last2, Comp& comp,
            Proj1& proj1, Proj2& proj2)
        {
            using hpx::util::invoke;

            std::size_t left1 = 0u, right1 = last1 - first1;
            std::size_t left2 = 0u, right2 = last2 - first2;
            std::size_t half_len = (right1 + right2) / 2;

            while (left1 < right1 && left2 < right2)
            {
                std::size_t mid1 = (left1 + right1) / 2;
                std::size_t mid2 = (left2 + right2) / 2;

                if (invoke(comp,
                    invoke(proj1, first1[mid1]),
                    invoke(proj2, first2[mid2])))
                {
                    if (mid1 + mid2 < half_len)
                        left1 = mid1 + 1;
                    else
                        right2 = mid2;
                }
                else
                {
                    if (mid1 + mid2 < half_len)
                        left2 = mid2 + 1;
                    else
                        right1 = mid1;
                }
            }

            if (left1 >= right1)
                right2 = half_len - right1;
            else
                right1 = half_len - right2;

            // TODO: Consider 'stableness'.
        }