# std.algorithm

<algorithm> header in Alexander Stepanov's Standard Template Library for C++. 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

Function Name | Description |
---|---|

balancedParens | balancedParens("((1 + 1) / 2)") returns true because the string
has balanced parentheses. |

boyerMooreFinder | find("hello world", boyerMooreFinder("or")) returns "orld" using the Boyer-Moore algorithm. |

canFind | canFind("hello world",
"or") returns true. |

count | Counts elements that are equal to a specified value or satisfy a predicate. count([1, 2, 1], 1) returns 2 and count!"a < 0"([1, -3, 0]) returns 1. |

countUntil | countUntil(a, b) returns the number of steps taken in a to reach b; for example, countUntil("hello!", "o") returns 4. |

endsWith | endsWith("rocks", "ks")
returns true. |

find | find("hello world", "or") returns "orld" using linear search. (For binary search refer to std.range.sortedRange.) |

findAdjacent | findAdjacent([1, 2, 3, 3, 4]) returns the subrange starting with two equal adjacent elements, i.e. [3, 3, 4]. |

findAmong | findAmong("abcd", "qcx") returns "cd" because 'c' is among "qcx". |

findSkip | If a = "abcde", then
findSkip(a, "x") returns false and leaves a unchanged,
whereas findSkip(a, 'c') advances a to "cde" and
returns true. |

findSplit | findSplit("abcdefg", "de") returns the three ranges "abc", "de", and "fg". |

findSplitAfter | findSplitAfter("abcdefg", "de") returns the two ranges "abcde" and "fg". |

findSplitBefore | findSplitBefore("abcdefg", "de") returns the two ranges "abc" and "defg". |

minCount | minCount([2, 1, 1, 4, 1]) returns tuple(1, 3). |

minPos | minPos([2, 3, 1, 3, 4, 1]) returns the subrange [1, 3, 4, 1], i.e., positions the range at the first occurrence of its minimal element. |

skipOver | Assume a = "blah". Then
skipOver(a, "bi") leaves a unchanged and returns false,
whereas skipOver(a, "bl") advances a to refer to "ah"
and returns true. |

startsWith | startsWith("hello,
world", "hello") returns true. |

until | Lazily iterates a range until a specific value is found. |

cmp | cmp("abc", "abcd") is -1, cmp("abc", aba") is 1, and cmp("abc", "abc") is 0. |

equal | Compares ranges for
element-by-element equality, e.g. equal([1, 2, 3], [1.0, 2.0,
3.0]) returns true. |

levenshteinDistance | levenshteinDistance("kitten", "sitting") returns 3 by using the Levenshtein distance algorithm. |

levenshteinDistanceAndPath | levenshteinDistanceAndPath("kitten", "sitting") returns tuple(3, "snnnsni") by using the Levenshtein distance algorithm. |

max | max(3, 4, 2) returns 4. |

min | min(3, 4, 2) returns 2. |

mismatch | mismatch("oh hi", "ohayo") returns tuple(" hi", "ayo"). |

filter | filter!"a > 0"([1, -1, 2, 0, -3]) iterates over elements 1, 2, and 0. |

filterBidirectional | Similar to filter, but also provides back and popBack at a small increase in cost. |

group | group([5, 2, 2, 3, 3]) returns a range containing the tuples tuple(5, 1), tuple(2, 2), and tuple(3, 2). |

joiner | joiner(["hello", "world!"], ";") returns a range that iterates over the characters "hello; world!". No new string is created - the existing inputs are iterated. |

map | map!"2 * a"([1, 2, 3]) lazily returns a range with the numbers 2, 4, 6. |

reduce | reduce!"a + b"([1, 2, 3, 4]) returns 10. |

splitter | Lazily splits a range by a separator. |

uniq | Iterates over the unique elements in a range, which is assumed sorted. |

completeSort | If a = [10, 20, 30] and b = [40, 6, 15], then completeSort(a, b) leaves a = [6, 10, 15] and b = [20, 30, 40]. The range a must be sorted prior to the call, and as a result the combination std.range.chain(a, b) is sorted. |

isPartitioned | isPartitioned!"a <
0"([-1, -2, 1, 0, 2]) returns true because the predicate is true for a portion of the range and false afterwards. |

isSorted | isSorted([1, 1, 2, 3])
returns true. |

makeIndex | Creates a separate index for a range. |

partialSort | If a = [5, 4, 3, 2, 1], then partialSort(a, 3) leaves a[0 .. 3] = [1, 2, 3]. The other elements of a are left in an unspecified order. |

partition | Partitions a range according to a predicate. |

schwartzSort | Sorts with the help of the Schwartzian transform. |

sort | Sorts. |

topN | Separates the top elements in a range. |

topNCopy | Copies out the top elements of a range. |

largestPartialIntersection | Copies out the values that occur most frequently in a range of ranges. |

largestPartialIntersectionWeighted | Copies out the values that occur most frequently (multiplied by per-value weights) in a range of ranges. |

nWayUnion | Computes the union of a set of sets implemented as a range of sorted ranges. |

setDifference | Lazily computes the set difference of two or more sorted ranges. |

setIntersection | Lazily computes the set difference of two or more sorted ranges. |

setSymmetricDifference | Lazily computes the symmetric set difference of two or more sorted ranges. |

setUnion | Lazily computes the set union of two or more sorted ranges. |

bringToFront | If a = [1, 2, 3] and b = [4, 5, 6, 7], bringToFront(a, b) leaves a = [4, 5, 6] and b = [7, 1, 2, 3]. |

copy | Copies a range to another. If a = [1, 2, 3] and b = new int[5], then copy(a, b) leaves b = [1, 2, 3, 0, 0] and returns b[3 .. $]. |

fill | Fills a range with a pattern, e.g., if a = new int[3], then fill(a, 4) leaves a = [4, 4, 4] and fill(a, [3, 4]) leaves a = [3, 4, 3]. |

initializeAll | If a = [1.2, 3.4], then initializeAll(a) leaves a = [double.init, double.init]. |

move | move(a, b) moves a into b. move(a) reads a destructively. |

moveAll | Moves all elements from one range to another. |

moveSome | Moves as many elements as possible from one range to another. |

reverse | If a = [1, 2, 3], reverse(a) changes it to [3, 2, 1]. |

swap | Swaps two values. |

swapRanges | Swaps all elements of two ranges. |

uninitializedFill | Fills a range (assumed uninitialized) with a value. |

**License:**

Boost License 1.0.

**Authors:**

Andrei Alexandrescu

**Source:**

std/algorithm.d

- auto
__map__(Range)(Range r) if (isInputRange!(Unqual!Range)); Implements the homonym function (also known as transform) present in many languages of functional flavor. The call__map__!(fun)(range) returns a range of which elements are obtained by applying fun(x) left to right for all x in range. The original ranges are not changed. Evaluation is done lazily.**Example:**

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

Multiple functions can be passed to__map__. In that case, the element type of__map__is a tuple containing one element for each function.**Example:**

auto arr1 = [ 1, 2, 3, 4 ]; foreach (e; map!("a + a", "a * a")(arr1)) { writeln(e[0], " ", e[1]); }

You may alias__map__with some function(s) to a symbol and use it separately:alias map!(to!string) stringize; assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));

