Function subtract

src/common/values.cpp:259–353

Subtract `right_` from `left_`, and return the result as Value::Ranges.

// Subtract `right_` from `left_`, and return the result as Value::Ranges.
Value::Ranges subtract(const Value::Ranges& left_, const Value::Ranges& right_)
{
  if (left_.range_size() == 0 || right_.range_size() == 0) {
    return left_;
  }

  // Convert the input `Ranges` to `vector<internal::Range>` and
  // sort the vector based on the start of a range.
  auto sortRanges = [](const Value::Ranges& ranges) {
    vector<internal::Range> result;
    result.reserve(ranges.range_size());

    foreach (const Value::Range& range, ranges.range()) {
      result.push_back({range.begin(), range.end()});
    }

    std::sort(
        result.begin(),
        result.end(),
        [](const internal::Range& left, const internal::Range& right) {
          return left.start < right.start;
        });

    return result;
  };

  Value::Ranges result;

  vector<internal::Range> left = sortRanges(left_);
  vector<internal::Range> right = sortRanges(right_);

  vector<internal::Range>::iterator itLeft = left.begin();
  for (vector<internal::Range>::const_iterator itRight = right.cbegin();
       itLeft != left.end() && itRight != right.cend();) {
    // Non-overlap:
    // L: |___|
    // R:       |___|
    if (itLeft->end < itRight->start) {
      Value::Range* newRange = result.add_range();
      newRange->set_begin(itLeft->start);
      newRange->set_end(itLeft->end);

      itLeft++;
      continue;
    }

    // Non-overlap:
    // L:       |___|
    // R: |___|
    if (itLeft->start > itRight->end) {
      itRight++;
      continue;
    }

    if (itLeft->start < itRight->start) {
      Value::Range* newRange = result.add_range();
      newRange->set_begin(itLeft->start);
      newRange->set_end(itRight->start - 1);