www.digitalmars.com

D Programming Language 2.0

Last update Thu Mar 6 15:45:39 2008

std.algorithm

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

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 implicit
Some 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.

Ranges[0] map(string fun,Ranges...)(Ranges rs);
Ranges[0] map(alias fun,Ranges...)(Ranges rs);
Implements the homonym function (also known as transform) present in many languages of functional flavor. The call map!(fun)(range1, range2, ..., rangeN) returns a new range of which elements are obtained by applying 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[]));


template reduce(F...)
Implements the homonym function (also known as accumulate, compress, inject, or foldl) present in various programming languages of functional flavor. The call reduce!(fun)(seed, range) first assigns 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 with reduce quickly and easily. The example below illustrates reduce's remarkable power and flexibility.

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 reduce, as in reduce!(fun)(seed, range1, range2, range3). Then reduce will simply apply its algorithm in succession to each range, from left to right.

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 why reduce accepts 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.

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 of reduce accepts multiple functions and multiple ranges simultaneously. The call reduce!(fun1, ..., funN)(seed1, ..., seedN, range1, ..., rangeM) applies the reduction algorithm for all functions and all ranges.

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


Ranges[0] filter(alias pred,Ranges...)(Ranges rs);
Implements the homonym function present in various programming languages of functional flavor. The call filter!(fun)(range) returns a new range only containing elements 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 filter, as in filter!(fun)(range1, range2, range3). Then filter will simply apply its algorithm in succession to each range, from left to right. The type returned is that of the first range.

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 ]);


void inPlace(alias fun,Range,Ranges...)(Range r, Ranges rs);
void inPlace(string fun,Ranges...)(Ranges rs);
Similar to map, but it manipulates the passed-in ranges in place and returns void. The call inPlace!(fun)(range1, range2, ..., rangeN) applies 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 ]);


void move(T)(ref T source, ref T target);
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.
See also std.contracts.pointsTo .

Preconditions:
!pointsTo(source, source)

void swap(T)(ref T lhs, ref T rhs);
Swaps lhs and rhs. See also std.contracts.pointsTo .

Preconditions:
!pointsTo(lhs, lhs) && !pointsTo(lhs, rhs) && !pointsTo(rhs, lhs) && !pointsTo(rhs, rhs)

Range overwriteAdjacent(alias pred,alias move,Range)(Range r);
Range overwriteAdjacent(string fun = "a == b",alias move = .move,Range)(Range r);
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 case overwriteAdjacent collapses adjacent duplicate elements to one (functionality akin to the uniq system utility).

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


Iterator!(Range) find(alias pred,Range,E)(Range haystack, E needle);
Iterator!(Range) find(string pred = "a == b",Range,E)(Range haystack, E needle);
Finds the first occurrence of needle in haystack by linear search and returns an iterator to it. An optional binary predicate pred instructs find on how to perform the comparison (with the current collection element in the first position and 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, call find(retro(haystack), needle) and compare the result against 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));


Iterator!(Range) find(alias pred,Range)(Range haystack);
Iterator!(Range) find(string pred,Range)(Range haystack);
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, call find!(pred)(retro(haystack)) and compare the result against 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));


Iterator!(Range1) findRange(alias pred,Range1,Range2)(Range1 seq, Range2 subseq);
Iterator!(Range1) findRange(string pred = "a == b",Range1,Range2)(Range1 seq, Range2 subseq);
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));


Iterator!(Range) findBoyerMoore(alias pred,Range)(Range seq, Range subseq);
Iterator!(Range) findBoyerMoore(string pred = "a == b",Range)(Range seq, Range subseq);
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.

Iterator!(Range) findAdjacent(alias pred,Range)(Range r);
Iterator!(Range) findAdjacent(string pred = "a == b",Range)(Range r);
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);


Iterator!(Range1) findAmong(alias pred,Range1,Range2)(Range1 seq, Range2 choices);
Iterator!(Range1) findAmong(string pred = "a == b",Range1,Range2)(Range1 seq, Range2 choices);
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));


Iterator!(Range1) findAmongSorted(alias less,Range1,Range2)(Range1 seq, in Range2 choices);
Iterator!(Range1) findAmongSorted(string less = "a < b",Range1,Range2)(Range1 seq, in Range2 subseq);
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, call findAmongSorted(retro(seq), choices) and compare the result against 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 true if and only if the corresponding 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));


size_t count(alias pred,Range,E)(Range r, E value);
size_t count(string pred = "a == b",Range,E)(Range r, E value);
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);


size_t count(alias pred,Range)(Range r);
size_t count(string pred,Range)(Range r);
Counts the number of elements x in r for which pred(x) is true. Performs Ο(r.length) evaluations of pred.

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


bool equal(alias pred,Range1,Range2)(Range1 r1, Range2 r2);
bool equal(string pred = "a == b",Range1,Range2)(Range1 r1, Range2 r2);
Returns true if and only if the two ranges compare 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));


Range overlap(Range)(Range r1, Range r2);
Returns the overlapping range, if any, of two ranges. Unlike equal, overlap only compares the iterators in the ranges, not the values referred by them. If 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)));


MinType!(T1,T2,T) min(T1,T2,T...)(T1 a, T2 b, T xs);
Returns the minimum of the passed-in values. The type of the result is computed by using std.traits.CommonType .

MaxType!(T1,T2,T) max(T1,T2,T...)(T1 a, T2 b, T xs);
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);


Tuple!(Iterator!(Range1),Iterator!(Range2)) mismatch(alias pred,Range1,Range2)(Range1 r1, Range2 r2);
Tuple!(Iterator!(Range1),Iterator!(Range2)) mismatch(string pred = "a == b",Range1,Range2)(Range1 r1, Range2 r2);
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);


