# std.algorithm

Implements algorithms oriented mainly towards processing of sequences. Some functions are semantic equivalents or supersets of those found in the*header in Alexander Stepanov's Standard Template Library for C++.*

__algorithm__**Author:**

Andrei Alexandrescu

**Note:**

Many functions in this module are parameterized with a function or a predicate . The predicate may be passed either as a function name, a delegate name, a functor name, or a compile-time string. The string may consist of

**any**legal D expression that uses the symbol

*a*(for unary functions) or the symbols

*a*and

*b*(for binary functions). These names will NOT interfere with other homonym symbols in user code because they are evaluated in a different context. The default for all binary comparison predicates is

*"a == b"*for unordered operations and

*"a < b"*for ordered operations.

**Example:**

int[] a = ...; static bool greater(int a, int b) { return a > b; } sort!(greater)(a); // predicate as alias sort!("a > b")(a); // predicate as string // (no ambiguity with array name) sort(a); // no predicate, "a < b" is implicitSome functions are additionally parameterized with primitives such as

*move*(defaulting to std.algorithm.move ) or

*iterSwap*primitive (defaulting to std.algorithm.iterSwap ). These parameters distill the way in which data is manipulated, and the algorithms guarantee they only use them to touch values. There is sometimes a need to override that default behavior. Possible uses include notifying observers, counting the number of operations, or manipulating multiple collections in lockstep.

- Implements the homonym function (also known as
*transform*) present in many languages of functional flavor. The callreturns a new range of which elements are obtained by applying__map__!(fun)(range1, range2, ..., rangeN)*fun(x)*left to right for all*x*in*range1*, then all*x*in*range2*, ..., all*x*in*rangeN*. The original ranges are not changed.

**Example:**

int[] arr1 = [ 1, 2, 3, 4 ]; int[] arr2 = [ 5, 6 ]; auto squares = map!("a * a")(arr1, arr2); assert(squares == [ 1, 4, 9, 16, 25, 36 ]);

In all cases, the type of the result is the same as of the type of the first range passed in. If a different type of range is needed, just supply an empty range of the needed type as the first argument.

**Example:**

short[] arr = [ 1, 2 ]; auto squares = map!("a * a")(cast(int[]) null, arr); assert(is(typeof(squares) == int[]));

- Implements the homonym function (also known as
*accumulate*,*compress*,*inject*, or*foldl*) present in various programming languages of functional flavor. The callfirst assigns__reduce__!(fun)(seed, range)*seed*to an internal variable*result*, also called the accumulator. Then, for each element*x*in*range*,*result = fun(result, x)*gets evaluated. Finally,*result*is returned. Many aggregate range operations turn out to be solved withquickly and easily. The example below illustrates__reduce__'s remarkable power and flexibility.__reduce__

**Example:**

int[] arr = [ 1, 2, 3, 4, 5 ]; // Sum all elements auto sum = reduce!("a + b")(0, arr); assert(sum == 15); // Compute the maximum of all elements auto largest = reduce!(max)(arr[0], arr[1 .. $]); assert(largest == 5); // Compute the number of odd elements auto odds = reduce!("a + (b & 1)")(0, arr); assert(odds == 3); // Compute the sum of squares auto ssquares = reduce!("a + b * b")(0, arr); assert(ssquares == 55);

**Multiple ranges:**

It is possible to pass any number of ranges to, as in__reduce__. Then__reduce__!(fun)(seed, range1, range2, range3)will simply apply its algorithm in succession to each range, from left to right.__reduce__

**Example:**

int[] a = [ 3, 4 ]; int[] b = [ 100 ]; auto r = reduce!("a + b")(0, a, b); assert(r == 107); // Mixing convertible types is fair game, too double[] c = [ 2.5, 3.0 ]; auto r1 = reduce!("a + b")(0.0, a, b, c); assert(r1 == 112.5);

**Multiple functions:**

Sometimes it is very useful to compute multiple aggregates in one pass. One advantage is that the computation is faster because the looping overhead is shared. That's whyaccepts multiple functions. If two or more functions are passed,__reduce__returns a std.typecons.Tuple object with one member per passed-in function. The number of seeds must be correspondingly increased.__reduce__

