LowerBound_with_3_ranges

#include <algorithm>
#include <execution>
#include <iostream>
#include <future>

#include "log_duration.h"

using namespace std;

template <typename RandomAccessIterator, typename Value>
RandomAccessIterator LowerBound(const execution::sequenced_policy&,
    RandomAccessIterator range_begin, RandomAccessIterator range_end, const Value& value) {
    auto left_bound = range_begin;
    auto right_bound = range_end;
    while (left_bound + 1 < right_bound) {
        const auto middle = left_bound + (right_bound - left_bound) / 2;
        if (*middle < value) {
            left_bound = middle;
        } else {
            right_bound = middle;
        }
    }
    if (left_bound == range_begin && !(*left_bound < value)) {
        return left_bound;
    } else {
        return right_bound;
    }
}

template <typename RandomAccessIterator, typename Value>
RandomAccessIterator LowerBound(RandomAccessIterator range_begin, RandomAccessIterator range_end,
    const Value& value) {
    return LowerBound(execution::seq, range_begin, range_end, value);
}

template <typename RandomAccessIterator, typename Value>
RandomAccessIterator LowerBound(const execution::parallel_policy&, RandomAccessIterator range_begin,
    RandomAccessIterator range_end, const Value& value) {
    RandomAccessIterator left_bound = range_begin;
    RandomAccessIterator right_bound = range_end;
    while (left_bound + 1 < right_bound) {
        size_t size_one_third = (right_bound - left_bound) / 3; // размер 2-х поддиапазонов
        const RandomAccessIterator middle_left = left_bound + size_one_third;
        const RandomAccessIterator middle_right = right_bound - left_bound < 3 ? right_bound - 1 : middle_left + size_one_third;

        future<bool> is_first_one_third = async([middle_left, &value] {
            return !(*middle_left < value); }); // false - левая часть нас не интересует
        bool is_second_one_third = !(*middle_right < value);

        if (is_first_one_third.get()) {
            right_bound = middle_left;
        } else if (is_second_one_third) {
            left_bound = middle_left;
            right_bound = middle_right;
        } else {
            left_bound = middle_right;
        }
    }
    if (left_bound == range_begin && !(*left_bound < value)) {
        return left_bound;
    } else {
        return right_bound;
    }
}


/* АВТОРСКОЕ РЕШЕНИЕ */
//template <typename RandomAccessIterator, typename Value>
//RandomAccessIterator LowerBound(const execution::parallel_policy&, RandomAccessIterator range_begin, RandomAccessIterator range_end, const Value& value) {
//    auto left_bound = range_begin;
//    auto right_bound = range_end;
//    while (left_bound + 1 < right_bound) {
//        const int distance = right_bound - left_bound;
//        const int part_length = max(1, distance / 3);
//        const auto middle_left = left_bound + part_length;
//        const auto middle_right = right_bound - part_length;
//
//        auto left_less_future = async([middle_left, &value] { return *middle_left < value; });
//
//        if (*middle_right < value) {
//            left_bound = middle_right;
//        } else if (left_less_future.get()) {
//            left_bound = middle_left;
//            right_bound = middle_right;
//        } else {
//            right_bound = middle_left;
//        }
//    }
//    if (left_bound == range_begin && !(*left_bound < value)) {
//        return left_bound;
//    } else {
//        return right_bound;
//    }
//}


/* МЕДЛЕННОЕ РЕШЕНИЕ */
//template <typename RandomAccessIterator, typename Value>
//RandomAccessIterator LowerBound(const execution::parallel_policy&, RandomAccessIterator range_begin,
//    RandomAccessIterator range_end, const Value& value) {
//    if (range_end - range_begin == 1) {
//        return range_begin;
//    }
//    if (range_end - range_begin == 2) {
//        return *range_begin < value ? range_begin : range_end;
//    }
//    // размер 2-х поддиапазонов
//    size_t size_one_third = (range_end - range_begin) / 3;
//    const RandomAccessIterator middle_left = range_begin + size_one_third;
//    const RandomAccessIterator middle_right = middle_left + size_one_third;
//    future<bool> is_first_one_third = async([middle_left, &value] {
//        return !(*middle_left < value); }); // false - левая часть нас не интересует
//    bool is_second_one_third = !(*middle_right < value);
//    //future<bool> no_is_second_one_third = async([middle_right, &value] {
//    //    return *middle_left < value; });
//
//    if (is_first_one_third.get()) {
//        return LowerBound(range_begin, middle_left, value);
//    } else if (is_second_one_third) {
//        return LowerBound(middle_left, middle_right, value);
//    } else {
//        return LowerBound(middle_right, range_end, value);
//    }
//}

int main() {
    const vector<string> strings = { "cat", "dog", "dog", "horse" };

    const vector<string> requests = { "bear", "cat", "deer", "dog", "dogs", "horses" };

    // последовательные версии
    cout << "Request [" << requests[0] << "] -> position "
        << LowerBound(strings.begin(), strings.end(), requests[0]) - strings.begin() << endl;
    cout << "Request [" << requests[1] << "] -> position "
        << LowerBound(execution::seq, strings.begin(), strings.end(), requests[1])
        - strings.begin()
        << endl;
    cout << "Request [" << requests[2] << "] -> position "
        << LowerBound(execution::seq, strings.begin(), strings.end(), requests[2])
        - strings.begin()
        << endl;

    // параллельные
    cout << "Request [" << requests[3] << "] -> position "
        << LowerBound(execution::par, strings.begin(), strings.end(), requests[3])
        - strings.begin()
        << endl;
    cout << "Request [" << requests[4] << "] -> position "
        << LowerBound(execution::par, strings.begin(), strings.end(), requests[4])
        - strings.begin()
        << endl;
    cout << "Request [" << requests[5] << "] -> position "
        << LowerBound(execution::par, strings.begin(), strings.end(), requests[5])
        - strings.begin()
        << endl;
}