Is there an efficient algorithm for merging numeric ranges?

Question

I am given series of ranges and I need to iterate each number in any of the ranges exactly once. The ranges may overlap and contain the same numbers.

The numbers in the range are

using Number = uint32_t;

Ranges are of this form

struct Range {
  Number first;
  Number last;
  Number interval;
};

Just to clarify the representation of Range.

Range range = {
  2,  //first
  14, //last
  3   //interval
};

//is equivalent to...

std::vector<Number> list = {2, 5, 8, 11, 14};

I have a few Ranges and I need to efficiently iterate all of the numbers in any order only once.

How do I efficiently iterate a set of ranges?

Also, Is there there a more efficient algorithm if interval is always 1?

Answer 1

For each range, remember the "current" value (going from first to last with the step size). Put that along with the range in a priority queue, sorted after the current value.

Take the top out, if its current value is different from the last, then use it. Then, insert the next step if there is another.

Assumes positive step size.

template<typename Iterator, typename Operation>
void iterate_ranges (Iterator from, Iterator to, Operation op) {
  using R = typename std::iterator_traits<Iterator>::value_type;
  using N = typename std::decay<decltype(std::declval<R>().first)>::type;
  using P = std::pair<N, R>;
  auto compare = [](P const & left, P const & right) {
    return left.first > right.first;};

  std::priority_queue<P, std::vector<P>, decltype(compare)> queue(compare);

  auto push = [& queue] (P p) {
    if (p.first < p.second.last) queue.push(p); };
  auto next = [](P const & p) -> P {
    assert(p.second.step > 0);
    return {p.first + p.second.step, p.second}; };
  auto init = [&push] (R const & r) {
    push({r.first, r}); };

  std::for_each(from, to, init);

  if (queue.empty()) return;

  N last = queue.top().first;
  push(next(queue.top()));
  queue.pop();
  op(last);

  while (! queue.empty()) {
    P current = queue.top();
    queue.pop();
    if (current.first != last) {
      op(current.first);
      last = current.first;
    }
    push(next(current));
  }
}

Memory requirement: linear in the number of ranges. Time requirement: sum of all step counts within each range.

Small example:

struct Range {
  int first;
  int last;
  int step; // a better name ...
};


int main() {
  Range ranges [] = {
    {1, 10, 2},
    {2, 50, 5}};

  auto print = [](auto n) { std::cout << n << std::endl; };

  iterate_ranges(std::begin(ranges), std::end(ranges), print);
}

To get all numbers in a vector, use a lambda with a reference to a vector and push back each one.

Is there there a more efficient algorithm if interval is always 1?

You could add that as a special case, but I don't think it will be necessary. If you only got ~50 ranges, then above push won't be that expensive. Though, with all optimisation: profile first!