testItemsNegativeIndex (3 instances):  repaired off-by-one glitch in loop (range(i, j, k) is always exclusive of j).

Fix bug indexing BTreeItems with negative values. Previous code assumed that idexes passed to BTreeItem_item would be negative, in practice this was not the case, and an index of -1 actually passed len(items)-1 as the index argument. Consequently, it was possible to access each item using two negative indexes (i.e., -1 and -len(items)-1). This made each item appear twice in a reverse iteration.

Code in BTreeItems_seek attempted to match the sign of the pseudoindex kept in the BTreeItems obj and the incoming index. Since this incoming index was never legitimately negative as it assumed, actually negatives passed in due to "overshooting" the first item would repeat the items again from the end. Removal of this code corrects the problem.

Unittests which provoke the error in the original code have also been added.

since the last call may have left us with an invalid index.  Raise
RuntimeError instead of segfaulting (or picking up random trash) if so.
A new (and previously segfaulting) test case is courtesy of Steve
Alexander.

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).

identification harder, especially when generic test classes are
inherited by multiple specific test classes.)

StorageTestBase.removefs() will attempt to remove files with all the
possible extensions that FileStorage will create.  It will raise
os.error for any error except ENOENT.

Remove many variants of removefs() implemented in the various test
suites.

fine; just keeping the test suite as closely in synch as possible.

of verifying that BTree invariants are satisfied, raising AssertionError
if they're not.  Nothing calls this method by magic; it's for debugging.

deletion endcases uncovered by the new degenerate-BTree tests.  The
degenerate testDeletes() and testEmptyFirstBucketReportedByGuido() are
enabled now.

disabled for now, because it dies in lots of ways.  I hope, but don't know,
that they're all related to "Guido's bug".

Also backported the "Guido's bug" test case from the Zope3 project.  This
is also disabled for now.

search returned a seemingly random slice of the tree.  A new test on the
painfully constructed highly-degenerate BTree turned up lots of these.
It turns out that BTree_rangeSearch had a much harder job than it
thought it had <0.7 wink>.

for lo > hi either, except if they happened to be in the same bucket.  All
sorts of strange results followed (the range should be empty if lo > hi,
and is after this patch).

passed in, it was quite possible for this to return *low > *high, and the
caller could crash due to trying to create a list with "negative length".
Changed the routine to consider a range empty if min>max on input, and added
test cases that fail before this patch.

legitimate) BTree.  New test testDegenerateBasicOps() does basic sanity
checks on it.  More tests against this tree will follow.

classes entirely (like for IITreeSets), and to run other test classes
twice.

key S in a bucket in a BTree is deleted, doing a range search on the
BTree with S on the high end may claim that the range is empty even when
it's not.  It proved difficult to fix this correctly and efficiently in
all cases (our BTrees don't like "searching backwards").  The
implementation here is a new and non-recursive one (in effect, to do
this efficiently you have to remember the deepest point in the tree where
it was *possible* to "go one left" of where binary search tells you to go;
an iterative algorithm makes that part all but obvious).  Alas, the
number of uses of persistence macros is amazing, unfortunately making
this still-hairy algorithm hard to follow.

testPathologicalRangeSearch():  uncommented the lines that failed
before this patch.  They pass now.

Insecurity:  The test case only exercises the simplest possible form
of the failure.  Any failing case is hard to provoke, even the simplest.
The hairier failing cases require generating degenerate trees, deep
and with some interior nodes near the top having just one or two children
(since the tree needs to be deep too, that isn't easy to provoke).  I'll
think about how to provoke this without needing to build up multi-million
element trees first; maybe using __setstate__ directly is the answer.

commented out for now, because it fails.  I'm working on a fix.  The
problem was found by eyeballing the range-test implementation.  If you
delete a key from a BTree that just happens to be the first key in a
bucket, then a later high-end range search giving that specific key as
the endpoint claims that no keys are in the range, and whether or not
that's actually true.

"BTreeItems slice contains 1 too many elements"
This also fixes many related glitches, such as that giving an
out-of-bound slice index raised IndexError instead of clipping.

BTreeItems_slice():  Emulate Python slicing semantics in all cases.

testBTrees.py:  new testSlicing() tests in MappingBase and NormalSetTests
to ensure that slicing of .keys()/.items()/.values() works exactly the
same way as slicing of Python lists, in all one-sided, two-sided and
whole-structure ([:]) cases, with both negative and positive slice indices,
and mixtures of + and -, and whether in bounds or out of bounds.

long overdue merge of toby-cmp-error-branch. btrees no longer ignore exceptions raised by the key comparison function

initial fix causes core dumps. We'll reenable this test when the bug
gets fixed (again).

keys at the beginning of the BTree were deleted.

the code

    try:
        root = self._getRoot()
        ...
    except:
        self._closeDB(root)
	self._delDB()
	raise

which fails with an UnboundLocalError if the first line in the try
clause fails.  Fixed this by setting 'root = None' before each such
try clause, and adding a None check to _closeDB().  Also removed a
useless 'root = None' from the body of _closeDB().

Barry: I saw this in the saz 1.0c1 release.  Is it worth backporting?
Probably not given that we're not going to do a merge pre-1.0.

- replaced assert statements by calls to self.assertEqual() and
  self.assert_()

Based on conversation with Evan yesterday, I think this is safe.