CODEWITHSUNDEEP
c++c++11c++14
Kailas
Kailas

Reputation: 827

Efficient Search through list of Ranges

I have list of ranges { start, end }, and a value (point) , now I am looking for effective way to get last n th index from range in which given value is present.

For example: List: [ { 0, 4 }, {5, 10 }, {11, 14 }, {15, 20} , {21, 25} ] n : 2 value: 22

So here, 22 is in range {21, 25 } which is at index 4 ( 0 based ). and since n is 2, function should return index of {11, 14 } because this is n th range from matching range.

Here, I can write binary function easily since I have sorted list of ranges. But I do not want to write while / for , I am looking for some C++ 11 / 14 algorithms / lambdas if available, which can solve this issue.

What is an efficient solution?

Upvotes: 2

Views: 1987

Answers (2)

ildjarn
ildjarn

Reputation: 62975

I like Jan's answer, but since the appropriate solution is notably different if your data is known to be sorted, here's an answer for the question as-asked:

#include <cstddef>
#include <utility>
#include <stdexcept>
#include <algorithm>
#include <iterator>

template<typename RngT, typename ValT, typename OffsetT>
std::size_t find_prev_interval(RngT const& rng, ValT const& value, OffsetT const offset) {
    using std::begin; using std::end;
    auto const first = begin(rng), last = end(rng);
    auto const it = std::lower_bound(
        first, last, value,
        [](auto const& ivl, auto const& v) { return ivl.second < v; }
    );

    // optional if value is *known* to be present
    if (it == last || value < it->first) {
        throw std::runtime_error("no matching interval");
    }

    auto const i = std::distance(first, it);
    return offset <= i
      ? i - offset
      : throw std::runtime_error("offset exceeds index of value");
}

As the implementation only needs forward-iterators, this will work for any standard library container or C-array; however for std::set<> or something like boost::containers::flat_set<>, you'll want to alter the logic to call rng.lower_bound() rather than std::lower_bound(). Also, replace exceptions with something like boost::optional if it is usual for offset to be too large to return a valid index.

Upvotes: 4

Jan Hohenheim
Jan Hohenheim

Reputation: 3752

Assuming that your point is stored as a std::pair and that returning an iterator instead of an index is acceptable:

template <typename container_t, typename value_t, typename n_t>
auto KailasFind(const container_t& vec, value_t value, n_t n) {
    auto match = std::find_if(vec.begin(), vec.end(), [&](const auto& p) {
        return value >= p.first && value <= p.second;
    });
    return match - n;
}

usage: 

using point_t = std::pair<int, int>;
std::vector<point_t> vec {{0, 4}, {5, 10}, {11, 14}, {15, 20}, {21, 25}};
auto it_to_result = KailasFind(vec, 22, 2);
auto result = *it_to_result;

Upvotes: 2

Related Questions