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.

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

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

alias map!(to!string) stringize;
assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));

auto  reduce(Args...)(Args args) if (Args.length > 0 && Args.length <= 2 && isIterable!(Args[$ - 1]));

Implements the homonym function (also known as accumulate, compress, inject, or foldl) present in various programming languages of functional flavor. The call  reduce!(fun)(seed, range) first assigns seed to an internal variable result, also called the accumulator. Then, for each element x in range, result = fun(result, x) gets evaluated. Finally, result is returned. The one-argument version  reduce!(fun)(range) works similarly, but it uses the first element of the range as the seed (the range must be non-empty).

Many aggregate range operations turn out to be solved with  reduce quickly and easily. The example below illustrates  reduce's remarkable power and flexibility.

int[] arr = [ 1, 2, 3, 4, 5 ];
// Sum all elements

auto sum = reduce!((a,b) => a + b)(0, arr);
assert(sum == 15);

// Sum again, using a string predicate with "a" and "b"

sum = reduce!"a + b"(0, arr);
assert(sum == 15);

// Compute the maximum of all elements

auto largest = reduce!(max)(arr);
assert(largest == 5);

// Max again, but with Uniform Function Call Syntax (UFCS)

largest = arr.reduce!(max);
assert(largest == 5);

// Compute the number of odd elements

auto odds = reduce!((a,b) => a + (b & 1))(0, arr);
assert(odds == 3);

// Compute the sum of squares

auto ssquares = reduce!((a,b) => a + b * b)(0, arr);
assert(ssquares == 55);

// Chain multiple ranges into seed

int[] a = [ 3, 4 ];
int[] b = [ 100 ];
auto r = reduce!("a + b")(chain(a, b));
assert(r == 107);

// Mixing convertible types is fair game, too

double[] c = [ 2.5, 3.0 ];
auto r1 = reduce!("a + b")(chain(a, b, c));
assert(approxEqual(r1, 112.5));

// To minimize nesting of parentheses, Uniform Function Call Syntax can be used

auto r2 = chain(a, b, c).reduce!("a + b");
assert(approxEqual(r2, 112.5));

double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ];
// Compute minimum and maximum in one pass

auto r = reduce!(min, max)(a);
// The type of r is Tuple!(int, int)

assert(approxEqual(r[0], 2));  // minimum

assert(approxEqual(r[1], 11)); // maximum


// Compute sum and sum of squares in one pass

r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a);
assert(approxEqual(r[0], 35));  // sum

assert(approxEqual(r[1], 233)); // sum of squares

// Compute average and standard deviation from the above

auto avg = r[0] / a.length;
auto stdev = sqrt(r[1] / a.length - avg * avg);

Fills range with a filler.

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

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

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

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

 uninitializedFill will only operate on ranges that expose references to its members and have assignable elements.

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

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

 initializeAll will operate on ranges that expose references to its members and have assignable elements, as well as on (mutable) strings.

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

auto  filter(Range)(Range rs) if (isInputRange!(Unqual!Range));

Implements the homonym function present in various programming languages of functional flavor. The call  filter!(predicate)(range) returns a new range only containing elements x in range for which predicate(x) is true.

int[] arr = [ 1, 2, 3, 4, 5 ];

// Sum all elements

auto small = filter!(a => a < 3)(arr);
assert(equal(small, [ 1, 2 ]));

// Sum again, but with Uniform Function Call Syntax (UFCS)

auto sum = arr.filter!(a => a < 3);
assert(equal(sum, [ 1, 2 ]));

// In combination with chain() to span multiple ranges

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

// Mixing convertible types is fair game, too

double[] c = [ 2.5, 3.0 ];
auto r1 = chain(c, a, b).filter!(a => cast(int) a != a);
assert(approxEqual(r1, [ 2.5 ]));

auto  filterBidirectional(Range)(Range r) if (isBidirectionalRange!(Unqual!Range));

