[ZODB-Dev] BTree ranges
Tim Peters
tim at zope.com
Sun Oct 5 22:21:06 EDT 2003
[John Belmonte]
> Currently, the BTree methods all use closed ranges. For example,
> OOBTree.items(x, y) returns items in the closed range [x, y] (that is,
> between x and y inclusive). Example:
>
> >>> from BTrees.OOBTree import OOBTree
> >>> a = OOBTree({1.5: 'foo', 2.0: 'bar'})
> >>> for x in a.items(1.0, 2.0): print x
> ...
> (1.5, 'foo')
> (2.0, 'bar')
>
> Closed ranges don't work well when dealing with continuous values,
> such as floating point numbers. Consider that you have an OOBTree
> with float keys. Say you want to iterate over the 10's, and then the
> 20's. With tree.items(10.0, 20.0) you'll get the first group. You
> only wanted only the 10's, but unfortunately you'll get 20.0 too if
> it happens to exist. That isn't the only problem. The second
> group, tree.items(20.0, 30.0), overlaps with the first. Again, if
> 20.0 exists in the tree, it will appear in both groups. The
> workarounds are ugly. You can use items(x, y-epsilon), but computing
> epsilon may be difficult, and furthermore this approach isn't
> straightforward if you are dealing with keys with custom __cmp__,
> such as a tuple object. Another way is to continue using items(x, y),
> but explicitly ignore y if it exists in the result.
I doubt anyone here uses BTrees indexed by floats. Luckily for you <wink>,
the same problems occur, mutatis mutandis, in BTrees indexed by strings.
For example, find all the keys starting with 'b'. Same problem, except
worse in that a suitable "epsilon" doesn't exist even in theory (there is no
"largest string" starting with 'b').
> The BTree methods should use half-open ranges.
Your point is well taken but futile as given: it would break far too much
code to change this.
However, in ZODB4 the relevant BTree methods have grown optional exclude_min
and exclude_max Boolean arguments. There, e.g.,
tree.items(10.0, 20.0, exclude_max=True)
does what you want. Since that's a new feature, it can't be added to the
3.1 or even 3.2 versions of ZODB. It may get backported to a 3.3 version of
ZODB (if such a thing ever exists).
More information about the ZODB-Dev
mailing list