std.algorithm.comparison

uint among(alias pred = (a, b) => a == b, Value, Values...)(Value value, Values values)
if (Values.length != 0);

template among(values...) if (isExpressionTuple!values)

Find value among values, returning the 1-based index of the first matching value in values, or 0 if value is not among values. The predicate pred is used to compare values, and uses equality by default.

Parameters:

pred	The predicate used to compare the values.
Value value	The value to search for.
Values values	The values to compare the value to.

Returns:

0 if value was not found among the values, otherwise the index of the found value plus one is returned.

See Also:

find and canFind for finding a value in a range.

Examples:

assert(3.among(1, 42, 24, 3, 2));

if (auto pos = "bar".among("foo", "bar", "baz"))
    writeln(pos); // 2
else
    assert(false);

// 42 is larger than 24
writeln(42.among!((lhs, rhs) => lhs > rhs)(43, 24, 100)); // 2

Examples:

Alternatively, values can be passed at compile-time, allowing for a more efficient search, but one that only supports matching on equality:

assert(3.among!(2, 3, 4));
writeln("bar".among!("foo", "bar", "baz")); // 2

auto castSwitch(choices...)(Object switchObject);

Executes and returns one of a collection of handlers based on the type of the switch object.

The first choice that switchObject can be casted to the type of argument it accepts will be called with switchObject casted to that type, and the value it'll return will be returned by castSwitch.

If a choice's return type is void, the choice must throw an exception, unless all the choices are void. In that case, castSwitch itself will return void.

Throws:

If none of the choice matches, a SwitchError will be thrown. SwitchError will also be thrown if not all the choices are void and a void choice was executed without throwing anything.

Parameters:

choices	The choices needs to be composed of function or delegate handlers that accept one argument. There can also be a choice that accepts zero arguments. That choice will be invoked if the switchObject is null.
Object switchObject	the object against which the tests are being made.

Returns:

The value of the selected choice.

Note castSwitch can only be used with object types.

Examples:

import std.algorithm.iteration : map;
import std.format : format;

class A
{
    int a;
    this(int a) {this.a = a;}
    @property int i() { return a; }
}
interface I { }
class B : I { }

Object[] arr = [new A(1), new B(), null];

auto results = arr.map!(castSwitch!(
                            (A a) => "A with a value of %d".format(a.a),
                            (I i) => "derived from I",
                            ()    => "null reference",
                        ))();

// A is handled directly:
writeln(results[0]); // "A with a value of 1"
// B has no handler - it is handled by the handler of I:
writeln(results[1]); // "derived from I"
// null is handled by the null handler:
writeln(results[2]); // "null reference"

Examples:

Using with void handlers:

import std.exception : assertThrown;

class A { }
class B { }
// Void handlers are allowed if they throw:
assertThrown!Exception(
    new B().castSwitch!(
        (A a) => 1,
        (B d)    { throw new Exception("B is not allowed!"); }
    )()
);

// Void handlers are also allowed if all the handlers are void:
new A().castSwitch!(
    (A a) { },
    (B b) { assert(false); },
)();

T1 clamp(T1, T2, T3)(T1 val, T2 lower, T3 upper);

Clamps val into the given bounds. Result has the same type as val.

Parameters:

T1 val	The value to clamp.
T2 lower	The lower bound of the clamp.
T3 upper	The upper bound of the clamp.

Returns:

lower if val is less than lower, upper if val is greater than upper, and val in all other cases. Comparisons are made correctly (using std.functional.lessThan and the return value is converted to the return type using the standard integer coversion rules std.functional.greaterThan) even if the signedness of T1, T2, and T3 are different.

Examples:

writeln(clamp(2, 1, 3)); // 2
writeln(clamp(0, 1, 3)); // 1
writeln(clamp(4, 1, 3)); // 3

writeln(clamp(1, 1, 1)); // 1

writeln(clamp(5, -1, 2u)); // 2

auto x = clamp(42, uint.max, uint.max);
static assert(is(typeof(x) == int));
writeln(x); // -1

auto cmp(R1, R2)(R1 r1, R2 r2)
if (isInputRange!R1 && isInputRange!R2);

int cmp(alias pred, R1, R2)(R1 r1, R2 r2)
if (isInputRange!R1 && isInputRange!R2);

Performs a lexicographical comparison on two input ranges. Iterating r1 and r2 in lockstep, cmp compares each element e1 of r1 with the corresponding element e2 in r2. 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.

A custom predicate may be specified, in which case cmp performs a three-way lexicographical comparison using pred. Otherwise the elements are compared using opCmp.

Parameters:

pred	Predicate used for comparison. Without a predicate specified the ordering implied by opCmp is used.
R1 r1	The first range.
R2 r2	The second range.

Returns:

0 if the ranges compare equal. A negative value if r1 is a prefix of r2 or the first differing element of r1 is less than the corresponding element of r2 according to pred. A positive value if r2 is a prefix of r1 or the first differing element of r2 is less than the corresponding element of r1 according to pred.

Note An earlier version of the documentation incorrectly stated that -1 is the only negative value returned and 1 is the only positive value returned. Whether that is true depends on the types being compared.

Examples:

int result;

result = cmp("abc", "abc");
writeln(result); // 0
result = cmp("", "");
writeln(result); // 0
result = cmp("abc", "abcd");
assert(result < 0);
result = cmp("abcd", "abc");
assert(result > 0);
result = cmp("abc"d, "abd");
assert(result < 0);
result = cmp("bbc", "abc"w);
assert(result > 0);
result = cmp("aaa", "aaaa"d);
assert(result < 0);
result = cmp("aaaa", "aaa"d);
assert(result > 0);
result = cmp("aaa", "aaa"d);
writeln(result); // 0
result = cmp("aaa"d, "aaa"d);
writeln(result); // 0
result = cmp(cast(int[])[], cast(int[])[]);
writeln(result); // 0
result = cmp([1, 2, 3], [1, 2, 3]);
writeln(result); // 0
result = cmp([1, 3, 2], [1, 2, 3]);
assert(result > 0);
result = cmp([1, 2, 3], [1L, 2, 3, 4]);
assert(result < 0);
result = cmp([1L, 2, 3], [1, 2]);
assert(result > 0);

Examples:

Example predicate that compares individual elements in reverse lexical order

int result;

result = cmp!"a > b"("abc", "abc");
writeln(result); // 0
result = cmp!"a > b"("", "");
writeln(result); // 0
result = cmp!"a > b"("abc", "abcd");
assert(result < 0);
result = cmp!"a > b"("abcd", "abc");
assert(result > 0);
result = cmp!"a > b"("abc"d, "abd");
assert(result > 0);
result = cmp!"a > b"("bbc", "abc"w);
assert(result < 0);
result = cmp!"a > b"("aaa", "aaaa"d);
assert(result < 0);
result = cmp!"a > b"("aaaa", "aaa"d);
assert(result > 0);
result = cmp!"a > b"("aaa", "aaa"d);
writeln(result); // 0
result = cmp("aaa"d, "aaa"d);
writeln(result); // 0
result = cmp!"a > b"(cast(int[])[], cast(int[])[]);
writeln(result); // 0
result = cmp!"a > b"([1, 2, 3], [1, 2, 3]);
writeln(result); // 0
result = cmp!"a > b"([1, 3, 2], [1, 2, 3]);
assert(result < 0);
result = cmp!"a > b"([1, 2, 3], [1L, 2, 3, 4]);
assert(result < 0);
result = cmp!"a > b"([1L, 2, 3], [1, 2]);
assert(result > 0);

template equal(alias pred = "a == b")

Compares two or more ranges for equality, as defined by predicate pred (which is == by default).

Examples:

import std.algorithm.comparison : equal;
import std.math.operations : isClose;

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

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

// predicated: ensure that two vectors are approximately equal
double[4] c = [ 1.0000000005, 2, 4, 3];
assert(equal!isClose(b[], c[]));

Examples:

Tip: equal can itself be used as a predicate to other functions. This can be very useful when the element type of a range is itself a range. In particular, equal can be its own predicate, allowing range of range (of range...) comparisons.

import std.algorithm.comparison : equal;
import std.range : iota, chunks;
assert(equal!(equal!equal)(
    [[[0, 1], [2, 3]], [[4, 5], [6, 7]]],
    iota(0, 8).chunks(2).chunks(2)
));

bool equal(Ranges...)(Ranges rs)
if (rs.length > 1 && allSatisfy!(isInputRange, Ranges) && !allSatisfy!(isInfinite, Ranges) && is(typeof(binaryFun!pred(rs[0].front, rs[1].front))) && (rs.length == 2 || is(typeof(equal!pred(rs[1..$])) == bool)));

Compares two or more ranges for equality. The ranges may have different element types, as long as all are comparable by means of the pred. Performs Ο(min(rs[0].length, rs[1].length, ...)) evaluations of pred. However, if equal is invoked with the default predicate, the implementation may take the liberty to use faster implementations that have the theoretical worst-case Ο(max(rs[0].length, rs[1].length, ...)).

At least one of the ranges must be finite. If one range involved is infinite, the result is (statically known to be) false.