**Example:**

double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ]; // Compute minimum and maximum in one pass auto r = reduce!(min, max)(double.max, -double.max, a); // The type of r is Tuple!(double, double) assert(r._0 == 2); // minimum assert(r._1 == 11); // maximum // Compute sum and sum of squares in one pass r = reduce!("a + b", "a + b * b")(0.0, 0.0, a); assert(r._0 == 35); // sum assert(r._1 == 233); // sum of squares // Compute average and standard deviation from the above auto avg = r._0 / a.length; auto stdev = sqrt(r._1 / a.length - avg * avg);

**Multiple ranges and functions:**

The most general form ofaccepts multiple functions and multiple ranges simultaneously. The call__reduce__applies the reduction algorithm for all functions and all ranges.__reduce__!(fun1, ..., funN)(seed1, ..., seedN, range1, ..., rangeM)

**Example:**

int[] a = [ 3, 4, 7, 11, 3, 2, 5 ]; double[] b = [ 2.5, 4, -4.5, 2, 10.9 ]; // Compute minimum and maximum in one pass over a and b auto r = reduce!(min, max)(double.max, -double.max, a, b); assert(r._0 == -4.5); // minimum assert(r._1 == 11); // maximum

- Implements the homonym function present in various programming
languages of functional flavor. The call
returns a new range only containing elements__filter__!(fun)(range)*x*in*r*for which*pred(x)*is.**true**

**Example:**

int[] arr = [ 1, 2, 3, 4, 5 ]; // Sum all elements auto small = filter!("a < 3")(arr); assert(small == [ 1, 2 ]);

**Multiple ranges:**

It is possible to pass any number of ranges to, as in__filter__. Then__filter__!(fun)(range1, range2, range3)will simply apply its algorithm in succession to each range, from left to right. The type returned is that of the first range.__filter__

**Example:**

int[] a = [ 3, -2, 400 ]; int[] b = [ 100, -101, 102 ]; auto r = filter!("a > 0")(a, b); assert(r == [ 3, 400, 100, 102 ]); // Mixing convertible types is fair game, too double[] c = [ 2.5, 3.0 ]; auto r1 = filter!("cast(int) a != a")(c, a, b); assert(r1 == [ 2.5 ]);

- Similar to
*map*, but it manipulates the passed-in ranges in place and returns*void*. The callapplies__inPlace__!(fun)(range1, range2, ..., rangeN)*fun(x)*left to right for all*ref x*in*range1*, then all*ref x*in*range2*, ..., all*ref x*in*rangeN*.

**Example:**

int[] arr1 = [ 1, 2, 3 ]; inPlace!(writeln)(arr1); // print the array double[] arr2 = [ 4.0, 8.5, 13 ]; inPlace!("++a")(arr1, arr2); assert(arr1 == [ 2, 3, 4 ]); assert(arr2 == [ 5.0, 9.5, 14 ]);

- Moves
*source*into*target*via a destructive copy. Specifically:- If
*hasAliasing!(T)*is**true**(see std.traits.hasAliasing ), then the representation of*source*is bitwise copied into*target*and then*source = T.init*is evaluated. - Otherwise,
*target = source*is evaluated.

**Preconditions:**

*!pointsTo(source, source)*

- If
- Swaps
*lhs*and*rhs*. See also std.contracts.pointsTo .

**Preconditions:**

*!pointsTo(lhs, lhs) && !pointsTo(lhs, rhs) && !pointsTo(rhs, lhs) && !pointsTo(rhs, rhs)*

- Reduces
*r*by shifting it to the left until no adjacent elements*a*,*b*remain in*r*such that*pred(a, b)*. Shifting is performed by evaluating*move(source, target)*as a primitive. The algorithm is stable and runs in**Ο****(***r.length***)**time. Returns the reduced range.

The default std.algorithm.move performs a potentially destructive assignment of*source*to*target*, so the objects beyond the returned range should be considered "empty". By default*pred*compares for equality, in which casecollapses adjacent duplicate elements to one (functionality akin to the uniq system utility).__overwriteAdjacent__

**Example:**