Similar to filter, except it defines a bidirectional range. There is a speed disadvantage - the constructor spends time finding the last element in the range that satisfies the filtering condition (in addition to finding the first one). The advantage is that the filtered range can be spanned from both directions. Also, std.range.retro can be applied against the filtered range.

int[] arr = [ 1, 2, 3, 4, 5 ];
auto small = filterBidirectional!("a < 3")(arr);
assert(small.back == 2);
assert(equal(small, [ 1, 2 ]));
assert(equal(retro(small), [ 2, 1 ]));
// In combination with chain() to span multiple ranges

int[] a = [ 3, -2, 400 ];
int[] b = [ 100, -101, 102 ];
auto r = filterBidirectional!("a > 0")(chain(a, b));
assert(r.back == 102);

Moves source into target via a destructive copy. Specifically:

• If hasAliasing!T is true (see std.traits.hasAliasing), then the representation of source is bitwise copied into target and then source = T.init is evaluated.
• Otherwise, target = source is evaluated.

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.

For each element a in src and each element b in tgt in lockstep in increasing order, calls move(a, b). Stops when either src or tgt have been exhausted. Returns the leftover portions of the two ranges.

Swaps lhs and rhs. See also std.exception.pointsTo.

Forwards function arguments with saving ref-ness.

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

assert(bar(1) == 1);
int i;
assert(bar(i) == 2);

void foo(int n, ref string s) { s = null; foreach (i; 0..n) s ~= "Hello"; }

// forwards all arguments which are bound to parameter tuple

void bar(Args...)(auto ref Args args) { return foo(forward!args); }

// forwards all arguments with swapping order

void baz(Args...)(auto ref Args args) { return foo(forward!args[$/2..$], forward!args[0..$/2]); }

string s;
bar(1, s);
assert(s == "Hello");
baz(s, 2);
assert(s == "HelloHello");

Splits a range using an element as a separator. This can be used with any narrow string type or sliceable range type, but is most popular with string types.

Two adjacent separators are considered to surround an empty element in the split range.

If the empty range is given, the result is a range with one empty element. If a range with one separator is given, the result is a range with two empty elements.

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

Splits a range using another range as a separator. This can be used with any narrow string type or sliceable range type, but is most popular with string types.

Lazily joins a range of ranges with a separator. The separator itself is a range. If you do not provide a separator, then the ranges are joined directly without anything in between them.

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

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

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

Similarly to uniq, group iterates unique consecutive elements of the given range. The element type is Tuple!(ElementType!R, uint) because it includes the count of equivalent elements seen. Equivalence of elements is assessed by using the predicate pred, by default "a == b".

 Group is an input range if R is an input range, and a forward range in all other cases.

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

Finds an individual element in an input range. Elements of haystack are compared with needle by using predicate pred. Performs Ο(walkLength(haystack)) evaluations of pred. See also STL's find.

To find the last occurence of needle in haystack, call  find(retro(haystack), needle). See also std.range.retro.

assert(find("hello, world", ',') == ", world");
assert(find([1, 2, 3, 5], 4) == []);
assert(find(SList!int(1, 2, 3, 4, 5)[], 4) == SList!int(4, 5)[]);
assert(find!"a > b"([1, 2, 3, 5], 2) == [3, 5]);

auto a = [ 1, 2, 3 ];
assert(find(a, 5).empty);       // not found

assert(!find(a, 2).empty);      // found


// Case-insensitive find of a string

string[] s = [ "Hello", "world", "!" ];
assert(!find!("toLower(a) == b")(s, "hello").empty);

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

assert(find("hello, world", "World").empty);
assert(find("hello, world", "wo") == "world");
assert(find([1, 2, 3, 4], SList!(2, 3)[]) == [2, 3, 4]);

Finds two or more needles into a haystack. The predicate pred is used throughout to compare elements. By default, elements are compared for equality.

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

assert(find(a, 5, [ 1.2, 3.5 ], 2.0, [ 1 ]) == tuple([ 2, 3 ], 3));

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.