- auto
__reduce__(Args...)(Args args) if (Args.length > 0 && Args.length <= 2 && isIterable!(Args[$ - 1])); 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. The one-argument version__reduce__!(fun)(range) works similarly, but it uses the first element of the range as the seed (the range must be non-empty). 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); 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); // Chain multiple ranges into seed int[] a = [ 3, 4 ]; int[] b = [ 100 ]; auto r = reduce!("a + b")(chain(a, b)); assert(r == 107); // Mixing convertible types is fair game, too double[] c = [ 2.5, 3.0 ]; auto r1 = reduce!("a + b")(chain(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)(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")(tuple(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);

- Fills range with a filler.
**Example:**

int[] a = [ 1, 2, 3, 4 ]; fill(a, 5); assert(a == [ 5, 5, 5, 5 ]);

- Fills range with a pattern copied from filler. The length of
range does not have to be a multiple of the length of filler. If filler is empty, an exception is thrown.
**Example:**

int[] a = [ 1, 2, 3, 4, 5 ]; int[] b = [ 8, 9 ]; fill(a, b); assert(a == [ 8, 9, 8, 9, 8 ]);

- Fills a range with a value. Assumes that the range does not currently
contain meaningful content. This is of interest for structs that
define copy constructors (for all other types, fill and
__uninitializedFill__are equivalent).**Example:**

struct S { ... } S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5]; uninitializedFill(s, 42); assert(s == [ 42, 42, 42, 42, 42 ]);

- Initializes all elements of a range with their .init
value. Assumes that the range does not currently contain meaningful
content.
**Example:**

struct S { ... } S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5]; initializeAll(s); assert(s == [ 0, 0, 0, 0, 0 ]);

- auto
__filter__(Range)(Range rs) if (isInputRange!(Unqual!Range)); Implements the homonym function present in various programming languages of functional flavor. The call__filter__!(predicate)(range) returns a new range only containing elements x in range for which predicate(x) is**true**.**Example:**

int[] arr = [ 1, 2, 3, 4, 5 ]; // Sum all elements auto small = filter!("a < 3")(arr); assert(equal(small, [ 1, 2 ])); // In combination with chain() to span multiple ranges int[] a = [ 3, -2, 400 ]; int[] b = [ 100, -101, 102 ]; auto r = filter!("a > 0")(chain(a, b)); assert(equal(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")(chain(c, a, b)); assert(equal(r1, [ 2.5 ]));

- auto
__filterBidirectional__(Range)(Range r) if (isBidirectionalRange!(Unqual!Range)); Similar to filter, except it defines a bidirectional range. There is a speed disadvantage - the constructor spends time finding the last element in the range that satisfies the filtering condition (in addition to finding the first one). The advantage is that the filtered range can be spanned from both directions. Also, std.range.retro can be applied against the filtered range.**Example:**

int[] arr = [ 1, 2, 3, 4, 5 ]; auto small = filterBidirectional!("a < 3")(arr); assert(small.back == 2); assert(equal(small, [ 1, 2 ])); assert(equal(retro(small), [ 2, 1 ])); // In combination with chain() to span multiple ranges int[] a = [ 3, -2, 400 ]; int[] b = [ 100, -101, 102 ]; auto r = filterBidirectional!("a > 0")(chain(a, b)); assert(r.back == 102);

- 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:**

&source == &target || !pointsTo(source, source) - If hasAliasing!T is
- For each element a in src and each element b in tgt in lockstep in increasing order, calls move(a, b). Returns
the leftover portion of tgt. Throws an exeption if there is not
enough room in tgt to acommodate all of src.
**Preconditions:**

walkLength(src) <= walkLength(tgt) - For each element a in src and each element b in tgt in lockstep in increasing order, calls move(a, b). Stops when either src or tgt have been exhausted. Returns the leftover portions of the two ranges.
- Swaps lhs and rhs. See also std.exception.pointsTo.
**Preconditions:**

!pointsTo(lhs, lhs) && !pointsTo(lhs, rhs) && !pointsTo(rhs, lhs) && !pointsTo(rhs, rhs) - Forwards function arguments with saving ref-ness.
**Example:**

int foo(int n) { return 1; } int foo(ref int n) { return 2; } int bar()(auto ref int x) { return foo(forward!x); } assert(bar(1) == 1); int i; assert(bar(i) == 2);

