/** Probing algoriths used by for instance hash tables.
 */
module nxt.probing;

import std.functional : unaryFun, binaryFun;

/** Search for a key in `haystack` matching predicate `pred` starting at `index`
 * in steps of triangular numbers, 0,1,3,6,10,15,21, ... .
 *
 * If `assumeNonFullHaystack` is `true` it is assumed that at least one element
 * in `haystack` matches `pred`, thereby enabling sentinel-based probing. Such
 * probing doesn't require in-loop range checking via `indexIncrement !=
 * haystack.length` and can be made faster.
 *
 * Returns: index into `haystack` upon hit, `haystack.length` upon miss.
 *
 * Note: `haystack.length` must be a power of two (or 1 or zero).
 *
 * See_Also: https://fgiesen.wordpress.com/2015/02/22/triangular-numbers-mod-2n/
 */
size_t triangularProbeFromIndex(alias pred,
                                bool assumeNonFullHaystack = false,
                                T)(const scope T[] haystack, size_t index)
if (is(typeof(unaryFun!pred(T.init))) ||
    is(typeof(binaryFun!pred(size_t.init, T.init))))
{
    immutable mask = haystack.length - 1;
    assert((~mask ^ mask) == typeof(return).max); // std.math.isPowerOf2(haystack.length)

    static if (assumeNonFullHaystack)
    {
        assert(haystack.length != 0, "haystack cannot be empty");
    }

    // search using triangular numbers as increments
    size_t indexIncrement = 0;
    while (true)
    {
        static if (assumeNonFullHaystack)
        {
            assert(indexIncrement != haystack.length,
                   "no element in `haystack` matches `pred`, cannot used sentinel-based probing");
        }
        else
        {
            if (indexIncrement == haystack.length) { return haystack.length; }
        }

        static if (is(typeof(unaryFun!pred(T.init))))
        {
            if (unaryFun!pred(haystack[index])) { return index; }
        }
        else static if (is(typeof(binaryFun!pred(size_t.min, T.init))))
        {
            if (binaryFun!pred(index, haystack[index])) { return index; }
        }
        else
        {
            static assert(0, "Unsupported predicate of type " ~ typeof(pred).stringof);
        }

        indexIncrement += 1;
        index = (index + indexIncrement) & mask; // next triangular number modulo length
    }
}

/** Search for a key in `haystack` matching hit predicate `hitPred` and hole
 * predicate `holePred` starting at `index` in steps of triangular numbers,
 * 0,1,3,6,10,15,21, ... .
 *
 * If `assumeNonFullHaystack` is `true` it is assumed that at least one element
 * in `haystack` matches `pred`, thereby enabling sentinel-based probing. Such
 * probing doesn't require in-loop range checking via `indexIncrement !=
 * haystack.length` and can be made faster.
 *
 * Returns: index into `haystack` upon hit, `haystack.length` upon miss.
 *
 * Note: `haystack.length` must be a power of two (or 1 or zero).
 *
 * See_Also: https://fgiesen.wordpress.com/2015/02/22/triangular-numbers-mod-2n/
 */
size_t triangularProbeFromIndexIncludingHoles(alias hitPred,
                                              alias holePred,
                                              bool assumeNonFullHaystack = false,
                                              T)(const scope T[] haystack,
                                                 size_t index,
                                                 ref size_t holeIndex) // first hole index
