Menu

- Learn
- Documentation
  - Language Reference
  - Library Reference
  - Command-line Reference
  - Feature Overview
  - Articles
- Packages
- Community
  - Blog
  - Orgs using D
  - Twitter
  - Forums
  - IRC
  - Wiki
  - GitHub
  - Issues
  - Get involved
  - Foundation
  - Donate
- Resources
  - Books
  - Tutorials
  - Tools
  - Editors
  - IDEs
  - Visual D
  - Acknowledgments
  - D Style
  - Glossary
  - Sitemap

Search
Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using a local clone.

# std.algorithm.comparison

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

Cheat Sheet
Function Name | Description
--- | ---
among | Checks if a value is among a set of values, e.g. if (v.among(1, 2, 3)) // v is 1, 2 or 3
castSwitch | (new A()).castSwitch((A a)=>1,(B b)=>2) returns 1.
clamp | clamp(1, 3, 6) returns 3. clamp(4, 3, 6) returns 4.
cmp | cmp("abc", "abcd") is -1, cmp("abc", "aba") is 1, and cmp("abc", "abc") is 0.
either | Return first parameter p that passes an if (p) test, e.g. either(0, 42, 43) returns 42.
equal | Compares ranges for element-by-element equality, e.g. equal([1, 2, 3], [1.0, 2.0, 3.0]) returns `true`.
isPermutation | isPermutation([1, 2], [2, 1]) returns `true`.
isSameLength | isSameLength([1, 2, 3], [4, 5, 6]) 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").
predSwitch | 2.predSwitch(1, "one", 2, "two", 3, "three") returns "two".

License:
Boost License 1.0.
Authors:
Andrei Alexandrescu

Source std/algorithm/comparison.d

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

auto `clamp`(T1, T2, T3)(T1 `val`, T2 `lower`, T3 `upper`);
  Clamps a value into the given bounds.
  This functions is equivalent to max(`lower`, min(`upper`,`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:
  Returns `val`, if it is between `lower` and `upper`. Otherwise returns the nearest of the two.
  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

int `cmp`(alias pred = "a < b", R1, R2)(R1 `r1`, R2 `r2`)
if (isInputRange!R1 && isInputRange!R2 && !(isSomeString!R1 && isSomeString!R2));
int `cmp`(alias pred = "a < b", R1, R2)(R1 `r1`, R2 `r2`)
if (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 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.
  Parameters:

  pred | The predicate used for comparison.
  R1 `r1` | The first range.
  R2 `r2` | The second range.

  Returns:
  0 if both ranges compare equal. -1 if the first differing element of `r1` is less than the corresponding element of `r2` according to pred. 1 if the first differing element of `r2` is less than the corresponding element of `r1` according to pred.
  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(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);

template `equal`(alias pred = "a == b")
  Compares two ranges for equality, as defined by predicate pred (which is == by default).
  Examples:

      import std.algorithm.comparison : equal;
      import std.math : approxEqual;

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

  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`(Range1, Range2)(Range1 `r1`, Range2 `r2`)
  if (isInputRange!Range1 && isInputRange!Range2 && is(typeof(binaryFun!pred(`r1`.front, `r2`.front))));
    Compares two ranges for equality. The ranges may have different element types, as long as pred(`r1`.front, `r2`.front) evaluates to bool. Performs Ο(min(`r1`.length, `r2`.length)) evaluations of pred.
    Parameters:

    Range1 `r1` | The first range to be compared.
    Range2 `r2` | The second range to be compared.

    Returns:
    `true` if and only if the two ranges compare equal element for element, according to binary predicate pred.
    See Also:
    STL's equal
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 Ο(`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"));

MaxType!T `max`(T...)(T `args`)
if (T.length >= 2);
  Iterates the passed arguments and return the maximum value.
  Parameters:

  T `args` | The values to select the maximum from. At least two arguments must be passed.

  Returns:
  The maximum of the passed-in `args`. The type of the returned value is the type among the passed arguments that is able to store the largest value.
  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

MinType!T `min`(T...)(T `args`)
if (T.length >= 2);
  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.
  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

      // With arguments of mixed signedness, the return type is the one that can
      // store the lowest values.
      a = -10;
      uint f = 10;
      static assert(is(typeof(min(a, f)) == int));
      writeln(min(a, f)); // -10

      // 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!(Range1, Range2) `mismatch`(alias pred = "a == b", Range1, Range2)(Range1 `r1`, Range2 `r2`)
if (isInputRange!Range1 && isInputRange!Range2);
  Sequentially compares elements in `r1` and `r2` in lockstep, and stops at the first `mismatch` (according to pred, by default equality). Returns a tuple with the reduced ranges that start with the two mismatched values. Performs Ο(min(`r1`.length, `r2`.length)) evaluations of pred.
  See Also:
  STL's mismatch
  Examples:

      int[]    x = [ 1,  5, 2, 7,   4, 3 ];
      double[] y = [ 1.0, 5, 2, 7.3, 4, 8 ];
      auto m = mismatch(x, y);
      writeln(m[0]); // x[3 .. $]
      writeln(m[1]); // 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`(Range1, Range2)(Range1 `r1`, Range2 `r2`)
if (isInputRange!Range1 && isInputRange!Range2 && !isInfinite!Range1 && !isInfinite!Range2);
  Checks if the two 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 both ranges have a length member, this function is Ο(1). Otherwise, this function is Ο(min(`r1`.length, `r2`.length)).
  Parameters:

  Range1 `r1` | a finite input range
  Range2 `r2` | a finite input range

  Returns:
  `true` if both ranges have the same length, `false` otherwise.
  Examples:

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

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

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

alias `AllocateGC` = std.typecons.Flag!"allocateGC".Flag;
  For convenience
bool `isPermutation`(AllocateGC allocate_gc, Range1, Range2)(Range1 `r1`, Range2 `r2`)
if (allocate_gc == 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
  allocate_gc | 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

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

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

Copyright © 1999-2017 by the D Language Foundation | Page generated by Ddoc on Wed Nov 1 23:25:10 2017