Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/hypothesis/internal/conjecture/shrinking/ordering.py: 31%

1# This file is part of Hypothesis, which may be found at 

2# https://github.com/HypothesisWorks/hypothesis/ 

3# 

4# Copyright the Hypothesis Authors. 

5# Individual contributors are listed in AUTHORS.rst and the git log. 

6# 

7# This Source Code Form is subject to the terms of the Mozilla Public License, 

8# v. 2.0. If a copy of the MPL was not distributed with this file, You can 

9# obtain one at https://mozilla.org/MPL/2.0/. 

10 

11from hypothesis.internal.conjecture.junkdrawer import find_integer 

12from hypothesis.internal.conjecture.shrinking.common import Shrinker 

13from hypothesis.internal.conjecture.utils import identity 

14 

15 

16class Ordering(Shrinker): 

17 """A shrinker that tries to make a sequence more sorted. 

18 

19 Will not change the length or the contents, only tries to reorder 

20 the elements of the sequence. 

21 """ 

22 

23 def setup(self, key=identity): 

24 self.key = key 

25 

26 def make_immutable(self, value): 

27 return tuple(value) 

28 

29 def short_circuit(self): 

30 # If we can flat out sort the target then there's nothing more to do. 

31 return self.consider(sorted(self.current, key=self.key)) 

32 

33 def left_is_better(self, left, right): 

34 return tuple(map(self.key, left)) < tuple(map(self.key, right)) 

35 

36 def check_invariants(self, value): 

37 assert len(value) == len(self.current) 

38 assert sorted(value) == sorted(self.current) 

39 

40 def run_step(self): 

41 self.sort_regions() 

42 self.sort_regions_with_gaps() 

43 

44 def sort_regions(self): 

45 """Guarantees that for each i we have tried to swap index i with 

46 index i + 1. 

47 

48 This uses an adaptive algorithm that works by sorting contiguous 

49 regions starting from each element. 

50 """ 

51 i = 0 

52 while i + 1 < len(self.current): 

53 prefix = list(self.current[:i]) 

54 k = find_integer( 

55 lambda k: i + k <= len(self.current) 

56 and self.consider( 

57 prefix 

58 + sorted(self.current[i : i + k], key=self.key) 

59 + list(self.current[i + k :]) 

60 ) 

61 ) 

62 i += k 

63 

64 def sort_regions_with_gaps(self): 

65 """Guarantees that for each i we have tried to swap index i with 

66 index i + 2. 

67 

68 This uses an adaptive algorithm that works by sorting contiguous 

69 regions centered on each element, where that element is treated as 

70 fixed and the elements around it are sorted.. 

71 """ 

72 for i in range(1, len(self.current) - 1): 

73 if self.current[i - 1] <= self.current[i] <= self.current[i + 1]: 

74 # The `continue` line is optimised out of the bytecode on 

75 # CPython >= 3.7 (https://bugs.python.org/issue2506) and on 

76 # PyPy, and so coverage cannot tell that it has been taken. 

77 continue # pragma: no cover 

78 

79 def can_sort(a, b): 

80 if a < 0 or b > len(self.current): 

81 return False 

82 assert a <= i < b 

83 split = i - a 

84 values = sorted(self.current[a:i] + self.current[i + 1 : b]) 

85 return self.consider( 

86 list(self.current[:a]) 

87 + values[:split] 

88 + [self.current[i]] 

89 + values[split:] 

90 + list(self.current[b:]) 

91 ) 

92 

93 left = i 

94 right = i + 1 

95 right += find_integer(lambda k: can_sort(left, right + k)) 

96 find_integer(lambda k: can_sort(left - k, right))