software/kisstdlib/./test/test_sorted.py

A set of modules for the Python programming language designed for system programming with conceptually and algebraically simple primitives.

Files

Raw Source

Contents

# Copyright (c) 2023-2025 Jan Malakhovski <oxij@oxij.org>
#
# This file is a part of `kisstdlib` project.
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

"""Testing `kisstdlib.sorted` module."""

import math as _math
import typing as _t

from kisstdlib import *
from kisstdlib.sorted import *


def test_nearer_to_than() -> None:
    assert nearer_to_than(1, 0, 0) is None
    assert nearer_to_than(0, 10, 100)
    assert nearer_to_than(0, 100, 10) is False

    inf: Decimal | float
    for inf in [Decimal("+inf"), _math.inf]:  # type: ignore
        assert nearer_to_than(inf, 1, 0)
        assert nearer_to_than(-inf, 0, 1)
        assert nearer_to_than(inf, 0, 1) is False
        assert nearer_to_than(-inf, 1, 0) is False


def prefill_AbstractSortedIndex(
    index: AbstractSortedIndex[str, Number, tuple[Number, None]],
    key: str,
    elements: list[tuple[Number, None]],
    ranges: list[tuple[Number, Number, Number]],
) -> None:
    for mini, maxi, step in ranges:
        for i in count_from_to(mini, maxi, step):
            e = (i, None)
            index.insert(key, e)
            elements.append(e)


def skip(step: Number, xs: _t.Iterable[tuple[Number, AType]]) -> _t.Iterator[tuple[Number, AType]]:
    prev = None
    for x in xs:
        if prev is not None and abs(prev[0] - x[0]) < step:
            continue
        yield x
        prev = x


def iter_range_result(
    elements: list[tuple[Number, AType]],
    start: Number,
    end: Number,
    step: Number,
    i_s: bool,
    i_e: bool,
) -> list[tuple[Number, AType]]:
    if start == end:
        if i_s and i_e:
            return [e for e in elements if e[0] == start]
        return []
    if start <= end:
        f = filter(
            lambda x: start < x[0] < end or i_s and x[0] == start or i_e and x[0] == end,
            elements,
        )
        return list(skip(step, f))
    f = filter(
        lambda x: end < x[0] < start or i_s and x[0] == start or i_e and x[0] == end,
        elements,
    )
    l = list(f)
    l.reverse()
    return list(skip(step, l))


def check_AbstractSortedIndex_range(
    index: AbstractSortedIndex[str, Number, tuple[Number, AType]],
    key: str,
    elements: list[tuple[Number, AType]],
    mini: Number,
    maxi: Number,
    maxstep: Number,
    nstep: Number,
) -> None:
    for i in count_from_to(mini, maxi, nstep):
        for j in count_from_to(mini, maxi, nstep):
            for step in count_from_to(0, maxstep, nstep):
                for i_s in (True, False):
                    for i_e in (True, False):
                        # print((i, j, step, i_s, i_e))
                        # if (i, j, step, i_s, i_e) == (0.0, 0.0, 0, True, True):
                        #    breakpoint()
                        r = list(
                            index.iter_range(key, i, j, step, include_start=i_s, include_end=i_e)
                        )
                        assert r == iter_range_result(elements, i, j, step, i_s, i_e)


def check_AbstractSortedIndex_nearest(
    index: AbstractSortedIndex[str, Number, tuple[Number, AType]],
    key: str,
    elements: list[tuple[Number, AType]],
    mini: Number,
    maxi: Number,
    nstep: Number,
) -> None:
    for i in count_from_to(mini, maxi, nstep):
        # print(i)
        r = list(index.iter_nearest(key, i))
        # because right-most elements go first
        s: list[tuple[Number, AType]]
        s = list(filter(lambda x: x[0] >= i, elements))  # pylint: disable=cell-var-from-loop
        s += list(filter(lambda x: x[0] < i, elements))  # pylint: disable=cell-var-from-loop
        s.sort(key=lambda x: abs(sub_(x[0], i)))  # type: ignore # pylint: disable=cell-var-from-loop
        assert r == s


def check_AbstractSortedIndex(
    index: AbstractSortedIndex[str, Number, tuple[Number, None]], maxi: int = 102
) -> None:
    elements_a: list[tuple[Number, None]] = []
    prefill_AbstractSortedIndex(
        index, "a", elements_a, [(0, 8, 1), (20, 31, 0.5), (32, 50, 0.25), (59, 100, 0.3)]
    )
    prefill_AbstractSortedIndex(index, "b", [], [(30, 50, 1)])
    check_AbstractSortedIndex_nearest(index, "a", elements_a, -2, 102, 0.5)
    check_AbstractSortedIndex_range(index, "a", elements_a, -2, maxi, 3, 0.5)


def test_SortedIndex_quick() -> None:
    test_SortedIndex_slow(10)


def test_SortedIndex_slow(maxi: int = 102) -> None:
    check_AbstractSortedIndex(SortedIndex(key_key=identity, value_key=fst), maxi)