int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; auto r = overwriteAdjacent(arr); assert(r == [ 1, 2, 3, 4, 5 ]);

- Finds the first occurrence of
*needle*in*haystack*by linear search and returns an iterator to it. An optional binary predicate*pred*instructson how to perform the comparison (with the current collection element in the first position and__find__*needle*in the second position). By default, comparison is for equality. Performs**Ο****(***haystack.length***)**evaluations of*pred*. See also STL's find.

To__find__the last occurence of*needle*in*haystack*, calland compare the result against__find__(retro(haystack), needle)*rEnd(haystack)*. See also std.iterator.retro .

**Example:**

auto a = [ 1, 2, 3 ]; assert(find(a, 5) == end(a)); // not found assert(find(a, 2) == begin(a) + 1); // found // Case-insensitive find of a string string[] s = [ "Hello", "world", "!" ]; assert(find!("toupper(a) == toupper(b)")(s, "hello") == begin(s));

- Finds the first element in a range satisfying the unary predicate
*pred*. Performs**Ο****(***haystack.length***)**evaluations of*pred*. See also STL's find_if.

To__find__the last element of*haystack*satisfying*pred*, calland compare the result against__find__!(pred)(retro(haystack))*rEnd(haystack)*. See also std.iterator.retro .

**Example:**

auto arr = [ 1, 2, 3 ]; assert(find!("a > 2")(arr) == end(arr) - 1); // with predicate alias bool pred(int x) { return x + 1 > 1.5; } assert(find!(pred)(arr) == begin(arr));

- Finds the first occurrence of
*subseq*in*seq*by repeated linear searches. Performs**Ο****(***seq.length * subseq.length***)**evaluations of*pred*, which makes it unrecommended for very large ranges, for which std.algorithm.findBoyerMoore may be more appropriate. See also STL's search.

**Example:**

int[] a = [ -1, 0, 1, 2, 3, 4, 5 ]; int[] b = [ 1, 2, 3 ]; assert(findRange(a, b) == begin(a) + 2); assert(findRange(b, a) == end(b));

- Finds the first occurrence of
*subseq*in*seq*by using the Boyer-Moore algorithm. The algorithm has an upfront cost but scales sublinearly, so it is most suitable for large sequences. Performs**Ο****(***seq.length***)**evaluations of*pred*in the worst case and**Ο****(***seq.length / subseq.length***)**evaluations in the best case.

**Example:**

int[] a = [ -1, 0, 1, 2, 3, 4, 5 ]; int[] b = [ 1, 2, 3 ]; assert(findBoyerMoore(a, b) == begin(a) + 2); assert(findBoyerMoore(b, a) == end(b));

BUGS:

Should cache the scaffolding built for the last*subseq*in thread-safe storage so it is not rebuilt repeatedly.

- Finds the first two adjacent elements
*a*,*b*in the range*r*that satisfy*pred(a, b)*. Performs**Ο****(***r.length***)**evaluations of*pred*. See also STL's adjacent_find.

**Example:**

int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ]; auto p = findAdjacent(a); assert(p == begin(a) + 1); p = findAdjacent!("a < b")(a); assert(p == begin(a) + 6);

- Finds the first element in
*seq*that compares equal (according to*pred*) with some element in*choices*. Choices are sought by linear search. Performs**Ο****(***seq.length * choices.length***)**evaluations of*pred*. See also STL's find_first_of.

**Example:**

int[] a = [ -1, 0, 1, 2, 3, 4, 5 ]; int[] b = [ 3, 1, 2 ]; assert(findAmong(a, b) == begin(a) + 2); assert(findAmong(b, a) == begin(b));

- Finds the first element
*x*in*seq*that compares equal with some element*y*in*choices*(meaning*!less(x, y) && !less(y, x)*). The*choices*range is sought by binary search. Consequently*choices*is assumed to be sorted according to*pred*, which by default is*"a < b"*. Performs**Ο****(***seq.length * log(choices.length)***)**evaluations of*less*.

To find the last element of*seq*instead of the first, calland compare the result against__findAmongSorted__(retro(seq), choices)*rEnd(seq)*. See also std.iterator.retro .

**Example:**