auto arr = [ 1, 2, 3, 4, 1 ];
assert(find!("a > 2")(arr) == [ 3, 4, 1 ]);

// with predicate alias

bool pred(int x) { return x + 1 > 1.5; }
assert(find!(pred)(arr) == arr);

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

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

These functions find the first occurrence of needle in haystack and then split haystack as follows.

 findSplit returns a tuple result containing three ranges. result[0] is the portion of haystack before needle, result[1] is the portion of haystack that matches needle, and result[2] is the portion of haystack after the match. If needle was not found, result[0] comprehends haystack entirely and result[1] and result[2] are empty.

findSplitBefore returns a tuple result containing two ranges. result[0] is the portion of haystack before needle, and result[1] is the balance of haystack starting with the match. If needle was not found, result[0] comprehends haystack entirely and result[1] is empty.

findSplitAfter returns a tuple result containing two ranges. result[0] is the portion of haystack up to and including the match, and result[1] is the balance of haystack starting after the match. If needle was not found, result[0] is empty and result[1] is haystack.

In all cases, the concatenation of the returned ranges spans the entire haystack.

If haystack is a random-access range, all three components of the tuple have the same type as haystack. Otherwise, haystack must be a forward range and the type of result[0] and result[1] is the same as std.range.takeExactly.

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

Returns the number of elements which must be popped from the front of haystack before reaching an element for which startsWith!pred(haystack, 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.

assert(countUntil("hello world", "world") == 6);
assert(countUntil("hello world", 'r') == 8);
assert(countUntil("hello world", "programming") == -1);
assert(countUntil("日本語", "本語") == 1);
assert(countUntil("日本語", '語')   == 2);
assert(countUntil("日本語", "五") == -1);
assert(countUntil("日本語", '五') == -1);
assert(countUntil([0, 7, 12, 22, 9], [12, 22]) == 2);
assert(countUntil([0, 7, 12, 22, 9], 9) == 4);
assert(countUntil!"a > b"([0, 7, 12, 22, 9], 20) == 3);

Returns the number of elements which must be popped from haystack before pred(haystack.front) is true.

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

Interval option specifier for until (below) and others.

Lazily iterates range until value sentinel is found, at which point it stops.

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

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

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

If startsWith(r1, r2), consume the corresponding elements off r1 and return true. Otherwise, leave r1 unchanged and return false.

Checks whether a range starts with an element, and if so, consume that element off r and return true. Otherwise, leave r unchanged and return false.

The reciprocal of startsWith.

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

Returns the common prefix of two ranges. Example:

assert(commonPrefix("hello, world", "hello, there") == "hello, ");

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.

int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ];
auto r = findAdjacent(a);
assert(r == [ 10, 10, 9, 8, 8, 7, 8, 9 ]);
p = findAdjacent!("a < b")(a);
assert(p == [ 7, 8, 9 ]);

Advances seq by calling seq.popFront until either find!(pred)(choices, seq.front) is true, or seq becomes empty. Performs Ο(seq.length * choices.length) evaluations of pred. See also STL's find_first_of.

int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
int[] b = [ 3, 1, 2 ];
assert(findAmong(a, b) == a[2 .. $]);

The first version counts the number of elements x in r for which pred(x, value) is true. pred defaults to equality. Performs Ο(r.length) evaluations of pred.

The second version returns the number of times needle occurs in haystack. Throws an exception if needle.empty, as the count of the empty range in any range would be infinite. Overlapped counts are not considered, for example  count("aaa", "aa") is 1, not 2.

The third version counts the elements for which pred(x) is true. Performs Ο(r.length) evaluations of pred.

// count elements in range

int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ];
assert(count(a, 2) == 3);
assert(count!("a > b")(a, 2) == 5);
// count range in range

assert(count("abcadfabf", "ab") == 2);
assert(count("ababab", "abab") == 1);
assert(count("ababab", "abx") == 0);
// fuzzy count range in range

