Coverage for blind_charging/broken_range.py: 90%

1"""Data type for discontinuous ranges.""" 

2from typing import List, Tuple 

3 

4 

5def _find_index(R: List[int], value: int, inside: bool = False) -> int: 

6 """Find the index of the member equal to or greater than the input value. 

7 

8 :param R: List of range blocks, as [b0_s, b0_e, ... ] 

9 :param value: Value to search for 

10 :param inside: Use > instead of >= as comparator 

11 :returns: The index of the smallest member greater than or equal to the 

12 input value. The return value will be equal to the length of the list if 

13 there is no member that's greater or equal to the input. 

14 """ 

15 if not R: 

16 return 0 

17 

18 low = 0 

19 high = len(R) 

20 

21 while (high - low) > 1: 

22 mid = low + ((high - low) >> 1) 

23 if value < R[mid]: 

24 high = mid 

25 else: 

26 low = mid 

27 

28 idx = low if value <= R[low] else high 

29 

30 if idx == len(R): 

31 return idx 

32 

33 if inside and R[idx] == value: 

34 return idx + 1 

35 return idx 

36 

37 

38class BrokenRange(object): 

39 """Representation of a discontinuous range. 

40 

41 Includes utilities to update range and merge overlaps. 

42 """ 

43 

44 def __init__(self): 

45 self._range: List[int] = [] 

46 

47 def addspan(self, start: int, end: int): 

48 """Incorporate span [start, end) into the range. 

49 

50 :param start: Index of start 

51 :param end: Index of end (exclusive) 

52 :returns: BrokenRange (self) 

53 """ 

54 if end <= start: 

55 raise ValueError("Invalid extent: {}".format(end - start)) 

56 

57 R = self._range 

58 

59 # Find the index in the range of the start of the block where this 

60 # span should go. 

61 start_idx = _find_index(R, start) 

62 if start_idx % 2 == 1: 

63 start_idx -= 1 

64 

65 # When the span is higher than any existing block, just append it. 

66 # This handles the initial condition when no ranges have been added 

67 # as well. 

68 if start_idx == len(R): 

69 self._range += [start, end] 

70 return self 

71 

72 # Find the index in the range of the end of the block where this 

73 # span should go. 

74 end_idx = _find_index(R, end + 1) 

75 if end_idx % 2 == 0: 

76 end_idx -= 1 

77 

78 # When the span precedes any existing block, prepend it. 

79 if end_idx < 0: 

80 self._range = [start, end] + R 

81 return self 

82 

83 block_start = min(start, R[start_idx]) 

84 block_end = max(end, R[end_idx]) 

85 self._range = R[:start_idx] + [block_start, block_end] + R[end_idx + 1 :] 

86 

87 return self 

88 

89 def contains(self, value: int) -> bool: 

90 """Test whether a value is contained in the range. 

91 

92 :param value: Value to test 

93 :returns: Boolean indicating membership 

94 """ 

95 idx = _find_index(self._range, value) 

96 

97 # If the index is out of range, value is not contained 

98 if idx == len(self._range): 

99 return False 

100 

101 # If the index is even, it must be exact match to be contained. 

102 # If the index is odd, it must *not* be exact match to be contained. 

103 if idx % 2 == 0: 

104 return value == self._range[idx] 

105 else: 

106 return value != self._range[idx] 

107 

108 def overlaps(self, start: int, end: int) -> bool: 

109 """Test whether given span overlaps any part of this range. 

110 

111 :param start: Start of span 

112 :param end: End of span 

113 :returns: Boolean indicating overlap 

114 """ 

115 if end <= start: 

116 raise ValueError("Invalid extent: {}".format(end - start)) 

117 

118 start_idx = _find_index(self._range, start, inside=True) 

119 end_idx = _find_index(self._range, end, inside=False) 

120 

121 # An odd index implies span starts inside block 

122 if start_idx % 2 == 1: 

123 return True 

124 

125 # Otherwise if the span crosses any range, there must be overlap. 

126 return start_idx != end_idx 

127 

128 def __iadd__(self, span: Tuple[int, int]) -> "BrokenRange": 

129 return self.addspan(span[0], span[1]) 

130 

131 def __repr__(self) -> str: 

132 R = self._range 

133 spans = ["[{},{}]".format(R[i], R[i + 1]) for i in range(0, len(R), 2)] 

134 return "BrokenRange({})".format(",".join(spans))