.algorithmImplements 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++. Sequences processed by these functions define range-based interfaces. Reference on rangesLicense:
Boost License 1.0. Authors:
Andrei Alexandrescu Source:
std/algorithm.d
- template map(fun...) if (fun.length >= 1)
- 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. Examples:; }Examples:
You may alias map with some function(s) to a symbol and use it separately:
import std.conv : to; alias stringize = map!(to!string); assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));
- template reduce(fun...) if (fun.length >= 1)
- auto reduce(Args...)(Args args) if (Args.length > 0 && Args.length <= 2 && isIterable!(Args[$ -).);
-.
- void fill(Range, Value)(Range range, Value filler) if (isInputRange!Range && is(typeof(range.front = filler)));
- Fills range with a filler..)))
- 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. Examples:
import std.math : approxEqual;)
- auto filterBidirectional(Range)(Range r) if (isBidirectionalRange!(Unqual!Range));. Examples:);
- void move(T)(ref T source, ref T target);
T move(T)(ref T source);
- Moves source into target via a destructive copy.
-). Returns the leftover portion of tgt. Throws an exception if there is not enough room in tgt to accommodate all of src. Preconditions:
walkLength(src) <= walkLength(tgt)
-. Returns the leftover portions of the two ranges.
- pure nothrow  ));
- overload below). See also splitter">std.regex.splitter for a version that splits using a regular expression defined separator. Examples:] ]));
-. See also splitter">std.regex.splitter for a version that splits using a regular expression defined separator.
-). Examples:
auto a = " a bcd ef gh "; assert(equal(splitter(a), ["a", "bcd", "ef", "gh"][]));
-. Examples:"));
-:
STL's find Examples:
import std.container : SList; assert(find("hello, world", ',') == ", world"); assert(find([1, 2, 3, 5], 4) == []); assert(equal(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);
- R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) if (isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool) && !isRandomAccessRange!R1);
- 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.. 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.:
STL's find);
- 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.));
- 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). Examples:
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);
-:
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);
-:
std.range.takeExactly:
STL's adjacent_find:
STL's find_first_of.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 Ο(haystack.length) evaluations of pred. Note:
Regardless of the overload, count will not accept infinite ranges for haystack. Examples:
import std.uni : toLower; // 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); // : equal; 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))))));
- 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
- int cmp(alias pred = "a < b", R1, R2)(R1 r1, R2 r2) if (isInputRange!R1 && isInputRange!R2 && !(isSomeString!R1 && isSomeString!R2));
- 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.
-:
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 ]);
- Tuple!(Range1, Range2) mismatch(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2) if (isInputRange!Range1 && isInputRange!Range2);
- 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 Examples:
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 .. $]);
- enum EditOp: char;
- 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.
- size_t levenshteinDistance(alias equals = "a == b", Range1, Range2)(Range1 s, Range2 t) if (isForwardRange!Range1 && isForwardRange!Range2);
- 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.:
STL's copy]);
-:
STL's reverse:
STL's rotate Examples:
The simplest use of bringToFront is for rotating elements in a buffer. For example:
auto arr = [4, 5, 6, 7, 1, 2, 3]; auto p = bringToFront(arr[0 .. 4], arr[4 .. $]); assert(p == arr.length - 4); assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ]);Examples:
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..container : SList; 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, std.algorithm ]);
- Range partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Range r) if (ss == SwapStrategy.stable && isRandomAccessRange!Range || ss != SwapStrategy.stable && isForwardRange!Range);
- 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). Examples:. BUGS:
stable partition3 has not been implemented yet.. See Also:
STL's nth_element BUGS:
Stable topN has not been implemented yet. Examples:
int[] v = [ 25, 7, 9, 2, 0, 5, 21 ]; auto n = 4; topN!"a < b"(v, n); assert(v[n] == 9);
- void. Examples:
int[] a = [ 5, 7, 2, 6, 7 ]; int[] b = [ 2, 1, 5, 6, 7, 3, 0 ]; topN(a, b); sort(a); assert(a == [0, 1, 2, 2, 3]);
-:
std.range.assumeSorted
std.range.SortedRange
std.algorithm.SwapStrategy
std.functional.binaryFun" ]);
- template multiSort(less...)
- void multiSort(Range)(Range r) if (validPredicates!(ElementType!Range,. (Not to be confused with the other Schwartz.). Examples:]). Examples:
int[] a = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]; partialSort(a, 5); assert(a[0 .. 5] == [ 0, 1, 2, 3, 4 ]);
-. Examples:. Examples:
int[] arr = [4, 3, 2, 1]; assert(!isSorted(arr)); sort(arr); assert(isSorted(arr)); sort!("a > b")(arr); assert(isSorted!("a > b")(arr));
-));
-:
all can also be used without a predicate, if its items can be evaluated to true or false in a conditional statement. This can be a convenient way to quickly evaluate that all of the elements of a range are true.
int[3] vals = [5, 3, 18]; assert( all(vals[]));
-.);
- 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. Examples:
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 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.);
- 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.:
// 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:
// 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.
- bool nextPermutation(alias less = "a<b", BidirectionalRange)(ref));Returns:
false if the range was lexicographically the greatest, in which case the range is reversed back to the lexicographically smallest permutation; otherwise returns true.)(ref);
-);