int[] a = [ -1, 0, 1, 2, 3, 4, 5 ]; int[] b = [ 1, 2, 3 ]; assert(findAmongSorted(a, b) == begin(a) + 2); assert(findAmongSorted(b, a) == end(b));

- bool
__canFind__(alias pred,Range,E)(Range*haystack*, E*needle*);

bool__canFind__(string pred = "a == b",Range,E)(Range*haystack*, E*needle*);

bool__canFind__(alias pred,Range,E)(Range*haystack*);

bool__canFind__(string pred,Range,E)(Range*haystack*);

bool__canFindAmong__(alias pred,Range1,Range2)(Range*seq*, Range2*choices*);

bool__canFindAmong__(string pred,Range1,Range2)(Range*seq*, Range2*choices*);

bool__canFindAmongSorted__(alias pred,Range1,Range2)(Range*seq*, Range2*choices*);

bool__canFindAmongSorted__(string pred,Range1,Range2)(Range*seq*, Range2*choices*); - Convenience functions returning
if and only if the corresponding**true***find**functions return an iterator different from*end(r)*. They are handy in the numerous situations when the success of the*find**functions is queried but the actual position found is unimportant.

**Example:**

int[] a = [ -1, 0, 1, 2, 3, 4, 5 ]; assert(canFind(a, 4)); assert(!canFind(a, 10)); assert(canFind!("a - 1 < b")(a, 4)); assert(!canFind!("a > 5")(a));

- Counts the number of elements
*x*in*r*for which*pred(x, value)*is.**true***pred*defaults to equality. Performs**Ο****(***r.length***)**evaluations of*pred*.

**Example:**

int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; assert(count(a, 2) == 3); assert(count!("a > b")(a, 2) == 5);

- Counts the number of elements
*x*in*r*for which*pred(x)*is. Performs**true****Ο****(***r.length***)**evaluations of*pred*.

**Example:**

int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; assert(count!("a > 1")(a) == 8);

- Returns
if and only if the two ranges compare**true**__equal__element for element, according to binary predicate*pred*. The ranges may have different element types, as long as*pred(a, b)*evaluates to*bool*for*a*in*r1*and*b*in*r2*. Performs**Ο****(***min(r1.length, r2.length)***)**evaluations of*pred*. See also STL's__equal__.

**Example:**

int[] a = [ 1, 2, 4, 3 ]; assert(!equal(a, a[1..$])); assert(equal(a, a)); // different types double[] b = [ 1., 2, 4, 3]; assert(!equal(a, b[1..$])); assert(equal(a, b)); // predicated: ensure that two vectors are approximately equal double[] c = [ 1.005, 2, 4, 3]; assert(equal!(approxEqual)(b, c));

- Returns the overlapping range, if any, of two ranges. Unlike
*equal*,only compares the iterators in the ranges, not the values referred by them. If__overlap__*r1*and*r2*have an overlapping range, returns that range. Otherwise, returns an empty range. Performs**Ο****(***min(r1.length, r2.length)***)**iterator increment operations and comparisons if the ranges are forward, and**Ο****(***1***)**operations if the ranges have random access.

**Example:**

int[] a = [ 10, 11, 12, 13, 14 ]; int[] b = a[1 .. 3]; assert(overlap(a, b) == [ 11, 12 ]); b = b.dup; // overlap disappears even though the content is the same assert(isEmpty(overlap(a, b)));

- Returns the minimum of the passed-in values. The type of the result is
computed by using std.traits.CommonType
.

- Returns the maximum of the passed-in values. The type of the result is
computed by using std.traits.CommonType
.

**Example:**

int a = 5; short b = 6; double c = 2; auto d = max(a, b); assert(is(typeof(d) == int)); assert(d == 6); auto e = min(a, b, c); assert(is(typeof(e) == double)); assert(e == 2);

- Sequentially compares elements in
*r1*and*r2*in lockstep, and stops at the first__mismatch__(according to*pred*, by default equality). Returns a tuple with the iterators that refer to the two mismatched values. Performs**Ο****(***min(r1.length, r2.length)***)**evaluations of*pred*. See also STL's__mismatch__.

**Example:**

