-
Tim Peters authored
is check.check(btree), which performs value-based sanity checks on a BTree (or TreeSet) that the btree._check() method doesn't do. The new checks include that all the bucket keys are in sorted order, and that all the keys within each bucket, and within each internal BTree node, lie within the range necessary for that node. That last is a subtle invariant that can't be checked locally: it requires propagating range info down the tree, and modifying it for each child and each level. This *should* catch any BTree B for which iterating over the keys yields a key K for which B.has_key(K) returns false. Another function check.display(btree) prints the internal structure of a BTree (or TreeSet, Bucket, or Set) to stdout. If check.check(B) ever complains, a clearer picture of the damage can be gotten by staring at check.display(B)'s output. Also beefed up the regular BTree tests by calling check.check() in key places. No surprises (the tests still pass).
f4e8c075