assert(count!"std.uni.toLower(a) == std.uni.toLower(b)"("AbcAdFaBf", "ab") == 2);
// count predicate in range

assert(count!("a > 1")(a) == 8);

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

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

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[] a = [ 1, 2, 4, 3 ];
assert(!equal(a, a[1..$]));
assert(equal(a, a));

// different types

double[] b = [ 1.0, 2, 4, 3];
assert(!equal(a, b[1..$]));
assert(equal(a, b));

// predicated: ensure that two vectors are approximately equal

double[] c = [ 1.005, 2, 4, 3];
assert(equal!(approxEqual)(b, c));

Performs three-way lexicographical comparison on two input ranges according to predicate pred. Iterating r1 and r2 in lockstep,  cmp compares each element e1 of r1 with the corresponding element e2 in r2. If binaryFun!pred(e1, e2),  cmp returns a negative value. If binaryFun!pred(e2, e1),  cmp returns a positive value. If one of the ranges has been finished,  cmp returns a negative value if r1 has fewer elements than r2, a positive value if r1 has more elements than r2, and 0 if the ranges have the same number of elements.

If the ranges are strings,  cmp performs UTF decoding appropriately and compares the ranges one code point at a time.

Returns the minimum of the passed-in values. The type of the result is computed by using std.traits.CommonType.

Returns the maximum of the passed-in values. The type of the result is computed by using std.traits.CommonType.

int a = 5;
short b = 6;
double c = 2;
auto d = max(a, b);
assert(is(typeof(d) == int));
assert(d == 6);
auto e = min(a, b, c);
assert(is(typeof(e) == double));
assert(e == 2);

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

int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
// Minimum is 1 and occurs 3 times

assert(minCount(a) == tuple(1, 3));
// Maximum is 4 and occurs 2 times

assert(minCount!("a > b")(a) == tuple(4, 2));

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

int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ];
// Minimum is 1 and first occurs in position 3

assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]);
// Maximum is 4 and first occurs in position 2

assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 2 ]);

Sequentially compares elements in r1 and r2 in lockstep, and stops at the first  mismatch (according to pred, by default equality). Returns a tuple with the reduced ranges that start with the two mismatched values. Performs Ο(min(r1.length, r2.length)) evaluations of pred. See also STL's mismatch.

int[]    x = [ 1,  5, 2, 7,   4, 3 ];
double[] y = [ 1.0, 5, 2, 7.3, 4, 8 ];
auto m = mismatch(x, y);
assert(m[0] == x[3 .. $]);
assert(m[1] == y[3 .. $]);

Encodes edit operations necessary to transform one sequence into another. Given sequences s (source) and t (target), a sequence of  EditOp encodes the steps that need to be taken to convert s into t. For example, if s = "cat" and "cars", the minimal sequence that transforms s into t is: skip two characters, replace 't' with 'r', and insert an 's'. Working with edit operations is useful in applications such as spell-checkers (to find the closest word to a given misspelled word), approximate searches, diff-style programs that compute the difference between files, efficient encoding of patches, DNA sequence analysis, and plagiarism detection.

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.

assert(levenshteinDistance("cat", "rat") == 1);
assert(levenshteinDistance("parks", "spark") == 2);
assert(levenshteinDistance("kitten", "sitting") == 3);
// ignore case

assert(levenshteinDistance!("std.uni.toUpper(a) == std.uni.toUpper(b)")
    ("parks", "SPARK") == 2);

Returns the Levenshtein distance and the edit path between s and t.

string a = "Saturday", b = "Sunday";
auto p = levenshteinDistanceAndPath(a, b);
assert(p[0] == 3);
assert(equal(p[1], "nrrnsnnn"));

Copies the content of source into target and returns the remaining (unfilled) part of target. See also STL's copy. If a behavior similar to STL's copy_backward is needed, use  copy(retro(source), retro(target)). See also std.range.retro.

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