int[] x = [ 1, 5, 2, 7, 4, 3 ]; double[] y = [ 1., 5, 2, 7.3, 4, 8 ]; auto m = mismatch(x, y); assert(m._0 == begin(x) + 3); assert(m._1 == begin(y) + 3);

- Encodes edit operations necessary to transform one sequence into
another. Given sequences
*s*(source) and*t*(target), a sequence ofencodes the steps that need to be taken to convert__EditOp__*s*into*t*. For example, if*s = "cat"*and*"cars"*, the minimal sequence that transforms*s*into*t*is: skip two characters, replace 't' with 'r', and insert an 's'. Working with edit operations is useful in applications such as spell-checkers (to find the closest word to a given misspelled word), approximate searches, diff-style programs that compute the difference between files, efficient encoding of patches, DNA sequence analysis, and plagiarism detection.

- Current items are equal; no editing is necessary.

- Substitute current item in target with current item in source.

- Insert current item from the source into the target.

- Remove current item from the target.

- Returns the Levenshtein
distance between
*s*and*t*. The Levenshtein distance computes the minimal amount of edit operations necessary to transform*s*into*t*. Performs**Ο****(***s.length * t.length***)**evaluations of*equals*and occupies**Ο****(***s.length * t.length***)**storage.

**Example:**

assert(levenshteinDistance("cat", "rat") == 1); assert(levenshteinDistance("parks", "spark") == 2); assert(levenshteinDistance("kitten", "sitting") == 3); // ignore case assert(levenshteinDistance!("toupper(a) == toupper(b)") ("parks", "SPARK") == 2);

- Returns the Levenshtein distance and the edit path between
*s*and*t*.

**Example:**

string a = "Saturday", b = "Sunday"; auto p = levenshteinDistanceAndPath(a, b); assert(p._0, 3); assert(equals(p._1, "nrrnsnnn"));

- Copies the content of
*source*into*target*and returns the remaining (unfilled) part of*target*. See also STL's__copy__. If a behavior similar to STL's copy_backward is needed, use. See also std.iterator.retro .__copy__(retro(source), retro(target))

**Example:**

int[] a = [ 1, 5 ]; int[] b = [ 9, 8 ]; int[] c = new int[a.length + b.length + 10]; auto d = copy(b, copy(a, c)); assert(c[0 .. a.length + b.length] == a ~ b); assert(d.length == 10);

As long as the target range elements support assignment from source range elements, different types of ranges are accepted.

**Example:**

float[] a = [ 1.0f, 5 ]; double[] b = new double[a.length]; auto d = copy(a, b);

- Copies in increasing order the elements
*x*of*source*satisfying*pred(x)*into*target*and returns the remaining (unfilled) part of*target*. See also STL's copy_if.

**Example:**

int[] a = [ 1, 5, 8, 9, 10, 1, 2, 0 ]; auto b = new int[a.length]; auto c = copyIf!("(a & 1) == 1")(a, b); assert(b[0 .. $ - c.length] == [ 1, 5, 9, 1 ]);

As long as the target range elements support assignment from source range elements, different types of ranges are accepted.

**Example:**

float[] a = [ 1.0f, 5, -3, -5, 0, 4, -3 ]; double[] b = new double[a.length]; auto d = copyIf!("a > 0")(a, b); assert(a == [ 1.0f, 5, 0, 4 ]);

- Swaps
**lhs*and**rhs*.

**Preconditions:**

Same as for*swap(*lhs, *rhs)*.

- Swaps all elements of
*r1*with successive elements in*r2*using*iterSwap*as a primitive.*r1*must contain less or the same number of elements as*r2*; an exception will be thrown otherwise. Returns the tail portion of*r2*that was not swapped.

**Example:**

int[] a = [ 100, 101, 102, 103 ]; int[] b = [ 0, 1, 2, 3 ]; auto c = swapRanges(a[1 .. 2], b[2 .. 3]); assert(!c.length); assert(a == [ 100, 2, 3, 103 ]); assert(b == [ 0, 1, 101, 102 ]);

- Reverses
*r*in-place. Performs*r.length*evaluations of*iterSwap*. See also STL's__reverse__.

