[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