Function std.algorithm.sorting.partition
Partitions a range in two using the given predicate
.
Range partition(alias predicate, SwapStrategy ss, Range)
(
Range r
)
if (ss == SwapStrategy .stable && isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range && hasSwappableElements!Range);
Range partition(alias predicate, SwapStrategy ss = SwapStrategy .unstable, Range)
(
Range r
)
if (ss != SwapStrategy .stable && isInputRange!Range && hasSwappableElements!Range);
Specifically, reorders the range r = [left, rightclass="pln">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 Ο(r
) (if unstable or semistable) or Ο(r
) (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).
Parameters
Name | Description |
---|---|
predicate | The predicate to partition by. |
ss | The swapping strategy to employ. |
r | The random-access range to partition. |
Returns
The right part of r
after partitioning.
If ss == SwapStrategy
, partition
preserves the relative
ordering of all elements a
, b
in r
for which
predicate(a) == predicate(b)
.
If ss == SwapStrategy
, partition
preserves
the relative ordering of all elements a
, b
in the left part of r
for which predicate(a) == predicate(b)
.
Example
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
writeln(r); // arr[5 .. $]
writeln(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);
writeln(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 .. $]);