Function std.algorithm.sorting.partition
Partitions a range in two using the given predicate.
Specifically, reorders the range r = [left, right)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.length) (if unstable or semistable) or Ο(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).
Prototype
Range partition(alias predicate, std.algorithm.mutation.SwapStrategy ss, Range)( Range r ) if (ss == SwapStrategy.stable && isRandomAccessRange!Range || ss != SwapStrategy.stable && isForwardRange!Range);
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
If ss == SwapStrategy.stable, partitiona, b in rpredicate(a) ==
predicate(b). If ss == SwapStrategy.semistable, partitiona, b in the left part of rpredicate(a) == predicate(b).
See Also
STL's partition
STL's stable_partition
Example
import std.algorithm : count, find; // FIXME import std.conv : text; 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 .. $]);