void foo(int n, ref string s) { s = null; foreach (i; 0..n) s ~= "Hello"; } // forwards all arguments which are bound to parameter tuple void bar(Args...)(auto ref Args args) { return foo(forward!args); } // forwards all arguments with swapping order void baz(Args...)(auto ref Args args) { return foo(forward!args[$/2..$], forward!args[0..$/2]); } string s; bar(1, s); assert(s == "Hello"); baz(s, 2); assert(s == "HelloHello");

- Splits a range using an element as a separator. This can be used with
any narrow string type or sliceable range type, but is most popular
with string types.
Two adjacent separators are considered to surround an empty element in
the split range.
If the empty range is given, the result is a range with one empty
element. If a range with one separator is given, the result is a range
with two empty elements.
**Example:**

assert(equal(splitter("hello world", ' '), [ "hello", "", "world" ])); int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; int[][] w = [ [1, 2], [], [3], [4, 5] ]; assert(equal(splitter(a, 0), w)); a = null; assert(equal(splitter(a, 0), [ (int[]).init ])); a = [ 0 ]; assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ])); a = [ 0, 1 ]; assert(equal(splitter(a, 0), [ [], [1] ]));

- Splits a range using another range as a separator. This can be used with any narrow string type or sliceable range type, but is most popular with string types.
- Lazily joins a range of ranges with a separator. The separator itself
is a range. If you do not provide a separator, then the ranges are
joined directly without anything in between them.
**Example:**

assert(equal(joiner([""], "xyz"), "")); assert(equal(joiner(["", ""], "xyz"), "xyz")); assert(equal(joiner(["", "abc"], "xyz"), "xyzabc")); assert(equal(joiner(["abc", ""], "xyz"), "abcxyz")); assert(equal(joiner(["abc", "def"], "xyz"), "abcxyzdef")); assert(equal(joiner(["Mary", "has", "a", "little", "lamb"], "..."), "Mary...has...a...little...lamb")); assert(equal(joiner(["abc", "def"]), "abcdef"));

- Iterates unique consecutive elements of the given range (functionality
akin to the uniq system
utility). Equivalence of elements is assessed by using the predicate
pred, by default "a == b". If the given range is
bidirectional,
__uniq__also yields a bidirectional range.**Example:**

int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));

- Similarly to uniq, group iterates unique consecutive
elements of the given range. The element type is Tuple!(ElementType!R, uint) because it includes the count of
equivalent elements seen. Equivalence of elements is assessed by using
the predicate pred, by default "a == b".
__Group__is an input range if R is an input range, and a forward range in all other cases.**Example:**

int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u), tuple(4, 3u), tuple(5, 1u) ][]));

- Finds an individual element in an input range. Elements of haystack are compared with needle by using predicate pred. Performs
**Ο****(**walkLength(haystack)**)**evaluations of pred. See also STL's find. To find the last occurence of needle in haystack, call__find__(retro(haystack), needle). See also std.range.retro.**Parameters:**haystack The range searched in. needle The element searched for. **Constraints:**

isInputRange!R && is(typeof(binaryFun!pred(haystack.front, needle) : bool))**Returns:**

haystack advanced such that binaryFun!pred(haystack.front, needle) is**true**(if no such position exists, returns haystack after exhaustion).**Example:**

assert(find("hello, world", ',') == ", world"); assert(find([1, 2, 3, 5], 4) == []); assert(find(SList!int(1, 2, 3, 4, 5)[], 4) == SList!int(4, 5)[]); assert(find!"a > b"([1, 2, 3, 5], 2) == [3, 5]); auto a = [ 1, 2, 3 ]; assert(find(a, 5).empty); // not found assert(!find(a, 2).empty); // found // Case-insensitive find of a string string[] s = [ "Hello", "world", "!" ]; assert(!find!("toLower(a) == b")(s, "hello").empty);

- Finds a forward range in another. Elements are compared for
equality. Performs
**Ο****(**walkLength(haystack) * walkLength(needle)**)**comparisons in the worst case. Specializations taking advantage of bidirectional or random access (where present) may accelerate search depending on the statistics of the two ranges' content.**Parameters:**haystack The range searched in. needle The range searched for. **Constraints:**

isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front) : bool))**Returns:**

haystack advanced such that needle is a prefix of it (if no such position exists, returns haystack advanced to termination).assert(find("hello, world", "World").empty); assert(find("hello, world", "wo") == "world"); assert(find([1, 2, 3, 4], SList!(2, 3)[]) == [2, 3, 4]);

- Finds two or more needles into a haystack. The predicate pred is used throughout to compare elements. By default, elements are
compared for equality.
**Parameters:**haystack The target of the search. Must be an input range . If any of needles is a range with elements comparable to elements in haystack, then haystack must be a forward range such that the search can backtrack. needles One or more items to search for. Each of needles must be either comparable to one element in haystack, or be itself a forward range with elements comparable with elements in haystack. **Returns:**

A tuple containing haystack positioned to match one of the needles and also the 1-based index of the matching element in needles (0 if none of needles matched, 1 if needles[0] matched, 2 if needles[1] matched...). The first needle to be found will be the one that matches. If multiple needles are found at the same spot in the range, then the shortest one is the one which matches (if multiple needles of the same length are found at the same spot (e.g "a" and 'a'), then the left-most of them in the argument list matches). The relationship between haystack and needles simply means that one can e.g. search for individual ints or arrays of ints in an array of ints. In addition, if elements are individually comparable, searches of heterogeneous types are allowed as well: a double[] can be searched for an int or a short[], and conversely a long can be searched for a float or a double[]. This makes for efficient searches without the need to coerce one side of the comparison into the other's side type.**Example:**