If the ranges have different kinds of UTF code unit (char, wchar, or dchar), then they are compared using UTF decoding to avoid accidentally integer-promoting units.

Parameters:

Ranges rs

The ranges to be compared.

Returns:

true if and only if all ranges compare equal element for element, according to binary predicate pred.

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.

Examples:

with(EditOp)
{
    // [none, none, none, insert, insert, insert]
    writeln(levenshteinDistanceAndPath("foo", "foobar")[1]);
    // [substitute, none, substitute, none, none, remove]
    writeln(levenshteinDistanceAndPath("banana", "fazan")[1]);
}

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) => a == b, Range1, Range2)(Range1 s, Range2 t)
if (isForwardRange!Range1 && isForwardRange!Range2);

size_t levenshteinDistance(alias equals = (a, b) => a == b, Range1, Range2)(auto ref Range1 s, auto ref Range2 t)
if (isConvertibleToString!Range1 || isConvertibleToString!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 Ο(min(s.length, t.length)) storage.

Parameters:

equals	The binary predicate to compare the elements of the two ranges.
Range1 s	The original range.
Range2 t	The transformation target

Returns:

The minimal number of edits to transform s into t.

Does not allocate GC memory.

Examples:

import std.algorithm.iteration : filter;
import std.uni : toUpper;

writeln(levenshteinDistance("cat", "rat")); // 1
writeln(levenshteinDistance("parks", "spark")); // 2
writeln(levenshteinDistance("abcde", "abcde")); // 0
writeln(levenshteinDistance("abcde", "abCde")); // 1
writeln(levenshteinDistance("kitten", "sitting")); // 3
assert(levenshteinDistance!((a, b) => toUpper(a) == toUpper(b))
    ("parks", "SPARK") == 2);
writeln(levenshteinDistance("parks".filter!"true", "spark".filter!"true")); // 2
writeln(levenshteinDistance("ID", "I♥D")); // 1

Tuple!(size_t, EditOp[]) levenshteinDistanceAndPath(alias equals = (a, b) => a == b, Range1, Range2)(Range1 s, Range2 t)
if (isForwardRange!Range1 && isForwardRange!Range2);

Tuple!(size_t, EditOp[]) levenshteinDistanceAndPath(alias equals = (a, b) => a == b, Range1, Range2)(auto ref Range1 s, auto ref Range2 t)
if (isConvertibleToString!Range1 || isConvertibleToString!Range2);

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

Parameters:

equals	The binary predicate to compare the elements of the two ranges.
Range1 s	The original range.
Range2 t	The transformation target

Returns:

Tuple with the first element being the minimal amount of edits to transform s into t and the second element being the sequence of edits to effect this transformation.

Allocates GC memory for the returned EditOp[] array.

Examples:

string a = "Saturday", b = "Sundays";
auto p = levenshteinDistanceAndPath(a, b);
writeln(p[0]); // 4
assert(equal(p[1], "nrrnsnnni"));

auto max(T...)(T args)
if (T.length >= 2 && !is(CommonType!T == void));

T max(T, U)(T a, U b)
if (is(T == U) && is(typeof(a < b)));

Iterates the passed arguments and returns the maximum value.

Parameters:

T args

The values to select the maximum from. At least two arguments must be passed, and they must be comparable with <.

Returns:

The maximum of the passed-in values. The type of the returned value is the type among the passed arguments that is able to store the largest value. If at least one of the arguments is NaN, the result is an unspecified value. See std.algorithm.searching.maxElement for examples on how to cope with NaNs.

See Also:

std.algorithm.searching.maxElement

Examples:

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

auto min(T...)(T args)
if (T.length >= 2 && !is(CommonType!T == void));

T min(T, U)(T a, U b)
if (is(T == U) && is(typeof(a < b)));

Iterates the passed arguments and returns the minimum value.

Parameters:

T args

The values to select the minimum from. At least two arguments must be passed, and they must be comparable with <.

Returns:

The minimum of the passed-in values. The type of the returned value is the type among the passed arguments that is able to store the smallest value. If at least one of the arguments is NaN, the result is an unspecified value. See std.algorithm.searching.minElement for examples on how to cope with NaNs.

See Also:

std.algorithm.searching.minElement

Examples:

int a = 5;
short b = 6;
double c = 2;
auto d = min(a, b);
static assert(is(typeof(d) == int));
writeln(d); // 5
auto e = min(a, b, c);
static assert(is(typeof(e) == double));
writeln(e); // 2
ulong f = 0xffff_ffff_ffff;
const uint g = min(f, 0xffff_0000);
writeln(g); // 0xffff_0000
dchar h = 100;
uint i = 101;
static assert(is(typeof(min(h, i)) == dchar));
static assert(is(typeof(min(i, h)) == uint));
writeln(min(h, i)); // 100

Examples:

With arguments of mixed signedness, the return type is the one that can store the lowest values.

int a = -10;
uint f = 10;
static assert(is(typeof(min(a, f)) == int));
writeln(min(a, f)); // -10

Examples:

User-defined types that support comparison with < are supported.

import std.datetime;
writeln(min(Date(2012, 12, 21), Date(1982, 1, 4))); // Date(1982, 1, 4)
writeln(min(Date(1982, 1, 4), Date(2012, 12, 21))); // Date(1982, 1, 4)
writeln(min(Date(1982, 1, 4), Date.min)); // Date.min
writeln(min(Date.min, Date(1982, 1, 4))); // Date.min
writeln(min(Date(1982, 1, 4), Date.max)); // Date(1982, 1, 4)
writeln(min(Date.max, Date(1982, 1, 4))); // Date(1982, 1, 4)
writeln(min(Date.min, Date.max)); // Date.min
writeln(min(Date.max, Date.min)); // Date.min

Tuple!Ranges mismatch(alias pred = (a, b) => a == b, Ranges...)(Ranges rs)
if (rs.length >= 2 && allSatisfy!(isInputRange, Ranges));

Sequentially compares elements in rs 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(r[0].length, r[1].length, ...)) evaluations of pred.

