partition<T> function

int partition<T>(
  1. List<T> list,
  2. bool predicate(
    1. T
    )
)

Reorders the elements in the list in such a way that all elements for which the predicate returns true precede the elements for which it returns false.

The relative order of the elements is not guaranteed to be preserved. Returns the index of the first element of the second group (i.e. returning false).

Example:

final list = [1, 2, 3, 4, 5, 6];
final p = partition(list, (int n) => n % 2 == 0);
// list becomes [6, 2, 4, 3, 5, 1] (or similar), returns 3

Implementation

int partition<T>(List<T> list, bool Function(T) predicate) {
  var first = 0;
  var last = list.length;
  while (true) {
    while (first < last && predicate(list[first])) {
      ++first;
    }
    if (first == last) break;

    --last;
    while (first < last && !predicate(list[last])) {
      --last;
    }
    if (first == last) break;

    _swap(list, first, last);
    ++first;
  }
  return first;
}