.. _std_algorithm:
.. highlight:: d

std.algorithm
-------------

.. c:namespace:: std.algorithm

Module entries: :func:`all`, :func:`any`, :func:`array`, :func:`cumulativeFold`, :func:`filter`, :func:`map`, :func:`reverse`, :func:`reversed`, :func:`sort`, :func:`splitter`, :func:`zip`

.. function:: all(left, right)

    `bool all(T, U)(T left, U right)`

    Returns true if all values in the range fulfill the condition.

    Example::

        assert((0 .. 5).all(a => a < 5));

.. function:: any(left, right)

    `bool any(T, U)(T left, U right)`

    Returns true if any value in the range fulfills the condition.

    Example::

        assert((0 .. 5).any(a => a == 3));

.. function:: array(range)

    `typeof(range.front)[] array(T)(T range)`

    Converts a range into an array.

    Example::

        assert((0 .. 5).array == [0, 1, 2, 3, 4]);

.. function:: cumulativeFold(range, seed, lambda)

    `auto cumulativeFold(R, S, L)(R range, S seed, L lambda)`

    Applies a lambda repeatedly to an initial value and a value from a range, yielding the result at every step.

    Example::

        assert((1 .. 6).cumulativeFold(0, (a, b) => a + b).array == [1, 3, 6, 10, 15]);

.. function:: filter(left, right)

    `auto filter(T, U)(T left, U right)`

    Filters a range by a condition.

    Example::

        auto a = (0 .. 10).filter(a => a > 4).array;

        assert(a == [5, 6, 7, 8, 9]);

.. function:: map(left, right)

    `auto map(T, U)(T left, U right)`

    Maps a range onto a lambda.

    If the input range is `[x, y, z]`,
    the output range is `[lambda(x), lambda(y), lambda(z)]`.

    Example::

        auto a = (0 .. 5).map(a => a * 2);

        assert(a.length == 5);
        assert(a.array == [0, 2, 4, 6, 8]);

.. function:: reverse(arr)

    `void reverse(T)(T[] arr)`

    Reverse a mutable array in place.

    Example::

        int mut[] array = [2, 3, 4].dup;
        array.reverse;
        assert(array == [4, 3, 2]);

.. function:: reversed(arr)

    `T[] reversed(T)(T[] arr)`

    Given an array, return the reverse.

    Example::

        assert([2, 3, 4].reversed == [4, 3, 2]);

.. function:: sort(array, smaller)

    `T sort(T, U)(T array, U smaller)`

    TODO: document

    Example::

        // quick xorshift rng
        mut long a = 23;
        int rand() {
            mut long x = a;
            x ^= x << 13;
            x ^= x >> 7;
            x ^= x << 17;
            a = x;
            return cast(int) x;
        }
        auto randomArray = [rand % i for i in 1 .. 10_000];
        auto sortedArray = randomArray.sort((a, b) => a < b);
        assert(sortedArray.length == randomArray.length);
        // quick checksum
        assert([sum a for a in randomArray] == [sum a for a in sortedArray]);
        for (i in 0 .. sortedArray.length - 1) {
            assert(sortedArray[i] <= sortedArray[i + 1]);
        }

.. function:: splitter(range, element)

    `auto splitter(R, E)(R range, E element)`

    Given a range, returns a range of ranges consisting of the original range separated at element `element`.

    Example::

        assert([2, 3, 4, 5].splitter(4).map(a => a.array).array == [[2, 3], [5]]);

.. function:: zip(first, second)

    `auto zip(R, S)(R first, S second)`

    TODO: document

    Example::

        assert((0 .. 5).zip(3 .. 5).array == [(0, 3), (1, 4)]);