The D Programming Language's Unofficial Docs
beta
The D Programming Language's Unofficial Docs
beta
The predicate to partition by.
The swapping strategy to employ.
The random-access range to partition.
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).
1 import std.algorithm.mutation : SwapStrategy; 2 import std.algorithm.searching : count, find; 3 import std.conv : text; 4 import std.range.primitives : empty; 5 6 auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; 7 auto arr = Arr.dup; 8 static bool even(int a) { return (a & 1) == 0; } 9 // Partition arr such that even numbers come first 10 auto r = partition!(even)(arr); 11 // Now arr is separated in evens and odds. 12 // Numbers may have become shuffled due to instability 13 assert(r == arr[5 .. $]); 14 assert(count!(even)(arr[0 .. 5]) == 5); 15 assert(find!(even)(r).empty); 16 17 // Can also specify the predicate as a string. 18 // Use 'a' as the predicate argument name 19 arr[] = Arr[]; 20 r = partition!(q{(a & 1) == 0})(arr); 21 assert(r == arr[5 .. $]); 22 23 // Now for a stable partition: 24 arr[] = Arr[]; 25 r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr); 26 // Now arr is [2 4 6 8 10 1 3 5 7 9], and r points to 1 27 assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]); 28 29 // In case the predicate needs to hold its own state, use a delegate: 30 arr[] = Arr[]; 31 int x = 3; 32 // Put stuff greater than 3 on the left 33 bool fun(int a) { return a > x; } 34 r = partition!(fun, SwapStrategy.semistable)(arr); 35 // Now arr is [4 5 6 7 8 9 10 2 3 1] and r points to 2 36 assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);
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).