lib/algo/legacy/tests/searches.viv

# Generated by tools/algo/check.py from lib/algo/algo.spec: do not edit.
# Each case prints its input (= X), its results, and the verdict of each postcondition
# (? ...) as lib/algo/props.viv computes it; check.py checks them again in Python.
from algo.cases import algo_case, algo_needles, CASE_NAMES
from algo.props import algo_all_upper_bounds
from algo.legacy.searches import bisect, npr_lg_search

#| npr_lg_search: lib/nprandom's searchsorted(side='right')
def algo_t_npr_lg_search(kind, n, inside, skip: Arr) -> Bool {
    X = algo_case(kind, n, 1 + 97 * kind + n)
    print("@ npr_lg_search", CASE_NAMES[kind], n)
    V = copy(X)
    sort(V)
    Q = algo_needles(V)
    RS = zeros(len(Q))
    for k to len(Q) {
        RS[k] = npr_lg_search(V, Q[k])
    }
    print("= X", fmt(X))
    print("= RS", fmt(RS))
    print("= V", fmt(V))
    print("= Q", fmt(Q))
    p0 = algo_all_upper_bounds(RS, V, Q)
    print("?", p0)
    return inside == 0 or ((p0 or skip[0] == 1))
}

#| fasta_bisect: the fasta benchmark's bisect.bisect
def algo_t_fasta_bisect(kind, n, inside, skip: Arr) -> Bool {
    X = algo_case(kind, n, 1 + 97 * kind + n)
    print("@ fasta_bisect", CASE_NAMES[kind], n)
    V = copy(X)
    sort(V)
    Q = algo_needles(V)
    RS = zeros(len(Q))
    for k to len(Q) {
        RS[k] = bisect(V, Q[k])
    }
    print("= X", fmt(X))
    print("= RS", fmt(RS))
    print("= V", fmt(V))
    print("= Q", fmt(Q))
    p0 = algo_all_upper_bounds(RS, V, Q)
    print("?", p0)
    return inside == 0 or ((p0 or skip[0] == 1))
}

algo_t_ok_npr_lg_search = true
algo_t_kinds_npr_lg_search = [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0]
algo_t_inside_npr_lg_search = [1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.0]
algo_t_sizes_npr_lg_search = [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 7.0, 8.0, 9.0, 15.0, 16.0, 17.0, 31.0, 32.0, 33.0, 63.0, 64.0, 65.0, 129.0, 257.0]
algo_t_skip_npr_lg_search = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
for algo_t_k to len(algo_t_kinds_npr_lg_search) {
    for algo_t_s to len(algo_t_sizes_npr_lg_search) {
        algo_t_r = algo_t_npr_lg_search(algo_t_kinds_npr_lg_search[algo_t_k], algo_t_sizes_npr_lg_search[algo_t_s], algo_t_inside_npr_lg_search[algo_t_k], algo_t_skip_npr_lg_search[algo_t_k * 1:(algo_t_k + 1) * 1])
        algo_t_ok_npr_lg_search = algo_t_ok_npr_lg_search and algo_t_r
    }
}

algo_t_ok_fasta_bisect = true
algo_t_kinds_fasta_bisect = [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0]
algo_t_inside_fasta_bisect = [1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.0]
algo_t_sizes_fasta_bisect = [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 7.0, 8.0, 9.0, 15.0, 16.0, 17.0, 31.0, 32.0, 33.0, 63.0, 64.0, 65.0, 129.0, 257.0]
algo_t_skip_fasta_bisect = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
for algo_t_k to len(algo_t_kinds_fasta_bisect) {
    for algo_t_s to len(algo_t_sizes_fasta_bisect) {
        algo_t_r = algo_t_fasta_bisect(algo_t_kinds_fasta_bisect[algo_t_k], algo_t_sizes_fasta_bisect[algo_t_s], algo_t_inside_fasta_bisect[algo_t_k], algo_t_skip_fasta_bisect[algo_t_k * 1:(algo_t_k + 1) * 1])
        algo_t_ok_fasta_bisect = algo_t_ok_fasta_bisect and algo_t_r
    }
}

test "npr_lg_search: upper-bounds RS V Q (kinds random dups sorted reversed equal organ sawtooth nearly zeros)" {
    assert_true(algo_t_ok_npr_lg_search)
}

test "fasta_bisect: upper-bounds RS V Q (kinds random dups sorted reversed equal organ sawtooth nearly zeros)" {
    assert_true(algo_t_ok_fasta_bisect)
}