subtract static method

IntervalSet subtract(IntervalSet left, IntervalSet right)

Compute the set difference between two interval sets. The specific operation is {@code left - right}. If either of the input sets is null, it is treated as though it was an empty set.

Implementation

static IntervalSet subtract(IntervalSet left, IntervalSet right) {
  if (left.isNil) {
    return IntervalSet();
  }

  final result = IntervalSet.ofSet(left);
  if (right.isNil) {
    // right set has no elements; just return the copy of the current set
    return result;
  }

  var resultI = 0;
  var rightI = 0;
  while (
      resultI < result.intervals.length && rightI < right.intervals.length) {
    final resultInterval = result.intervals[resultI];
    final rightInterval = right.intervals[rightI];

// operation: (resultInterval - rightInterval) and update indexes

    if (rightInterval.b < resultInterval.a) {
      rightI++;
      continue;
    }

    if (rightInterval.a > resultInterval.b) {
      resultI++;
      continue;
    }

    Interval? beforeCurrent;
    Interval? afterCurrent;
    if (rightInterval.a > resultInterval.a) {
      beforeCurrent = Interval(resultInterval.a, rightInterval.a - 1);
    }

    if (rightInterval.b < resultInterval.b) {
      afterCurrent = Interval(rightInterval.b + 1, resultInterval.b);
    }

    if (beforeCurrent != null) {
      if (afterCurrent != null) {
// split the current interval into two
        result.intervals[resultI] = beforeCurrent;
        result.intervals.insert(resultI + 1, afterCurrent);
        resultI++;
        rightI++;
        continue;
      } else {
// replace the current interval
        result.intervals[resultI] = beforeCurrent;
        resultI++;
        continue;
      }
    } else {
      if (afterCurrent != null) {
// replace the current interval
        result.intervals[resultI] = afterCurrent;
        rightI++;
        continue;
      } else {
// remove the current interval (thus no need to increment resultI)
        result.intervals.removeAt(resultI);
        continue;
      }
    }
  }

// If rightI reached right.intervals.length, no more intervals to subtract from result.
// If resultI reached result.intervals.length, we would be subtracting from an empty set.
// Either way, we are done.
  return result;
}