if ((is(typeof(unaryFun!hitPred(T.init))) ||
     is(typeof(binaryFun!hitPred(size_t.init, T.init)))) ||
    (is(typeof(unaryFun!holePred(T.init))) ||
     is(typeof(binaryFun!holePred(size_t.init, T.init)))))
{
    immutable mask = haystack.length - 1;
    assert((~mask ^ mask) == typeof(return).max); // std.math.isPowerOf2(haystack.length)

    static if (assumeNonFullHaystack)
    {
        assert(haystack.length != 0, "haystack cannot be empty");
    }

    // search using triangular numbers as increments
    size_t indexIncrement = 0;
    while (true)
    {
        static if (assumeNonFullHaystack)
        {
            assert(indexIncrement != haystack.length,
                   "no element in `haystack` matches `hitPred`, cannot used sentinel-based probing");
        }
        else
        {
            if (indexIncrement == haystack.length) { return haystack.length; }
        }

        static if (is(typeof(unaryFun!hitPred(T.init))))
        {
            if (unaryFun!hitPred(haystack[index])) { return index; }
        }
        else static if (is(typeof(binaryFun!hitPred(size_t.min, T.init))))
        {
            if (binaryFun!hitPred(index, haystack[index])) { return index; }
        }
        else
        {
            static assert(0, "Unsupported hit predicate of type " ~ typeof(hitPred).stringof);
        }

        if (holeIndex == size_t.max) // if not yet initialized
        {
            static if (is(typeof(unaryFun!holePred(T.init))))
            {
                if (unaryFun!holePred(haystack[index])) { holeIndex = index; }
            }
            else static if (is(typeof(binaryFun!holePred(size_t.min, T.init))))
            {
                if (binaryFun!holePred(index, haystack[index])) { holeIndex = index; }
            }
        }

        indexIncrement += 1;
        index = (index + indexIncrement) & mask; // next triangular number modulo length
    }
}

size_t triangularProbeCountFromIndex(alias pred,
                                     T)(const scope T[] haystack, size_t index)
if (is(typeof(unaryFun!pred(T.init))))
{
    immutable mask = haystack.length - 1;
    assert((~mask ^ mask) == typeof(return).max); // std.math.isPowerOf2(haystack.length)

    // search using triangular numbers as increments
    size_t indexIncrement = 0;
    while (true)
    {
        if (indexIncrement == haystack.length) { return indexIncrement + 1; }
        if (unaryFun!pred(haystack[index])) { return indexIncrement + 1; }
        indexIncrement += 1;
        index = (index + indexIncrement) & mask; // next triangular number modulo length
    }
}

/// empty case
@safe pure nothrow unittest
{
    import std.typecons : Nullable;
    alias T = Nullable!int;

    immutable length = 0;
    immutable hitKey = T(42); // key to store
    auto haystack = new T[length];

    assert(haystack.triangularProbeFromIndex!((T element) => (element is hitKey ||
                                                              element.isNull))(0) == haystack.length);
    assert(haystack.triangularProbeFromIndex!((size_t index, T element) => true)(0) == 0);
    assert(haystack.triangularProbeFromIndex!((size_t index, T element) => false)(0) == haystack.length);
}

/// generic case
@safe pure nothrow unittest
{
    import std.typecons : Nullable;
    alias T = Nullable!int;

    foreach (immutable lengthPower; 0 .. 20)
    {
        immutable length = 2^^lengthPower;

        immutable hitKey = T(42);  // key to store
        immutable missKey = T(43); // other key not present

        auto haystack = new T[length];
        haystack[] = T(17);     // make haystack full
        haystack[$/2] = hitKey;

        alias elementHitPredicate = element => (element is hitKey || element.isNull);
        alias elementMissPredicate = element => (element is missKey || element.isNull);

        // key hit
        assert(haystack.triangularProbeFromIndex!(elementHitPredicate)(lengthPower) != haystack.length);

        // key miss
        assert(haystack.triangularProbeFromIndex!(elementMissPredicate)(lengthPower) == haystack.length);
    }
}

@trusted pure unittest
{
    class C { int value; }
    C x;
    C y = cast(C)((cast(size_t*)null) + 1); // indicates a lazily deleted key
    struct S
    {
        // TODO make these work:
        // enum C hole1 = cast(C)((cast(size_t*)null) + 1);
        // static immutable C hole2 = cast(C)((cast(size_t*)null) + 1);
    }
}