2

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?

Mafii
  • 7,227
  • 1
  • 35
  • 55
Kailas
  • 807
  • 1
  • 6
  • 20
  • So if the value was e.g. `17` then you would return range `{5,10}` (i.e. index 1 in your "list")?? – Some programmer dude Sep 16 '16 at 04:27
  • @JoachimPileborg Yes – Kailas Sep 16 '16 at 04:36
  • 1
    Possible duplicate of [Where can I get a "useful" C++ binary search algorithm?](http://stackoverflow.com/questions/446296/where-can-i-get-a-useful-c-binary-search-algorithm) – Snowhawk Sep 16 '16 at 05:17
  • 3
    is it accidental that those ranges are in order, non-overlapping, and leave no gaps? if not, that changes the approach, and should be stated in the question. – sp2danny Sep 16 '16 at 07:27

2 Answers2

4

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.

ildjarn
  • 62,044
  • 9
  • 127
  • 211
2

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;
Jan Hohenheim
  • 3,552
  • 2
  • 17
  • 42