CASE_RANDOM = 0
CASE_DUPS = 1
CASE_SORTED = 2
CASE_REVERSED = 3
CASE_EQUAL = 4
CASE_ORGAN = 5
CASE_SAWTOOTH = 6
CASE_NEARLY = 7
CASE_ZEROS = 8
CASE_SPECIAL = 9
CASE_NAMES = ["random", "dups", "sorted", "reversed", "equal", "organ", "sawtooth", "nearly", "zeros", "special"]

# the distinct values of a `dups` case, and the period of a `sawtooth` one
CASE_FEW = 4
CASE_TEETH = 8
# one swap in `nearly` per this many entries, and one more
CASE_SWAP_EVERY = 16

#| An entry drawn from `pool`, each equally likely.
def case_pick(pool: Arr) {
    return pool[floor(rand() * len(pool))]
}

#| The test input of kind `kind`, `n` entries, from seed `seed`.
def algo_case(kind, n, seed) -> Arr {
    srand(seed)
    a = zeros(n)
    inf = 1.0 / 0.0
    zeros_pool = [0.0, -0.0, 1.0, -1.0]
    special_pool = [0.0, -0.0, 1.0, -1.0, 0.0 / 0.0, inf, -inf, 2.5]
    for i to n {
        if kind == CASE_RANDOM {
            a[i] = rand() - 0.5
        }
        else if kind == CASE_DUPS {
            a[i] = floor(rand() * CASE_FEW)
        }
        else if kind == CASE_SORTED {
            a[i] = i
        }
        else if kind == CASE_REVERSED {
            a[i] = n - 1 - i
        }
        else if kind == CASE_EQUAL {
            a[i] = 1.0
        }
        else if kind == CASE_ORGAN {
            a[i] = min(i, n - 1 - i)
        }
        else if kind == CASE_SAWTOOTH {
            a[i] = i % CASE_TEETH
        }
        else if kind == CASE_NEARLY {
            a[i] = i
        }
        else if kind == CASE_ZEROS {
            a[i] = case_pick(zeros_pool)
        }
        else {
            a[i] = case_pick(special_pool)
        }
    }
    if kind == CASE_NEARLY and n > 1 {
        for s to floor(n / CASE_SWAP_EVERY) + 1 {
            i = floor(rand() * n)
            j = floor(rand() * n)
            t = a[i]
            a[i] = a[j]
            a[j] = t
        }
    }
    return a
}

#| The values to search for in `v`: each entry, a point half-way to the next one, and
#| one below and one above everything (or just 0 for an empty `v`).
def algo_needles(v: Arr) -> Arr {
    n = len(v)
    if n == 0 {
        return [0.0]
    }
    q = zeros(2 * n + 2)
    lo = v[0]
    hi = v[0]
    for i to n {
        q[2 * i] = v[i]
        if i + 1 < n {
            q[2 * i + 1] = 0.5 * (v[i] + v[i + 1])
        }
        else {
            q[2 * i + 1] = v[i] + 0.5
        }
        if v[i] < lo {
            lo = v[i]
        }
        if v[i] > hi {
            hi = v[i]
        }
    }
    q[2 * n] = lo - 1.0
    q[2 * n + 1] = hi + 1.0
    return q
}

test "the kinds are the shapes they are named for" {
    assert_true(all(algo_case(CASE_SORTED, 5, 1) == [0.0, 1.0, 2.0, 3.0, 4.0]))
    assert_true(all(algo_case(CASE_REVERSED, 4, 1) == [3.0, 2.0, 1.0, 0.0]))
    assert_true(all(algo_case(CASE_ORGAN, 5, 1) == [0.0, 1.0, 2.0, 1.0, 0.0]))
    assert_true(all(algo_case(CASE_EQUAL, 3, 1) == 1.0))
    assert_true(len(algo_case(CASE_RANDOM, 0, 1)) == 0)
    d = algo_case(CASE_DUPS, 50, 2)
    assert_true(all(d >= 0.0) and all(d < CASE_FEW) and all(d == floor(d)))
}

test "one seed gives one array" {
    assert_true(all(algo_case(CASE_RANDOM, 9, 3) == algo_case(CASE_RANDOM, 9, 3)))
    assert_true(any(algo_case(CASE_RANDOM, 9, 3) != algo_case(CASE_RANDOM, 9, 4)))
}

test "needles fall on, between, below and above the entries" {
    q = algo_needles([1.0, 2.0, 4.0])
    assert_true(all(q == [1.0, 1.5, 2.0, 3.0, 4.0, 4.5, 0.0, 5.0]))
}

# SPDX-License-Identifier: MIT OR Apache-2.0
# SPDX-FileCopyrightText: 2026 The Viv authors