float[] a = [ 1.0f, 5 ];
double[] b = new double[a.length];
auto d = copy(a, b);

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

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

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

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

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

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

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

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.

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

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

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

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.

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

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

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

int[] a = [ 0, 1, 2, 3 ];
assert(remove!(SwapStrategy.unstable)(a, 1) == [ 0, 3, 2 ]);

• If s == SwapStrategy.unstable && isRandomAccessRange!Range && hasLength!Range, then elements are moved from the end of the range into the slots to be filled. In this case, the absolute minimum of moves is performed.
• Otherwise, if s == SwapStrategy.unstable && isBidirectionalRange!Range && hasLength!Range, then elements are still moved from the end of the range, but time is spent on advancing between slots by repeated calls to range.popFront.
• Otherwise, elements are moved incrementally towards the front of range; a given element is never moved several times, but more elements are moved than in the previous cases.

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

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

Partitions a range in two using pred as a predicate. Specifically, reorders the range r = [left, right) using swap such that all elements i for which pred(i) is true come before all elements j for which pred(j) returns false.

Performs Ο(r.length) (if unstable or semistable) or Ο(r.length * log(r.length)) (if stable) evaluations of less and swap. The unstable version computes the minimum possible evaluations of swap (roughly half of those performed by the semistable version).

See also STL's partition and stable_partition.

auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
auto arr = Arr.dup;
static bool even(int a) { return (a & 1) == 0; }
// Partition arr such that even numbers come first

auto r = partition!(even)(arr);
// Now arr is separated in evens and odds.

// Numbers may have become shuffled due to instability

assert(r == arr[5 .. $]);
assert(count!(even)(arr[0 .. 5]) == 5);
assert(find!(even)(r).empty);

// Can also specify the predicate as a string.

// Use 'a' as the predicate argument name

arr[] = Arr[];
r = partition!(q{(a & 1) == 0})(arr);
assert(r == arr[5 .. $]);

// Now for a stable partition:

arr[] = Arr[];
r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr);
// Now arr is [2 4 6 8 10 1 3 5 7 9], and r points to 1

assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]);

// In case the predicate needs to hold its own state, use a delegate:

arr[] = Arr[];
int x = 3;
// Put stuff greater than 3 on the left

bool fun(int a) { return a > x; }
r = partition!(fun, SwapStrategy.semistable)(arr);
// Now arr is [4 5 6 7 8 9 10 2 3 1] and r points to 2

assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);

Returns true if r is partitioned according to predicate pred.

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

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

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

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.

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

topN!("a < b")(v, n);
assert(v[n] == 9);

Stores the smallest elements of the two ranges in the left-hand range.

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

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.

int[] array = [ 1, 2, 3, 4 ];
// sort in descending order

sort!("a > b")(array);
assert(array == [ 4, 3, 2, 1 ]);
// sort in ascending order

sort(array);
assert(array == [ 1, 2, 3, 4 ]);
// sort with a delegate

bool myComp(int x, int y) { return x > y; }
sort!(myComp)(array);
assert(array == [ 4, 3, 2, 1 ]);
// Showcase stable sorting

string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words);
assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);

void  multiSort(Range)(Range r) if (validPredicates!(ElementType!Range, less));

Sorts a range by multiple keys. The call  multiSort!("a.id < b.id", "a.date > b.date")(r) sorts the range r by id ascending, and sorts elements that have the same id by date descending. Such a call is equivalent to sort!"a.id != b.id ? a.id < b.id : a.date > b.date"(r), but  multiSort is faster because it does fewer comparisons (in addition to being more convenient).

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

Sorts a range using an algorithm akin to the Schwartzian transform, also known as the decorate-sort-undecorate pattern in Python and Lisp. (Not to be confused with the other Schwartz.) This function is helpful when the sort comparison includes an expensive computation. The complexity is the same as that of the corresponding sort, but  schwartzSort evaluates transform only r.length times (less than half when compared to regular sorting). The usage can be best illustrated with an example.

