[kupfer] relevance: Rewrite _findBestMatch inner loop

[Ulrik Sverdrup <usverdrup src gnome org>]

commit bb9786474699bc95c09846abfe93dccc565d9ab0
Author: Ulrik Sverdrup <ulrik sverdrup gmail com>
Date:   Fri Sep 11 20:23:19 2009 +0200

    relevance: Rewrite _findBestMatch inner loop
    
    The inner loop should loop over the query, not the string since the
    query is always shorter than the string (or equal).
    
    The inner loop will loop over the query characters, trying to find
    them between the last found query char and the known end of the range.
    
    This speeds up string ranking to wicked fast levels!

 kupfer/relevance.py |   21 +++++++++++----------
 1 files changed, 11 insertions(+), 10 deletions(-)
---
diff --git a/kupfer/relevance.py b/kupfer/relevance.py
index 852553a..6088f01 100644
--- a/kupfer/relevance.py
+++ b/kupfer/relevance.py
@@ -185,6 +185,8 @@ def _findBestMatch(s, query):
     (0, 8)
     >>> _findBestMatch('teerminal', 'erml')
     (2, 9)
+    >>> _findBestMatch('terminal', 'e')
+    (1, 2)
     """
     bestMatch = -1, -1
     
@@ -202,20 +204,19 @@ def _findBestMatch(s, query):
     queryLength = len(query)
     lastIndex = lastChar - len(query) + 1
     while 0 <= index <= lastIndex:
-        # Look for the best match in the tail
+        # See if we can fit the whole query in the tail
         # We know the first char matches, so we dont check it.
         cur = index + 1
         qcur = 1
-        while (qcur < queryLength) and (cur < len(s)):
-            if query[qcur] == s[cur]:
-                qcur += 1
+        while qcur < queryLength:
+            # find where in the string the next query character is
+            # if not found, we are done
+            cur = s.find(query[qcur], cur, lastChar + 1)
+            if cur == -1:
+                return bestMatch
             cur += 1
-
-        # if whole query fit, save it; else we are done
-        if (qcur == queryLength):
-            bestMatch = (index, cur)
-        else:
-            break
+            qcur += 1
+        bestMatch = (index, cur)
 
         index = s.find(query[0], index + 1)