int[] a = [ 1, 4, 2, 3 ]; assert(find(a, 4) == [ 4, 2, 3 ]); assert(find(a, [ 1, 4 ]) == [ 1, 4, 2, 3 ]); assert(find(a, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2)); // Mixed types allowed if comparable assert(find(a, 5, [ 1.2, 3.5 ], 2.0, [ 1 ]) == tuple([ 2, 3 ], 3));

The complexity of the search is**Ο****(**haystack.length * max(needles.length)**)**. (For needles that are individual items, length is considered to be 1.) The strategy used in searching several subranges at once maximizes cache usage by moving in haystack as few times as possible. - Advances the input range haystack by calling haystack.popFront
until either pred(haystack.front), or haystack.empty. Performs
**Ο****(**haystack.length**)**evaluations of pred. See also STL's find_if. To__find__the last element of a bidirectional haystack satisfying pred, call__find__!(pred)(retro(haystack)). See also std.range.retro.**Example:**

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

- If needle occurs in haystack, positions haystack
right after the first occurrence of needle and returns
**true**. Otherwise, leaves haystack as is and returns**false**.**Example:**

string s = "abcdef"; assert(findSkip(s, "cd") && s == "ef"); s = "abcdef"; assert(!findSkip(s, "cxd") && s == "abcdef"); assert(findSkip(s, "def") && s.empty);

- These functions find the first occurrence of needle in haystack and then split haystack as follows.
__findSplit__returns a tuple result containing*three*ranges. result[0] is the portion of haystack before needle, result[1] is the portion of haystack that matches needle, and result[2] is the portion of haystack after the match. If needle was not found, result[0] comprehends haystack entirely and result[1] and result[2] are empty. findSplitBefore returns a tuple result containing two ranges. result[0] is the portion of haystack before needle, and result[1] is the balance of haystack starting with the match. If needle was not found, result[0] comprehends haystack entirely and result[1] is empty. findSplitAfter returns a tuple result containing two ranges. result[0] is the portion of haystack up to and including the match, and result[1] is the balance of haystack starting after the match. If needle was not found, result[0] is empty and result[1] is haystack. In all cases, the concatenation of the returned ranges spans the entire haystack. If haystack is a random-access range, all three components of the tuple have the same type as haystack. Otherwise, haystack must be a forward range and the type of result[0] and result[1] is the same as std.range.takeExactly.**Example:**

auto a = "Carl Sagan Memorial Station"; auto r = findSplit(a, "Velikovsky"); assert(r[0] == a); assert(r[1].empty); assert(r[2].empty); r = findSplit(a, " "); assert(r[0] == "Carl"); assert(r[1] == " "); assert(r[2] == "Sagan Memorial Station"); auto r1 = findSplitBefore(a, "Sagan"); assert(r1[0] == "Carl ", r1[0]); assert(r1[1] == "Sagan Memorial Station"); auto r2 = findSplitAfter(a, "Sagan"); assert(r2[0] == "Carl Sagan"); assert(r2[1] == " Memorial Station");

- Returns the number of elements which must be popped from the front of
haystack before reaching an element for which
startsWith!pred(haystack, needle) is
**true**. If startsWith!pred(haystack, needle) is not**true**for any element in haystack, then -1 is returned. needle may be either an element or a range.**Examples:**assert(countUntil("hello world", "world") == 6); assert(countUntil("hello world", 'r') == 8); assert(countUntil("hello world", "programming") == -1); assert(countUntil("æ—¥æœ¬èªž", "æœ¬èªž") == 1); assert(countUntil("æ—¥æœ¬èªž", 'èªž') == 2); assert(countUntil("æ—¥æœ¬èªž", "äº”") == -1); assert(countUntil("æ—¥æœ¬èªž", 'äº”') == -1); assert(countUntil([0, 7, 12, 22, 9], [12, 22]) == 2); assert(countUntil([0, 7, 12, 22, 9], 9) == 4); assert(countUntil!"a > b"([0, 7, 12, 22, 9], 20) == 3);

- Returns the number of elements which must be popped from haystack
before pred(haystack.front) is
**true**.**Examples:**assert(countUntil!(std.uni.isWhite)("hello world") == 5); assert(countUntil!(std.ascii.isDigit)("hello world") == -1); assert(countUntil!"a > 20"([0, 7, 12, 22, 9]) == 3);

- Deprecated. It will be removed in January 2013.
Currently defaults to countUntil instead.
Not to be confused with its homonym function
in std.string.
Please use std.string.
__indexOf__if you wish to find the index of a character in a string. Otherwise, please use std.string.countUntil to find an element's logical position in a range.**Example:**

assert(std.string.indexOf("æ—¥æœ¬èªž", 'æœ¬') == 3); assert(std.algorithm.countUntil("æ—¥æœ¬èªž", 'æœ¬') == 1);

- Interval option specifier for until (below) and others.
- Interval is closed to the right (last element included)
- Interval is open to the right (last element is not included)

- struct
__Until__(alias pred, Range, Sentinel) if (isInputRange!(Range));

Until!(pred, Range, Sentinel)__until__(alias pred = "a == b", Range, Sentinel)(Range*range*, Sentinel*sentinel*, OpenRight*openRight*= OpenRight.yes);

Until!(pred, Range, void)__until__(alias pred, Range)(Range*range*, OpenRight*openRight*= OpenRight.yes); - Lazily iterates range until value sentinel is found, at
which point it stops.
**Example:**

int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5]; assert(equal(a.until(7), [1, 2, 4][])); assert(equal(a.until(7, OpenRight.no), [1, 2, 4, 7][]));

- If the range doesThisStart starts with
*any*of the withOneOfThese ranges or elements, returns 1 if it starts with withOneOfThese[0], 2 if it starts with withOneOfThese[1], and so on. If none match, returns 0. In the case where doesThisStart starts with multiple of the ranges or elements in withOneOfThese, then the shortest one matches (if there are two which match which are of the same length (e.g. "a" and 'a'), then the left-most of them in the argument list matches).**Example:**

