Rev 69: Only read relevant nodes when generating suggestions in btree indices. in http://people.ubuntu.com/~robertc/baz2.0/plugins/search/trunk

[Robert Collins]

At http://people.ubuntu.com/~robertc/baz2.0/plugins/search/trunk

------------------------------------------------------------
revno: 69
revision-id: robertc at robertcollins.net-20090121075957-oohxgh668zis7ceq
parent: robertc at robertcollins.net-20090121065603-gsboq7bendemfh4s
committer: Robert Collins <robertc at robertcollins.net>
branch nick: trunk
timestamp: Wed 2009-01-21 18:59:57 +1100
message:
  Only read relevant nodes when generating suggestions in btree indices.
=== modified file 'index.py'
--- a/index.py	2009-01-21 06:56:03 +0000
+++ b/index.py	2009-01-21 07:59:57 +0000
@@ -1387,20 +1387,23 @@
         key_prefix = key[:-1]
         key_suffix = key[-1]
 
-        lower_key = key_prefix + ('',)
-        higher_key = key_prefix + (highest(),)
+        lower_key = key
+        higher_key = key_prefix + (key_suffix[:-1] + chr(ord(key_suffix[-1]) + 1),)
 
         for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
+            # find the lower node and higher node bounding the suggestion range
             node_indices = set([low_index, high_index])
             nodes = self._get_internal_nodes(node_indices)
+            # Lower edge
             low_node = nodes[low_index]
-            positions = self._multi_bisect_right([lower_key], low_node.keys)
+            position = bisect_left(low_node.keys, lower_key)
             node_offset = next_row_start + low_node.offset
-            low_index = node_offset + positions[0][0]
+            low_index = node_offset + position
+            # Higher edge
             high_node = nodes[high_index]
-            positions = self._multi_bisect_right([higher_key], high_node.keys)
+            position = bisect_left(high_node.keys, higher_key)
             node_offset = next_row_start + high_node.offset
-            high_index = node_offset + positions[0][0]
+            high_index = node_offset + position
         # We should now be at the _LeafNodes
         node_indices = range(low_index, high_index + 1)
 
@@ -1437,13 +1440,6 @@
                         yield (self, node_key, value)
 
 
-class highest(object):
-    """An object that is always after everything else"""
-
-    def __cmp__(self, other):
-        return 1
-
-
 _original_make_search_filter = None