**Example:**

int[] arr = [ 1, 2, 3 ]; reverse(arr); assert(arr == [ 3, 2, 1 ]);

- Rotates the range
*r = [first, last)*such that the slice*[middle, last)*gets moved in front of the slice*[first, middle)*. Performs**Ο****(***r.length***)**evaluations of*iterSwap*. See also STL's__rotate__.

**Preconditions:**

*first <= middle && middle <= last*;

**Returns:**

The position in which*first*has been rotated.

**Example:**

auto arr = [4, 5, 6, 7, 1, 2, 3]; auto p = rotate(arr, begin(arr) + 4); assert(p - begin(arr) == 3); assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ]);

- Defines the swapping strategy for algorithms that need to swap
elements in a range (such as partition and sort). The strategy
concerns the swapping of elements that are not the core concern of the
algorithm. For example, consider an algorithm that sorts
*[ "abc", "b", "aBc" ]*according to*toupper(a) < toupper(b)*. That algorithm might choose to swap the two equivalent strings*"abc"*and*"aBc"*. That does not affect the sorting since both*[ "abc", "aBc", "b" ]*and*[ "aBc", "abc", "b" ]*are valid outcomes.

Some situations require that the algorithm must NOT ever change the relative ordering of equivalent elements (in the example above, only*[ "abc", "aBc", "b" ]*would be the correct result). Such algorithms are called**stable**. If the ordering algorithm may swap equivalent elements discretionarily, the ordering is called**unstable**.

Yet another class of algorithms may choose an intermediate tradeoff by being stable only on a well-defined subrange of the range. There is no established terminology for such behavior; this library calls it**semistable**.

Generally, the*stable*ordering strategy may be more costly in time and/or space than the other two because it imposes additional constraints. Similarly,*semistable*may be costlier than*unstable*. As (semi-)stability is not needed very often, the ordering algorithms in this module parameterized byall choose__SwapStrategy__as the default.__SwapStrategy__.unstable

- Allows freely swapping of elements as long as the output
satisfies the algorithm's requirements.

- In algorithms partitioning ranges in two, preserve relative
ordering of elements only to the left of the partition point.

- Preserve the relative ordering of elements to the largest
extent allowed by the algorithm's requirements.

- Reduces
*r*by overwriting all elements*x*that satisfy*pred(x)*. Returns the reduced range.

**Example:**

int[] arr = [ 1, 2, 3, 4, 5 ]; // eliminate even elements auto r = eliminate!("(a & 1) == 0")(arr); assert(r == [ 1, 3, 5 ]); assert(arr == [ 1, 3, 5, 4, 5 ]);

- Reduces
*r*by overwriting all elements*x*that satisfy*pred(x, v)*. Returns the reduced range.

**Example:**

int[] arr = [ 1, 2, 3, 2, 4, 5, 2 ]; // keep elements different from 2 auto r = eliminate(arr, 2); assert(r == [ 1, 3, 4, 5 ]); assert(arr == [ 1, 3, 4, 5, 4, 5, 2 ]);

- Partitions a range in two using
*pred*as a predicate and*iterSwap*as a primitive to swap two elements. Specifically, reorders the range*r = [left, right)*using*iterSwap*such that all elements*i*for which*pred(i)*iscome before all elements**true***j*for which*pred(j)*returns.**false**

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

always calls__partition__*iterSwap(i, j)*for iterators satisfying*i < j && !pred(*i) && pred(*j)*. After the call to*iterSwap(i, j)*,makes no assumption on the values of__partition__**i*and**j*. Therefore,can be used to actually copy partitioned data to a different container or overwrite part of the array (in fact__partition__*eliminate*useswith a custom__partition__*iterSwap*).

See also STL's__partition__and stable_partition.

**Returns:**

An iterator*p*such that the following conditions are simultaneously**true**:*pred(*p1)*for all*p1*in [*left*,*p*), if any*!pred(*p2)*for all*p2*in [*p*,*right*), if any

*ss == SwapStrategy.stable*,preserves the relative ordering of all elements__partition__*a*,*b*in*r*for which*pred(a) == pred(b)*. If*ss == SwapStrategy.semistable*,preserves the relative ordering of all elements__partition__*a*,*b*in*begin(r) .. p*for which*pred(a) == pred(b)*.

