D Programming Language
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 local clone. Page wiki View or edit the community-maintained wiki page associated with this page.

# 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.
equal | Compares ranges for element-by-element equality, e.g. equal([1, 2, 3], [1.0, 2.0, 3.0]) returns true.
levenshteinDistance | levenshteinDistance("kitten", "sitting") returns 3 by using the Levenshtein distance algorithm.
levenshteinDistanceAndPath | levenshteinDistanceAndPath("kitten", "sitting") returns tuple(3, "snnnsni") by using the Levenshtein distance algorithm.
max | max(3, 4, 2) returns 4.
min | min(3, 4, 2) returns 2.
mismatch | mismatch("oh hi", "ohayo") returns tuple(" hi", "ayo").
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.
  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"))
          assert(pos == 2);
      else
          assert(false);

      // 42 is larger than 24
      assert(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));
      assert("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.
  choices needs to be composed of function or delegate handlers that accept one argument. 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.

  There can also be a choice that accepts zero arguments. That choice will be invoked if switchObject is null.

  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.

  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:
      assert(results[0] == "A with a value of 1");
      // B has no handler - it is handled by the handler of I:
      assert(results[1] == "derived from I");
      // null is handled by the null handler:
      assert(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) { assert(true); },
          (B b) { assert(false); },
      )();

auto clamp(T1, T2, T3)(T1 val, T2 lower, T3 upper);
  Returns val, if it is between lower and upper. Otherwise returns the nearest of the two. Equivalent to max(lower, min(upper,val)).
  Examples:

      assert(clamp(2, 1, 3) == 2);
      assert(clamp(0, 1, 3) == 1);
      assert(clamp(4, 1, 3) == 3);

      assert(clamp(1, 1, 1) == 1);

      assert(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));
  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.
template equal(alias pred = "a == b")
  Compares two ranges for equality, as defined by predicate pred (which is == by default).
  Examples:

      import std.math : approxEqual;
      import std.algorithm : 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));

  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.range : iota, chunks;
      import std.algorithm : equal;
      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))));
    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
enum EditOp: char;
  Encodes edit operations necessary to transform one sequence into another. Given sequences s (source) and t (target), a sequence of EditOp encodes the steps that need to be taken to convert s into t. For example, if s = "cat" and "cars", the minimal sequence that transforms s into t is: skip two characters, replace 't' with 'r', and insert an 's'. Working with edit operations is useful in applications such as spell-checkers (to find the closest word to a given misspelled word), approximate searches, diff-style programs that compute the difference between files, efficient encoding of patches, DNA sequence analysis, and plagiarism detection.
  none
    Current items are equal; no editing is necessary.
  substitute
    Substitute current item in target with current item in source.
  insert
    Insert current item from the source into the target.
  remove
    Remove current item from the target.
size_t levenshteinDistance(alias equals = "a == b", Range1, Range2)(Range1 s, Range2 t) if (isForwardRange!Range1 && isForwardRange!Range2);
  Returns the Levenshtein distance between s and t. The Levenshtein distance computes the minimal amount of edit operations necessary to transform s into t. Performs Ο(s.length * t.length) evaluations of equals and occupies Ο(s.length * t.length) storage.
  Allocates GC memory.
  Examples:

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

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

Tuple!(size_t, EditOp[]) levenshteinDistanceAndPath(alias equals = "a == b", Range1, Range2)(Range1 s, Range2 t) if (isForwardRange!Range1 && isForwardRange!Range2);
  Returns the Levenshtein distance and the edit path between s and t.
  Allocates GC memory.
  Examples:

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

MaxType!T max(T...)(T args) if (T.length >= 2);
  Returns the maximum of the passed-in values.
  Examples:

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

MinType!T min(T...)(T args) if (T.length >= 2);
  Returns the minimum of the passed-in values.
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);
      assert(m[0] == x[3 .. $]);
      assert(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");

      assert(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
              );
      }
      assert(factorial(3) == 6);

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

Andrei Alexandrescu 2008-. | Page generated by Ddoc on Tue Mar 24 14:30:34 2015