assert(startsWith("abc", "")); assert(startsWith("abc", "a")); assert(!startsWith("abc", "b")); assert(startsWith("abc", 'a', "b") == 1); assert(startsWith("abc", "b", "a") == 2); assert(startsWith("abc", "a", "a") == 1); assert(startsWith("abc", "ab", "a") == 2); assert(startsWith("abc", "x", "a", "b") == 2); assert(startsWith("abc", "x", "aa", "ab") == 3); assert(startsWith("abc", "x", "aaa", "sab") == 0); assert(startsWith("abc", "x", "aaa", "a", "sab") == 3);

- If startsWith(r1, r2), consume the corresponding elements off r1 and return
**true**. Otherwise, leave r1 unchanged and return**false**. - Checks whether a range starts with an element, and if so, consume that
element off r and return
**true**. Otherwise, leave r unchanged and return**false**. - The reciprocal of startsWith.
**Example:**

assert(endsWith("abc", "")); assert(!endsWith("abc", "b")); assert(endsWith("abc", "a", 'c') == 2); assert(endsWith("abc", "c", "a") == 1); assert(endsWith("abc", "c", "c") == 1); assert(endsWith("abc", "bc", "c") == 2); assert(endsWith("abc", "x", "c", "b") == 2); assert(endsWith("abc", "x", "aa", "bc") == 3); assert(endsWith("abc", "x", "aaa", "sab") == 0); assert(endsWith("abc", "x", "aaa", 'c', "sab") == 3);

- Returns the common prefix of two ranges. Example:
assert(commonPrefix("hello, world", "hello, there") == "hello, ");

The type of the result is the same as takeExactly(r1, n), where n is the number of elements that both ranges start with. - Advances r until it finds the first two adjacent elements a,
b 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 r = findAdjacent(a); assert(r == [ 10, 10, 9, 8, 8, 7, 8, 9 ]); p = findAdjacent!("a < b")(a); assert(p == [ 7, 8, 9 ]);

- Advances seq by calling seq.popFront until either find!(pred)(choices, seq.front) is
**true**, or seq becomes empty. 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) == a[2 .. $]);

- The first version 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. The second version returns the number of times needle occurs in haystack. Throws an exception if needle.empty, as the count of the empty range in any range would be infinite. Overlapped counts are not considered, for example__count__("aaa", "aa") is 1, not 2. The third version counts the elements for which pred(x) is**true**. Performs**Ο****(**r.length**)**evaluations of pred.**Note:**

Regardless of the overload,__count__will not accept infinite ranges for haystack.**Example:**

// count elements in range int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; assert(count(a, 2) == 3); assert(count!("a > b")(a, 2) == 5); // count range in range assert(count("abcadfabf", "ab") == 2); assert(count("ababab", "abab") == 1); assert(count("ababab", "abx") == 0); // fuzzy count range in range assert(count!"std.uni.toLower(a) == std.uni.toLower(b)"("AbcAdFaBf", "ab") == 2); // count predicate in range assert(count!("a > 1")(a) == 8);

- Checks whether r has "balanced parentheses", i.e. all instances
of lPar are closed by corresponding instances of rPar. The
parameter maxNestingLevel controls the nesting level allowed. The
most common uses are the default or 0. In the latter case, no
nesting is allowed.
**Example:**

auto s = "1 + (2 * (3 + 1 / 2)"; assert(!balancedParens(s, '(', ')')); s = "1 + (2 * (3 + 1) / 2)"; assert(balancedParens(s, '(', ')')); s = "1 + (2 * (3 + 1) / 2)"; assert(!balancedParens(s, '(', ')', 1)); s = "1 + (2 * 3 + 1) / (2 - 5)"; assert(balancedParens(s, '(', ')', 1));

- 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.0, 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));

- Performs three-way lexicographical comparison on two input ranges
according to predicate pred. Iterating r1 and r2 in
lockstep,
__cmp__compares each element e1 of r1 with the corresponding element e2 in r2. If binaryFun!pred(e1, e2),__cmp__returns a negative value. If binaryFun!pred(e2, e1),__cmp__returns a positive value. If one of the ranges has been finished,__cmp__returns a negative value if r1 has fewer elements than r2, a positive value if r1 has more elements than r2, and 0 if the ranges have the same number of elements. If the ranges are strings,__cmp__performs UTF decoding appropriately and compares the ranges one code point at a time. - 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);

- Returns the minimum element of a range together with the number of
occurrences. The function can actually be used for counting the
maximum or any other ordering predicate (that's why maxCount is
not provided).
**Example:**

int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; // Minimum is 1 and occurs 3 times assert(minCount(a) == tuple(1, 3)); // Maximum is 4 and occurs 2 times assert(minCount!("a > b")(a) == tuple(4, 2));

