diff options
author | jmbills <jason.m.bills@intel.com> | 2021-10-04 22:42:48 +0300 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-10-04 22:42:48 +0300 |
commit | 0c9e31989c615598b5d042ffab385606660c93c0 (patch) | |
tree | 8019999b0ca042482e5193d6cabc06220c71d776 /poky/meta/recipes-devtools/python/python3-hypothesis/test_rle.py | |
parent | 04cd92067d2481643df5010cb39b2134b648cf4d (diff) | |
parent | ffe6d597d9e3d4407cf8062b5d6505a80ce08f41 (diff) | |
download | openbmc-0c9e31989c615598b5d042ffab385606660c93c0.tar.xz |
Update
Diffstat (limited to 'poky/meta/recipes-devtools/python/python3-hypothesis/test_rle.py')
-rw-r--r-- | poky/meta/recipes-devtools/python/python3-hypothesis/test_rle.py | 101 |
1 files changed, 101 insertions, 0 deletions
diff --git a/poky/meta/recipes-devtools/python/python3-hypothesis/test_rle.py b/poky/meta/recipes-devtools/python/python3-hypothesis/test_rle.py new file mode 100644 index 000000000..4d618865a --- /dev/null +++ b/poky/meta/recipes-devtools/python/python3-hypothesis/test_rle.py @@ -0,0 +1,101 @@ +# 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 example demonstrates testing a run length encoding scheme. That is, we +take a sequence and represent it by a shorter sequence where each 'run' of +consecutive equal elements is represented as a single element plus a count. So +e.g. + +[1, 1, 1, 1, 2, 1] is represented as [[1, 4], [2, 1], [1, 1]] + +This demonstrates the useful decode(encode(x)) == x invariant that is often +a fruitful source of testing with Hypothesis. + +It also has an example of testing invariants in response to changes in the +underlying data. +""" + +from hypothesis import assume, given, strategies as st + + +def run_length_encode(seq): + """Encode a sequence as a new run-length encoded sequence.""" + if not seq: + return [] + # By starting off the count at zero we simplify the iteration logic + # slightly. + result = [[seq[0], 0]] + for s in seq: + if ( + # If you uncomment this line this branch will be skipped and we'll + # always append a new run of length 1. Note which tests fail. + # False and + s + == result[-1][0] + # Try uncommenting this line and see what problems occur: + # and result[-1][-1] < 2 + ): + result[-1][1] += 1 + else: + result.append([s, 1]) + return result + + +def run_length_decode(seq): + """Take a previously encoded sequence and reconstruct the original from + it.""" + result = [] + for s, i in seq: + for _ in range(i): + result.append(s) + return result + + +# We use lists of a type that should have a relatively high duplication rate, +# otherwise we'd almost never get any runs. +Lists = st.lists(st.integers(0, 10)) + + +@given(Lists) +def test_decodes_to_starting_sequence(ls): + """If we encode a sequence and then decode the result, we should get the + original sequence back. + + Otherwise we've done something very wrong. + """ + assert run_length_decode(run_length_encode(ls)) == ls + + +@given(Lists, st.data()) +def test_duplicating_an_element_does_not_increase_length(ls, data): + """The previous test could be passed by simply returning the input sequence + so we need something that tests the compression property of our encoding. + + In this test we deliberately introduce or extend a run and assert + that this does not increase the length of our encoding, because they + should be part of the same run in the final result. + """ + # We use assume to get a valid index into the list. We could also have used + # e.g. flatmap, but this is relatively straightforward and will tend to + # perform better. + assume(ls) + i = data.draw(st.integers(0, len(ls) - 1)) + ls2 = list(ls) + # duplicating the value at i right next to it guarantees they are part of + # the same run in the resulting compression. + ls2.insert(i, ls2[i]) + assert len(run_length_encode(ls2)) == len(run_length_encode(ls)) |