[ZODB-Dev] BTree ranges
John Belmonte
jvb at prairienet.org
Sun Oct 5 22:01:58 EDT 2003
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.
The BTree methods should use half-open ranges. OOBTree.items(x, y)
should returns items in the half-open range [x, y) (that is, between x
and y, excluding y). The maxKey method should also be changed
accordingly: If a key argument if provided, return the largest key that
is less than the argument.
Using closed ranges is a pain for programmers. That's why, for example,
the ANSI C++ standard library use half-open ranges religiously. So does
Python. Consider:
>>> range(5) # return sequence of integers in the range [0, 5)
[0, 1, 2, 3, 4]
>>> ('foo', 'bar')[0:1] # return slice with indices in the range [0, 1)
('foo',)
Please make the BTree objects more useful by changing them to accept
half-open ranges.
-John Belmonte
--
http:// if le.o /
More information about the ZODB-Dev
mailing list