- Returns the position of the minimum element of forward range range, i.e. a subrange of range starting at the position of its
smallest element and with the same ending as range. The function
can actually be used for counting the maximum or any other ordering
predicate (that's why maxPos is not provided).
**Example:**

int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; // Minimum is 1 and first occurs in position 3 assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]); // Maximum is 4 and first occurs in position 2 assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 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 reduced ranges that start with 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.0, 5, 2, 7.3, 4, 8 ]; auto m = mismatch(x, y); assert(m[0] == x[3 .. $]); assert(m[1] == y[3 .. $]);

- 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.- 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!("std.uni.toUpper(a) == std.uni.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(equal(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
__copy__(retro(source), retro(target)). See also std.range.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);

To__copy__at most n elements from range a to range b, you may want to use__copy__(take(a, n), b). To__copy__those elements from range a that satisfy predicate pred to range b, you may want to use__copy__(filter!(pred)(a), b).**Example:**

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

- Swaps all elements of r1 with successive elements in r2.
Returns a tuple containing the remainder portions of r1 and r2 that were not swapped (one of them will be empty). The ranges may
be of different types but must have the same element type and support
swapping.
**Example:**

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

- Reverses r in-place. Performs r.length / 2 evaluations of swap. See also STL's reverse.
**Example:**

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

- Reverses r in-place, where r is a narrow string (having
elements of type char or wchar). UTF sequences consisting of
multiple code units are preserved properly.
**Example:**

char[] arr = "hello\U00010143\u0100\U00010143".dup; reverse(arr); assert(arr == "\U00010143\u0100\U00010143olleh");

- The
__bringToFront__function has considerable flexibility and usefulness. It can rotate elements in one buffer left or right, swap buffers of equal length, and even move elements across disjoint buffers of different types and different lengths.__bringToFront__takes two ranges front and back, which may be of different types. Considering the concatenation of front and back one unified range,__bringToFront__rotates that unified range such that all elements in back are brought to the beginning of the unified range. The relative ordering of elements in front and back, respectively, remains unchanged. The simplest use of__bringToFront__is for rotating elements in a buffer. For example:auto arr = [4, 5, 6, 7, 1, 2, 3]; bringToFront(arr[0 .. 4], arr[4 .. $]); assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ]);

The front range may actually "step over" the back range. This is very useful with forward ranges that cannot compute comfortably right-bounded subranges like arr[0 .. 4] above. In the example below, r2 is a right subrange of r1.auto list = SList!(int)(4, 5, 6, 7, 1, 2, 3); auto r1 = list[]; auto r2 = list[]; popFrontN(r2, 4); assert(equal(r2, [ 1, 2, 3 ])); bringToFront(r1, r2); assert(equal(list[], [ 1, 2, 3, 4, 5, 6, 7 ]));

Elements can be swapped across ranges of different types:auto list = SList!(int)(4, 5, 6, 7); auto vec = [ 1, 2, 3 ]; bringToFront(list[], vec); assert(equal(list[], [ 1, 2, 3, 4 ])); assert(equal(vec, [ 5, 6, 7 ]));

Performs**Ο****(**max(front.length, back.length)**)**evaluations of swap. See also STL's rotate.**Preconditions:**

Either front and back are disjoint, or back is reachable from front and front is not reachable from back.**Returns:**

The number of elements brought to the front, i.e., the length of back. - 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.- 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.

- Eliminates elements at given offsets from range and returns the
shortened range. In the simplest call, one element is removed.
int[] a = [ 3, 5, 7, 8 ]; assert(remove(a, 1) == [ 3, 7, 8 ]); assert(a == [ 3, 7, 8, 8 ]);

In the case above the element at offset 1 is removed and__remove__returns the range smaller by one element. The original array has remained of the same length because all functions in std.algorithm only change*content*, not*topology*. The value 8 is repeated because std.algorithm.move was invoked to move elements around and on integers move simply copies the source to the destination. To replace a with the effect of the removal, simply assign a =__remove__(a, 1). The slice will be rebound to the shorter array and the operation completes with maximal efficiency. Multiple indices can be passed into__remove__. In that case, elements at the respective indices are all removed. The indices must be passed in increasing order, otherwise an exception occurs.int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]; assert(remove(a, 1, 3, 5) == [ 0, 2, 4, 6, 7, 8, 9, 10 ]);

(Note how all indices refer to slots in the*original*array, not in the array as it is being progressively shortened.) Finally, any combination of integral offsets and tuples composed of two integral offsets can be passed in.int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]; assert(remove(a, 1, tuple(3, 5), 9) == [ 0, 2, 6, 7, 8, 10 ]);

In this case, the slots at positions 1, 3, 4, and 9 are removed from the array. The tuple passes in a range closed to the left and open to the right (consistent with built-in slices), e.g. tuple(3, 5) means indices 3 and 4 but not 5. If the need is to__remove__some elements in the range but the order of the remaining elements does not have to be preserved, you may want to pass SwapStrategy.unstable to__remove__.int[] a = [ 0, 1, 2, 3 ]; assert(remove!(SwapStrategy.unstable)(a, 1) == [ 0, 3, 2 ]);

In the case above, the element at slot 1 is removed, but replaced with the last element of the range. Taking advantage of the relaxation of the stability requirement,__remove__moved elements from the end of the array over the slots to be removed. This way there is less data movement to be done which improves the execution time of the function. The function__remove__works on any forward range. The moving strategy is (listed from fastest to slowest):- If s == SwapStrategy.unstable && isRandomAccessRange!Range && hasLength!Range, then elements are moved from the end of the range into the slots to be filled. In this case, the absolute minimum of moves is performed.
- Otherwise, if s == SwapStrategy.unstable && isBidirectionalRange!Range && hasLength!Range, then elements are still moved from the end of the range, but time is spent on advancing between slots by repeated calls to range.popFront.
- Otherwise, elements are moved incrementally towards the front of range; a given element is never moved several times, but more elements are moved than in the previous cases.

- Reduces the length of the bidirectional range range by removing
elements that satisfy pred. If s = SwapStrategy.unstable,
elements are moved from the right end of the range over the elements
to eliminate. If s = SwapStrategy.stable (the default),
elements are moved progressively to front such that their relative
order is preserved. Returns the filtered range.
**Example:**

int[] a = [ 1, 2, 3, 2, 3, 4, 5, 2, 5, 6 ]; assert(remove!("a == 2")(a) == [ 1, 3, 3, 4, 5, 5, 6 ]);

- Partitions a range in two using pred as a
predicate. Specifically, reorders the range r = [left,
right) using swap 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 swap. The unstable version computes the minimum possible evaluations of swap (roughly half of those performed by the semistable version). See also STL's partition and stable_partition.**Returns:**

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 pred(a) == pred(b). If ss == SwapStrategy.semistable,__partition__preserves the relative ordering of all elements a, b in the left part of r 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 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 .. $]);