Examples:

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

auto m2 = mismatch(x[], y[], x[], y[]);
writeln(m2[0]); // x[3 .. $]
writeln(m2[1]); // y[3 .. $]
writeln(m2[2]); // x[3 .. $]
writeln(m2[3]); // y[3 .. $]

auto predSwitch(alias pred = "a == b", T, R...)(T switchExpression, lazy R choices);

Returns one of a collection of expressions based on the value of the switch expression.

choices needs to be composed of pairs of test expressions and return expressions. Each test-expression is compared with switchExpression using pred(switchExpression is the first argument) and if that yields true - the return expression is returned.

Both the test and the return expressions are lazily evaluated.

Parameters:

T switchExpression

The first argument for the predicate.

R choices

Pairs of test expressions and return expressions. The test expressions will be the second argument for the predicate, and the return expression will be returned if the predicate yields true with switchExpression and the test expression as arguments. May also have a default return expression, that needs to be the last expression without a test expression before it. A return expression may be of void type only if it always throws.

Returns:

The return expression associated with the first test expression that made the predicate yield true, or the default return expression if no test expression matched.

Throws:

If there is no default return expression and the predicate does not yield true with any test expression - SwitchError is thrown. SwitchError is also thrown if a void return expression was executed without throwing anything.

Examples:

string res = 2.predSwitch!"a < b"(
    1, "less than 1",
    5, "less than 5",
    10, "less than 10",
    "greater or equal to 10");

writeln(res); // "less than 5"

//The arguments are lazy, which allows us to use predSwitch to create
//recursive functions:
int factorial(int n)
{
    return n.predSwitch!"a <= b"(
        -1, {throw new Exception("Can not calculate n! for n < 0");}(),
        0, 1, // 0! = 1
        n * factorial(n - 1) // n! = n * (n - 1)! for n >= 0
        );
}
writeln(factorial(3)); // 6

//Void return expressions are allowed if they always throw:
import std.exception : assertThrown;
assertThrown!Exception(factorial(-9));

bool isSameLength(Ranges...)(Ranges rs)
if (allSatisfy!(isInputRange, Ranges));

Checks if two or more ranges have the same number of elements. This function is optimized to always take advantage of the length member of either range if it exists.

If all ranges have a length member or at least one is infinite, _isSameLength's complexity is Ο(1). Otherwise, complexity is Ο(n), where n is the smallest of the lengths of ranges with unknown length.

Infinite ranges are considered of the same length. An infinite range has never the same length as a finite range.

Parameters:

Ranges rs

two or more input ranges

Returns:

true if both ranges have the same length, false otherwise.

Examples:

assert(isSameLength([1, 2, 3], [4, 5, 6]));
assert(isSameLength([1, 2, 3], [4, 5, 6], [7, 8, 9]));
assert(isSameLength([0.3, 90.4, 23.7, 119.2], [42.6, 23.6, 95.5, 6.3]));
assert(isSameLength("abc", "xyz"));
assert(isSameLength("abc", "xyz", [1, 2, 3]));

int[] a;
int[] b;
assert(isSameLength(a, b));
assert(isSameLength(a, b, a, a, b, b, b));

