setDifference<T> function

List<T> setDifference<T>(
  1. Iterable<T> a,
  2. Iterable<T> b, {
  3. int compare(
    1. T,
    2. T
    )?,
})

Constructs a sorted difference of elements from two sorted sequences a and b.

Both sequences must be sorted according to the same compare function. The resulting sequence contains all elements that are present in a but not in b.

Example:

final list1 = [1, 2, 4, 5];
final list2 = [2, 3, 5, 6];
final diff = setDifference(list1, list2); // Returns [1, 4]

Implementation

List<T> setDifference<T>(
  Iterable<T> a,
  Iterable<T> b, {
  int Function(T, T)? compare,
}) {
  compare ??= _defaultCompare;
  var res = <T>[];
  var itA = a.iterator;
  var itB = b.iterator;
  bool hasA = itA.moveNext();
  bool hasB = itB.moveNext();

  while (hasA && hasB) {
    var comp = compare(itA.current, itB.current);
    if (comp < 0) {
      res.add(itA.current);
      hasA = itA.moveNext();
    } else if (comp > 0) {
      hasB = itB.moveNext();
    } else {
      hasA = itA.moveNext();
      hasB = itB.moveNext();
    }
  }
  while (hasA) {
    res.add(itA.current);
    hasA = itA.moveNext();
  }
  return res;
}