/** Extensions to std.algorithm.
    Copyright: Per Nordlöw 2018-.
    License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
    Authors: $(WEB Per Nordlöw)

    TODO: merge stuff from algorithm_ex_2.d
*/
module nxt.algorithm_ex;

/* version = show; */

import std.traits : isArray, Unqual, isIntegral, CommonType, arity, isSomeString, isExpressionTuple;
import std.range.primitives : ElementType, isInputRange, isForwardRange, isBidirectionalRange, isRandomAccessRange, front;
import nxt.traits_ex : allSame;
import std.functional : binaryFun;
import std.algorithm.searching : find;

version(show)
{
    import nxt.dbgio : dbg;
}

import std.range : dropOne;
alias tail = dropOne;

/** This overload enables, when possible, lvalue return.
 *
 * BUG: this overload is not chosen over `std.algorithm.either` so function
 * must currently be called `eitherRef` instead of `either`.
 */
ref Ts[0] eitherRef(Ts...)(ref Ts a)
if (a.length != 0 &&
    allSame!Ts)         // TODO: better trait for this?
{
    static if (Ts.length == 1)
        return a[0];
    else
        return a[0] ? a[0] : eitherRef(a[1 .. $]); // recurse
}

///
@safe pure /*TODO: nothrow*/ unittest
{
    int x = 1, y = 2;
    eitherRef(x, y) = 3;
    assert(x == 3);
    assert(y == 2);
}

/** Returns: last argument if all arguments implicitly bool-convert to `true`
 * otherwise `CommonType!T.init`.
 *
 * Similar to behaviour of `and` operator in dynamic languages such as of Lisp's
 * `(and a...)` and Python's `a and ....`.
 *
 * TODO: Is inout Conversion!T the correct return value?
*/
CommonType!T every(T...)(lazy T a)
if (T.length != 0)
{
    auto a0 = a[0]();           // evaluate only once
    static if (T.length == 1)
        return a0;
    else
        return a0 ? every(a[1 .. $]) : CommonType!T.init; // recurse
}

///
@safe pure /*TODO: nothrow*/ unittest
{
    assert(every(3) == 3);
    assert(every(3, 4) == 4);
    assert(every(0, 4) == 0);
    assert(every(0, 0) == 0);
    assert(every([0, 1], [1, 2]) == [1, 2]);
    assert(every([0, 1], [1]) == [1]);
    assert(every(`a`, `b`) == `b`);
    assert(every(``, `b`) == `b`);
    assert(every(cast(string)null, `b`) == cast(string)null);
}

version(none) // WARNING disabled because I don't see any use of this for.
{
    /** This overload enables, when possible, lvalue return.
    */
    auto ref every(T...)(ref T a)
    if (T.length != 0 && allSame!T)
    {
        static if (T.length == 1)
            return a[0];
        else
            return a[0] ? every(a[1 .. $]) : a[0]; // recurse
    }

    ///
    unittest
    {
        immutable p = 1, q = 2;
        assert(every(p, q) == 2);

        int x = 1, y = 2;
        every(x, y) = 3;
        assert(x == 1);
        assert(y == 3);
    }
}

/** Evaluate all `parts` possibly digesting `whole`.
 *
 * If all values of `parts` implicitly convert to `bool true`, return the values
 * as an array, otherwise restore whole and return null.
 */
CommonType!T[] tryEvery(S, T...)(ref S whole, lazy T parts)
if (T.length != 0)
{
    auto wholeBackup = whole;
    bool all = true;
    alias R = typeof(return);
    R results;
    foreach (result; parts) // evaluate each part
    {
        if (result)
            results ~= result;
        else
        {
            all = false;
            break;
        }
    }
    if (all)
        return results;        // ok that whole has been changed in caller scope
    else
    {
        whole = wholeBackup; // restore whole in caller scope if any failed
        return R.init;
    }
}

///
unittest
{
    auto whole = `xyz`;
    import std.algorithm.searching : skipOver;

    assert(whole.tryEvery(whole.skipOver('x'),
                          whole.skipOver('z')) == []); // failing match
    assert(whole == `xyz`); // should restore whole

    assert(whole.tryEvery(whole.skipOver('x'),
                          whole.skipOver('y'),
                          whole.skipOver('w')) == []); // failing match
    assert(whole == `xyz`); // should restore whole

    assert(whole.tryEvery(whole.skipOver('x'),
                          whole.skipOver('y')) == [true, true]); // successful match
    assert(whole == `z`); // should digest matching part
}

import std.traits : isInstanceOf;

import std.typecons : Nullable;

/** Returns: `true` iff `a` has a value containing meaningful information.
 */
bool hasContents(T)(in T a)
{
    static if (isInstanceOf!(Nullable, T))
        return !a.isNull;
    else static if (isArray!T ||
                    isSomeString!T)
        return cast(bool)a.length; // see: http://stackoverflow.com/questions/18563414/empty-string-should-implicit-convert-to-bool-true/18566334?noredirect=1#18566334
    else
        return cast(bool)a;
}

/** Reset `a` to its default value.
 *
 * Params:
 *      T = the argument type, likely to be infered.
 *      a = a reference to a T.
 *
 * See_Also: std.typecons.Nullable.nullify
 */
auto ref reset(T)(ref T a) @trusted // pure nothrow
{
    static if (isInstanceOf!(Nullable, T))
        a.nullify();
    else
        return a = T.init;
}

///
@safe @nogc pure nothrow unittest
{
    uint a = 159;
    a.reset();
    assert(a == a.init);

    string b = "bla";
    b.reset();
    assert(b == b.init);
}

///
unittest
{
    import std.typecons : Nullable;
    auto n = Nullable!(size_t,
                       size_t.max)();
    import nxt.predicates : isUntouched;
    assert(n.isUntouched);
    n = 0;
    assert(!n.isUntouched);
    assert(n == 0);
    n.reset;
    assert(n.isUntouched);
}

import std.typecons : Tuple, tuple;

/** Find `needles` in order in `haystack`. */
auto findInOrder(alias pred = `a == b`,
                 alias finder = find,
                 R,
                 E...)(R haystack,
                       E needles) /* @trusted pure nothrow */
{
    import std.range.primitives : empty;
    auto hit = haystack; // reference
    foreach (needle; needles) // for every needle in order
    {
        hit = finder!pred(hit, needle);
        if (hit.empty)
            break;
    }
    return hit;
}

///
@safe pure nothrow @nogc unittest
{
    import std.range.primitives : empty;
    assert(`a b c`.findInOrder(`a`, `b`, `c`));
    assert(`b a`.findInOrder(`a`, `b`).empty);
}

/** Returns: If `range` is symmetric.
 *
 * See_Also: http://forum.dlang.org/thread/dlfeiszyweafpjiocplf@forum.dlang.org#post-vpzuaqxvtdpzpeuorxdl:40forum.dlang.org
 * See_Also: https://stackoverflow.com/questions/21849580/equality-operator-in-favour-of-std-range-equal
 *
 * TODO: Test graphemes in `string` and `wstring`.
 * TODO: Move to Phobos
*/
bool isSymmetric(R)(R range)
if (isBidirectionalRange!(R))
{
    size_t i = 0;
    import std.range.primitives : empty;
    while (!range.empty)
    {
        import std.range.primitives : front, back, popFront, popBack;
        if (range.front != range.back)
            return false;
        range.popFront(); ++i;
        if (range.empty)
            break;
        range.popBack(); ++i;
    }
    return true;
}

///
@safe pure unittest
{
    assert(`dallassallad`.isSymmetric);
    assert(!`ab`.isSymmetric);
    assert(`a`.isSymmetric);
    assert(`åäå`.isSymmetric);
    assert(`áá`.isSymmetric);
    assert(`åäå`.isSymmetric);
    assert(``.isSymmetric);
    assert([1, 2, 2, 1].isSymmetric);
}

/** Returns: If `range` is a palindrome larger than `minLength`.
 */
bool isPalindrome(R)(R range,
                     size_t minLength = 0) // TODO: good value for minLength?
if (isBidirectionalRange!(R))
{
    static if (isRandomAccessRange!R) // arrays excluding `char[]` and `wchar[]`
        if (range.length < minLength)
            return false;
    size_t i = 0;
    // TODO: reuse `isSymmetric`
    import std.range.primitives : empty;
    while (!range.empty)
    {
        import std.range.primitives : front, back, popFront, popBack;
        if (range.front != range.back)
            return false;
        range.popFront(); ++i;
        if (range.empty)
            break;
        range.popBack(); ++i;
    }
    return i >= minLength;
}

