I have a function find_all_intervals_below
that iterates through a vector and finds all the index intervals of at least a given length where each element within the interval is below a given threshold.
struct Interval {
int start;
int end;
};
std::vector<Interval>
find_all_intervals_below(const std::vector<int> &v, const int &threshold,
const int &min_length) {
auto start_position { 0 };
auto end_position { 0 };
std::vector<Interval> intervals;
bool found_start { false };
for (auto current_pos = 0; current_pos < v.size(); ++current_pos) {
if (v[current_pos] <= threshold and not found_start) {
start_position = current_pos;
end_position = 0;
found_start = true;
} else if (found_start and v[current_pos] > threshold and end_position == 0) {
end_position = current_pos;
if (end_position - start_position >= min_length) {
Interval interval;
interval.start = start_position;
interval.end = end_position;
intervals.push_back(interval);
}
start_position = 0;
found_start = false;
}
}
if (found_start and end_position == 0 and v.size() - start_position >= min_length) {
end_position = v.size();
Interval interval;
interval.start = start_position;
interval.end = end_position;
intervals.push_back(interval);
}
return intervals;
}
This function works perfectly fine, I would just like to get some input from others as I imagine there is likely much more succinct ways of doing this. search_n
from STL looks like it might be a solution but I couldn't figure out how to use it for my case.
EDIT: I need the solution to be C++11 compatible, unfortunately.
Test example
const auto min_len { 3 };
const auto threshold { 3 };
const std::vector<int> v { 4, 2, 1, 1, 4, 1, 2, 4 };
const auto actual { find_all_intervals_below(v, threshold, min_len) };
const std::vector<Interval> expected { Interval(1, 4) };
assert(actual == expected);