Rev 15: Get rid of the left bisect, as we don't use it in http://bzr.arbash-meinel.com/plugins/index2

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/plugins/index2

------------------------------------------------------------
revno: 15
revision-id: john at arbash-meinel.com-20080702145412-3qulu1g2k4cm3r57
parent: john at arbash-meinel.com-20080702145001-vz3rohjcio2226cb
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: index2
timestamp: Wed 2008-07-02 09:54:12 -0500
message:
  Get rid of the left bisect, as we don't use it
-------------- next part --------------
=== modified file 'btree_index.py'
--- a/btree_index.py	2008-07-02 14:50:01 +0000
+++ b/btree_index.py	2008-07-02 14:54:12 +0000
@@ -18,7 +18,7 @@
 """B+Tree indices"""
 
 import array
-from bisect import bisect_left, bisect_right
+from bisect import bisect_right
 from copy import deepcopy
 import tempfile
 import zlib
@@ -503,66 +503,6 @@
             output.append(cur_out)
         return output
 
-    @staticmethod
-    def _multi_bisect_left(in_keys, fixed_keys):
-        """Find the positions where each 'in_key' would fit in fixed_keys.
-
-        This is equivalent to doing "bisect_left" on each in_key into
-        fixed_keys
-
-        :param in_keys: A sorted list of keys to match with fixed_keys
-        :param fixed_keys: A sorted list of keys to match against
-        :return: A list of integer positions.
-        """
-        if not in_keys:
-            return []
-        if not fixed_keys:
-            raise AssertionError('we must have entries in fixed_keys')
-        if len(in_keys) == 1: # Bisect will always be faster for M = 1
-            return [(bisect_left(fixed_keys, in_keys[0]), in_keys)]
-        in_keys_iter = iter(in_keys)
-        fixed_keys_iter = enumerate(fixed_keys)
-        cur_in_key = in_keys_iter.next()
-        cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()
-
-        class InputDone(Exception): pass
-        class FixedDone(Exception): pass
-
-        output = []
-        cur_out = []
-
-        try:
-            while True:
-                if cur_in_key <= cur_fixed_key:
-                    cur_keys = []
-                    cur_out = (cur_fixed_offset, cur_keys)
-                    output.append(cur_out)
-                    while cur_in_key <= cur_fixed_key:
-                        cur_keys.append(cur_in_key)
-                        try:
-                            cur_in_key = in_keys_iter.next()
-                        except StopIteration:
-                            raise InputDone
-                    # At this point cur_in_key must be >= cur_fixed_key
-                # step the cur_fixed_key until we pass the cur key, or walk off
-                # the end
-                while cur_in_key > cur_fixed_key:
-                    try:
-                        cur_fixed_offset, cur_fixed_key = fixed_keys_iter.next()
-                    except StopIteration:
-                        raise FixedDone
-        except InputDone:
-            # We consumed all of the input, nothing more to do
-            pass
-        except FixedDone:
-            # There was some input left, but we consumed all of fixed, so we
-            # have to add one more for the tail
-            cur_keys = [cur_in_key]
-            cur_keys.extend(in_keys_iter)
-            cur_out = (len(fixed_keys), cur_keys)
-            output.append(cur_out)
-        return output
-
     def iter_entries(self, keys):
         """Iterate over keys within the index.
 

=== modified file 'tests/test_btree_index.py'
--- a/tests/test_btree_index.py	2008-07-02 14:50:01 +0000
+++ b/tests/test_btree_index.py	2008-07-02 14:54:12 +0000
@@ -639,38 +639,3 @@
                                      (4, ['g', 'h'])],
                                     ['a', 'b', 'd', 'e', 'g', 'h'],
                                     ['c', 'd', 'f', 'g'])
-
-
-class TestMultiBisectLeft(tests.TestCase):
-
-    def assertMultiBisectLeft(self, offsets, search_keys, fixed_keys):
-        self.assertEqual(offsets,
-                         btree_index.BTreeGraphIndex._multi_bisect_left(
-                            search_keys, fixed_keys))
-
-    def test_after(self):
-        self.assertMultiBisectLeft([(1, ['b'])], ['b'], ['a'])
-        self.assertMultiBisectLeft([(3, ['e', 'f', 'g'])],
-                                    ['e', 'f', 'g'], ['a', 'b', 'c'])
-
-    def test_before(self):
-        self.assertMultiBisectLeft([(0, ['a'])], ['a'], ['b'])
-        self.assertMultiBisectLeft([(0, ['a', 'b', 'c', 'd'])],
-                                    ['a', 'b', 'c', 'd'], ['e', 'f', 'g'])
-
-    def test_exact(self):
-        self.assertMultiBisectLeft([(0, ['a'])], ['a'], ['a'])
-        self.assertMultiBisectLeft([(0, ['a']), (1, ['b'])], ['a', 'b'], ['a', 'b'])
-        self.assertMultiBisectLeft([(0, ['a']), (2, ['c'])],
-                                    ['a', 'c'], ['a', 'b', 'c'])
-
-    def test_inbetween(self):
-        self.assertMultiBisectLeft([(1, ['b'])], ['b'], ['a', 'c'])
-        self.assertMultiBisectLeft([(1, ['b', 'c', 'd']), (2, ['f', 'g'])],
-                                    ['b', 'c', 'd', 'f', 'g'], ['a', 'e', 'h'])
-
-    def test_mixed(self):
-        self.assertMultiBisectLeft([(0, ['a', 'b']), (1, ['d']), (2, ['e']),
-                                     (3, ['g']), (4, ['h'])],
-                                    ['a', 'b', 'd', 'e', 'g', 'h'],
-                                    ['c', 'd', 'f', 'g'])