dunkelheit reference

dkh.algorithm

  • binSearch

    Declaration

    T binSearch(alias pred, T)(T l, T r) if (isIntegral!T);
    T binSearch(alias pred, T)(T l, T r, int cnt = 60) if (isFloatingPoint!T);

    Do binary search, pred(l) must be false, pred(r) must be true, and pred must have monotonic

    Discussion

    [pred(l) = false, false, ..., false, true, true, ..., pred(r) = true]

    Return Value

    minimum x, s.t. pred(x) = true

    Examples

    1. assert(binSearch!(x => x*x >= 100)(0, 20) == 10); assert(binSearch!(x => x*x >= 101)(0, 20) == 11); assert(binSearch!(x => true)(0, 20) == 1); assert(binSearch!(x => false)(0, 20) == 20);

  • minimum

    Declaration

    E minimum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed) if (isInputRange!Range && !isInfinite!Range);
    ElementType!Range minimum(alias pred = "a < b", Range)(Range range);

    Find minimum

    Examples

    1. assert(minimum([2, 1, 3]) == 1); assert(minimum!"a > b"([2, 1, 3]) == 3); assert(minimum([2, 1, 3], -1) == -1); assert(minimum!"a > b"([2, 1, 3], 100) == 100);

  • maximum

    Declaration

    E maximum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed) if (isInputRange!Range && !isInfinite!Range);
    ElementType!Range maximum(alias pred = "a < b", Range)(Range range);

    Find maximum

    Examples

    1. assert(maximum([2, 1, 3]) == 3); assert(maximum!"a > b"([2, 1, 3]) == 1); assert(maximum([2, 1, 3], 100) == 100); assert(maximum!"a > b"([2, 1, 3], -1) == -1);

  • rotator

    Declaration

    Rotator!Range rotator(Range)(Range r);
    struct Rotator(Range) if (isForwardRange!Range && hasLength!Range);

    Range that rotate elements.

    Examples

    1. import std.algorithm : equal, cmp; import std.array : array; int[] a = [1, 2, 3]; assert(equal!equal(a.rotator, [ [1, 2, 3], [2, 3, 1], [3, 1, 2], ])); int[] b = [3, 1, 4, 1, 5]; assert(equal(b.rotator.maximum!"cmp(a, b) == -1", [5, 3, 1, 4, 1]));