**Example:**

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 a such that even numbers come first auto p = partition!(even)(arr); // Now arr is separated in evens and odds. // Numbers may have become shuffled due to instability assert(p == arr.ptr + 5); assert(count!(even)(range(begin(arr), p)) == p - begin(arr)); assert(find!(even)(range(p, end(arr))) == end(arr)); // Can also specify the predicate as a string. // Use 'a' as the predicate argument name arr[] = Arr[]; p = partition!(q{(a & 1) == 0})(arr); assert(p == arr.ptr + 5); // Now for a stable partition: arr[] = Arr[]; p = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr); // Now arr is [2 4 6 8 10 1 3 5 7 9], and p points to 1 assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && p == arr.ptr + 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; } p = partition!(fun, SwapStrategy.semistable)(arr); // Now arr is [4 5 6 7 8 9 10 2 3 1] and p points to 2 assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && p == arr.ptr + 7);

- Reorders the range
*r = [first, last)*using*iterSwap*as a swapping primitive such that*nth*points to the element that would fall there if the range were fully sorted. Effectively, it finds the nth smallest (according to*less*) element in*r*. In addition, it also partitions*r*such that all elements*p1*in*[first, nth)*satisfy*less(*p1, *nth)*, and all elements*p2*in*[nth, last)*satisfy*!less(*p2, nth)*. Performs**Ο****(***r.length***)**(if unstable) or**Ο****(***r.length * log(r.length)***)**(if stable) evaluations of*less*and*iterSwap*. See also STL's nth_element.

**Example:**

int[] v = [ 25, 7, 9, 2, 0, 5, 21 ]; auto n = 4; topN!(less)(v, begin(v) + n); assert(v[n] == 9); // Equivalent form: topN!("a < b")(v, begin(v) + n); assert(v[n] == 9);

BUGS:

stable__topN__has not been implemented yet.

- Sorts a random-access range according to predicate
*less*. Performs**Ο****(***r.length * log(r.length)***)**(if unstable) or**Ο****(***r.length * log(r.length) * log(r.length)***)**(if stable) evaluations of*less*and*iterSwap*. See also STL's__sort__and stable_sort.

**Example:**

int[] array = [ 1, 2, 3, 4 ]; // sort in descending order sort!("a > b")(array); assert(array == [ 4, 3, 2, 1 ]); // sort in ascending order sort(array); assert(array == [ 1, 2, 3, 4 ]); // sort with a delegate bool myComp(int x, int y) { return x > y; } sort!(myComp)(array); assert(array == [ 4, 3, 2, 1 ]); // Showcase stable sorting string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ]; sort!("toupper(a) < toupper(b)", SwapStrategy.stable)(words); assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);

- Sorts a range using an algorithm akin to the Schwartzian transform, also
known as the decorate-sort-undecorate pattern in Python and Lisp. (Not
to be confused with the other
Schwartz.) This function is helpful when the sort comparison includes
an expensive computation. The complexity is the same as that of the
corresponding
*sort*, butevaluates__schwartzSort__*transform*only*r.length*times (less than half when compared to regular sorting). The usage can be best illustrated with an example.

**Example:**

uint hashFun(string) { ... expensive computation ... } string[] array = ...; // Sort strings by hash, slow sort!("hashFun(a) < hashFun(b)")(array); // Sort strings by hash, fast (only computes arr.length hashes): schwartzSort!(hashFun, "a < b")(array);

Thefunction might require less temporary data and be faster than the Perl idiom or the decorate-sort-undecorate idiom present in Python and Lisp. This is because sorting is done in-place and only minimal extra data (one array of transformed elements) is created.__schwartzSort__

- Reorders
*r*such that the range*begin(r) .. mid*is the same as if*r*were sorted, and leaves the range*mid .. end(r)*in no particular order. Performs**Ο****(***r.length * log(mid - begin(r))***)**evaluations of*pred*.

**Example:**

int[] a = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]; partialSort(a, begin(a) + 5); assert(a[0 .. 5] == [ 0, 1, 2, 3, 4 ]);