///
@safe pure unittest
{
    assert(`dallassallad`.isPalindrome);
    assert(!`ab`.isPalindrome);
    assert(`a`.isPalindrome);
    assert(`åäå`.isPalindrome);
    assert(`áá`.isPalindrome);
    assert(`åäå`.isPalindrome);
    assert(``.isPalindrome);
    assert([1, 2, 2, 1].s[].isPalindrome);
}

import nxt.traits_ex : areEquable;

/** Return true if $(D s1) is an Anagram of $(D s2).
 *
 * Equal arguments are not considered to be an anagrams of each other.
 *
 * TODO: Is there a faster way of calculating anagrams?
 * TODO: Allow const input
 * TODO: Move to Phobos std.algorithm.sorting.
 * TODO: Should requirement isInputRange be relaxed?
 *
 * Note that implementations in http://rosettacode.org/wiki/Anagrams#D doesn't
 * correctly handle multi-byte encoded characters in string and wstring.
 */
auto isAnagramOf(R1, R2)(scope R1 r1, scope R2 r2) // TODO: nothrow
if (isInputRange!R1 &&
    isInputRange!R2 &&
    areEquable!(ElementType!R1,
                ElementType!R2))
{
    immutable sortLimit = 0;
    import std.range.primitives : empty;
    if (r1.empty || r2.empty)
        return false;
    if (r1.length + r2.length < sortLimit)
    {
        import std.algorithm.comparison : equal;
        import nxt.sort_ex : sorted; // NOTE allocates
        return equal(r1.sorted,
                     r2.sorted);
    }
    else
    {
        alias E1 = ElementType!R1;
        alias E2 = ElementType!R2;
        alias C = CommonType!(E1, E2);

        alias T = Tuple!(size_t, // R1 histogram bin count
                         size_t); // R2 histogram bin count

        import std.traits : isNarrowString;
        import std.utf : byUTF;

        // TODO: functionize
        static if (isNarrowString!R1)
            auto s1 = r1.byUTF!dchar;
        else
            auto s1 = r1; // TODO: avoid copying

        static if (isNarrowString!R2)
            auto s2 = r2.byUTF!dchar;
        else
            auto s2 = r2; // TODO: avoid copying

        // histogram
        T[C] hist;              // TODO: use non-GC-allocating AA

        // create histograms
        foreach (const ref e1; s1)
        {
            // TODO: functionize to hist.initOrUpdate(e1, T(0,1), (ref AA aa){ aa[0] += 1; })
            if (auto hit = e1 in hist)
                (*hit)[0] += 1;
            else
                hist[e1] = T(1, 0);
        }
        foreach (const ref e2; s2)
        {
            // TODO: functionize to hist.initOrUpdate(e2, T(0,1), (ref AA aa){ aa[1] += 1; })
            if (auto hit = e2 in hist)
                (*hit)[1] += 1;
            else
                hist[e2] = T(0, 1);
        }

        // check histograms
        foreach (const ref e; hist) // TODO: nothrow
            if (e[0] != e[1])
                return false;
        return true;
    }
}
alias isPermutationOf = isAnagramOf; // TODO: Only define isAnagramOf for strings?

///
@safe pure unittest
{
    assert([1, 2, 3, 4, 5].s[].isPermutationOf([1, 2, 4, 5, 3].s[]));
    assert(![1, 2, 3, 4, 5].s[].isPermutationOf([1, 4, 5, 3].s[]));
}

///
@safe pure unittest
{
    assert(!``w.isAnagramOf(``));
    assert(`äöå`w.isAnagramOf(`åäö`));
    assert(`äöå`.isAnagramOf(`åäö`w));
    assert(`äöå`w.isAnagramOf(`åäö`w));

    assert(`äöå`d.isAnagramOf(`åäö`));
    assert(`äöå`.isAnagramOf(`åäö`d));
    assert(`äöå`d.isAnagramOf(`åäö`d));
}

///
@safe pure unittest
{
    assert(`äöå`.isAnagramOf(`åäö`));
    assert(!`äöå`.isAnagramOf(`xyz`));
    assert(!`äöå`.isAnagramOf(``));
    assert(!``.isAnagramOf(`åäö`));
}
@safe pure unittest
{
    assert(`xyzxyzxyzxyzxyzxyzxyzxyz`.isAnagramOf(`xyzxyzxyzxyzxyzxyzxyzxyz`));
    assert(`xyzxyzxyzxyzxyzxyzxyzxyz`.isAnagramOf(`xxyyzzxxyyzzxxyyzzxxyyzz`));
}

///
@safe pure unittest
{
    import std.conv: to;

    auto x = `äöå`.to!(dchar[]);

    auto y = sort(x);
    alias Y = typeof(y);

    immutable z = `åäö`;

    assert(y.isAnagramOf(z));
    assert(z.isAnagramOf(y));
}

/* ref Unqual!T unqual(T)(in T x) pure nothrow if isStuct!T { return cast(Unqual!T)x; } */
/* /// */
/* unittest { */
/*     const int x; */
/*     unqual(x) = 1; */
/* } */

enum Reduction
{
    forwardDifference,
    backwardDifference,
    sum,
}

/** Generalized Windowed Reduce.
 *
 * See_Also: https://stackoverflow.com/questions/21004944/forward-difference-algorithm
 * See_Also: http://forum.dlang.org/thread/ujouqtqeehkegmtaxebg@forum.dlang.org#post-lczzsypupcfigttghkwx:40forum.dlang.org
 * See_Also: http://rosettacode.org/wiki/Forward_difference#D
*/
auto ref windowedReduce(Reduction reduction = Reduction.forwardDifference, R)(R range)
if (isInputRange!R)
{
    import std.algorithm.iteration: map;
    import std.range: zip, dropOne;
    auto ref op(T)(T a, T b) @safe pure nothrow
    {
        static      if (reduction == Reduction.forwardDifference)
            return b - a; // TODO: final static switch
        else static if (reduction == Reduction.backwardDifference)
            return a - b;
        else static if (reduction == Reduction.sum)
            return a + b;
    }
    return range.zip(range.dropOne).map!(a => op(a[0], a[1])); // a is a tuple here
}
// NOTE: Disabled for now because this solution cannot be made nothrow
/* auto ref windowedReduce(Reduction reduction = Reduction.forwardDifference, uint N = 0, R)(R range) */
/*     @safe pure /\* nothrow *\/ if (isInputRange!R) */
/* { */
/*     auto ref helper(R range) @safe pure /\* nothrow *\/ { */
/*         import std.algorithm.iteration: map; */
/*         import std.range: zip, dropOne; */
/*         //  Note: that a[0] and a[1] indexes Zip tuple */
/*         static if (reduction == Reduction.forwardDifference) */
/*             return range.zip(range.dropOne).map!(a => a[1] - a[0]); */
/*         static if (reduction == Reduction.backwardDifference) */
/*             return range.zip(range.dropOne).map!(a => a[0] - a[1]); */
/*         static if (reduction == Reduction.sum) */
/*             return range.zip(range.dropOne).map!(a => a[0] + a[1]); */
/*     } */
/*     static if (N != 0) { */
/*         return windowedReduce!(reduction, N - 1)(helper(range)); */
/*     } else { */
/*         return helper(range); */
/*     } */
/* } */

/* /// */
/* unittest { */
/*     import std.range: front; */
/*     dbg([1].windowedReduce!(Reduction.forwardDifference)); */
/*     dbg([1, 22].windowedReduce!(Reduction.forwardDifference)); */
/*     dbg([1, 22, 333].windowedReduce!(Reduction.forwardDifference)); */
/* } */

///
unittest
{
    import std.datetime : Clock, SysTime;
    SysTime[] times;
    immutable n = 4;
    foreach (_; 0 .. n)
        times ~= Clock.currTime;
    version(show) dbg(times);
    auto spans = times.windowedReduce!(Reduction.forwardDifference);
    version(show) dbg(spans);
    // dbg(*(cast(ulong*)&(spans.front)));
    version(show) import std.datetime : Duration;
    version(show) dbg(Duration.sizeof);
}

