[Zope-Checkins] CVS: Zope3/lib/python/Persistence/BTrees/tests - testBTrees.py:1.10

[Tim Peters]

Update of /cvs-repository/Zope3/lib/python/Persistence/BTrees/tests
In directory cvs.zope.org:/tmp/cvs-serv29184/tests

Modified Files:
	testBTrees.py 
Log Message:
BTree_rangeSearch():  Writing an exhaustive range-search test against
a degenerate BTree turned up lots of other holes in this driver.  Worst,
if you do tree.keys(lo, hi), the true range may be empty even if lo < hi,
and there are keys >= lo in the tree, and keys <= hi in the tree (all of
that does *not* imply there's a key with lo <= key <= hi!).

For xample, if lo=2 and hi=3, 2 and 3 aren't in the tree, but 1 and 4 are.
Then the low-end search for 2 finds 4, the high-end search for 3 finds 1,
but they're "in the wrong order", and since they may not even be in the
same bucket, there's no simple way to determine whether that's the case.
This introduces a constant-time method to resolve such ambiguities,


=== Zope3/lib/python/Persistence/BTrees/tests/testBTrees.py 1.9 => 1.10 ===
             self.assertEqual(t.has_key(i), 0)
 
+    def _checkRanges(self, tree, keys):
+        self.assertEqual(len(tree), len(keys))
+        self.assertEqual(list(tree.keys()), keys)
+        for k in keys:
+            self.assert_(tree.has_key(k))
+        if keys:
+            lokey = min(keys)
+            hikey = max(keys)
+            self.assertEqual(lokey, tree.minKey())
+            self.assertEqual(hikey, tree.maxKey())
+        else:
+            lokey = hikey = 42
+
+        # Try all range searches.
+        for lo in range(lokey - 1, hikey + 2):
+            for hi in range(lo - 1, hikey + 2):
+                want = [k for k in keys if lo <= k <= hi]
+                got = list(tree.keys(lo, hi))
+                self.assertEqual(want, got)
+
+    def testRanges(self):
+        t = self._build_degenerate_tree()
+        self._checkRanges(t, [1, 3, 5, 7, 11])
+
 def make_test(klass, base):
     class Test(base):
         def setUp(self):