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 implicitSome functions are additionally parameterized with primitives such as move (defaulting to std.algorithm.move) or iterSwap primitive (defaulting to std.algorithm.iterSwap). These parameters distill the way in which data is manipulated, and the algorithms guarantee they only use them to touch values. There is sometimes a need to override that default behavior. Possible uses include notifying observers, counting the number of operations, or manipulating multiple collections in lockstep.
- Implements the homonym function (also known as transform) present
in many languages of functional flavor. The 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[]));
- 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
- 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)));
- 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 ]);
- 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 ]);
- Moves source into target via a destructive
copy. Specifically:
- If hasAliasing!(T) is true (see std.traits.hasAliasing), then the representation of source is bitwise copied into target and then source = T.init is evaluated.
- Otherwise, target = source is evaluated.
Preconditions:
!pointsTo(source, source)
- Swaps lhs and rhs. See also std.contracts.pointsTo.
Preconditions:
!pointsTo(lhs, lhs) && !pointsTo(lhs, rhs) && !pointsTo(rhs, lhs) && !pointsTo(rhs, rhs)
- Reduces r by shifting it to the left until no adjacent elements
a, b remain in r such that pred(a, b). Shifting is
performed by evaluating move(source, target) as a primitive. The
algorithm is stable and runs in Ο(r.length) time. Returns the
reduced range.
The default std.algorithm.move performs a potentially destructive assignment of source to target, so the objects beyond the returned range should be considered "empty". By default pred compares for equality, in which 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 ]);
- 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));
- 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));
- Finds the first occurrence of subseq in seq by repeated
linear searches. Performs Ο(seq.length * subseq.length)
evaluations of pred, which makes it unrecommended for very large
ranges, for which std.algorithm.findBoyerMoore may be more
appropriate. See also STL's
search.
Example:
int[] a = [ -1, 0, 1, 2, 3, 4, 5 ]; int[] b = [ 1, 2, 3 ]; assert(findRange(a, b) == begin(a) + 2); assert(findRange(b, a) == end(b));
- Finds the first occurrence of subseq in seq by using the
Boyer-Moore
algorithm. The algorithm has an upfront cost but scales sublinearly,
so it is most suitable for large sequences. Performs Ο(seq.length) evaluations of pred in the worst case and Ο(seq.length / subseq.length) evaluations in the best case.
Example:
int[] a = [ -1, 0, 1, 2, 3, 4, 5 ]; int[] b = [ 1, 2, 3 ]; assert(findBoyerMoore(a, b) == begin(a) + 2); assert(findBoyerMoore(b, a) == end(b));
BUGS:
Should cache the scaffolding built for the last subseq in thread-safe storage so it is not rebuilt repeatedly.
- Finds the first two adjacent elements a, b in the range r that satisfy pred(a, b). Performs Ο(r.length)
evaluations of pred. See also STL's adjacent_find.
Example:
int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ]; auto p = findAdjacent(a); assert(p == begin(a) + 1); p = findAdjacent!("a < b")(a); assert(p == begin(a) + 6);
- Finds the first element in seq that compares equal (according to
pred) with some element in choices. Choices are sought by
linear search. Performs Ο(seq.length * choices.length)
evaluations of pred. See also STL's find_first_of.
Example:
int[] a = [ -1, 0, 1, 2, 3, 4, 5 ]; int[] b = [ 3, 1, 2 ]; assert(findAmong(a, b) == begin(a) + 2); assert(findAmong(b, a) == begin(b));
- Finds the first element x in seq that compares equal with
some element y in choices (meaning !less(x, y) &&
!less(y, x)). The choices range is sought by binary
search. Consequently choices is assumed to be sorted according to
pred, which by default is "a < b". Performs Ο(seq.length * log(choices.length)) evaluations of less.
To find the last element of seq instead of the first, 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));
- 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));
- Counts the number of elements x in r for which pred(x,
value) is true. pred defaults to equality. Performs Ο(r.length) evaluations of pred.
Example:
int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; assert(count(a, 2) == 3); assert(count!("a > b")(a, 2) == 5);
- Counts the number of elements x in r for which pred(x)
is 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);
- 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));
- Returns the minimum of the passed-in values. The type of the result is
computed by using std.traits.CommonType.
- Returns the maximum of the passed-in values. The type of the result is
computed by using std.traits.CommonType.
Example:
int a = 5; short b = 6; double c = 2; auto d = max(a, b); assert(is(typeof(d) == int)); assert(d == 6); auto e = min(a, b, c); assert(is(typeof(e) == double)); assert(e == 2);
- Sequentially compares elements in r1 and r2 in lockstep, and
stops at the first mismatch (according to pred, by default
equality). Returns a tuple with the iterators that refer to the two
mismatched values. Performs Ο(min(r1.length, r2.length))
evaluations of pred. See also STL's mismatch.
Example:
int[] x = [ 1, 5, 2, 7, 4, 3 ]; double[] y = [ 1., 5, 2, 7.3, 4, 8 ]; auto m = mismatch(x, y); assert(m._0 == begin(x) + 3); assert(m._1 == begin(y) + 3);
- Encodes edit operations necessary to transform one sequence into
another. Given sequences s (source) and t (target), a
sequence 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!("toupper(a) == toupper(b)") ("parks", "SPARK") == 2);
- Returns the Levenshtein distance and the edit path between s and
t.
Example:
string a = "Saturday", b = "Sunday"; auto p = levenshteinDistanceAndPath(a, b); assert(p._0, 3); assert(equals(p._1, "nrrnsnnn"));
- Copies the content of source into target and returns the
remaining (unfilled) part of target. See also STL's copy. If a behavior similar to
STL's copy_backward is
needed, use 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);
- Copies in increasing order the elements x of source
satisfying pred(x) into target and returns the remaining
(unfilled) part of target. See also STL's copy_if.
Example:
int[] a = [ 1, 5, 8, 9, 10, 1, 2, 0 ]; auto b = new int[a.length]; auto c = copyIf!("(a & 1) == 1")(a, b); assert(b[0 .. $ - c.length] == [ 1, 5, 9, 1 ]);
As long as the target range elements support assignment from source range elements, different types of ranges are accepted.
Example:
float[] a = [ 1.0f, 5, -3, -5, 0, 4, -3 ]; double[] b = new double[a.length]; auto d = copyIf!("a > 0")(a, b); assert(a == [ 1.0f, 5, 0, 4 ]);
- Swaps *lhs and *rhs.
Preconditions:
Same as for swap(*lhs, *rhs).
- Swaps all elements of r1 with successive elements in r2
using iterSwap as a primitive. r1 must contain less or the
same number of elements as r2; an exception will be thrown
otherwise. Returns the tail portion of r2 that was not swapped.
Example:
int[] a = [ 100, 101, 102, 103 ]; int[] b = [ 0, 1, 2, 3 ]; auto c = swapRanges(a[1 .. 2], b[2 .. 3]); assert(!c.length); assert(a == [ 100, 2, 3, 103 ]); assert(b == [ 0, 1, 101, 102 ]);
- Reverses r in-place. Performs r.length evaluations of iterSwap. See also STL's
reverse.
Example:
int[] arr = [ 1, 2, 3 ]; reverse(arr); assert(arr == [ 3, 2, 1 ]);
- Rotates the range r = [first, last) such that the slice
[middle, last) gets moved in front of the slice [first, middle). Performs Ο(r.length) evaluations of
iterSwap. See also STL's
rotate.
Preconditions:
first <= middle && middle <= last;
Returns:
The position in which first has been rotated.
Example:
auto arr = [4, 5, 6, 7, 1, 2, 3]; auto p = rotate(arr, begin(arr) + 4); assert(p - begin(arr) == 3); assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ]);
- Defines the swapping strategy for algorithms that need to swap
elements in a range (such as partition and sort). The strategy
concerns the swapping of elements that are not the core concern of the
algorithm. For example, consider an algorithm that sorts [ "abc",
"b", "aBc" ] according to toupper(a) < toupper(b). That
algorithm might choose to swap the two equivalent strings "abc"
and "aBc". That does not affect the sorting since both [
"abc", "aBc", "b" ] and [ "aBc", "abc", "b" ] are valid
outcomes.
Some situations require that the algorithm must NOT ever change the relative ordering of equivalent elements (in the example above, only [ "abc", "aBc", "b" ] would be the correct result). Such algorithms are called stable. If the ordering algorithm may swap equivalent elements discretionarily, the ordering is called unstable.
Yet another class of algorithms may choose an intermediate tradeoff by being stable only on a well-defined subrange of the range. There is no established terminology for such behavior; this library calls it semistable.
Generally, the stable ordering strategy may be more costly in time and/or space than the other two because it imposes additional constraints. Similarly, semistable may be costlier than unstable. As (semi-)stability is not needed very often, the ordering algorithms in this module parameterized 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.
- Reduces r by overwriting all elements x that satisfy pred(x). Returns the reduced range.
Example:
int[] arr = [ 1, 2, 3, 4, 5 ]; // eliminate even elements auto r = eliminate!("(a & 1) == 0")(arr); assert(r == [ 1, 3, 5 ]); assert(arr == [ 1, 3, 5, 4, 5 ]);
- Reduces r by overwriting all elements x that satisfy pred(x, v). Returns the reduced range.
Example:
int[] arr = [ 1, 2, 3, 2, 4, 5, 2 ]; // keep elements different from 2 auto r = eliminate(arr, 2); assert(r == [ 1, 3, 4, 5 ]); assert(arr == [ 1, 3, 4, 5, 4, 5, 2 ]);
- Partitions a range in two using pred as a predicate and iterSwap as a primitive to swap two elements. Specifically, reorders
the range r = [left, right) using iterSwap such that
all elements i for which pred(i) 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:- pred(*p1) for all p1 in [left, p), if any
- !pred(*p2) for all p2 in [p, right), if any
Example:
auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; auto arr = Arr.dup; static bool even(int a) { return (a & 1) == 0; } // Partition a such that even numbers come first auto p = partition!(even)(arr); // Now arr is separated in evens and odds. // Numbers may have become shuffled due to instability assert(p == arr.ptr + 5); assert(count!(even)(range(begin(arr), p)) == p - begin(arr)); assert(find!(even)(range(p, end(arr))) == end(arr)); // Can also specify the predicate as a string. // Use 'a' as the predicate argument name arr[] = Arr[]; p = partition!(q{(a & 1) == 0})(arr); assert(p == arr.ptr + 5); // Now for a stable partition: arr[] = Arr[]; p = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr); // Now arr is [2 4 6 8 10 1 3 5 7 9], and p points to 1 assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && p == arr.ptr + 5); // In case the predicate needs to hold its own state, use a delegate: arr[] = Arr[]; int x = 3; // Put stuff greater than 3 on the left bool fun(int a) { return a > x; } p = partition!(fun, SwapStrategy.semistable)(arr); // Now arr is [4 5 6 7 8 9 10 2 3 1] and p points to 2 assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && p == arr.ptr + 7);
- Reorders the range r = [first, last) using iterSwap
as a swapping primitive such that nth points to the element that
would fall there if the range were fully sorted. Effectively, it finds
the nth smallest (according to less) element in r. In
addition, it also partitions r such that all elements p1 in
[first, nth) satisfy less(*p1, *nth), and all
elements p2 in [nth, last) satisfy !less(*p2,
nth). Performs Ο(r.length) (if unstable) or Ο(r.length *
log(r.length)) (if stable) evaluations of less and iterSwap. See also STL's
nth_element.
Example:
int[] v = [ 25, 7, 9, 2, 0, 5, 21 ]; auto n = 4; topN!(less)(v, begin(v) + n); assert(v[n] == 9); // Equivalent form: topN!("a < b")(v, begin(v) + n); assert(v[n] == 9);
BUGS:
Stable topN has not been implemented yet.
- Sorts a random-access range according to predicate less. Performs
Ο(r.length * log(r.length)) (if unstable) or Ο(r.length *
log(r.length) * log(r.length)) (if stable) evaluations of less
and iterSwap. See also STL's sort and stable_sort.
Example:
int[] array = [ 1, 2, 3, 4 ]; // sort in descending order sort!("a > b")(array); assert(array == [ 4, 3, 2, 1 ]); // sort in ascending order sort(array); assert(array == [ 1, 2, 3, 4 ]); // sort with a delegate bool myComp(int x, int y) { return x > y; } sort!(myComp)(array); assert(array == [ 4, 3, 2, 1 ]); // Showcase stable sorting string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ]; sort!("toupper(a) < toupper(b)", SwapStrategy.stable)(words); assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
- Sorts a range using an algorithm akin to the Schwartzian transform, also
known as the decorate-sort-undecorate pattern in Python and Lisp. (Not
to be confused with the other
Schwartz.) This function is helpful when the sort comparison includes
an expensive computation. The complexity is the same as that of the
corresponding sort, 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.
- Reorders r such that the range begin(r) .. mid is the same
as if r were sorted, and leaves the range mid .. end(r) in
no particular order. Performs Ο(r.length * log(mid - begin(r)))
evaluations of pred.
Example:
int[] a = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]; partialSort(a, begin(a) + 5); assert(a[0 .. 5] == [ 0, 1, 2, 3, 4 ]);
- Checks whether a random-access range is sorted according to the
comparison operation less. Performs Ο(r.length) evaluations
of less.
Example:
int[] arr = [4, 3, 2, 1]; assert(!isSorted(arr)); sort(arr); assert(isSorted(arr)); sort!("a > b")(arr); assert(isSorted!("a > b")(arr));
- topNIndex
- Computes an index for source based on the comparison less
and deposits the result in target. It is acceptable that target.length < source.length, in which case only the smallest target.length elements in source get indexed. The target
provides a sorted "view" into source. This technique is similar
to sorting and partial sorting, but it is more flexible because (1) it
allows "sorting" of invariant collections, (2) allows binary search
even if the original collection does not offer random access, (3)
allows multiple indexes, each on a different comparison criterion, (4)
may be faster when dealing with large objects. However, using an index
may also be slower under certain circumstances due to the extra
indirection, and is always larger than a sorting-based solution
because it needs space for the index in addition to the original
collection. The complexity is Ο(source.length *
log(target.length)).
Two types of indexes are accepted. They are selected by simply passing the appropriate target argument:- Indexes of type Iterator!(Source), in which case the index will be sorted with the predicate less(*a, *b);
- Indexes of an integral type (e.g. size_t), in which case the index will be sorted with the predicate less(source[a], source[b]).
Example:
invariant arr = [ 2, 3, 1 ]; int* index[3]; partialIndex(arr, index); assert(*index[0] == 1 && *index[1] == 2 && *index[2] == 3); assert(isSorted!("*a < *b")(index));
- Checks whether a random-access range is sorted according to the
comparison operation less(transform(a), transform(b)). Performs
Ο(r.length) evaluations of less and transform. The
advantage over isSorted is that it evaluates transform only
half as many times.
Example:
int[] arr = [ "ab", "Ab", "aB", "bc", "Bc" ]; assert(!schwartzIsSorted!(toupper, "a < b")(arr));
- Returns the leftmost position in range such that all other values
x to the left of that position satisfy less(x,
value). Performs Ο(log(r.length)) evaluations of less. See
also STL's lower_bound.
Precondition:
isSorted!(less)(r)
Returns:
i such that less(*p, i) for all p in [begin(r), i).
Example:
int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]; auto p = lowerBound!(less)(a, 4); assert(*p == 4); p = lowerBound(a, 4); // uses less by default assert(*p == 4); p = lowerBound!("a < b")(a, 4); // predicate as string assert(*p == 4);
- Returns the rightmost position in r such that all other elements
x to the left of that position satisfy !less(value, x).
Performs Ο(log(r.length)) evaluations of less. See also
STL's upper_bound.
Precondition:
isSorted!(less)(r)
Returns:
i such that less(*p, value) for all p in [begin(r), i).
Example:
auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ]; auto p = upperBound(a, 3); assert(p == begin(a) + 5);
- The call 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 ]);
- 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.
- Converts the range r into a heap. Performs Ο(r.length)
evaluations of less.
- popHeap
- sortHeap
- topNCopy
- partialSortCopy