///
@safe pure unittest
{
    immutable i = [1, 4, 9, 17];
    assert(i.windowedReduce!(Reduction.forwardDifference).equal ([+3, +5, +8]));
    assert(i.windowedReduce!(Reduction.backwardDifference).equal([-3, -5, -8]));
    assert(i.windowedReduce!(Reduction.sum).equal ([+5, +13, +26]));
    assert([1].windowedReduce.empty);
    version(show) dbg(i.windowedReduce!(Reduction.sum));
}

/* TODO: Assert that ElementType!R only value semantics.  */
auto ref packBitParallelRunLengths(R)(in R x)
if (isInputRange!R)
{
    import std.bitmanip: BitArray;
    import core.bitop: bt;
    alias E = ElementType!R; // element type
    enum nBits = 8*E.sizeof;

    BitArray[nBits] runs;

    // allocate runs
    foreach (ref run; runs)
        run.length = x.length;

    /* string toString() @property @trusted const { */
    /*     typeof(return) y; */
    /*     import std.conv: to; */
    /*     foreach (run; runs) { */
    /*         y ~= run.to!string ~ "\n"; */
    /*     } */
    /*     return y; */
    /* } */

    /* size_t[nBits] counts; */

    import nxt.static_bitarray : StaticBitArray;
    import nxt.bitop_ex: testBit;
    foreach (eltIx, elt; x)
        /* StaticBitArray!nBits bits; */
        foreach (bitIndex; 0..nBits)
            runs[bitIndex][eltIx] = elt.testBit(bitIndex);
    return runs;
}
alias packBPRL = packBitParallelRunLengths;

///
pure unittest
{
    /* import backtrace.backtrace; */
    /* import std.stdio: stderr; */
    /* backtrace.backtrace.install(stderr); */
    immutable x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    immutable xPacked = x.packBitParallelRunLengths;
    version(show) dbg(xPacked);
}

/** Compute Forward Difference of `range`.
 *
 * TODO: Is there a difference between whether `R r` is immutable, const or
 * mutable?
 *
 * TODO: If `r` contains only one element return empty range.
 *
 * See_Also: https://stackoverflow.com/questions/21004944/forward-difference-algorithm
 * See_Also: http://forum.dlang.org/thread/ujouqtqeehkegmtaxebg@forum.dlang.org#post-lczzsypupcfigttghkwx:40forum.dlang.org
 * See_Also: http://rosettacode.org/wiki/Forward_difference#D
 */
auto forwardDifference(R)(R r)
if (isInputRange!R)
{
    import std.range: front, empty, popFront, dropOne;

    struct ForwardDifference
    {
        R _range;
        alias E = ElementType!R;                       // Input ElementType
        alias D = typeof(_range.front - _range.front); // Element Difference Type. TODO: Use this as ElementType of range
        D _front;
        bool _initialized = false;

        this(R range)
        in(!range.empty)
        {
            auto tmp = range;
            if (tmp.dropOne.empty) // TODO: This may be an unneccesary cost but is practical to remove extra logic
                _range = R.init; // return empty range
            else
                _range = range; // store range internally (by reference)
        }

        @property:
        auto ref front()
        {
            if (!_initialized)
                popFront();
            return _front;
        }
        auto ref moveFront()
        {
            popFront();
            return _front;
        }
        void popFront()
        {
            if (empty is false)
            {
                _initialized = true;
                E rf = _range.front;
                _range.popFront();
                if (_range.empty is false)
                    _front = _range.front - rf;
            }
        }
        bool empty() => _range.empty;
    }

    return ForwardDifference(r);
}

///
unittest
{
    auto x = [long.max, 0, 1];
    auto y = x.forwardDifference;
    version(show) dbg(y);
}

import std.traits: isCallable, ReturnType, arity;
import nxt.traits_ex: arityMin0;

/** Create Range of Elements Generated by `fun`.
 *
 * Use for example to generate random instances of return value of fun.
 *
 * TODO: I believe we need arityMin, arityMax trait here
 */
auto apply(alias fun, N)(N n)
if (// TODO: isCallable!fun &&
        arityMin0!fun &&
        !is(ReturnType!fun == void) &&
        isIntegral!N)
{
    import std.range: iota;
    import std.algorithm.iteration: map;
    return n.iota.map!(n => fun);
}

///
unittest
{
    import std.datetime: Clock;
    import std.array: array;
    immutable n = 3;
    auto times = n.apply!(Clock.currTime).array;
    version(show) dbg(times);
    auto spans = times.forwardDifference;
    version(show) dbg(spans);
}

/** In Place Ordering (in Sorted Order) of all Elements `t`.
 *
 * See_Also: https://stackoverflow.com/questions/21102646/in-place-ordering-of-elements/
 * See_Also: http://forum.dlang.org/thread/eweortsmcmibppmvtriw@forum.dlang.org#post-eweortsmcmibppmvtriw:40forum.dlang.org
*/
void orderInPlace(T...)(ref T t) @trusted
{
    import std.algorithm: sort, swap;
    static if (t.length == 2)
    {
        if (t[0] > t[1])
            swap(t[0], t[1]);
    }
    else
    {                           // generic version
        T[0][T.length] buffer;      // static buffer to capture elements
        foreach (idx, a; t)
            buffer[idx] = a;
        auto sorted = sort(buffer[]);
        foreach (idx, a; t)
            t[idx] = sorted[idx];
    }
}

///
unittest
{
    auto x = 2, y = 1;
    orderInPlace(x, y);
    assert(x == 1);
    assert(y == 2);
}

///
unittest
{
    auto x = 3, y = 1, z = 2;
    orderInPlace(x, y, z);
    assert(x == 1);
    assert(y == 2);
    assert(z == 3);
}

import std.algorithm: SwapStrategy;

/** Allow static arrays to be sorted without [].
 *
 * See_Also: http://forum.dlang.org/thread/jhzurojjnlkatjdgcfhg@forum.dlang.org
 */
template sort(alias less = `a < b`, SwapStrategy ss = SwapStrategy.unstable)
{
    import std.algorithm: stdSort = sort;
    auto sort(Arr)(ref Arr arr)
    if (__traits(isStaticArray, Arr))
    {
        return stdSort!(less, ss)(arr[]);
    }
    auto sort(Range)(Range r)
    if (!__traits(isStaticArray, Range))
    {
        return stdSort!(less, ss)(r);
    }
}

///
unittest
{
    int[5] a = [ 9, 5, 1, 7, 3 ];
    int[]  b = [ 4, 2, 1, 6, 3 ];
    sort(a);
    sort(b);
}

/** Stable Variant of Quick Sort.
 *
 * See_Also: http://forum.dlang.org/thread/gjuvmrypvxeebvztszpr@forum.dlang.org
 */
auto ref stableSort(T)(auto ref T a) pure
if (isRandomAccessRange!T)
{
    if (a.length >= 2)
    {
        import std.algorithm: partition3, sort;
        auto parts = partition3(a, a[$ / 2]); // mid element as pivot
        parts[0].sort();
        parts[2].sort();
    }
    return a;
}

///
unittest
{
    import nxt.random_ex : randInPlace;
    immutable n = 2^^16;
    auto a = new int[n];
    a.randInPlace();
    auto b = a.dup;
    a[].stableSort;
    import std.algorithm: sort;
    sort(b);
    assert(a == b);
}

/** Execute Expression `expr` the same way `n` times. */
void doTimes(uint n, lazy void expr)
{
    while (n--)
        expr();
}

/** Execute Expression `expr` $(I inline) the same way `n` times.
    `n` must be a constant known at compile time.
*/
void doTimes(uint n)(lazy void expr)
{
    static foreach (i; 0 .. n)
        expr();
}

///
unittest
{
    int i = 0;
    doTimes!4(i++);
    assert(i == 4);
}

alias loop = doTimes;
alias doN = doTimes;
alias repeat = doTimes;

/** Execute Expression `action` the same way `n` times. */
void times(alias action, N)(N n)
if (isCallable!action &&
    isIntegral!N &&
    arity!action <= 1)
{
    import std.traits: ParameterTypeTuple;
    static if (arity!action == 1 && // if one argument and
               isIntegral!(ParameterTypeTuple!action[0])) // its an integer
        foreach (i; 0 .. n)
            action(i); // use it as action input
    else
        foreach (i; 0 .. n)
            action();
}

///
unittest
{
    enum n = 10;
    int sum = 0;
    10.times!({ sum++; });
    assert(sum == n);
}