- Checks whether a random-access range is sorted according to the
comparison operation
*less*. Performs**Ο****(***r.length***)**evaluations of*less*.

**Example:**

int[] arr = [4, 3, 2, 1]; assert(!isSorted(arr)); sort(arr); assert(isSorted(arr)); sort!("a > b")(arr); assert(isSorted!("a > b")(arr));

__topNIndex__

- Computes an index for
*source*based on the comparison*less*and deposits the result in*target*. It is acceptable that*target.length < source.length*, in which case only the smallest*target.length*elements in*source*get indexed. The target provides a sorted "view" into*source*. This technique is similar to sorting and partial sorting, but it is more flexible because (1) it allows "sorting" of invariant collections, (2) allows binary search even if the original collection does not offer random access, (3) allows multiple indexes, each on a different comparison criterion, (4) may be faster when dealing with large objects. However, using an index may also be slower under certain circumstances due to the extra indirection, and is always larger than a sorting-based solution because it needs space for the index in addition to the original collection. The complexity is**Ο****(***source.length * log(target.length)***)**.

Two types of indexes are accepted. They are selected by simply passing the appropriate*target*argument:- Indexes of type
*Iterator!(Source)*, in which case the index will be sorted with the predicate*less(*a, *b)*; - Indexes of an integral type
(e.g.
*size_t*), in which case the index will be sorted with the predicate*less(source[a], source[b])*.

**Example:**

invariant arr = [ 2, 3, 1 ]; int* index[3]; partialIndex(arr, index); assert(*index[0] == 1 && *index[1] == 2 && *index[2] == 3); assert(isSorted!("*a < *b")(index));

- Indexes of type
- Checks whether a random-access range is sorted according to the
comparison operation
*less(transform(a), transform(b))*. Performs**Ο****(***r.length***)**evaluations of*less*and*transform*. The advantage over*isSorted*is that it evaluates*transform*only half as many times.

**Example:**

int[] arr = [ "ab", "Ab", "aB", "bc", "Bc" ]; assert(!schwartzIsSorted!(toupper, "a < b")(arr));

- Returns the leftmost position in
*range*such that all other values*x*to the left of that position satisfy*less(x, value)*. Performs**Ο****(***log(r.length)***)**evaluations of*less*. See also STL's lower_bound.

**Precondition:**

*isSorted!(less)(r)*

**Returns:**

*i*such that*less(*p, i)*for all p in*[begin(r), i)*.

**Example:**

int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]; auto p = lowerBound!(less)(a, 4); assert(*p == 4); p = lowerBound(a, 4); // uses less by default assert(*p == 4); p = lowerBound!("a < b")(a, 4); // predicate as string assert(*p == 4);

- Returns the rightmost position in
*r*such that all other elements*x*to the left of that position satisfy*!less(value, x)*. Performs**Ο****(***log(r.length)***)**evaluations of*less*. See also STL's upper_bound.

**Precondition:**

*isSorted!(less)(r)*

**Returns:**

*i*such that*less(*p, value)*for all p in*[begin(r), i)*.

**Example:**

auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ]; auto p = upperBound(a, 3); assert(p == begin(a) + 5);

- The call
returns__equalRange__!(less)(r, v)*range(*but a bit more efficiently than calling both functions. Performs*lowerBound!(less)(r, v),*)*upperBound!(less)(r, v)***Ο****(***log(r.length)***)**evaluations of*less*. See also STL's equal_range.

**Precondition:**

*isSorted!(less)(range)*

**Returns:**

The largest subrange of*r*such that for all*p*in that range,*!less(*p, value) && !less(value, *p)*.

**Example:**

auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ]; auto r = equalRange(a, 3); assert(r == [ 3, 3, 3 ]);

- Returns
if and only if**true***value*can be found in*range*, which is assumed to be sorted. Performs**Ο****(***log(r.length)***)**evaluations of*less*. See also STL's binary_search.

- Converts the range
*r*into a heap. Performs**Ο****(***r.length***)**evaluations of*less*.

__popHeap__

__sortHeap__

__topNCopy__

__partialSortCopy__