Implements algorithms oriented mainly towards processing of
sequences. Some functions are semantic equivalents or supersets of
those found in the
. The predicate may be passed either as a
function name, a delegate name, a
name, or a
compile-time string. The string may consist of
(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
Cheat SheetFunction Name | Description |
Searching
|
all | all!"a > 0"([1, 2, 3, 4]) returns true because all elements are positive |
any | any!"a > 0"([1, 2, -3, -4]) returns true because at least one element is positive |
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. |
Comparison
|
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"). |
Iteration
|
filter | filter!"a > 0"([1, -1, 2,
0, -3]) iterates over elements 1 and 2. |
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. |
Sorting
|
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. |
nextPermutation | Computes the next lexicographically
greater permutation of a range in-place. |
nextEvenPermutation | Computes the next
lexicographically greater even permutation of a range in-place. |
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. |
Set operations
|
cartesianProduct | Computes Cartesian product of two
ranges. |
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
intersection 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. |
Mutation
|
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]. |
strip | Strips all leading and trailing
elements equal to a value, or that satisfy a predicate.
If a = [1, 1, 0, 1, 1], then strip(a, 1) and strip!(e => e == 1)(a)
returns [0]. |
stripLeft | Strips all leading elements equal to a value,
or that satisfy a predicate.
If a = [1, 1, 0, 1, 1], then stripLeft(a, 1) and stripLeft!(e => e == 1)(a)
returns [0, 1, 1]. |
stripRight | Strips all trailing elements equal to a value,
or that satisfy a predicate.
If a = [1, 1, 0, 1, 1], then stripRight(a, 1) and stripRight!(e => e == 1)(a)
returns [1, 1, 0]. |
swap | Swaps two values. |
swapRanges | Swaps all elements of two
ranges. |
uninitializedFill | Fills a range
(assumed uninitialized) with a value. |
- 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.
Example:
int[] arr1 = [ 1, 2, 3, 4 ];
int[] arr2 = [ 5, 6 ];
auto squares = map!(a => 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" ]));
- template reduce(fun...) if (fun.length >= 1)
- 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 ];
auto sum = reduce!((a,b) => a + b)(0, arr);
assert(sum == 15);
sum = reduce!"a + b"(0, arr);
assert(sum == 15);
auto largest = reduce!(max)(arr);
assert(largest == 5);
largest = arr.reduce!(max);
assert(largest == 5);
auto odds = reduce!((a,b) => a + (b & 1))(0, arr);
assert(odds == 3);
auto ssquares = reduce!((a,b) => a + b * b)(0, arr);
assert(ssquares == 55);
int[] a = [ 3, 4 ];
int[] b = [ 100 ];
auto r = reduce!("a + b")(chain(a, b));
assert(r == 107);
double[] c = [ 2.5, 3.0 ];
auto r1 = reduce!("a + b")(chain(a, b, c));
assert(approxEqual(r1, 112.5));
auto r2 = chain(a, b, c).reduce!("a + b");
assert(approxEqual(r2, 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 ];
auto r = reduce!(min, max)(a);
assert(approxEqual(r[0], 2)); assert(approxEqual(r[1], 11));
r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a);
assert(approxEqual(r[0], 35)); assert(approxEqual(r[1], 233)); auto avg = r[0] / a.length;
auto stdev = sqrt(r[1] / a.length - avg * avg);
- void fill(Range, Value)(Range range, Value filler) if (isInputRange!Range && is(typeof(range.front = filler)));
- Fills range with a filler.
Example:
int[] a = [ 1, 2, 3, 4 ];
fill(a, 5);
assert(a == [ 5, 5, 5, 5 ]);
- void fill(Range1, Range2)(Range1 range, Range2 filler) if (isInputRange!Range1 && (isForwardRange!Range2 || isInputRange!Range2 && isInfinite!Range2) && is(typeof(Range1.init.front = Range2.init.front)));
- 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 ]);
- void uninitializedFill(Range, Value)(Range range, Value filler) if (isInputRange!Range && hasLvalueElements!Range && is(typeof(range.front = filler)));
- 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).
uninitializedFill will only operate on ranges that expose references to its
members and have assignable elements.
Example:
struct S { ... }
S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5];
uninitializedFill(s, 42);
assert(s == [ 42, 42, 42, 42, 42 ]);
- void initializeAll(Range)(Range range) if (isInputRange!Range && hasLvalueElements!Range && hasAssignableElements!Range);
- Initializes all elements of a range with their .init
value. Assumes that the range does not currently contain meaningful
content.
initializeAll will operate on ranges that expose references to its
members and have assignable elements, as well as on (mutable) strings.
Example:
struct S { ... }
S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5];
initializeAll(s);
assert(s == [ 0, 0, 0, 0, 0 ]);
- template filter(alias pred) if (is(typeof(unaryFun!pred)))
- 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 ];
auto small = filter!(a => a < 3)(arr);
assert(equal(small, [ 1, 2 ]));
auto sum = arr.filter!(a => a < 3);
assert(equal(sum, [ 1, 2 ]));
int[] a = [ 3, -2, 400 ];
int[] b = [ 100, -101, 102 ];
auto r = chain(a, b).filter!(a => a > 0);
assert(equal(r, [ 3, 400, 100, 102 ]));
double[] c = [ 2.5, 3.0 ];
auto r1 = chain(c, a, b).filter!(a => cast(int) a != a);
assert(approxEqual(r1, [ 2.5 ]));
- template filterBidirectional(alias pred)
- 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 ]));
int[] a = [ 3, -2, 400 ];
int[] b = [ 100, -101, 102 ];
auto r = filterBidirectional!("a > 0")(chain(a, b));
assert(r.back == 102);
- void move(T)(ref T source, ref T target);
T move(T)(ref T source);
- Moves source into target via a destructive
copy. Specifically:
- If hasAliasing!T is true (see
std.traits.hasAliasing), then the representation of source
is bitwise copied into target and then source = T.init is
evaluated.
- Otherwise, target = source is evaluated.
See
also std.exception.pointsTo.
Preconditions:
&source == &target || !pointsTo(source, source)
- Range2 moveAll(Range1, Range2)(Range1 src, Range2 tgt) if (isInputRange!Range1 && isInputRange!Range2 && is(typeof(move(src.front, tgt.front))));
- 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)
- Tuple!(Range1, Range2) moveSome(Range1, Range2)(Range1 src, Range2 tgt) if (isInputRange!Range1 && isInputRange!Range2 && is(typeof(move(src.front, tgt.front))));
- 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.
- pure nothrow @trusted void swap(T)(ref T lhs, ref T rhs) if (isMutable!T && !is(typeof(T.init.proxySwap(T.init))));
- Swaps lhs and rhs. See also std.exception.pointsTo.
Preconditions:
!pointsTo(lhs, lhs) && !pointsTo(lhs, rhs) && !pointsTo(rhs, lhs)
&& !pointsTo(rhs, rhs)
- template forward(args...)
- 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"; }
void bar(Args...)(auto ref Args args) { return foo(forward!args); }
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");
- auto splitter(Range, Separator)(Range r, Separator s) if (is(typeof(ElementType!Range.init == Separator.init)) && (hasSlicing!Range && hasLength!Range || isNarrowString!Range));
- 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] ]));
- auto splitter(Range, Separator)(Range r, Separator s) if (is(typeof(Range.init.front == Separator.init.front) : bool) && (hasSlicing!Range || isNarrowString!Range) && isForwardRange!Separator && (hasLength!Separator || isNarrowString!Separator));
- 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.
- auto joiner(RoR, Separator)(RoR r, Separator sep) if (isInputRange!RoR && isInputRange!(ElementType!RoR) && isForwardRange!Separator && is(ElementType!Separator : ElementType!(ElementType!RoR)));
auto joiner(RoR)(RoR r) if (isInputRange!RoR && isInputRange!(ElementType!RoR));
- 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"));
- auto uniq(alias pred = "a == b", Range)(Range r) if (isInputRange!Range && is(typeof(binaryFun!pred(r.front, r.front)) == bool));
- 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 ][]));
- struct Group(alias pred, R) if (isInputRange!R);
Group!(pred, Range) group(alias pred = "a == b", Range)(Range r);
- 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) ][]));
- R find(alias pred = "a == b", R, E)(R haystack, E needle) if (isInputRange!R && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));
- 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:
R haystack |
The range searched in. |
E 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); assert(!find(a, 2).empty);
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.
Parameters:
R1 haystack |
The range searched in. |
R2 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]);
- Tuple!(Range, size_t) find(alias pred = "a == b", Range, Ranges...)(Range haystack, Ranges needles) if (Ranges.length > 1 && is(typeof(startsWith!pred(haystack, needles))));
struct BoyerMooreFinder(alias pred, Range);
BoyerMooreFinder!(binaryFun!pred, Range) boyerMooreFinder(alias pred = "a == b", Range)(Range needle) if (isRandomAccessRange!Range || isSomeString!Range);
- 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:
Range 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. |
Ranges 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));
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.
- Range find(alias pred, Range)(Range haystack) if (isInputRange!Range);
- 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 ]);
bool pred(int x) { return x + 1 > 1.5; }
assert(find!(pred)(arr) == arr);
- bool findSkip(alias pred = "a == b", R1, R2)(ref R1 haystack, R2 needle) if (isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front))));
- 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);
- auto findSplit(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) if (isForwardRange!R1 && isForwardRange!R2);
auto findSplitBefore(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) if (isForwardRange!R1 && isForwardRange!R2);
auto findSplitAfter(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) if (isForwardRange!R1 && isForwardRange!R2);
- 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");
- ptrdiff_t countUntil(alias pred = "a == b", R, Rs...)(R haystack, Rs needles) if (isForwardRange!R && Rs.length > 0 && isForwardRange!(Rs[0]) == isInputRange!(Rs[0]) && is(typeof(startsWith!pred(haystack, needles[0]))) && (Rs.length == 1 || is(typeof(countUntil!pred(haystack, needles[1..__dollar])))));
ptrdiff_t countUntil(alias pred = "a == b", R, N)(R haystack, N needle) if (isInputRange!R && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));
- Returns the number of elements which must be popped from the front of
haystack before reaching an element for which
startsWith!pred(haystack, needles) is true. If
startsWith!pred(haystack, needles) is not true for any element in
haystack, then -1 is returned.
needles 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);
- ptrdiff_t countUntil(alias pred, R)(R haystack) if (isInputRange!R && is(typeof(unaryFun!pred(haystack.front)) : bool));
- 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);
- enum OpenRight: int;
- Interval option specifier for until (below) and others.
- no
- Interval is closed to the right (last element included)
- yes
- 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) if (!is(Sentinel == OpenRight));
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][]));
- uint startsWith(alias pred = "a == b", Range, Needles...)(Range doesThisStart, Needles withOneOfThese) if (isInputRange!Range && Needles.length > 1 && is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[0])) : bool) && is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[1..__dollar])) : uint));
bool startsWith(alias pred = "a == b", R1, R2)(R1 doesThisStart, R2 withThis) if (isInputRange!R1 && isInputRange!R2 && is(typeof(binaryFun!pred(doesThisStart.front, withThis.front)) : bool));
bool startsWith(alias pred = "a == b", R, E)(R doesThisStart, E withThis) if (isInputRange!R && is(typeof(binaryFun!pred(doesThisStart.front, withThis)) : bool));
- 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);
- bool skipOver(alias pred = "a == b", R1, R2)(ref R1 r1, R2 r2) if (is(typeof(binaryFun!pred(r1.front, r2.front))));
- If startsWith(r1, r2), consume the corresponding elements off r1 and return true. Otherwise, leave r1 unchanged and
return false.
- bool skipOver(alias pred = "a == b", R, E)(ref R r, E e) if (is(typeof(binaryFun!pred(r.front, e))));
- 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.
- uint endsWith(alias pred = "a == b", Range, Needles...)(Range doesThisEnd, Needles withOneOfThese) if (isBidirectionalRange!Range && Needles.length > 1 && is(typeof(.endsWith!pred(doesThisEnd, withOneOfThese[0])) : bool) && is(typeof(.endsWith!pred(doesThisEnd, withOneOfThese[1..__dollar])) : uint));
bool endsWith(alias pred = "a == b", R1, R2)(R1 doesThisEnd, R2 withThis) if (isBidirectionalRange!R1 && isBidirectionalRange!R2 && is(typeof(binaryFun!pred(doesThisEnd.back, withThis.back)) : bool));
bool endsWith(alias pred = "a == b", R, E)(R doesThisEnd, E withThis) if (isBidirectionalRange!R && is(typeof(binaryFun!pred(doesThisEnd.back, withThis)) : bool));
- 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);
- auto commonPrefix(alias pred = "a == b", R1, R2)(R1 r1, R2 r2) if (isForwardRange!R1 && isInputRange!R2 && !isNarrowString!R1 && is(typeof(binaryFun!pred(r1.front, r2.front))));
- Returns the common prefix of two ranges. Example:
assert(commonPrefix("hello, world", "hello, there") == "hello, ");
If the first argument is a string, then the result is a slice of r1 which
contains the characters that both ranges start with. For all other types, the
type of the result is the same as the result of takeExactly(r1, n), where
n is the number of elements that both ranges start with.
See Also:
std.range.takeExactly
- Range findAdjacent(alias pred = "a == b", Range)(Range r) if (isForwardRange!Range);
- 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 ]);
- Range1 findAmong(alias pred = "a == b", Range1, Range2)(Range1 seq, Range2 choices) if (isInputRange!Range1 && isForwardRange!Range2);
- 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 .. $]);
- size_t count(alias pred = "a == b", Range, E)(Range haystack, E needle) if (isInputRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));
size_t count(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) if (isForwardRange!R1 && !isInfinite!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool));
size_t count(alias pred = "true", R)(R haystack) if (isInputRange!R && !isInfinite!R && is(typeof(unaryFun!pred(haystack.front)) : bool));
- 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:
int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
assert(count(a, 2) == 3);
assert(count!("a > b")(a, 2) == 5);
assert(count("abcadfabf", "ab") == 2);
assert(count("ababab", "abab") == 1);
assert(count("ababab", "abx") == 0);
assert(count!"std.uni.toLower(a) == std.uni.toLower(b)"("AbcAdFaBf", "ab") == 2);
assert(count!("a > 1")(a) == 8);
- bool balancedParens(Range, E)(Range r, E lPar, E rPar, size_t maxNestingLevel = size_t.max) if (isInputRange!Range && is(typeof(r.front == lPar)));
- 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 + $(LPAREN)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));
- bool equal(Range1, Range2)(Range1 r1, Range2 r2) if (isInputRange!Range1 && isInputRange!Range2 && is(typeof(r1.front == r2.front)));
bool equal(alias pred, Range1, Range2)(Range1 r1, Range2 r2) if (isInputRange!Range1 && isInputRange!Range2 && is(typeof(binaryFun!pred(r1.front, r2.front))));
- 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));
double[] b = [ 1.0, 2, 4, 3];
assert(!equal(a, b[1..$]));
assert(equal(a, b));
double[] c = [ 1.005, 2, 4, 3];
assert(equal!(approxEqual)(b, c));
- 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.
- MinType!(T1, T2, T) min(T1, T2, T...)(T1 a, T2 b, T xs) if (is(typeof(a < b)));
- Returns the minimum of the passed-in values. The type of the result is
computed by using std.traits.CommonType.
- MaxType!(T1, T2, T) max(T1, T2, T...)(T1 a, T2 b, T xs) if (is(typeof(a < b)));
- Returns the maximum of the passed-in values. The type of the result is
computed by using std.traits.CommonType.
Example:
int a = 5;
short b = 6;
double c = 2;
auto d = max(a, b);
assert(is(typeof(d) == int));
assert(d == 6);
auto e = min(a, b, c);
assert(is(typeof(e) == double));
assert(e == 2);
- Tuple!(ElementType!Range, size_t) minCount(alias pred = "a < b", Range)(Range range) if (isInputRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));
- 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 ];
assert(minCount(a) == tuple(1, 3));
assert(minCount!("a > b")(a) == tuple(4, 2));
- Range minPos(alias pred = "a < b", Range)(Range range) if (isForwardRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));
- 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 ];
assert(minPos(a) == [ 1, 2, 4, 1, 1, 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.
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 .. $]);
- 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.
- none
- Current items are equal; no editing is necessary.
- substitute
- Substitute current item in target with current item in source.
- insert
- Insert current item from the source into the target.
- remove
- Remove current item from the target.
- size_t levenshteinDistance(alias equals = "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.
Example:
assert(levenshteinDistance("cat", "rat") == 1);
assert(levenshteinDistance("parks", "spark") == 2);
assert(levenshteinDistance("kitten", "sitting") == 3);
assert(levenshteinDistance!("std.uni.toUpper(a) == std.uni.toUpper(b)")
("parks", "SPARK") == 2);
- Tuple!(size_t, EditOp[]) levenshteinDistanceAndPath(alias equals = "a == b", Range1, Range2)(Range1 s, Range2 t) if (isForwardRange!Range1 && isForwardRange!Range2);
- 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"));
- Range2 copy(Range1, Range2)(Range1 source, Range2 target) if (isInputRange!Range1 && isOutputRange!(Range2, ElementType!Range1));
- 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 ]);
- Tuple!(Range1, Range2) swapRanges(Range1, Range2)(Range1 r1, Range2 r2) if (isInputRange!Range1 && isInputRange!Range2 && hasSwappableElements!Range1 && hasSwappableElements!Range2 && is(ElementType!Range1 == ElementType!Range2));
- 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 ]);
- void reverse(Range)(Range r) if (isBidirectionalRange!Range && !isRandomAccessRange!Range && hasSwappableElements!Range);
void reverse(Range)(Range r) if (isRandomAccessRange!Range && hasLength!Range);
- 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 ]);
- void reverse(Char)(Char[] s) if (isNarrowString!(Char[]) && !is(Char == const) && !is(Char == immutable));
- 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");
- Range strip(Range, E)(Range range, E element) if (isBidirectionalRange!Range && is(typeof(range.front == element) : bool));
Range strip(alias pred, Range)(Range range) if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool));
Range stripLeft(Range, E)(Range range, E element) if (isInputRange!Range && is(typeof(range.front == element) : bool));
Range stripLeft(alias pred, Range)(Range range) if (isInputRange!Range && is(typeof(pred(range.front)) : bool));
Range stripRight(Range, E)(Range range, E element) if (isBidirectionalRange!Range && is(typeof(range.back == element) : bool));
Range stripRight(alias pred, Range)(Range range) if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool));
- The strip group of functions allow stripping of either leading, trailing,
or both leading and trailing elements.
The stripLeft function will strip the front of the range,
the stripRight function will strip the back of the range,
while the strip function will strip both the front and back
of the range.
Note that the strip and stripRight functions require the range to
be a BidirectionalRange range.
All of these functions come in two varieties: one takes a target element,
where the range will be stripped as long as this element can be found.
The other takes a lambda predicate, where the range will be stripped as
long as the predicate returns true.
Examples:
Strip leading and trailing elements equal to the target element.
assert(" foobar ".strip(' ') == "foobar");
assert("00223.444500".strip('0') == "223.4445");
assert("ëëêéüŗōpéêëë".strip('ë') == "êéüŗōpéê");
assert([1, 1, 0, 1, 1].strip(1) == [0]);
assert([0.0, 0.01, 0.01, 0.0].strip(0).length == 2);
Examples:
Strip leading and trailing elements while the predicate returns true.
assert(" foobar ".strip!(a => a == ' ')() == "foobar");
assert("00223.444500".strip!(a => a == '0')() == "223.4445");
assert("ëëêéüŗōpéêëë".strip!(a => a == 'ë')() == "êéüŗōpéê");
assert([1, 1, 0, 1, 1].strip!(a => a == 1)() == [0]);
assert([0.0, 0.01, 0.5, 0.6, 0.01, 0.0].strip!(a => a < 0.4)().length == 2);
Examples:
Strip leading elements equal to the target element.
assert(" foobar ".stripLeft(' ') == "foobar ");
assert("00223.444500".stripLeft('0') == "223.444500");
assert("ůůűniçodêéé".stripLeft('ů') == "űniçodêéé");
assert([1, 1, 0, 1, 1].stripLeft(1) == [0, 1, 1]);
assert([0.0, 0.01, 0.01, 0.0].stripLeft(0).length == 3);
Examples:
Strip leading elements while the predicate returns true.
assert(" foobar ".stripLeft!(a => a == ' ')() == "foobar ");
assert("00223.444500".stripLeft!(a => a == '0')() == "223.444500");
assert("ůůűniçodêéé".stripLeft!(a => a == 'ů')() == "űniçodêéé");
assert([1, 1, 0, 1, 1].stripLeft!(a => a == 1)() == [0, 1, 1]);
assert([0.0, 0.01, 0.10, 0.5, 0.6].stripLeft!(a => a < 0.4)().length == 2);
Examples:
Strip trailing elements equal to the target element.
assert(" foobar ".stripRight(' ') == " foobar");
assert("00223.444500".stripRight('0') == "00223.4445");
assert("ùniçodêéé".stripRight('é') == "ùniçodê");
assert([1, 1, 0, 1, 1].stripRight(1) == [1, 1, 0]);
assert([0.0, 0.01, 0.01, 0.0].stripRight(0).length == 3);
Examples:
Strip trailing elements while the predicate returns true.
assert(" foobar ".stripRight!(a => a == ' ')() == " foobar");
assert("00223.444500".stripRight!(a => a == '0')() == "00223.4445");
assert("ùniçodêéé".stripRight!(a => a == 'é')() == "ùniçodê");
assert([1, 1, 0, 1, 1].stripRight!(a => a == 1)() == [1, 1, 0]);
assert([0.0, 0.01, 0.10, 0.5, 0.6].stripRight!(a => a > 0.4)().length == 3);
- size_t bringToFront(Range1, Range2)(Range1 front, Range2 back) if (isInputRange!Range1 && isForwardRange!Range2);
- 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.
- enum SwapStrategy: int;
- Defines the swapping strategy for algorithms that need to swap
elements in a range (such as partition and sort). The strategy
concerns the swapping of elements that are not the core concern of the
algorithm. For example, consider an algorithm that sorts [ "abc",
"b", "aBc" ] according to toUpper(a) < toUpper(b). That
algorithm might choose to swap the two equivalent strings "abc"
and "aBc". That does not affect the sorting since both [
"abc", "aBc", "b" ] and [ "aBc", "abc", "b" ] are valid
outcomes.
Some situations require that the algorithm must NOT ever change the
relative ordering of equivalent elements (in the example above, only
[ "abc", "aBc", "b" ] would be the correct result). Such
algorithms are called stable. If the ordering algorithm may swap
equivalent elements discretionarily, the ordering is called unstable.
Yet another class of algorithms may choose an intermediate tradeoff by
being stable only on a well-defined subrange of the range. There is no
established terminology for such behavior; this library calls it semistable.
Generally, the stable ordering strategy may be more costly in
time and/or space than the other two because it imposes additional
constraints. Similarly, semistable may be costlier than unstable. As (semi-)stability is not needed very often, the ordering
algorithms in this module parameterized by SwapStrategy all
choose SwapStrategy.unstable as the default.
- unstable
- Allows freely swapping of elements as long as the output
satisfies the algorithm's requirements.
- semistable
- In algorithms partitioning ranges in two, preserve relative
ordering of elements only to the left of the partition point.
- stable
- Preserve the relative ordering of elements to the largest
extent allowed by the algorithm's requirements.
- Range remove(SwapStrategy s = SwapStrategy.stable, Range, Offset...)(Range range, Offset offset) if (s != SwapStrategy.stable && isBidirectionalRange!Range && hasLength!Range && Offset.length >= 1);
- 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.
- Range remove(alias pred, SwapStrategy s = SwapStrategy.stable, Range)(Range range) if (isBidirectionalRange!Range);
- 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 ]);
- 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(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; }
auto r = partition!(even)(arr);
assert(r == arr[5 .. $]);
assert(count!(even)(arr[0 .. 5]) == 5);
assert(find!(even)(r).empty);
arr[] = Arr[];
r = partition!(q{(a & 1) == 0})(arr);
assert(r == arr[5 .. $]);
arr[] = Arr[];
r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr);
assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]);
arr[] = Arr[];
int x = 3;
bool fun(int a) { return a > x; }
r = partition!(fun, SwapStrategy.semistable)(arr);
assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);
- bool isPartitioned(alias pred, Range)(Range r) if (isForwardRange!Range);
- 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));
- auto partition3(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, E)(Range r, E pivot) if (ss == SwapStrategy.unstable && isRandomAccessRange!Range && hasSwappableElements!Range && hasLength!Range && is(typeof(binaryFun!less(r.front, pivot)) == bool) && is(typeof(binaryFun!less(pivot, r.front)) == bool) && is(typeof(binaryFun!less(r.front, r.front)) == bool));
- 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.
- void topN(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r, size_t nth) if (isRandomAccessRange!Range && hasLength!Range);
- 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 an expected
Ο(r.length) (if unstable) or Ο(r.length * log(r.length))
(if stable) evaluations of less and swap. See also STL's nth_element.
If n >= r.length, the algorithm has no effect.
Examples:
int[] v = [ 25, 7, 9, 2, 0, 5, 21 ];
auto n = 4;
topN!(less)(v, n);
assert(v[n] == 9);
topN!("a < b")(v, n);
assert(v[n] == 9);
BUGS:
Stable topN has not been implemented yet.
- void topN(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(Range1 r1, Range2 r2) if (isRandomAccessRange!Range1 && hasLength!Range1 && isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2));
- Stores the smallest elements of the two ranges in the left-hand range.
Examples:
Ditto
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]);
- SortedRange!(Range, less) sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r) if ((ss == SwapStrategy.unstable && (hasSwappableElements!Range || hasAssignableElements!Range) || ss != SwapStrategy.unstable && hasAssignableElements!Range) && isRandomAccessRange!Range && hasSlicing!Range && hasLength!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!("a > b")(array);
assert(array == [ 4, 3, 2, 1 ]);
sort(array);
assert(array == [ 1, 2, 3, 4 ]);
bool myComp(int x, int y) { return x > y; }
sort!(myComp)(array);
assert(array == [ 4, 3, 2, 1 ]);
string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words);
assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
- template multiSort(less...)
- 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);
- SortedRange!(R, (a, b) => binaryFun!less(unaryFun!transform(a), unaryFun!transform(b))) schwartzSort(alias transform, alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, R)(R r) if (isRandomAccessRange!R && hasLength!R);
- Sorts a range using an algorithm akin to the Schwartzian transform, also
known as the decorate-sort-undecorate pattern in Python and Lisp. (Not
to be confused with the other
Schwartz.) This function is helpful when the sort comparison includes
an expensive computation. The complexity is the same as that of the
corresponding sort, but schwartzSort evaluates transform only r.length times (less than half when compared to
regular sorting). The usage can be best illustrated with an example.
Examples:
uint hashFun(string) { ... expensive computation ... }
string[] array = ...;
sort!((a, b) => hashFun(a) < hashFun(b))(array);
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)).
Returns:
The initial range wrapped as a SortedRange with the
predicate (a, b) => binaryFun!less(transform(a),
transform(b)).
- void partialSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r, size_t n) if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range);
- 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 ]);
- void completeSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(SortedRange!(Range1, less) lhs, Range2 rhs) if (hasLength!Range2 && hasSlicing!Range2);
- 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 ]);
- bool isSorted(alias less = "a < b", Range)(Range r) if (isForwardRange!Range);
- 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));
- SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b)) makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index) if (isForwardRange!Range && isRandomAccessRange!RangeIndex && is(ElementType!RangeIndex : ElementType!Range*));
void makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index) if (isRandomAccessRange!Range && !isInfinite!Range && isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex && isIntegral!(ElementType!RangeIndex));
- 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.
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.
makeIndex overwrites its second argument with the result, but
never reallocates it.
Returns:
The pointer-based version returns a SortedRange wrapper
over index, of type SortedRange!(RangeIndex, (a, b) =>
binaryFun!less(*a, *b)) thus reflecting the ordering of the
index. The index-based version returns void because the ordering
relation involves not only index but also r.
Throws:
If the second argument's length is less than that of the range
indexed, an exception is thrown.
Example:
immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];
auto index1 = new immutable(int)*[arr.length];
makeIndex!("a < b")(arr, index1);
assert(isSorted!("*a < *b")(index1));
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));
- enum SortOutput: int;
- Specifies whether the output of certain algorithm is desired in sorted
format.
- no
- Don't sort output
- yes
- Sort output
- bool canFind(alias pred = "a == b", R, E)(R haystack, E needle) if (is(typeof(find!pred(haystack, needle))));
- Returns true if and only if value can be found in range. Performs Ο(needle.length) evaluations of pred.
- size_t canFind(alias pred = "a == b", Range, Ranges...)(Range haystack, Ranges needles) if (Ranges.length > 1 && allSatisfy!(isForwardRange, Ranges) && is(typeof(find!pred(haystack, needles))));
- 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.
- bool any(alias pred, Range)(Range range) if (is(typeof(find!pred(range))));
- 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.
- bool all(alias pred, R)(R range) if (isInputRange!R && is(typeof(unaryFun!pred(range.front))));
- 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]));
- TRange topNCopy(alias less = "a < b", SRange, TRange)(SRange source, TRange target, SortOutput sorted = SortOutput.no) if (isInputRange!SRange && isRandomAccessRange!TRange && hasLength!TRange && hasSlicing!TRange);
- 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 ]);
- struct SetUnion(alias less = "a < b", Rs...) if (allSatisfy!(isInputRange, Rs));
SetUnion!(less, Rs) setUnion(alias less = "a < b", Rs...)(Rs rs);
- 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][]));
- struct SetIntersection(alias less = "a < b", Rs...) if (allSatisfy!(isInputRange, Rs));
SetIntersection!(less, Rs) setIntersection(alias less = "a < b", Rs...)(Rs ranges) if (allSatisfy!(isInputRange, Rs));
- 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][]));
- struct SetDifference(alias less = "a < b", R1, R2) if (isInputRange!R1 && isInputRange!R2);
SetDifference!(less, R1, R2) setDifference(alias less = "a < b", R1, R2)(R1 r1, R2 r2);
- 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][]));
- struct SetSymmetricDifference(alias less = "a < b", R1, R2) if (isInputRange!R1 && isInputRange!R2);
SetSymmetricDifference!(less, R1, R2) setSymmetricDifference(alias less = "a < b", R1, R2)(R1 r1, R2 r2);
- 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][]));
- struct NWayUnion(alias less, RangeOfRanges);
NWayUnion!(less, RangeOfRanges) nWayUnion(alias less = "a < b", RangeOfRanges)(RangeOfRanges ror);
- 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[]));
- void largestPartialIntersection(alias less = "a < b", RangeOfRanges, Range)(RangeOfRanges ror, Range tgt, SortOutput sorted = SortOutput.no);
- 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:
double[][] a =
[
[ 1, 4, 7, 8 ],
[ 1, 7 ],
[ 1, 7, 8],
[ 4 ],
[ 7 ],
];
auto b = new Tuple!(double, uint)[1];
largestPartialIntersection(a, b);
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).
- void largestPartialIntersectionWeighted(alias less = "a < b", RangeOfRanges, Range, WeightsAA)(RangeOfRanges ror, Range tgt, WeightsAA weights, SortOutput sorted = SortOutput.no);
- Similar to largestPartialIntersection, but associates a weight
with each distinct element in the intersection.
Example:
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);
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 BidirectionalRange range) if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);
- Permutes range in-place to the next lexicographically greater
permutation.
The predicate less defines the lexicographical ordering to be used on
the range.
If the range is currently the lexicographically greatest permutation, it is
permuted back to the least permutation and false is returned. Otherwise,
true is returned. One can thus generate all permutations of a range by
sorting it according to less, which produces the lexicographically
least permutation, and then calling nextPermutation until it returns false.
This is guaranteed to generate all distinct permutations of the range
exactly once. If there are N elements in the range and all of them are
unique, then N! permutations will be generated. Otherwise, if there are
some duplicated elements, fewer permutations will be produced.
int[] a = [1,2,3,4,5];
while (nextPermutation(a))
{
}
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.
Example:
int[] a = [1,2,3];
assert(nextPermutation(a) == true);
assert(a == [1,3,2]);
assert(nextPermutation(a) == true);
assert(a == [2,1,3]);
assert(nextPermutation(a) == true);
assert(a == [2,3,1]);
assert(nextPermutation(a) == true);
assert(a == [3,1,2]);
assert(nextPermutation(a) == true);
assert(a == [3,2,1]);
assert(nextPermutation(a) == false);
assert(a == [1,2,3]);
int[] a = [1,1,2];
assert(nextPermutation(a) == true);
assert(a == [1,2,1]);
assert(nextPermutation(a) == true);
assert(a == [2,1,1]);
assert(nextPermutation(a) == false);
assert(a == [1,1,2]);
- bool nextEvenPermutation(alias less = "a<b", BidirectionalRange)(ref BidirectionalRange range) if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);
- Permutes range in-place to the next lexicographically greater even
permutation.
The predicate less defines the lexicographical ordering to be used on
the range.
An even permutation is one which is produced by swapping an even number of
pairs of elements in the original range. The set of even permutations
is distinct from the set of all permutations only when there are no
duplicate elements in the range. If the range has N unique elements,
then there are exactly N!/2 even permutations.
If the range is already the lexicographically greatest even permutation, it
is permuted back to the least even permutation and false is returned.
Otherwise, true is returned, and the range is modified in-place to be the
lexicographically next even permutation.
One can thus generate the even permutations of a range with unique elements
by starting with the lexicographically smallest permutation, and repeatedly
calling nextEvenPermutation until it returns false.
int[] a = [1,2,3,4,5];
while (nextEvenPermutation(a))
{
}
One can also generate the odd permutations of a range by noting that
permutations obey the rule that even + even = even, and odd + even = odd.
Thus, by swapping the last two elements of a lexicographically least range,
it is turned into the first odd permutation. Then calling
nextEvenPermutation on this first odd permutation will generate the next
even permutation relative to this odd permutation, which is actually the
next odd permutation of the original range. Thus, by repeatedly calling
nextEvenPermutation until it returns false, one enumerates the odd
permutations of the original range.
int[] a = [1,2,3,4,5];
swap(a[$-2], a[$-1]); while (nextEvenPermutation(a))
{
}
Warning:
Since even permutations are only distinct from all permutations
when the range elements are unique, this function assumes that there are no
duplicate elements under the specified ordering. If this is not true, some
permutations may fail to be generated. When the range has non-unique
elements, you should use nextPermutation instead.
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.
Examples:
int[] a = [1,2,3];
assert(nextEvenPermutation(a) == true);
assert(a == [2,3,1]);
assert(nextEvenPermutation(a) == true);
assert(a == [3,1,2]);
assert(nextEvenPermutation(a) == false);
assert(a == [1,2,3]);
Even permutations are useful for generating coordinates of certain geometric
shapes. Here's a non-trivial example:
import std.math, std.stdio;
enum real Phi = (1.0 + sqrt(5.0)) / 2.0; real[][] seeds = [
[0.0, 1.0, 3.0*Phi],
[1.0, 2.0+Phi, 2.0*Phi],
[Phi, 2.0, Phi^^3]
];
foreach (seed; seeds)
{
do
{
size_t i;
do
{
for (i=0; i < seed.length; i++)
{
if (seed[i] != 0.0)
{
seed[i] = -seed[i];
if (seed[i] < 0.0)
break;
}
}
writeln(seed);
} while (i < seed.length);
} while (nextEvenPermutation(seed));
}
- auto cartesianProduct(R1, R2)(R1 range1, R2 range2);
auto cartesianProduct(R1, R2, RR...)(R1 range1, R2 range2, RR otherRanges);
- Lazily computes the Cartesian product of two or more ranges. The product is a
range of tuples of elements from each respective range.
The conditions for the two-range case are as follows:
If both ranges are finite, then one must be (at least) a forward range and the
other an input range.
If one range is infinite and the other finite, then the finite range must
be a forward range, and the infinite range can be an input range.
If both ranges are infinite, then both must be forward ranges.
When there are more than two ranges, the above conditions apply to each
adjacent pair of ranges.
Examples:
auto N = sequence!"n"(0); auto N2 = cartesianProduct(N, N);
assert(canFind(N2, tuple(0, 0)));
assert(canFind(N2, tuple(123, 321)));
assert(canFind(N2, tuple(11, 35)));
assert(canFind(N2, tuple(279, 172)));
auto B = [ 1, 2, 3 ];
auto C = [ 4, 5, 6 ];
auto BC = cartesianProduct(B, C);
foreach (n; [[1, 4], [2, 4], [3, 4], [1, 5], [2, 5], [3, 5], [1, 6],
[2, 6], [3, 6]])
{
assert(canFind(BC, tuple(n[0], n[1])));
}
auto A = [ 1, 2, 3 ];
auto B = [ 'a', 'b', 'c' ];
auto C = [ "x", "y", "z" ];
auto ABC = cartesianProduct(A, B, C);
assert(ABC.equal([
tuple(1, 'a', "x"), tuple(2, 'a', "x"), tuple(3, 'a', "x"),
tuple(1, 'b', "x"), tuple(2, 'b', "x"), tuple(3, 'b', "x"),
tuple(1, 'c', "x"), tuple(2, 'c', "x"), tuple(3, 'c', "x"),
tuple(1, 'a', "y"), tuple(2, 'a', "y"), tuple(3, 'a', "y"),
tuple(1, 'b', "y"), tuple(2, 'b', "y"), tuple(3, 'b', "y"),
tuple(1, 'c', "y"), tuple(2, 'c', "y"), tuple(3, 'c', "y"),
tuple(1, 'a', "z"), tuple(2, 'a', "z"), tuple(3, 'a', "z"),
tuple(1, 'b', "z"), tuple(2, 'b', "z"), tuple(3, 'b', "z"),
tuple(1, 'c', "z"), tuple(2, 'c', "z"), tuple(3, 'c', "z")
]));