private string genNaryFun(string fun, V...)()
{
    string code;
    import std.string : format;
    foreach (n, v; V)
        code ~= "alias values[%d] %s;".format(n, cast(char)('a'+n));
    code ~= `return ` ~ fun ~ `;`;
    return code;
}
template naryFun(string fun)
{
    auto naryFun(V...)(V values)
    {
        mixin(genNaryFun!(fun, V));
    }
}

///
unittest
{
    alias test = naryFun!`a + b + c`;
    assert(test(1, 2, 3) == 6);
}

import std.meta : allSatisfy;

/** Zip `ranges` together with operation `fun`.
 *
 * TODO: Remove when Issue 8715 is fixed providing zipWith
 */
auto zipWith(alias fun, Ranges...)(Ranges ranges)
if (Ranges.length >= 2 &&
    allSatisfy!(isInputRange, Ranges))
{
    import std.range: zip;
    import std.algorithm.iteration: map;
    static if (ranges.length < 2)
        static assert(0, `Need at least 2 range arguments.`);
    else static if (ranges.length == 2)
        return zip(ranges).map!(a => binaryFun!fun(a.expand));
    else
        return zip(ranges).map!(a => naryFun!fun(a.expand));
    // return zip(ranges).map!(a => fun(a.expand));
}

///
unittest
{
    auto x = [1, 2, 3];
    import std.array: array;
    assert(zipWith!`a+b`(x, x).array == [2, 4, 6]);
    assert(zipWith!((a, b) => a + b)(x, x).array == [2, 4, 6]);
    assert(zipWith!`a+b+c`(x, x, x).array == [3, 6, 9]);
}

auto zipWith(fun, StoppingPolicy, Ranges...)(StoppingPolicy sp,
                                             Ranges ranges)
if (Ranges.length != 0 &&
    allSatisfy!(isInputRange, Ranges))
{
    import std.range: zip;
    import std.algorithm.iteration: map;
    return zip(sp, ranges).map!fun;
}

/** Pair. TODO: std.typecons */
alias Pair(T, U) = Tuple!(T, U);
/** Instantiator for `Pair`. */
auto pair(T, U)(T t, U u) { return Pair!(T, U)(t, u); }

/** Triple. TODO: std.typecons */
alias Triple(T, U, V) = Tuple!(T, U, V);
/** Instantiator for `Triple`. */
auto triple(T, U, V)(T t, U u, V v) { return Triple!(T, U, V)(t, u, v); }

/** Quadruple. TODO: std.typecons */
alias Quadruple(T, U, V, W) = Tuple!(T, U, V, W);
/** Instantiator for `Quadruple`. */
auto quadruple(T, U, V, W)(T t, U u, V v, W w) { return Quadruple!(T, U, V, W)(t, u, v, w); }

/** Limit/Span (Min,Max) Pair.
 *
 * TODO: Simultaneous min and max (minmax) can be optimized to 3/4 comparison.
 * TODO: Decide on either Span, MinMax or Limits
 * See_Also: https://stackoverflow.com/questions/21241878/generic-span-type-in-phobos
 */
struct Limits(T)
{
    import std.algorithm.comparison : min, max;

    @property:

    /** Expand Limits to include `a`. */
    auto ref include(in T a) nothrow
    {
        _lims[0] = min(_lims[0], a);
        _lims[1] = max(_lims[1], a);
        return this;
    }
    alias expand = include;

    auto ref reset() nothrow
    {
        _lims[0] = T.max;
        _lims[1] = T.min;
    }

    string toString() const
    {
        import std.conv: to;
        return (`[` ~ to!string(_lims[0]) ~
                `...` ~ to!string(_lims[1]) ~ `]`) ;
    }

    auto _lims = tuple(T.max, T.min);

    alias _lims this;
}

auto limits(T)() { return Limits!T(); }

///
unittest
{
    /* import std.file: SysTime; */
    /* SysTime st; */
    Limits!int x;
    x.expand(-10);
    x.expand(10);
    assert(x[0] == -10);
    assert(x[1] == +10);
    version(show) dbg(x);
}

/* import rational: Rational; */

/* template getTypeString(T) { */
/*     static if (is(T == Rational)) */
/*         string getTypeString(T)() @safe pure nothrow { */
/*             return x`211A`; */
/*         } */
/* } */
/* /// */
/* unittest { */
/*     import rational: Rational; */
/*     dbg(getTypeString!Rational); */
/* } */

/** Check if `a` and `b` are colinear. */
bool areColinear(T)(T a, T b)
{
    // a and b are colinear if a.x / a.y == b.x / b.y
    // We can avoid the division by multiplying out.
    return a.x * b.y == a.y * b.x;
}

/* /\** TODO: Remove when each is standard in Phobos. *\/ */
/* void each(R)(R range, delegate x) @safe pure /\* nothrow *\/ if (isInputRange!R) { */
/*     foreach (ref elt; range) { */
/*         x(elt); */
/*     } */
/* } */
/* /// */
/* unittest { */
/*     version(show) [1, 2, 3, 4].each(a => dbg(a)); */
/* } */

enum isIntLike(T) = is(typeof({T t = 0; t = t+t;})); // More if needed

/** $(LUCKY Fibonacci) Numbers (Infinite Range).
    See_Also: http://forum.dlang.org/thread/dqlrfoxzsppylcgljyyf@forum.dlang.org#post-mailman.1072.1350619455.5162.digitalmars-d-learn:40puremagic.com
    See_Also: https://www.reddit.com/r/programming/comments/rif9x/uniform_function_call_syntax_for_the_d/
*/
auto fibonacci(T = int)(T nth = 0)
if (isIntLike!T)
{
    static struct Result
    {
        T a, b;
        inout(T) front() inout => b;
        void popFront()
        {
            T c = a+b;
            a = b;
            b = c;
        }
        bool empty() const @property => false;
    }
    return nth == 0 ? Result(0, 1) : Result(1, 1);
}

///
unittest
{
    import std.range: take;
    assert(fibonacci.take(10).equal([1, 1, 2, 3, 5, 8, 13, 21, 34, 55]));
    assert(1.fibonacci.take(9).equal([1, 2, 3, 5, 8, 13, 21, 34, 55]));
}

/** Expand Static `array` into a parameter arguments (AliasSeq!).
    See_Also: http://forum.dlang.org/thread/hwellpcaomwbpnpofzlx@forum.dlang.org?page=1
*/
template expand(alias array, size_t idx = 0)
if (__traits(isStaticArray, typeof(array)))
{
    @property ref delay() { return array[idx]; }
    static if (idx + 1 < array.length)
    {
        import std.meta : AliasSeq;
        alias expand = AliasSeq!(delay, expand!(array, idx + 1));
    }
    else
        alias expand = delay;
}

///
unittest
{
    static void foo(int a, int b, int c)
    {
        version(show)
        {
            import std.stdio: writefln;
            writefln("a: %s, b: %s, c: %s", a, b, c);
        }
    }
    int[3] arr = [1, 2, 3];
    foo(expand!arr);
}

/** Python Style To-String-Conversion Alias. */
string str(T)(in T a)
{
    import std.conv: to;
    return to!string(a);
}

/** Python Style Length Alias. */
auto len(T)(in T a)
{
    return a.length;
}

///
unittest
{
    import std.algorithm.iteration: map;
    import std.array: array;
    assert(([42].map!str).array == [`42`]);
}

import std.range: InputRange, OutputRange;
alias Source = InputRange; // nicer alias
alias Sink = OutputRange; // nicer alias

/* belongs to std.range */
import std.range: cycle, retro;
import std.functional: compose;
alias retroCycle = compose!(cycle, retro);

import std.traits: isAggregateType;

/** Generic Member Setter.
    See_Also: http://forum.dlang.org/thread/fdjkijrtduraaajlxxne@forum.dlang.org
*/
auto ref T set(string member, T, U)(auto ref T a, in U value)
if (isAggregateType!T &&
    __traits(hasMember, T, member))
{
    __traits(getMember, a, member) = value;
    return a;
}

///
unittest
{
    class C { int x, y, z, w; }
    auto c = new C().set!`x`(11).set!`w`(44);
    assert(c.x == 11);
    assert(c.w == 44);
}

/* Check if `part` is part of `whole`.
   See_Also: http://forum.dlang.org/thread/ls9dbk$jkq$1@digitalmars.com
   TODO: Standardize name and remove alises.
 */
