Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/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 

13 

14 

15def identity(v): 

16 return v 

17 

18 

19class Ordering(Shrinker): 

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

21 

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

23 the elements of the sequence. 

24 """ 

25 

26 def setup(self, key=identity): 

27 self.key = key 

28 

29 def make_immutable(self, value): 

30 return tuple(value) 

31 

32 def short_circuit(self): 

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

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

35 

36 def left_is_better(self, left, right): 

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

38 

39 def check_invariants(self, value): 

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

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

42 

43 def run_step(self): 

44 self.sort_regions() 

45 self.sort_regions_with_gaps() 

46 

47 def sort_regions(self): 

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

49 index i + 1. 

50 

51 This uses an adaptive algorithm that works by sorting contiguous 

52 regions starting from each element. 

53 """ 

54 i = 0 

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

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

57 k = find_integer( 

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

59 and self.consider( 

60 prefix 

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

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

63 ) 

64 ) 

65 i += k 

66 

67 def sort_regions_with_gaps(self): 

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

69 index i + 2. 

70 

71 This uses an adaptive algorithm that works by sorting contiguous 

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

73 fixed and the elements around it are sorted.. 

74 """ 

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

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

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

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

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

80 continue # pragma: no cover 

81 

82 def can_sort(a, b): 

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

84 return False 

85 assert a <= i < b 

86 split = i - a 

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

88 return self.consider( 

89 list(self.current[:a]) 

90 + values[:split] 

91 + [self.current[i]] 

92 + values[split:] 

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

94 ) 

95 

96 left = i 

97 right = i + 1 

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

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