uint hashFun(string) { ... expensive computation ... }
string[] array = ...;
// Sort strings by hash, slow

sort!((a, b) => hashFun(a) < hashFun(b))(array);
// Sort strings by hash, fast (only computes arr.length hashes):

schwartzSort!(hashFun, "a < b")(array);

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

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

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

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

Checks whether a forward range is sorted according to the comparison operation less. Performs Ο(r.length) evaluations of less.

int[] arr = [4, 3, 2, 1];
assert(!isSorted(arr));
sort(arr);
assert(isSorted(arr));
sort!("a > b")(arr);
assert(isSorted!("a > b")(arr));

Computes an index for r based on the comparison less. The index is a sorted array of pointers or indices into the original range. This technique is similar to sorting, but it is more flexible because (1) it allows "sorting" of immutable collections, (2) allows binary search even if the original collection does not offer random access, (3) allows multiple indexes, each on a different predicate, and (4) may be faster when dealing with large objects. However, using an index may also be slower under certain circumstances due to the extra indirection, and is always larger than a sorting-based solution because it needs space for the index in addition to the original collection. The complexity is the same as sort's.

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.

immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];
// index using pointers

auto index1 = new immutable(int)*[arr.length];
makeIndex!("a < b")(arr, index1);
assert(isSorted!("*a < *b")(index1));
// index using offsets

auto index2 = new size_t[arr.length];
makeIndex!("a < b")(arr, index2);
assert(isSorted!
    ((size_t a, size_t b){ return arr[a] < arr[b];})
    (index2));

Specifies whether the output of certain algorithm is desired in sorted format.

Returns true if and only if value can be found in range. Performs Ο(needle.length) evaluations of pred.

Returns the 1-based index of the first needle found in haystack. If no needle is found, then 0 is returned.

So, if used directly in the condition of an if statement or loop, the result will be true if one of the needles is found and false if none are found, whereas if the result is used elsewhere, it can either be cast to bool for the same effect or used to get which needle was found first without having to deal with the tuple that LREF find returns for the same operation.

Returns true if and only if a value v satisfying the predicate pred can be found in the forward range range. Performs Ο(r.length) evaluations of pred.

Returns true if and only if  all values in range satisfy the predicate pred. Performs Ο(r.length) evaluations of pred.

assert(all!"a & 1"([1, 3, 5, 7, 9]));
assert(!all!"a & 1"([1, 2, 3, 5, 7, 9]));

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Similar to largestPartialIntersection, but associates a weight with each distinct element in the intersection.

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

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.

// Enumerate all permutations

int[] a = [1,2,3,4,5];
while (nextPermutation(a))
{
    // a now contains the next permutation of the array.

}

// Step through all permutations of a sorted array in lexicographic order

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

// Step through permutations of an array containing duplicate elements:

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

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.

// Enumerate even permutations

int[] a = [1,2,3,4,5];
while (nextEvenPermutation(a))
{
    // a now contains the next even permutation of the array.

}

// Enumerate odd permutations

int[] a = [1,2,3,4,5];
swap(a[$-2], a[$-1]);    // a is now the first odd permutation of [1,2,3,4,5]

while (nextEvenPermutation(a))
{
    // a now contains the next odd permutation of the original array

    // (which is an even permutation of the first odd permutation).

}

// Step through even permutations of a sorted array in lexicographic order

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

// Print the 60 vertices of a uniform truncated icosahedron (soccer ball)

import std.math, std.stdio;
enum real Phi = (1.0 + sqrt(5.0)) / 2.0;    // Golden ratio

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)
{
    // Loop over even permutations of each seed

    do
    {
        // Loop over all sign changes of each permutation

        size_t i;
        do
        {
            // Generate all possible sign changes

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

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.

auto N = sequence!"n"(0);         // the range of natural numbers

auto N2 = cartesianProduct(N, N); // the range of all pairs of natural numbers


// Various arbitrary number pairs can be found in the range in finite time.

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