The OpenD Programming Language

partition

Partitions a range in two using the given predicate.

Specifically, reorders the range r = [left, right$(RPAREN) using swap such that all elements i for which predicate(i) is true come before all elements j for which predicate(j) returns false.

Performs O(r.length) (if unstable or semistable) or O(r.length * log(r.length)) (if stable) evaluations of less and swap. The unstable version computes the minimum possible evaluations of swap (roughly half of those performed by the semistable version).

  1. Range partition(Range r)
    Range
    partition
    (
    alias predicate
    Range
    )
    (
    Range r
    )
  2. Range partition(Range r)

Parameters

predicate

The predicate to partition by.

ss

The swapping strategy to employ.

r Range

The random-access range to partition.

Return Value

Type: Range

The right part of r after partitioning.

If ss == SwapStrategy.stable, partition preserves the relative ordering of all elements a, b in r for which predicate(a) == predicate(b). If ss == SwapStrategy.semistable, partition preserves the relative ordering of all elements a, b in the left part of r for which predicate(a) == predicate(b).

Examples

import std.algorithm.mutation : SwapStrategy;
import std.algorithm.searching : count, find;
import std.conv : text;
import std.range.primitives : empty;

auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
auto arr = Arr.dup;
static bool even(int a) { return (a & 1) == 0; }
// Partition arr such that even numbers come first
auto r = partition!(even)(arr);
// Now arr is separated in evens and odds.
// Numbers may have become shuffled due to instability
assert(r == arr[5 .. $]);
assert(count!(even)(arr[0 .. 5]) == 5);
assert(find!(even)(r).empty);

// Can also specify the predicate as a string.
// Use 'a' as the predicate argument name
arr[] = Arr[];
r = partition!(q{(a & 1) == 0})(arr);
assert(r == arr[5 .. $]);

// Now for a stable partition:
arr[] = Arr[];
r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr);
// Now arr is [2 4 6 8 10 1 3 5 7 9], and r points to 1
assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]);

// In case the predicate needs to hold its own state, use a delegate:
arr[] = Arr[];
int x = 3;
// Put stuff greater than 3 on the left
bool fun(int a) { return a > x; }
r = partition!(fun, SwapStrategy.semistable)(arr);
// Now arr is [4 5 6 7 8 9 10 2 3 1] and r points to 2
assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);

Meta