bool isSliceOf(T)(in T[] part,
                  in T[] whole)
{
    return (whole.ptr <= part.ptr &&
            part.ptr + part.length <=
            whole.ptr + whole.length);
}

/* See_Also: http://forum.dlang.org/thread/cjpplpzdzebfxhyqtskw@forum.dlang.org#post-cjpplpzdzebfxhyqtskw:40forum.dlang.org */
auto dropWhile(alias pred = `a == b`, R, E)(R range, E element)
if (isInputRange!R &&
    is (typeof(binaryFun!pred(range.front, element)) : bool))
{
    alias predFun = binaryFun!pred;
    return range.find!(a => !predFun(a, element));
}
alias dropAllOf = dropWhile;
alias stripFront = dropWhile;
alias lstrip = dropWhile;       // Python style

import std.algorithm.searching: until;
alias takeUntil = until;

alias dropUntil = find;

///
unittest
{
    assert([1, 2, 3].dropWhile(1) == [2, 3]);
    assert([1, 1, 1, 2, 3].dropWhile(1) == [2, 3]);
    assert([1, 2, 3].dropWhile(2) == [1, 2, 3]);
    assert(`aabc`.dropWhile('a') == `bc`); // TODO: Remove restriction on cast to dchar
}

/* See_Also: http://forum.dlang.org/thread/cjpplpzdzebfxhyqtskw@forum.dlang.org#post-cjpplpzdzebfxhyqtskw:40forum.dlang.org */
auto takeWhile(alias pred = `a == b`, R, E)(R range, E element)
if (isInputRange!R &&
    is (typeof(binaryFun!pred(range.front, element)) : bool))
{
    import std.algorithm: until;
    alias predFun = binaryFun!pred;
    return range.until!(a => !predFun(a, element));
}
alias takeAllOf = takeWhile;

///
unittest
{
    assert(equal([1, 1, 2, 3].takeWhile(1),
                 [1, 1]));
}

/** Simpler variant of Phobos' `split`. */
auto split(alias pred, R)(R haystack)
if (isForwardRange!R)
{
    import std.range.primitives : empty;
    static if (isSomeString!R ||
               isRandomAccessRange!R)
    {
        auto balance = find!pred(haystack);
        immutable pos1 = haystack.length - balance.length;
        immutable pos2 = balance.empty ? pos1 : pos1 + 1;
        return tuple(haystack[0 .. pos1],
                     haystack[pos1 .. pos2],
                     haystack[pos2 .. haystack.length]);
    }
    else
    {
        import std.functional : unaryFun;
        auto original = haystack.save;
        auto h = haystack.save;
        size_t pos1, pos2;
        while (!h.empty)
        {
            if (unaryFun!pred(h.front))
            {
                h.popFront();
                ++pos2;
            }
            else
            {
                haystack.popFront();
                h = haystack.save;
                pos2 = ++pos1;
            }
        }
        // TODO: use Voldemort struct instead of tuple
        return tuple(takeExactly(original, pos1),
                     takeExactly(haystack, pos2 - pos1),
                     h);
    }
}

///
unittest
{
    import std.ascii: isDigit;
    assert(`aa1bb`.split!(a => a.isDigit) == tuple(`aa`, `1`, `bb`));
    assert(`aa1`.split!(a => a.isDigit) == tuple(`aa`, `1`, ``));
    assert(`1bb`.split!(a => a.isDigit) == tuple(``, `1`, `bb`));
}

/** Simpler variant of Phobos' `splitBefore`. */
auto splitBefore(alias pred, R)(R haystack)
if (isForwardRange!R)
{
    static if (isSomeString!R ||
               sRandomAccessRange!R)
    {
        auto balance = find!pred(haystack);
        immutable pos = haystack.length - balance.length;
        return tuple(haystack[0 .. pos],
                     haystack[pos .. haystack.length]);
    }
    else
    {
        import std.functional : unaryFun;
        auto original = haystack.save;
        auto h = haystack.save;
        size_t pos;
        import std.range.primitives : empty;
        while (!h.empty)
            if (unaryFun!pred(h.front))
                h.popFront();
            else
            {
                haystack.popFront();
                h = haystack.save;
                ++pos;
            }
        // TODO: use Voldemort struct instead of tuple
        return tuple(takeExactly(original, pos),
                     haystack);
    }
}

///
unittest
{
    import std.ascii: isDigit;
    assert(`11ab`.splitBefore!(a => !a.isDigit) == tuple(`11`, `ab`));
    assert(`ab`.splitBefore!(a => !a.isDigit) == tuple(``, `ab`));
}

auto splitAfter(alias pred, R)(R haystack)
if (isForwardRange!R)
{
    static if (isSomeString!R || isRandomAccessRange!R)
    {
        import std.range.primitives : empty;
        auto balance = find!pred(haystack);
        immutable pos = balance.empty ? 0 : haystack.length - balance.length + 1;
        // TODO: use Voldemort struct instead of tuple
        return tuple(haystack[0 .. pos], haystack[pos .. haystack.length]);
    }
    else
    {
        static assert(0, `How to implement this?`);
        // import std.range.primitives : empty;
        /* auto original = haystack.save; */
        /* auto h = haystack.save; */
        /* size_t pos1, pos2; */
        /* while (!n.empty) */
        /* { */
        /*     if (h.empty) */
        /*     { */
        /*         // Failed search */
        /*         return tuple(takeExactly(original, 0), original); */
        /*     } */
        /*     if (binaryFun!pred(h.front, n.front)) */
        /*     { */
        /*         h.popFront(); */
        /*         n.popFront(); */
        /*         ++pos2; */
        /*     } */
        /*     else */
        /*     { */
        /*         haystack.popFront(); */
        /*         n = needle.save; */
        /*         h = haystack.save; */
        /*         pos2 = ++pos1; */
        /*     } */
        /* } */
        /* return tuple(takeExactly(original, pos2), h); */
    }
}

///
unittest
{
    import std.ascii: isDigit;
    assert(`aa1bb`.splitAfter!(a => a.isDigit) == tuple(`aa1`, `bb`));
    assert(`aa1`.splitAfter!(a => a.isDigit) == tuple(`aa1`, ``));
}

auto moveUntil(alias pred, R)(ref R r)
if (isInputRange!R)
{
    auto split = r.splitBefore!pred;
    r = split[1];
    return split[0];
}

///
unittest
{
    auto r = `xxx111`;
    auto id = r.moveUntil!(a => a == '1');
    assert(id == `xxx`);
    assert(r == `111`);
}

auto moveWhile(alias pred, R)(ref R r)
if (isInputRange!R)
{
    return r.moveUntil!(a => !pred(a));
}

///
unittest
{
    auto r = `xxx111`;
    auto id = r.moveWhile!(a => a == 'x');
    assert(id == `xxx`);
    assert(r == `111`);
}

/** Variant of `findSplitBefore` that destructively pops everything up to,
    not including, `needle` from `haystack`.
*/
auto findPopBefore(alias pred = `a == b`, R1, R2)(ref R1 haystack, R2 needle)
if (isForwardRange!R1 &&
    isForwardRange!R2)
{
    import std.range.primitives : empty;

    if (needle.empty)
        return haystack[0 .. 0]; // contextual empty hit
    if (haystack.empty)
        return R1.init;

    import std.algorithm.searching : findSplitBefore;
    if (auto split = findSplitBefore!pred(haystack, needle)) // TODO: If which case are empty and what return value should they lead to?
    {
        haystack = split[1];
        return split[0];
    }
    else
        return R1.init; // TODO: correct?
}

///
@safe pure nothrow @nogc unittest
{
    auto haystack = `xy`;
    const needle = `z`;
    auto pop = haystack.findPopBefore(needle);
    assert(haystack == `xy`);
    assert(pop == ``);
}

///
@safe pure nothrow @nogc unittest
{
    auto haystack = `xyz`;
    const needle = `y`;
    auto pop = haystack.findPopBefore(needle);
    assert(pop == `x`);
    assert(haystack == `yz`);
}

