diff options
Diffstat (limited to 'poky/meta/recipes-devtools/python/python3-hypothesis/test_binary_search.py')
-rw-r--r-- | poky/meta/recipes-devtools/python/python3-hypothesis/test_binary_search.py | 135 |
1 files changed, 135 insertions, 0 deletions
diff --git a/poky/meta/recipes-devtools/python/python3-hypothesis/test_binary_search.py b/poky/meta/recipes-devtools/python/python3-hypothesis/test_binary_search.py new file mode 100644 index 0000000000..21267c4ac2 --- /dev/null +++ b/poky/meta/recipes-devtools/python/python3-hypothesis/test_binary_search.py @@ -0,0 +1,135 @@ +# This file is part of Hypothesis, which may be found at +# https://github.com/HypothesisWorks/hypothesis/ +# +# Most of this work is copyright (C) 2013-2021 David R. MacIver +# (david@drmaciver.com), but it contains contributions by others. See +# CONTRIBUTING.rst for a full list of people who may hold copyright, and +# consult the git log if you need to determine who owns an individual +# contribution. +# +# This Source Code Form is subject to the terms of the Mozilla Public License, +# v. 2.0. If a copy of the MPL was not distributed with this file, You can +# obtain one at https://mozilla.org/MPL/2.0/. +# +# END HEADER +# +# SPDX-License-Identifier: MPL-2.0 + +"""This file demonstrates testing a binary search. + +It's a useful example because the result of the binary search is so clearly +determined by the invariants it must satisfy, so we can simply test for those +invariants. + +It also demonstrates the useful testing technique of testing how the answer +should change (or not) in response to movements in the underlying data. +""" + +from hypothesis import given, strategies as st + + +def binary_search(ls, v): + """Take a list ls and a value v such that ls is sorted and v is comparable + with the elements of ls. + + Return an index i such that 0 <= i <= len(v) with the properties: + + 1. ls.insert(i, v) is sorted + 2. ls.insert(j, v) is not sorted for j < i + """ + # Without this check we will get an index error on the next line when the + # list is empty. + if not ls: + return 0 + + # Without this check we will miss the case where the insertion point should + # be zero: The invariant we maintain in the next section is that lo is + # always strictly lower than the insertion point. + if v <= ls[0]: + return 0 + + # Invariant: There is no insertion point i with i <= lo + lo = 0 + + # Invariant: There is an insertion point i with i <= hi + hi = len(ls) + while lo + 1 < hi: + mid = (lo + hi) // 2 + if v > ls[mid]: + # Inserting v anywhere below mid would result in an unsorted list + # because it's > the value at mid. Therefore mid is a valid new lo + lo = mid + # Uncommenting the following lines will cause this to return a valid + # insertion point which is not always minimal. + # elif v == ls[mid]: + # return mid + else: + # Either v == ls[mid] in which case mid is a valid insertion point + # or v < ls[mid], in which case all valid insertion points must be + # < hi. Either way, mid is a valid new hi. + hi = mid + assert lo + 1 == hi + # We now know that there is a valid insertion point <= hi and there is no + # valid insertion point < hi because hi - 1 is lo. Therefore hi is the + # answer we were seeking + return hi + + +def is_sorted(ls): + """Is this list sorted?""" + for i in range(len(ls) - 1): + if ls[i] > ls[i + 1]: + return False + return True + + +Values = st.integers() + +# We generate arbitrary lists and turn this into generating sorting lists +# by just sorting them. +SortedLists = st.lists(Values).map(sorted) + +# We could also do it this way, but that would be a bad idea: +# SortedLists = st.lists(Values).filter(is_sorted) +# The problem is that Hypothesis will only generate long sorted lists with very +# low probability, so we are much better off post-processing values into the +# form we want than filtering them out. + + +@given(ls=SortedLists, v=Values) +def test_insert_is_sorted(ls, v): + """We test the first invariant: binary_search should return an index such + that inserting the value provided at that index would result in a sorted + set.""" + ls.insert(binary_search(ls, v), v) + assert is_sorted(ls) + + +@given(ls=SortedLists, v=Values) +def test_is_minimal(ls, v): + """We test the second invariant: binary_search should return an index such + that no smaller index is a valid insertion point for v.""" + for i in range(binary_search(ls, v)): + ls2 = list(ls) + ls2.insert(i, v) + assert not is_sorted(ls2) + + +@given(ls=SortedLists, v=Values) +def test_inserts_into_same_place_twice(ls, v): + """In this we test a *consequence* of the second invariant: When we insert + a value into a list twice, the insertion point should be the same both + times. This is because we know that v is > the previous element and == the + next element. + + In theory if the former passes, this should always pass. In practice, + failures are detected by this test with much higher probability because it + deliberately puts the data into a shape that is likely to trigger a + failure. + + This is an instance of a good general category of test: Testing how the + function moves in responses to changes in the underlying data. + """ + i = binary_search(ls, v) + ls.insert(i, v) + assert binary_search(ls, v) == i |