Fix #344 - Backward scan when `--tiebreak=end`

2 files changed, 78 insertions, 38 deletions

diff --git a/src/algo/algo.go b/src/algo/algo.go
index 03266dd9..ac7bd8b2 100644
--- a/src/algo/algo.go
+++ b/src/algo/algo.go
@@ -15,8 +15,15 @@ import (
  * In short: They try to do as little work as possible.
  */
 
+func runeAt(runes []rune, index int, max int, forward bool) rune {
+	if forward {
+		return runes[index]
+	}
+	return runes[max-index-1]
+}
+
 // FuzzyMatch performs fuzzy-match
-func FuzzyMatch(caseSensitive bool, runes []rune, pattern []rune) (int, int) {
+func FuzzyMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) (int, int) {
 	if len(pattern) == 0 {
 		return 0, 0
 	}
@@ -34,7 +41,11 @@ func FuzzyMatch(caseSensitive bool, runes []rune, pattern []rune) (int, int) {
 	sidx := -1
 	eidx := -1
 
-	for index, char := range runes {
+	lenRunes := len(runes)
+	lenPattern := len(pattern)
+
+	for index := range runes {
+		char := runeAt(runes, index, lenRunes, forward)
 		// This is considerably faster than blindly applying strings.ToLower to the
 		// whole string
 		if !caseSensitive {
@@ -47,11 +58,12 @@ func FuzzyMatch(caseSensitive bool, runes []rune, pattern []rune) (int, int) {
 				char = unicode.To(unicode.LowerCase, char)
 			}
 		}
-		if char == pattern[pidx] {
+		pchar := runeAt(pattern, pidx, lenPattern, forward)
+		if char == pchar {
 			if sidx < 0 {
 				sidx = index
 			}
-			if pidx++; pidx == len(pattern) {
+			if pidx++; pidx == lenPattern {
 				eidx = index + 1
 				break
 			}
@@ -61,7 +73,7 @@ func FuzzyMatch(caseSensitive bool, runes []rune, pattern []rune) (int, int) {
 	if sidx >= 0 && eidx >= 0 {
 		pidx--
 		for index := eidx - 1; index >= sidx; index-- {
-			char := runes[index]
+			char := runeAt(runes, index, lenRunes, forward)
 			if !caseSensitive {
 				if char >= 'A' && char <= 'Z' {
 					char += 32
@@ -69,14 +81,19 @@ func FuzzyMatch(caseSensitive bool, runes []rune, pattern []rune) (int, int) {
 					char = unicode.To(unicode.LowerCase, char)
 				}
 			}
-			if char == pattern[pidx] {
+
+			pchar := runeAt(pattern, pidx, lenPattern, forward)
+			if char == pchar {
 				if pidx--; pidx < 0 {
 					sidx = index
 					break
 				}
 			}
 		}
-		return sidx, eidx
+		if forward {
+			return sidx, eidx
+		}
+		return lenRunes - eidx, lenRunes - sidx
 	}
 	return -1, -1
 }
@@ -88,20 +105,21 @@ func FuzzyMatch(caseSensitive bool, runes []rune, pattern []rune) (int, int) {
 //
 // We might try to implement better algorithms in the future:
 // http://en.wikipedia.org/wiki/String_searching_algorithm
-func ExactMatchNaive(caseSensitive bool, runes []rune, pattern []rune) (int, int) {
+func ExactMatchNaive(caseSensitive bool, forward bool, runes []rune, pattern []rune) (int, int) {
 	if len(pattern) == 0 {
 		return 0, 0
 	}
 
-	numRunes := len(runes)
-	plen := len(pattern)
-	if numRunes < plen {
+	lenRunes := len(runes)
+	lenPattern := len(pattern)
+
+	if lenRunes < lenPattern {
 		return -1, -1
 	}
 
 	pidx := 0
-	for index := 0; index < numRunes; index++ {
-		char := runes[index]
+	for index := 0; index < lenRunes; index++ {
+		char := runeAt(runes, index, lenRunes, forward)
 		if !caseSensitive {
 			if char >= 'A' && char <= 'Z' {
 				char += 32
@@ -109,10 +127,14 @@ func ExactMatchNaive(caseSensitive bool, runes []rune, pattern []rune) (int, int
 				char = unicode.To(unicode.LowerCase, char)
 			}
 		}
-		if pattern[pidx] == char {
+		pchar := runeAt(pattern, pidx, lenPattern, forward)
+		if pchar == char {
 			pidx++
-			if pidx == plen {
-				return index - plen + 1, index + 1
+			if pidx == lenPattern {
+				if forward {
+					return index - lenPattern + 1, index + 1
+				}
+				return lenRunes - (index + 1), lenRunes - (index - lenPattern + 1)
 			}
 		} else {
 			index -= pidx
@@ -123,7 +145,7 @@ func ExactMatchNaive(caseSensitive bool, runes []rune, pattern []rune) (int, int
 }
 
 // PrefixMatch performs prefix-match
-func PrefixMatch(caseSensitive bool, runes []rune, pattern []rune) (int, int) {
+func PrefixMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) (int, int) {
 	if len(runes) < len(pattern) {
 		return -1, -1
 	}
@@ -141,7 +163,7 @@ func PrefixMatch(caseSensitive bool, runes []rune, pattern []rune) (int, int) {
 }
 
 // SuffixMatch performs suffix-match
-func SuffixMatch(caseSensitive bool, input []rune, pattern []rune) (int, int) {
+func SuffixMatch(caseSensitive bool, forward bool, input []rune, pattern []rune) (int, int) {
 	runes := util.TrimRight(input)
 	trimmedLen := len(runes)
 	diff := trimmedLen - len(pattern)
@@ -162,7 +184,7 @@ func SuffixMatch(caseSensitive bool, input []rune, pattern []rune) (int, int) {
 }
 
 // EqualMatch performs equal-match
-func EqualMatch(caseSensitive bool, runes []rune, pattern []rune) (int, int) {
+func EqualMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) (int, int) {
 	if len(runes) != len(pattern) {
 		return -1, -1
 	}
diff --git a/src/algo/algo_test.go b/src/algo/algo_test.go
index db241962..95a020b7 100644
--- a/src/algo/algo_test.go
+++ b/src/algo/algo_test.go
@@ -5,11 +5,11 @@ import (
 	"testing"
 )
 
-func assertMatch(t *testing.T, fun func(bool, []rune, []rune) (int, int), caseSensitive bool, input string, pattern string, sidx int, eidx int) {
+func assertMatch(t *testing.T, fun func(bool, bool, []rune, []rune) (int, int), caseSensitive bool, forward bool, input string, pattern string, sidx int, eidx int) {
 	if !caseSensitive {
 		pattern = strings.ToLower(pattern)
 	}
-	s, e := fun(caseSensitive, []rune(input), []rune(pattern))
+	s, e := fun(caseSensitive, forward, []rune(input), []rune(pattern))
 	if s != sidx {
 		t.Errorf("Invalid start index: %d (expected: %d, %s / %s)", s, sidx, input, pattern)
 	}
@@ -19,33 +19,51 @@ func assertMatch(t *testing.T, fun func(bool, []rune, []rune) (int, int), caseSe
 }
 
 func TestFuzzyMatch(t *testing.T) {
-	assertMatch(t, FuzzyMatch, false, "fooBarbaz", "oBZ", 2, 9)
-	assertMatch(t, FuzzyMatch, true, "fooBarbaz", "oBZ", -1, -1)
-	assertMatch(t, FuzzyMatch, true, "fooBarbaz", "oBz", 2, 9)
-	assertMatch(t, FuzzyMatch, true, "fooBarbaz", "fooBarbazz", -1, -1)
+	assertMatch(t, FuzzyMatch, false, true, "fooBarbaz", "oBZ", 2, 9)
+	assertMatch(t, FuzzyMatch, true, true, "fooBarbaz", "oBZ", -1, -1)
+	assertMatch(t, FuzzyMatch, true, true, "fooBarbaz", "oBz", 2, 9)
+	assertMatch(t, FuzzyMatch, true, true, "fooBarbaz", "fooBarbazz", -1, -1)
+}
+
+func TestFuzzyMatchBackward(t *testing.T) {
+	assertMatch(t, FuzzyMatch, false, true, "foobar fb", "fb", 0, 4)
+	assertMatch(t, FuzzyMatch, false, false, "foobar fb", "fb", 7, 9)
 }
 
 func TestExactMatchNaive(t *testing.T) {
-	assertMatch(t, ExactMatchNaive, false, "fooBarbaz", "oBA", 2, 5)
-	assertMatch(t, ExactMatchNaive, true, "fooBarbaz", "oBA", -1, -1)
-	assertMatch(t, ExactMatchNaive, true, "fooBarbaz", "fooBarbazz", -1, -1)
+	for _, dir := range []bool{true, false} {
+		assertMatch(t, ExactMatchNaive, false, dir, "fooBarbaz", "oBA", 2, 5)
+		assertMatch(t, ExactMatchNaive, true, dir, "fooBarbaz", "oBA", -1, -1)
+		assertMatch(t, ExactMatchNaive, true, dir, "fooBarbaz", "fooBarbazz", -1, -1)
+	}
+}
+
+func TestExactMatchNaiveBackward(t *testing.T) {
+	assertMatch(t, FuzzyMatch, false, true, "foobar foob", "oo", 1, 3)
+	assertMatch(t, FuzzyMatch, false, false, "foobar foob", "oo", 8, 10)
 }
 
 func TestPrefixMatch(t *testing.T) {
-	assertMatch(t, PrefixMatch, false, "fooBarbaz", "Foo", 0, 3)
-	assertMatch(t, PrefixMatch, true, "fooBarbaz", "Foo", -1, -1)
-	assertMatch(t, PrefixMatch, false, "fooBarbaz", "baz", -1, -1)
+	for _, dir := range []bool{true, false} {
+		assertMatch(t, PrefixMatch, false, dir, "fooBarbaz", "Foo", 0, 3)
+		assertMatch(t, PrefixMatch, true, dir, "fooBarbaz", "Foo", -1, -1)
+		assertMatch(t, PrefixMatch, false, dir, "fooBarbaz", "baz", -1, -1)
+	}
 }
 
 func TestSuffixMatch(t *testing.T) {
-	assertMatch(t, SuffixMatch, false, "fooBarbaz", "Foo", -1, -1)
-	assertMatch(t, SuffixMatch, false, "fooBarbaz", "baz", 6, 9)
-	assertMatch(t, SuffixMatch, true, "fooBarbaz", "Baz", -1, -1)
+	for _, dir := range []bool{true, false} {
+		assertMatch(t, SuffixMatch, false, dir, "fooBarbaz", "Foo", -1, -1)
+		assertMatch(t, SuffixMatch, false, dir, "fooBarbaz", "baz", 6, 9)
+		assertMatch(t, SuffixMatch, true, dir, "fooBarbaz", "Baz", -1, -1)
+	}
 }
 
 func TestEmptyPattern(t *testing.T) {
-	assertMatch(t, FuzzyMatch, true, "foobar", "", 0, 0)
-	assertMatch(t, ExactMatchNaive, true, "foobar", "", 0, 0)
-	assertMatch(t, PrefixMatch, true, "foobar", "", 0, 0)
-	assertMatch(t, SuffixMatch, true, "foobar", "", 6, 6)
+	for _, dir := range []bool{true, false} {
+		assertMatch(t, FuzzyMatch, true, dir, "foobar", "", 0, 0)
+		assertMatch(t, ExactMatchNaive, true, dir, "foobar", "", 0, 0)
+		assertMatch(t, PrefixMatch, true, dir, "foobar", "", 0, 0)
+		assertMatch(t, SuffixMatch, true, dir, "foobar", "", 6, 6)
+	}
 }