/** Variant of `findSplitAfter` that destructively pops everything up to,
    including, `needle` from `haystack`.
*/
auto findPopAfter(alias pred = `a == b`, R1, R2)(ref R1 haystack, R2 needle)
if (isForwardRange!R1 &&
    isForwardRange!R2)
{
    import std.range.primitives : empty;

    if (needle.empty)
        return haystack[0 .. 0]; // contextual empty hit
    if (haystack.empty)
        return R1.init;

    import std.algorithm.searching : findSplitAfter;
    auto split = findSplitAfter!pred(haystack, needle);// TODO: use new interface to findSplitAfter
    if (split[0].empty)
        return R1.init; // TODO: correct?
    else
    {
        haystack = split[1];
        return split[0];
    }
}

///
@safe pure nothrow @nogc unittest
{
    auto source = `xyz`;
    auto haystack = source;
    const needle = `y`;
    auto pop = haystack.findPopAfter(needle);
    assert(pop == `xy`);
    assert(haystack == `z`);
}

///
@safe pure nothrow @nogc unittest
{
    auto source = `xy`;
    auto haystack = source;
    const needle = `z`;
    auto pop = haystack.findPopAfter(needle);
    assert(pop is null);
    assert(!pop);
    assert(haystack == source);
}

/** Find First Occurrence any of `needles` in `haystack`.
 *
 * Like to std.algorithm.find but takes an array of needles as argument instead
 * of a variadic list of key needle arguments.  Return found range plus index
 * into needles starting at 1 upon.
 */
Tuple!(R, size_t) findFirstOfAnyInOrder(alias pred = `a == b`, R)(R haystack, const R[] needles)
{
    import std.algorithm.searching : find;
    switch (needles.length)
    {
        case 1:
            import std.range.primitives : empty;
            auto hit = haystack.find(needles[0]);
            return tuple(hit, hit.empty ? 0UL : 1UL);
        case 2:
            return haystack.find(needles[0],
                                 needles[1]);
        case 3:
            return haystack.find(needles[0],
                                 needles[1],
                                 needles[2]);
        case 4:
            return haystack.find(needles[0],
                                 needles[1],
                                 needles[2],
                                 needles[3]);
        case 5:
            return haystack.find(needles[0],
                                 needles[1],
                                 needles[2],
                                 needles[3],
                                 needles[4]);
        case 6:
            return haystack.find(needles[0],
                                 needles[1],
                                 needles[2],
                                 needles[3],
                                 needles[4],
                                 needles[5]);
        case 7:
            return haystack.find(needles[0],
                                 needles[1],
                                 needles[2],
                                 needles[3],
                                 needles[4],
                                 needles[5],
                                 needles[6]);
        case 8:
            return haystack.find(needles[0],
                                 needles[1],
                                 needles[2],
                                 needles[3],
                                 needles[4],
                                 needles[5],
                                 needles[6],
                                 needles[7]);
        default:
            import std.conv: to;
            assert(0, `Too many keys ` ~ needles.length.to!string);
    }
}

///
@safe pure unittest
{
    assert(`abc`.findFirstOfAnyInOrder([`x`]) == tuple(``, 0UL));
    assert(`abc`.findFirstOfAnyInOrder([`a`]) == tuple(`abc`, 1UL));
    assert(`abc`.findFirstOfAnyInOrder([`c`]) == tuple(`c`, 1UL));
    assert(`abc`.findFirstOfAnyInOrder([`a`, `b`]) == tuple(`abc`, 1UL));
    assert(`abc`.findFirstOfAnyInOrder([`a`, `b`]) == tuple(`abc`, 1UL));
    assert(`abc`.findFirstOfAnyInOrder([`x`, `b`]) == tuple(`bc`, 2UL));
}

Tuple!(R, size_t)[] findAllOfAnyInOrder(alias pred = `a == b`, R)(R haystack, R[] needles)
{
    // TODO: Return some clever lazy range that calls each possible haystack.findFirstOfAnyInOrder(needles);
    return typeof(return).init;
}

/** Return true if all arguments `args` are strictly ordered, that is args[0] <
 * args[1] < args[2] < ... .
 *
 * TODO: CT-variant
 * See_Also: http://forum.dlang.org/thread/wzsdhzycwqyrvqmmttix@forum.dlang.org?page=2#post-vprvhifglfegnlvzqmjj:40forum.dlang.org
 */
bool areStrictlyOrdered(Ts...)(Ts args)
if (args.length >= 2 &&
    haveCommonType!Ts)
{
    foreach (i, arg; args[1..$])
        if (args[i] >= arg)
            return false;
    return true;
}

///
@safe pure nothrow @nogc unittest
{
    static assert(!__traits(compiles, areStrictlyOrdered()));
    static assert(!__traits(compiles, areStrictlyOrdered(1)));
    assert(areStrictlyOrdered(1, 2, 3));
    assert(!areStrictlyOrdered(1, 3, 2));
    assert(!areStrictlyOrdered(1, 2, 2));
    assert(areStrictlyOrdered('a', 'b', 'c'));
}

/** Return true if all arguments `args` are unstrictly ordered,
 * that is args[0] <= args[1] <= args[2] <= ... .
 *
 * TODO: CT-variant
 * See_Also: http://forum.dlang.org/thread/wzsdhzycwqyrvqmmttix@forum.dlang.org?page=2#post-vprvhifglfegnlvzqmjj:40forum.dlang.org
*/
bool areUnstrictlyOrdered(Ts...)(Ts args)
if (args.length >= 2 &&
    haveCommonType!Ts)
{
    foreach (i, arg; args[1..$])
        if (args[i] > arg)
            return false;
    return true;
}

///
@safe pure nothrow @nogc unittest
{
    static assert(!__traits(compiles, areUnstrictlyOrdered()));
    static assert(!__traits(compiles, areUnstrictlyOrdered(1)));
    assert(areUnstrictlyOrdered(1, 2, 2, 3));
    assert(!areUnstrictlyOrdered(1, 3, 2));
    assert(areUnstrictlyOrdered('a', 'b', 'c'));
}

import core.checkedint: addu, subu, mulu;

alias sadd = addu;
alias ssub = subu;
alias smul = mulu;

/** Distinct Elements of `r`.
 *
 * See_Also: http://forum.dlang.org/thread/jufggxqwzhlsmhshtnfj@forum.dlang.org?page=2
 * See_Also: http://dpaste.dzfl.pl/7b4b37b490a7
 */
auto distinct(R)(R r)
if (isInputRange!(Unqual!R))
{
    import std.traits: ForeachType;
    bool[ForeachType!R] seen; // TODO: Use containers.hashset.HashSet
    import std.algorithm.iteration: filter;
    return r.filter!((k)
                     {
                         if (k !in seen)
                             return false;
                         else
                             return seen[k] = true;
                     });
}

// unittest
// {
//     immutable first = [1, 0, 2, 1, 3];
//     immutable second = [1,5,6];
//     import std.range: chain, take;
//     assert(equal(first.chain(second).distinct.take(5),
//                  [1, 0, 2, 3, 5]));
// }

/** Returns: `true` iff `value` is equal to any of `values`, `false` otherwise. */
bool isAmong(alias pred = (a, b) => a == b,
             Value,
             Values...)(Value value,
                        Values values)
if (Values.length != 0)
{
    import std.algorithm.comparison : among;
    return cast(bool)value.among!pred(values);
}

///
@safe pure nothrow @nogc unittest
{
    assert(`b`.isAmong(`a`, `b`));
    assert(!`c`.isAmong(`a`, `b`));
}

import std.traits : isExpressionTuple;
import nxt.traits_ex : haveCommonType;

/** Returns: `true` iff `value` is equal to any of `values`, `false` otherwise. */
template isAmong(values...)
if (isExpressionTuple!values &&
    values.length != 0)
{
    bool isAmong(Value)(Value value)
        if (haveCommonType!(Value, values))
    {
        switch (value)
        {
            foreach (uint i, v; values)
            case v:
                return true;
        default:
            return false;
        }
    }
}

///
@safe pure nothrow @nogc unittest
{
    assert(`b`.isAmong!(`a`, `b`));
    assert(!`c`.isAmong!(`a`, `b`));
}

import std.algorithm.setops : cartesianProduct;

/** More descriptive alias. */
alias elementCombinations = cartesianProduct;

/** Reset all members in aggregate instance `c`.
 *
 * See_Also: http://forum.dlang.org/post/ckitmpguywfitgadfpkv@forum.dlang.org
 * See_Also: http://forum.dlang.org/post/fbs8b5$5bu$1@digitalmars.com
 */
