Merge pull request #15 from dannyyoo/master
Correcting indexOf and adding lastIndexOf.
diff --git a/diffmatchpatch/dmp.go b/diffmatchpatch/dmp.go
index 0ec5f51..fb560f4 100644
--- a/diffmatchpatch/dmp.go
+++ b/diffmatchpatch/dmp.go
@@ -70,25 +70,31 @@
return append(slice[:index], append(elements, slice[index+amount:]...)...)
}
+// indexOf returns the first index of pattern in str, starting at str[i].
func indexOf(str string, pattern string, i int) int {
if i > len(str)-1 {
return -1
}
-
- if i == 0 {
+ if i <= 0 {
return strings.Index(str, pattern)
}
-
- str1 := str[0:i]
- str2 := str[i:]
-
- ind := strings.Index(str2, pattern)
+ ind := strings.Index(str[i:], pattern)
if ind == -1 {
return -1
}
+ return ind + i
+}
- return ind + len(str1)
-
+// lastIndexOf returns the last index of pattern in str, starting at str[i].
+func lastIndexOf(str string, pattern string, i int) int {
+ if i < 0 {
+ return -1
+ }
+ if i >= len(str) {
+ return strings.LastIndex(str, pattern)
+ }
+ _, size := utf8.DecodeRuneInString(str[i:])
+ return strings.LastIndex(str[:i+size], pattern)
}
// Return the index of pattern in target, starting at target[i].
@@ -96,11 +102,14 @@
if i > len(target)-1 {
return -1
}
+ if i <= 0 {
+ return runesIndex(target, pattern)
+ }
ind := runesIndex(target[i:], pattern)
if ind == -1 {
return -1
}
- return i + ind
+ return ind + i
}
func min(x, y int) int {
@@ -1583,12 +1592,12 @@
// Highest score beyond which we give up.
var score_threshold float64 = dmp.MatchThreshold
// Is there a nearby exact match? (speedup)
- best_loc := strings.Index(text, pattern)
+ best_loc := indexOf(text, pattern, loc)
if best_loc != -1 {
score_threshold = math.Min(dmp.matchBitapScore(0, best_loc, loc,
pattern), score_threshold)
// What about in the other direction? (speedup)
- best_loc = strings.LastIndex(text, pattern)
+ best_loc = lastIndexOf(text, pattern, loc+len(pattern))
if best_loc != -1 {
score_threshold = math.Min(dmp.matchBitapScore(0, best_loc, loc,
pattern), score_threshold)
diff --git a/diffmatchpatch/dmp_test.go b/diffmatchpatch/dmp_test.go
index 086e5df..34d696e 100644
--- a/diffmatchpatch/dmp_test.go
+++ b/diffmatchpatch/dmp_test.go
@@ -257,7 +257,6 @@
assert.True(t, utf8.ValidString(d.Text))
}
}
-
func Test_diffLinesToChars(t *testing.T) {
dmp := New()
@@ -1385,6 +1384,80 @@
assert.Equal(t, "x123\ttrue", resultStr, "patch_apply: Edge partial match.")
}
+func TestIndexOf(t *testing.T) {
+ type TestCase struct {
+ String string
+ Pattern string
+ Position int
+ Expected int
+ }
+ cases := []TestCase{
+ {"hi world", "world", -1, 3},
+ {"hi world", "world", 0, 3},
+ {"hi world", "world", 1, 3},
+ {"hi world", "world", 2, 3},
+ {"hi world", "world", 3, 3},
+ {"hi world", "world", 4, -1},
+ {"abbc", "b", -1, 1},
+ {"abbc", "b", 0, 1},
+ {"abbc", "b", 1, 1},
+ {"abbc", "b", 2, 2},
+ {"abbc", "b", 3, -1},
+ {"abbc", "b", 4, -1},
+ // The greek letter beta is the two-byte sequence of "\u03b2".
+ {"a\u03b2\u03b2c", "\u03b2", -1, 1},
+ {"a\u03b2\u03b2c", "\u03b2", 0, 1},
+ {"a\u03b2\u03b2c", "\u03b2", 1, 1},
+ {"a\u03b2\u03b2c", "\u03b2", 3, 3},
+ {"a\u03b2\u03b2c", "\u03b2", 5, -1},
+ {"a\u03b2\u03b2c", "\u03b2", 6, -1},
+ }
+ for i, c := range cases {
+ actual := indexOf(c.String, c.Pattern, c.Position)
+ assert.Equal(t, c.Expected, actual, fmt.Sprintf("TestIndex case %d", i))
+ }
+}
+
+func TestLastIndexOf(t *testing.T) {
+ type TestCase struct {
+ String string
+ Pattern string
+ Position int
+ Expected int
+ }
+ cases := []TestCase{
+ {"hi world", "world", -1, -1},
+ {"hi world", "world", 0, -1},
+ {"hi world", "world", 1, -1},
+ {"hi world", "world", 2, -1},
+ {"hi world", "world", 3, -1},
+ {"hi world", "world", 4, -1},
+ {"hi world", "world", 5, -1},
+ {"hi world", "world", 6, -1},
+ {"hi world", "world", 7, 3},
+ {"hi world", "world", 8, 3},
+ {"abbc", "b", -1, -1},
+ {"abbc", "b", 0, -1},
+ {"abbc", "b", 1, 1},
+ {"abbc", "b", 2, 2},
+ {"abbc", "b", 3, 2},
+ {"abbc", "b", 4, 2},
+ // The greek letter beta is the two-byte sequence of "\u03b2".
+ {"a\u03b2\u03b2c", "\u03b2", -1, -1},
+ {"a\u03b2\u03b2c", "\u03b2", 0, -1},
+ {"a\u03b2\u03b2c", "\u03b2", 1, 1},
+ {"a\u03b2\u03b2c", "\u03b2", 3, 3},
+ {"a\u03b2\u03b2c", "\u03b2", 5, 3},
+ {"a\u03b2\u03b2c", "\u03b2", 6, 3},
+ }
+
+ for i, c := range cases {
+ actual := lastIndexOf(c.String, c.Pattern, c.Position)
+ assert.Equal(t, c.Expected, actual,
+ fmt.Sprintf("TestLastIndex case %d", i))
+ }
+}
+
func Benchmark_DiffMain(bench *testing.B) {
dmp := New()
dmp.DiffTimeout = time.Second