- Returns
**true**if r is partitioned according to predicate pred.**Example:**

int[] r = [ 1, 3, 5, 7, 8, 2, 4, ]; assert(isPartitioned!("a & 1")(r));

- Rearranges elements in r in three adjacent ranges and returns
them. The first and leftmost range only contains elements in r
less than pivot. The second and middle range only contains
elements in r that are equal to pivot. Finally, the third
and rightmost range only contains elements in r that are greater
than pivot. The less-than test is defined by the binary function
less.
**Example:**

auto a = [ 8, 3, 4, 1, 4, 7, 4 ]; auto pieces = partition3(a, 4); assert(a == [ 1, 3, 4, 4, 4, 7, 8 ]); assert(pieces[0] == [ 1, 3 ]); assert(pieces[1] == [ 4, 4, 4 ]); assert(pieces[2] == [ 7, 8 ]);

BUGS:

stable__partition3__has not been implemented yet. - Reorders the range r using swap such that r[nth] refers
to the element that would fall there if the range were fully
sorted. In addition, it also partitions r such that all elements
e1 from r[0] to r[nth] satisfy !less(r[nth], e1),
and all elements e2 from r[nth] to r[r.length] satisfy
!less(e2, r[nth]). Effectively, it finds the nth smallest
(according to less) elements in r. Performs
**Ο****(**r.length**)**(if unstable) or**Ο****(**r.length * log(r.length)**)**(if stable) evaluations of less and swap. See also STL's nth_element.**Example:**

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

BUGS:

Stable__topN__has not been implemented yet. - Stores the smallest elements of the two ranges in the left-hand range.
- Sorts a random-access range according to the 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 swap. See also STL's sort and stable_sort.__sort__returns a std.range.SortedRange over the original range, which functions that can take advantage of sorted data can then use to know that the range is sorted and adjust accordingly. The std.range.SortedRange is a wrapper around the original range, so both it and the original range are sorted, but other functions won't know that the original range has been sorted, whereas they*can*know that std.range.SortedRange has been sorted.**See Also:**

std.range.assumeSorted**Remark:**

Stable__sort__is implementated as Timsort, the original code at XSort by Xinok, public domain.**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
__multiSort__(Range)(Range r) if (validPredicates!(ElementType!Range, less)); Sorts a range by multiple keys. The call__multiSort__!("a.id < b.id", "a.date > b.date")(r) sorts the range r by id ascending, and sorts elements that have the same id by date descending. Such a call is equivalent to sort!"a.id != b.id ? a.id < b.id : a.date > b.date"(r), but__multiSort__is faster because it does fewer comparisons (in addition to being more convenient).**Example:**

static struct Point { int x, y; } auto pts1 = [ Point(0, 0), Point(5, 5), Point(0, 1), Point(0, 2) ]; auto pts2 = [ Point(0, 0), Point(0, 1), Point(0, 2), Point(5, 5) ]; multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable)(pts1); assert(pts1 == pts2);

- 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. To check whether an array was sorted and benefit of the speedup of Schwartz sorting, a function schwartzIsSorted is not provided because the effect can be achieved by calling isSorted!less(map!transform(r)). - Reorders the random-access range r such that the range r[0
.. mid] is the same as if the entire r were sorted, and leaves
the range r[mid .. r.length] in no particular order. Performs
**Ο****(**r.length * log(mid)**)**evaluations of pred. The implementation simply calls topN!(less, ss)(r, n) and then sort!(less, ss)(r[0 .. n]).**Example:**

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

- Sorts the random-access range chain(lhs, rhs) according to
predicate less. The left-hand side of the range lhs is
assumed to be already sorted; rhs is assumed to be unsorted. The
exact strategy chosen depends on the relative sizes of lhs and
rhs. Performs
**Ο****(**lhs.length + rhs.length * log(rhs.length)**)**(best case) to**Ο****(**(lhs.length + rhs.length) * log(lhs.length + rhs.length)**)**(worst-case) evaluations of swap.**Example:**

int[] a = [ 1, 2, 3 ]; int[] b = [ 4, 0, 6, 5 ]; completeSort(assumeSorted(a), b); assert(a == [ 0, 1, 2 ]); assert(b == [ 3, 4, 5, 6 ]);

- Checks whether a forward 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));