assert(!isSameLength([1, 2, 3], [4, 5]));
assert(!isSameLength([1, 2, 3], [4, 5, 6], [7, 8]));
assert(!isSameLength([0.3, 90.4, 23.7], [42.6, 23.6, 95.5, 6.3]));
assert(!isSameLength("abcd", "xyz"));
assert(!isSameLength("abcd", "xyz", "123"));
assert(!isSameLength("abcd", "xyz", "1234"));

bool isPermutation(Flag!"allocateGC" allocateGC, Range1, Range2)(Range1 r1, Range2 r2)
if (allocateGC == Yes.allocateGC && isForwardRange!Range1 && isForwardRange!Range2 && !isInfinite!Range1 && !isInfinite!Range2);

bool isPermutation(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2)
if (is(typeof(binaryFun!pred)) && isForwardRange!Range1 && isForwardRange!Range2 && !isInfinite!Range1 && !isInfinite!Range2);

Checks if both ranges are permutations of each other.

This function can allocate if the Yes.allocateGC flag is passed. This has the benefit of have better complexity than the Yes.allocateGC option. However, this option is only available for ranges whose equality can be determined via each element's toHash method. If customized equality is needed, then the pred template parameter can be passed, and the function will automatically switch to the non-allocating algorithm. See std.functional.binaryFun for more details on how to define pred.

Non-allocating forward range option: Ο(n^2) Non-allocating forward range option with custom pred: Ο(n^2) Allocating forward range option: amortized Ο(r1.length) + Ο(r2.length)

Parameters:

pred	an optional parameter to change how equality is defined
allocateGC	Yes.allocateGC/No.allocateGC
Range1 r1	A finite forward range
Range2 r2	A finite forward range

Returns:

true if all of the elements in r1 appear the same number of times in r2. Otherwise, returns false.

Examples:

import std.typecons : Yes;

assert(isPermutation([1, 2, 3], [3, 2, 1]));
assert(isPermutation([1.1, 2.3, 3.5], [2.3, 3.5, 1.1]));
assert(isPermutation("abc", "bca"));

assert(!isPermutation([1, 2], [3, 4]));
assert(!isPermutation([1, 1, 2, 3], [1, 2, 2, 3]));
assert(!isPermutation([1, 1], [1, 1, 1]));

// Faster, but allocates GC handled memory
assert(isPermutation!(Yes.allocateGC)([1.1, 2.3, 3.5], [2.3, 3.5, 1.1]));
assert(!isPermutation!(Yes.allocateGC)([1, 2], [3, 4]));

CommonType!(T, Ts) either(alias pred = (a) => a, T, Ts...)(T first, lazy Ts alternatives)
if (alternatives.length >= 1 && !is(CommonType!(T, Ts) == void) && allSatisfy!(ifTestable, T, Ts));

Get the first argument a that passes an if (unaryFun!pred(a)) test. If no argument passes the test, return the last argument.

Similar to behaviour of the or operator in dynamic languages such as Lisp's (or ...) and Python's a or b or ... except that the last argument is returned upon no match.

Simplifies logic, for instance, in parsing rules where a set of alternative matchers are tried. The first one that matches returns it match result, typically as an abstract syntax tree (AST).

Bugs:

Lazy parameters are currently, too restrictively, inferred by DMD to always throw even though they don't need to be. This makes it impossible to currently mark either as nothrow. See issue at Bugzilla 12647.

Returns:

The first argument that passes the test pred.

Examples:

const a = 1;
const b = 2;
auto ab = either(a, b);
static assert(is(typeof(ab) == const(int)));
writeln(ab); // a

auto c = 2;
const d = 3;
auto cd = either!(a => a == 3)(c, d); // use predicate
static assert(is(typeof(cd) == int));
writeln(cd); // d

auto e = 0;
const f = 2;
auto ef = either(e, f);
static assert(is(typeof(ef) == int));
writeln(ef); // f

Examples:

immutable p = 1;
immutable q = 2;
auto pq = either(p, q);
static assert(is(typeof(pq) == immutable(int)));
writeln(pq); // p

writeln(either(3, 4)); // 3
writeln(either(0, 4)); // 4
writeln(either(0, 0)); // 0
writeln(either("", "a")); // ""

Examples:

string r = null;
writeln(either(r, "a")); // "a"
writeln(either("a", "")); // "a"

immutable s = [1, 2];
writeln(either(s, s)); // s

writeln(either([0, 1], [1, 2])); // [0, 1]
writeln(either([0, 1], [1])); // [0, 1]
writeln(either("a", "b")); // "a"

static assert(!__traits(compiles, either(1, "a")));
static assert(!__traits(compiles, either(1.0, "a")));
static assert(!__traits(compiles, either('a', "a")));