enum EditOp;
Encodes edit operations necessary to transform one sequence into another. Given sequences s (source) and t (target), a sequence of EditOp encodes the steps that need to be taken to convert 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.

none
Current items are equal; no editing is necessary.

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

insert
Insert current item from the source into the target.

remove
Remove current item from the target.

size_t levenshteinDistance(alias equals,Range1,Range2)(Range1 s, Range2 t);
size_t levenshteinDistance(string equals = "a == b",Range1,Range2)(Range1 s, Range2 t);
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);


Tuple!(size_t,EditOp[]) levenshteinDistanceAndPath(alias equals,Range1,Range2)(Range1 s, Range2 t);
Tuple!(size_t,EditOp[]) levenshteinDistanceAndPath(string equals = "a == b",Range1,Range2)(Range1 s, Range2 t);
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"));


Range2 copy(Range1,Range2)(Range1 source, Range2 target);
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 copy(retro(source), retro(target)). See also std.iterator.retro .

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);


Range2 copyIf(alias pred,Range1,Range2)(Range1 source, Range2 target);
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 ]);


void iterSwap(It)(It lhs, It rhs);
Swaps *lhs and *rhs.

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

Range2 swapRanges(alias iterSwap = .iterSwap,Range1,Range2)(T r1, T r2);
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 ]);


void reverse(alias iterSwap = .iterSwap,Range)(Range r);
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 ]);


It rotate(alias iterSwap = .iterSwap,Range,It)(Range r, It middle);
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 ]);


enum SwapStrategy;
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 by SwapStrategy all choose SwapStrategy.unstable as the default.

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

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

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

Range eliminate(alias pred,SwapStrategy ss = SwapStrategy.unstable,alias move = .move,Range)(Range r);
Range eliminate(string fun,SwapStrategy ss = SwapStrategy.unstable,alias move = .move,Range)(Range r);
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 ]);


Range eliminate(alias pred,SwapStrategy ss = SwapStrategy.semistable,Range,Value)(Range r, Value v);
Range eliminate(string pred = "a == b",SwapStrategy ss = SwapStrategy.semistable,Range,Value)(Range r, Value v);
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  ]);


Iterator!(Range) partition(alias pred,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,Range)(Range r);
Iterator!(Range) partition(string pred,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,Range)(Range r);
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) is true come before all elements 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).

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

See also STL's partition and stable_partition.

Returns:
An iterator p such that the following conditions are simultaneously true:
  1. pred(*p1) for all p1 in [left, p), if any
  2. !pred(*p2) for all p2 in [p, right), if any
If ss == SwapStrategy.stable, partition preserves the relative ordering of all elements a, b in r for which pred(a) == pred(b). If ss == SwapStrategy.semistable, partition preserves the relative ordering of all elements 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);


void topN(alias less,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,Range,It)(Range r, It nth);
void topN(string less = "a < b",SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,Range,It)(Range r, It nth);
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.

void sort(alias less,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,Range)(Range r);
void sort(string less = "a < b",SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,Range)(Range r);
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" ]);


void schwartzSort(alias transform,alias less,SwapStrategy ss = SwapStrategy.unstable,Range)(Range r);
void schwartzSort(alias transform,string less = "a < b",SwapStrategy ss = SwapStrategy.unstable,Range)(Range r);
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, but schwartzSort evaluates 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);
The schwartzSort function 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.

void partialSort(alias less,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,Range,It)(Range r, It mid);
void partialSort(string less = "a < b",SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,Range,It)(Range r, It mid);
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 ]);


bool isSorted(alias less,Range)(Range r);
bool isSorted(string less = "a < b",Range)(Range r);
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));


void topNIndex(alias less,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,SRange,TRange)(SRange source, TRange target);
void topNIndex(string less,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,SRange,TRange)(SRange source, TRange target);
topNIndex

void partialIndex(alias less,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,SRange,TRange)(SRange source, TRange target);
void partialIndex(string less,SwapStrategy ss = SwapStrategy.unstable,alias iterSwap = .iterSwap,SRange,TRange)(SRange source, TRange target);
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:
  1. Indexes of type Iterator!(Source), in which case the index will be sorted with the predicate less(*a, *b);
  2. 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));


bool schwartzIsSorted(alias transform,alias less,Range)(Range r);
bool schwartzIsSorted(alias transform,string less = "a < b",Range)(Range r);
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));


Iterator!(Range) lowerBound(alias less,Range,V)(Range r, V value);
Iterator!(Range) lowerBound(string less = "a < b",Range,V)(Range r, V value);
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);


Iterator!(Range) upperBound(alias less,Range,V)(Range r, V value);
Iterator!(Range) upperBound(string less = "a < b",Range,V)(Range r, V value);
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);


Range equalRange(alias less,Range,V)(Range r, V value);
Range equalRange(string less = "a < b",Range,V)(Range r, V value);
The call equalRange!(less)(r, v) returns range(lowerBound!(less)(r, v), upperBound!(less)(r, v)) but a bit more efficiently than calling both functions. Performs Ο(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 ]);


bool canFindSorted(alias less,T,V)(T range, V value);
Returns true if and only if 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.

void makeHeap(alias less,alias iterSwap = .iterSwap,Range)(Range r);
Converts the range r into a heap. Performs Ο(r.length) evaluations of less.

void popHeap(alias less,alias iterSwap = .iterSwap,Range)(Range r);
popHeap

void sortHeap(alias less,alias iterSwap = .iterSwap,Range)(Range r);
sortHeap

void topNCopy(alias less,alias iterSwap = .iterSwap,SRange,TRange)(SRange source, TRange target);
topNCopy

void partialSortCopy(alias less,alias iterSwap = .iterSwap,SRange,TRange)(SRange source, TRange target);
partialSortCopy