void resetAllMembers(T)(T c)
if (is(T == class))
{
    foreach (ref m; c.tupleof)
    {
        import std.traits : isMutable;
        alias M = typeof(m);
        static if (isMutable!M)
            m = M.init;
    }
}

///
@safe pure nothrow unittest
{
    class C
    {
        this (int a, int b, string c)
        {
            this.a = a;
            this.b = b;
            this.c = c;
        }
        int a; int b; string c;
    }
    void f(C c)
    {
        c.resetAllMembers();
    }
    auto c = new C(1, 2, "3");
    assert(c.a == 1);
    assert(c.b == 2);
    assert(c.c == "3");
    f(c);
    assert(c.a == 0);
    assert(c.b == 0);
    assert(c.c == null);
}

/** Returns: `true` iff `r` contains strictly values that are strictly increase
 * with the increment `step`.
 *
 * See_Also: http://forum.dlang.org/post/mqjyhvqxepgfljpkxvmd@forum.dlang.org
 */
bool isLinearRamp(R)(R r, size_t step = 1)
if (isInputRange!R &&
    isIntegral!(ElementType!R))
{
    import std.algorithm.searching : findAdjacent;
    import std.range.primitives : empty;
    return r.findAdjacent!((a, b) => a + step != b).empty;
}

bool hasHoles(R)(R r)
if (isInputRange!R &&
    isIntegral!(ElementType!R))
{
    return !r.isLinearRamp;
}

///
@safe pure nothrow unittest
{
    assert([1].isLinearRamp);
    assert([1, 2, 3].isLinearRamp);
    assert(![1, 1].isLinearRamp);
    assert(![1, 2, 1].isLinearRamp);
    assert(![1, 2, 4].isLinearRamp);
}

/** Check if `r` counts to exactly `exactCount` elements.
 */
bool countsExactly(R)(R r, size_t exactCount) @("complexity", "O(exactCount)")
if (isInputRange!R)
{
    import std.range.primitives : hasLength;
    static if (hasLength!R)
        return r.length == exactCount;
    else
    {
        size_t n = 0;
        import std.range.primitives : empty;
        while (!r.empty)
        {
            r.popFront();
            if (++n > exactCount)
                return false;
        }
        return n == exactCount;
    }
}

/** Check if `r` counts to at least `minCount` elements.
 */
bool countsAtLeast(R)(R r, size_t minCount) @("complexity", "O(minCount)")
if (isInputRange!R)
{
    import std.range.primitives : hasLength;
    static if (hasLength!R)
        return r.length >= minCount;
    else
    {
        size_t n;
        import std.range.primitives : empty;
        while (!r.empty)
        {
            r.popFront();
            if (++n >= minCount)
                return true;
        }
        return false;
    }
}

/** Check if `r` counts to at most `maxCount` elements.
 */
bool countsAtMost(R)(R r, size_t maxCount) @("complexity", "O(maxCount)")
if (isInputRange!R)
{
    import std.range.primitives : hasLength;
    static if (hasLength!R)
        return r.length <= maxCount;
    else
    {
        size_t n;
        import std.range.primitives : empty;
        while (!r.empty)
        {
            r.popFront();
            if (++n > maxCount)
                return false;
        }
        return true;
    }
}

///
@safe pure nothrow @nogc unittest
{
    static void test(R)(R x)
        if (isInputRange!R)
    {
        import std.algorithm.searching : count;
        immutable n = x.count;

        // below
        foreach (immutable i; 0 .. n)
        {
            assert(x.countsAtLeast(i));
            assert(!x.countsExactly(i));
            assert(!x.countsAtMost(i));
        }

        // at
        assert(x.countsAtLeast(n));
        assert(x.countsExactly(n));
        assert(x.countsAtMost(n));

        // above
        foreach (immutable i; n + 1 .. n + 10)
        {
            assert(!x.countsAtLeast(i));
            assert(!x.countsExactly(i));
            assert(x.countsAtMost(i));
        }
    }

    import std.algorithm.iteration : filter;
    import std.range : iota;

    test(3.iota.filter!(x => true));

    int[3] x = [0, 1, 2];
    test(x[]);
}

import std.meta : allSatisfy;
import std.range.primitives : hasLength;

/** Returns: `true` iff `r` and all `ss` all have equal length.
 */
bool equalLength(R, Ss...)(const R r, const Ss ss)
    @safe pure nothrow @nogc
if (Ss.length != 0 &&
    allSatisfy!(hasLength, R, Ss))
{
    foreach (const ref s; ss)
        if (r.length != s.length)
            return false;
    return true;
}

///
@safe pure nothrow unittest
{
    assert(equalLength([1], [2], [3]));
    assert(!equalLength([1, 1], [2], [3]));
    assert(!equalLength([1], [2, 2], [3]));
    assert(!equalLength([1], [2], [3, 3]));
}

/** Collect/Gather the elements of `r` into a `Container` and return it.
 *
 * TODO: Use std.container.util.make instead?: https://dlang.org/phobos/std_container_util.html#.make
 * TODO: Rename `container` to `output`?
 * TODO: Support Set-containers via `insert` aswell, or add `alias put = insert` to them?
 * TODO: What about `Appender`?
 * TODO: Rename from `collect` to `gather`.
 */
Container collect(Container, Range) (Range r)
    // if (isInputRange!Range &&
    //     isOutputRange!(Container, ElementType!Range))
{
    static if (hasLength!Range)
    {
        static if (isArray!Container)
        {
            import std.array : uninitializedArray;
            auto output = uninitializedArray!(Container)(r.length);
        }
        else
        {
            Container output;
            output.length = r.length;
        }
        import std.algorithm.mutation : copy;
        r.copy(output[]);       // slicing is @trusted
        return output;
    }
    else
    {
        static if (isArray!Container)
        {
            import std.array : Appender;
            Appender!Container output;
            foreach (ref e; r)  // TODO: make const when this works with array_ex
                output.put(e);
            return output.data;
        }
        else
        {
            Container output;
            foreach (ref e; r)  // TODO: make const when this works with array_ex
                output ~= e; // TODO: use Appender or remove because too GC.intensive inefficient, or reuse `.array`?
            return output;
        }
    }
}

///
@safe pure nothrow unittest
{
    import std.range : iota;
    import std.algorithm.iteration : map, filter;
    import nxt.algorithm_ex : collect;

    alias E = int;
    alias V = E[];
    immutable n = 1000;

    auto x = 0.iota(n).collect!V;

    assert([0, 1, 2].map!(_ => _^^2).collect!V.equal([0, 1, 4]));
    assert([0, 1, 2, 3].filter!(_ => _ & 1).collect!V.equal([1, 3]));
}

/** Returns: `x` eagerly split in two parts, all as equal in length as possible.
 *
 * Safely avoids range checking thanks to D's builtin slice expressions.
 * Use in divide-and-conquer algorithms such as quicksort and binary search.
 */
auto spliced2(T)(T[] x) @trusted
{
    static struct Result        // Voldemort type
    {
        T[] first;              // first half
        T[] second;             // second half
    }
    immutable m = x.length / 2;
    // range checking is not needed
    return Result(x.ptr[0 .. m], // can be @trusted
                  x.ptr[m .. x.length]); // can be @trusted
}
alias halved = spliced2;

///
@safe pure nothrow @nogc unittest
{
    immutable int[6] x = [0, 1, 2, 3, 4, 5];
    immutable y = x.spliced2;
    assert(y.first.equal(x[0 .. 3]));
    assert(y.second.equal(x[3 .. $]));
}

/** Returns: `x` eagerly split in three parts, all as equal in length as possible.
 *
 * Safely avoids range checking thanks to D's builtin slice expressions.
 * Use in divide-and-conquer algorithms such as quicksort and binary search.
 */
auto spliced3(T)(T[] x) @trusted
{
    enum count = 3;
    static struct Result        // Voldemort type
    {
        T[] first;              // first half
        T[] second;             // second half
        T[] third;              // third half
    }
    // range checking is not needed
    immutable m = 1*x.length/count;
    immutable n = 2*x.length/count;
    return Result(x.ptr[0 .. m], // can be @trusted
                  x.ptr[m .. n], // can be @trusted
                  x.ptr[n .. x.length]); // can be @trusted
}

@safe pure nothrow @nogc unittest
{
    immutable int[6] x = [0, 1, 2, 3, 4, 5];
    immutable y = x.spliced3;
    assert(y.first.equal(x[0 .. 2]));
    assert(y.second.equal(x[2 .. 4]));
    assert(y.third.equal(x[4 .. 6]));
}