- Computes an index for r based on the comparison less. The
index is a sorted array of pointers or indices into the original
range. This technique is similar to sorting, but it is more flexible
because (1) it allows "sorting" of immutable collections, (2) allows
binary search even if the original collection does not offer random
access, (3) allows multiple indexes, each on a different predicate,
and (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 the same as sort's.
__makeIndex__overwrites its second argument with the result, but never reallocates it. If the second argument's length is less than that of the range indexed, an exception is thrown. The first overload of__makeIndex__writes to a range containing pointers, and the second writes to a range containing offsets. The first overload requires Range to be a forward range, and the latter requires it to be a random-access range.**Example:**

immutable(int[]) arr = [ 2, 3, 1, 5, 0 ]; // index using pointers auto index1 = new immutable(int)*[arr.length]; makeIndex!("a < b")(arr, index1); assert(isSorted!("*a < *b")(index1)); // index using offsets auto index2 = new size_t[arr.length]; makeIndex!("a < b")(arr, index2); assert(isSorted! ((size_t a, size_t b){ return arr[a] < arr[b];}) (index2));

- Specifies whether the output of certain algorithm is desired in sorted
format.
- Don't sort output
- Sort output

- Returns
**true**if and only if value can be found in range. Performs**Ο****(**needle.length**)**evaluations of pred. - Returns the 1-based index of the first needle found in haystack. If no
needle is found, then 0 is returned.
So, if used directly in the condition of an if statement or loop, the result
will be
**true**if one of the needles is found and**false**if none are found, whereas if the result is used elsewhere, it can either be cast to bool for the same effect or used to get which needle was found first without having to deal with the tuple that LREF find returns for the same operation. - Returns
**true**if and only if a value v satisfying the predicate pred can be found in the forward range range. Performs**Ο****(**r.length**)**evaluations of pred. - Returns
**true**if and only if__all__values in range satisfy the predicate pred. Performs**Ο****(**r.length**)**evaluations of pred.**Examples:**assert(all!"a & 1"([1, 3, 5, 7, 9])); assert(!all!"a & 1"([1, 2, 3, 5, 7, 9]));

- Copies the top n elements of the input range source into the
random-access range target, where n =
target.length. Elements of source are not touched. If sorted is
**true**, the target is sorted. Otherwise, the target respects the heap property.**Example:**

int[] a = [ 10, 16, 2, 3, 1, 5, 0 ]; int[] b = new int[3]; topNCopy(a, b, true); assert(b == [ 0, 1, 2 ]);

- Lazily computes the union of two or more ranges rs. The ranges
are assumed to be sorted by less. Elements in the output are not
unique; the length of the output is the sum of the lengths of the
inputs. (The length member is offered if all ranges also have
length.) The element types of all ranges must have a common type.
**Example:**

int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; int[] c = [ 10 ]; assert(setUnion(a, b).length == a.length + b.length); assert(equal(setUnion(a, b), [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9][])); assert(equal(setUnion(a, c, b), [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9, 10][]));

- Lazily computes the intersection of two or more input ranges rs. The ranges are assumed to be sorted by less. The element
types of all ranges must have a common type.
**Example:**

int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; int[] c = [ 0, 1, 4, 5, 7, 8 ]; assert(equal(setIntersection(a, a), a)); assert(equal(setIntersection(a, b), [1, 2, 4, 7][])); assert(equal(setIntersection(a, b, c), [1, 4, 7][]));

- Lazily computes the difference of r1 and r2. The two ranges
are assumed to be sorted by less. The element types of the two
ranges must have a common type.
**Example:**

int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; assert(equal(setDifference(a, b), [5, 9][]));

- Lazily computes the symmetric difference of r1 and r2,
i.e. the elements that are present in exactly one of r1 and r2. The two ranges are assumed to be sorted by less, and the
output is also sorted by less. The element types of the two
ranges must have a common type.
**Example:**

int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; assert(equal(setSymmetricDifference(a, b), [0, 5, 8, 9][]));

- Computes the union of multiple sets. The input sets are passed as a
range of ranges and each is assumed to be sorted by less. Computation is done lazily, one union element at a time. The
complexity of one popFront operation is
**Ο****(**log(ror.length)**)**. However, the length of ror decreases as ranges in it are exhausted, so the complexity of a full pass through__NWayUnion__is dependent on the distribution of the lengths of ranges contained within ror. If all ranges have the same length n (worst case scenario), the complexity of a full pass through__NWayUnion__is**Ο****(**n * ror.length * log(ror.length)**)**, i.e., log(ror.length) times worse than just spanning all ranges in turn. The output comes sorted (unstably) by less.**Warning:**

Because__NWayUnion__does not allocate extra memory, it will leave ror modified. Namely,__NWayUnion__assumes ownership of ror and discretionarily swaps and advances elements of it. If you want ror to preserve its contents after the call, you may want to pass a duplicate to__NWayUnion__(and perhaps cache the duplicate in between calls).**Example:**

double[][] a = [ [ 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ], ]; auto witness = [ 1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8 ]; assert(equal(nWayUnion(a), witness[]));

- Given a range of sorted forward ranges ror, copies to tgt
the elements that are common to most ranges, along with their number
of occurrences. All ranges in ror are assumed to be sorted by less. Only the most frequent tgt.length elements are returned.
**Example:**

// Figure which number can be found in most arrays of the set of // arrays below. double[][] a = [ [ 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ], ]; auto b = new Tuple!(double, uint)[1]; largestPartialIntersection(a, b); // First member is the item, second is the occurrence count assert(b[0] == tuple(7.0, 4u));

7.0 is the correct answer because it occurs in 4 out of the 5 inputs, more than any other number. The second member of the resulting tuple is indeed 4 (recording the number of occurrences of 7.0). If more of the top-frequent numbers are needed, just create a larger tgt range. In the axample above, creating b with length 2 yields tuple(1.0, 3u) in the second position. The function__largestPartialIntersection__is useful for e.g. searching an inverted index for the documents most likely to contain some terms of interest. The complexity of the search is**Ο****(**n * log(tgt.length)**)**, where n is the sum of lengths of all input ranges. This approach is faster than keeping an associative array of the occurrences and then selecting its top items, and also requires less memory (__largestPartialIntersection__builds its result directly in tgt and requires no extra memory).**Warning:**

Because__largestPartialIntersection__does not allocate extra memory, it will leave ror modified. Namely,__largestPartialIntersection__assumes ownership of ror and discretionarily swaps and advances elements of it. If you want ror to preserve its contents after the call, you may want to pass a duplicate to__largestPartialIntersection__(and perhaps cache the duplicate in between calls). - Similar to largestPartialIntersection, but associates a weight
with each distinct element in the intersection.
**Example:**

// Figure which number can be found in most arrays of the set of // arrays below, with specific per-element weights double[][] a = [ [ 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ], ]; auto b = new Tuple!(double, uint)[1]; double[double] weights = [ 1:1.2, 4:2.3, 7:1.1, 8:1.1 ]; largestPartialIntersectionWeighted(a, b, weights); // First member is the item, second is the occurrence count assert(b[0] == tuple(4.0, 2u));

The correct answer in this case is 4.0, which, although only appears two times, has a total weight 4.6 (three times its weight 2.3). The value 7 is weighted with 1.1 and occurs four times for a total weight 4.4.