std.algorithm.comparison

This is a submodule of std.algorithm. It contains generic comparison algorithms.

Copyright

Andrei Alexandrescu 2008-.

License

Boost License 1.0.

Authors

Andrei Alexandrescu

Source: std/algorithm/comparison.d

tmpl among equal indexOfFirstOvershadowingChoiceOnLast

alias AllocateGC

enum EditOp

struct Levenshtein

fn among castSwitch clamp cmp either isPermutation isSameLength levenshteinDistance levenshteinDistanceAndPath max min mismatch predSwitch

Types 3

enumEditOp : 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 = 'n'Current items are equal; no editing is necessary.

substitute = 's'Substitute current item in target with current item in source.

insert = 'i'Insert current item from the source into the target.

remove = 'r'Remove current item from the target.

private structLevenshtein(Range, alias equals, CostType = size_t)

Fields

CostType _deletionIncrement

CostType[] _matrix

size_t rows

Methods

EditOp[] path()

CostType matrix(size_t row, size_t col) ref

void AllocMatrix(size_t r, size_t c) @trusted

void FreeMatrix() @trusted

void InitMatrix()

uint min_index(CostType i0, CostType i1, CostType i2)

CostType distanceWithPath(Range s, Range t)

CostType distanceLowMem(Range s, Range t, CostType slen, CostType tlen)

Destructors

~this

aliasAllocateGC = Flag!"allocateGC"

Functions 19

fnuint among(alias pred = (a, b) => a == b, Value, Values...)(Value value, Values values) if (Values.length != 0)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 e...

fnauto castSwitch(choices...)(Object switchObject)Executes and returns one of a collection of handlers based on the type of the switch object.

fnT1 clamp(T1, T2, T3)(T1 val, T2 lower, T3 upper)Clamps `val` into the given bounds. Result has the same type as `val`.

fnauto cmp(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 r...

fnint cmp(alias pred, R1, R2)(R1 r1, R2 r2) if (isInputRange!R1 && isInputRange!R2)ditto

size_t levenshteinDistance(alias  equals = (a, b)  =>  a ==  b,  Range1,  Range2)(Range1 s,  Range2 t) if (isForwardRange!(Range1)  &&  isForwardRange!(Range2))

Returns the wikipedia.org/wiki/Levenshtein_distance between `s` and `t`. The Levenshtein distance computes the minimal amount of edit operations necessary to transform `s` into `t`. Performs s.len...

size_t levenshteinDistance(alias  equals = (a, b)  =>  a ==  b,  Range1,  Range2)(auto  ref  Range1 s,  auto  ref  Range2 t) if (isConvertibleToString!Range1 ||  isConvertibleToString!Range2)

ditto

Tuple!(size_t,  EditOp[]) levenshteinDistanceAndPath(alias  equals = (a, b)  =>  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`.

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)

ditto

fnauto max(T...)(T args) if (T.length >= 2 && !is(CommonType!T == void))Iterates the passed arguments and returns the maximum value.

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

fnauto min(T...)(T args) if (T.length >= 2 && !is(CommonType!T == void))Iterates the passed arguments and returns the minimum value.

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

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 misma...

fnauto 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.

fnbool 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.

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

Checks if both ranges are permutations of each other.

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)

ditto

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.

Templates 3

tmplamong(values...) if (isExpressionTuple!values)

Ditto

Functions

uint among(Value)(Value value) if (!is(CommonType!(Value, values) == void))

tmplindexOfFirstOvershadowingChoiceOnLast(choices...)

tmplequal(alias pred = "a == b")

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

Functions

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

`rs`	The ranges to be compared.

Returns

true if and only if all ranges compare _equal element

for element, according to binary predicate pred.

bool equalLoop(Rs...)(ref Rs rs)