/** Splice `x` in `N` parts, all as equal in lengths as possible.
 *
 * Safely avoids range checking thanks to D's builtin slice expressions.
 * Use in divide-and-conquer algorithms such as quicksort and binary search.
 */
auto splicerN(uint N, T)(T[] x) @trusted
{
    static struct Result        // Voldemort type
    {
        enum count = N;
        pragma(inline) @trusted pure nothrow @nogc:

        /// Returns: `i`:th slice.
        inout(T)[] at(uint i)() inout
        {
            static assert(i < N, "Index " ~ i ~ " to large");
            static if (i == 0)
                return _.ptr[0 .. (i + 1)*_.length/N]; // can be @trusted
            else static if (i + 1 == N)
                return _.ptr[i * _.length/N .. _.length]; // can be @trusted
            else
                return _.ptr[i * _.length/N .. (i + 1)*_.length/N]; // non-range-checked can be @trusted
        }

        private T[] _;
    }
    return Result(x);
}

///
@safe pure nothrow @nogc unittest
{
    enum count = 6;

    immutable int[count] x = [0, 1, 3, 3, 4, 5];
    immutable y = x.splicerN!count;

    static foreach (i; 0 .. count)
    {
        assert(y.at!i.equal(x[i .. i + 1]));
    }
}

/** Specialization of `splicerN` to `N` being 2. */
auto splicer2(T)(T[] x) @trusted
{
    static struct Result        // Voldemort type
    {
        enum count = 2;
        pragma(inline) @trusted pure nothrow @nogc:

        /// Returns: first part of splice.
        @property inout(T)[] first() inout
        {
            return _.ptr[0 .. _.length/count]; // can be @trusted
        }

        /// Returns: second part of splice.
        @property inout(T)[] second() inout
        {
            return _.ptr[_.length/count .. _.length]; // can be @trusted
        }

        inout(T)[] at(uint i)() inout
        {
            static assert(i < count, "Index " ~ i ~ " to large");
            static      if (i == 0)
                return first;
            else static if (i == 1)
                return second;
        }

        private T[] _;
    }
    return Result(x);
}

///
@safe pure nothrow @nogc unittest
{
    immutable int[6] x = [0, 1, 2, 3, 4, 5];
    immutable y = x.splicer2;
    assert(y.first.equal(x[0 .. 3]));
    assert(y.second.equal(x[3 .. $]));
    assert(y.at!0.equal(x[0 .. 3]));
    assert(y.at!1.equal(x[3 .. $]));
}

/** Specialization of `splicerN` to `N` being 3. */
auto splicer3(T)(T[] x) @trusted
{
    static struct Result        // Voldemort type
    {
        enum count = 3;
        pragma(inline) @trusted pure nothrow @nogc:

        /// Returns: first part of splice.
        @property inout(T)[] first() inout
        {
            return _.ptr[0 .. _.length/count];  // can be @trusted
        }

        /// Returns: second part of splice.
        @property inout(T)[] second() inout
        {
            return _.ptr[_.length/count .. 2*_.length/count];  // can be @trusted
        }

        /// Returns: third part of splice.
        @property inout(T)[] third() inout
        {
            return _.ptr[2*_.length/count .. _.length]; // can be @trusted
        }

        private T[] _;
    }
    return Result(x);
}

///
@safe pure nothrow @nogc unittest
{
    immutable int[6] x = [0, 1, 3, 3, 4, 5];
    immutable y = x.splicer3;
    assert(y.first.equal(x[0 .. 2]));
    assert(y.second.equal(x[2 .. 4]));
    assert(y.third.equal(x[4 .. $]));
}

/**
   See_Also: http://forum.dlang.org/post/mqfaevkvhwwtzaafrtve@forum.dlang.org
 */
auto use(alias F, T)(T t) if (is(typeof(F(T.init)))) => F(t);

@safe pure nothrow @nogc unittest
{
    foreach (const i; 1 .. 11)
        foreach (const j; 1 .. 11)
            immutable result = (i * j).use!(x => x*x);
}

import nxt.char_traits : isASCII;

/** TOOD Merge into Phobos' startsWith. */
template startsWith(needles...)
if (isExpressionTuple!needles &&
    needles.length != 0)
{
    uint startsWith(Haystack)(Haystack haystack) @trusted
        if (!is(CommonType!(typeof(Haystack.front), needles) == void))
    {
        if (haystack.length == 0)
            return 0;
        static if (isArray!Haystack &&
                   is(typeof(Haystack.init[0]) : char) &&
                   allSatisfy!(isASCII, needles))
        {
            // no front decoding needed
            static if (needles.length == 1)
                return haystack.ptr[0] == needles[0] ? 1 : 0;
            else
            {
                import std.algorithm.comparison : among;
                return haystack.ptr[0].among!(needles);
            }
        }
        else
        {
            import std.range.primitives : front; // need decoding
            import std.algorithm.comparison : among;
            return haystack.front.among!(needles);
        }
    }
}

@safe pure nothrow @nogc unittest
{
    const haystack = "abc";
    assert(haystack.startsWith!('a'));
    assert(!haystack.startsWith!('b'));
}

@safe pure unittest
{
    const haystack = "äbc";
    assert(haystack.startsWith!('ä'));
}

@safe pure nothrow @nogc unittest
{
    const haystack = "abc";
    assert(haystack.startsWith!('b') == 0);
    assert(haystack.startsWith!('a') == 1);
    assert(haystack.startsWith!('_',
                                'a') == 2);
}

/** TOOD Merge into Phobos' endsWith. */
template endsWith(needles...)
if (isExpressionTuple!needles &&
    needles.length != 0)
{
    uint endsWith(Haystack)(Haystack haystack)
        @trusted
    if (!is(CommonType!(typeof(Haystack.back), needles) == void))
    {
        if (haystack.length == 0)
            return 0;
        static if (isArray!Haystack &&
                   is(Unqual!(typeof(Haystack.init[0])) == char) && // TODO: reuse existing trait
                   allSatisfy!(isASCII, needles))
        {
            // no back decoding needed
            static if (needles.length == 1)
                return haystack.ptr[haystack.length - 1] == needles[0] ? 1 : 0;
            else
            {
                import std.algorithm.comparison : among;
                return haystack.ptr[haystack.length - 1].among!(needles);
            }
        }
        else
        {
            import std.range.primitives : back; // need decoding
            import std.algorithm.comparison : among;
            return haystack.back.among!(needles);
        }
    }
}

@safe pure nothrow @nogc unittest
{
    const haystack = "abc";
    assert(haystack.endsWith!('b') == 0);
    assert(haystack.endsWith!('c') == 1);
    assert(haystack.endsWith!('_',
                              'c') == 2);
}

@safe pure unittest
{
    const haystack = "abć";
    assert(haystack.endsWith!('ć'));
}

/**
 * Allows forbidden casts.
 *
 * Params:
 *      OT = The output type.
 *      IT = The input type, optional, likely to be infered.
 *      it = A reference to an IT.
 *
 * Returns:
 *      the same as $(D cast(OT) it), except that it never fails to compile.
 */
auto bruteCast(OT, IT)(auto ref IT it) => *cast(OT*) &it;

///
nothrow pure @nogc unittest
{
    static immutable array = [0u,1u,2u];
    size_t len;
    //len = cast(uint) array; // not allowed.
    len = bruteCast!uint(array);
    assert(len == array.length);
}

/** Split `range` using multiple separators stored as elements in `separators`.
 *
 * See_Also: https://forum.dlang.org/post/nv60ra$9vc$1@digitalmars.com
 */
auto splitterN(R, S)(scope return R range,
                     const scope S separators)
{
    import std.algorithm.iteration : splitter;
    import std.algorithm.searching : canFind;
    return range.splitter!(element => separators.canFind(element));
}

///
@safe pure unittest
{
    auto result = "a-b+c".splitterN("+-");
    assert(result.equal(["a", "b", "c"].s[]));
}

// splitter is nothrow @nogc when `haystack` is of same NarrowString as `needle`
@safe pure nothrow @nogc unittest
{
    import std.algorithm.iteration : splitter;
    assert("a b".splitter(" ").equal(["a", "b"].s[]));
}

version(unittest)
{
    import std.algorithm.comparison : equal;
    import nxt.array_help : s;
}