libtbx.binary_search
index
/net/chevy/raid1/nat/src/cctbx_project/libtbx/binary_search.py

 
Classes
       
__builtin__.object
true_false_bad_biased_up

 
class true_false_bad_biased_up(__builtin__.object)
    Example application: binary search in svn history, with handling
of "bad" revisions that do not build.
 
Example callback:
 
  def callback(point):
    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:
bad_gap_width
bad_points
high
high_point_true
low
low_point_false
number_of_callbacks
number_of_iterations

 
Data
        division = _Feature((2, 2, 0, 'alpha', 2), (3, 0, 0, 'alpha', 0), 8192)