||Example application: binary search in svn history, with handling|
of "bad" revisions that do not build.
bad_points = set([3,8,10])
critical_point = 7
if (point in bad_points): return None
return (point < critical_point)
The initial low point is assumed to be True, the initial high point
is assumed to be False; these assumptions are not verified, i.e.
callback is never called with point=low or point=high.
Illustration of binary search steps in region with bad points:
T . . . . . . . F
T . . . B . . . F
T . . . B . B . F
T . . . B . B B F
T . . . B . B b F
T . . . B . b b F
T . . . B B b b F
T . . . B b b b F
T . . . b b b b F
T . B . b b b b F
T . B B b b b b F
T . B b b b b b F
T . b b b b b b F
T B b b b b b b F
T b b b b b b b F
Each row shows the state at a step of the search.
Each column is for a search point (e.g. svn revision).
T = point known to be True
F = point known to be False
. = point not tried yet
B = point known to be bad (e.g. the True/False decision cannot be made)
b = point known to be bad and contiguously preceding F or b
In the algorithm below, T and B are stored in the i_true_or_bad list.
This reflects that bad points are initially treated as if they were
True. If the binary search converges with a bad point preceding a False
one, the bad point is reinterpreted as False. The final result is the
last point certain to be True and the first point certain to be False.
All revisions in between, if any, are known to be bad.
||Methods defined here:|
- __init__(O, low, high, callback, known_bad_points=())
Data descriptors defined here: