1// Copyright 2012 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package strings_test
6
7import (
8	"reflect"
9	. "strings"
10	"testing"
11)
12
13func TestFinderNext(t *testing.T) {
14	testCases := []struct {
15		pat, text string
16		index     int
17	}{
18		{"", "", 0},
19		{"", "abc", 0},
20		{"abc", "", -1},
21		{"abc", "abc", 0},
22		{"d", "abcdefg", 3},
23		{"nan", "banana", 2},
24		{"pan", "anpanman", 2},
25		{"nnaaman", "anpanmanam", -1},
26		{"abcd", "abc", -1},
27		{"abcd", "bcd", -1},
28		{"bcd", "abcd", 1},
29		{"abc", "acca", -1},
30		{"aa", "aaa", 0},
31		{"baa", "aaaaa", -1},
32		{"at that", "which finally halts.  at that point", 22},
33	}
34
35	for _, tc := range testCases {
36		got := StringFind(tc.pat, tc.text)
37		want := tc.index
38		if got != want {
39			t.Errorf("stringFind(%q, %q) got %d, want %d\n", tc.pat, tc.text, got, want)
40		}
41	}
42}
43
44func TestFinderCreation(t *testing.T) {
45	testCases := []struct {
46		pattern string
47		bad     [256]int
48		suf     []int
49	}{
50		{
51			"abc",
52			[256]int{'a': 2, 'b': 1, 'c': 3},
53			[]int{5, 4, 1},
54		},
55		{
56			"mississi",
57			[256]int{'i': 3, 'm': 7, 's': 1},
58			[]int{15, 14, 13, 7, 11, 10, 7, 1},
59		},
60		// From https://www.cs.utexas.edu/~moore/publications/fstrpos.pdf
61		{
62			"abcxxxabc",
63			[256]int{'a': 2, 'b': 1, 'c': 6, 'x': 3},
64			[]int{14, 13, 12, 11, 10, 9, 11, 10, 1},
65		},
66		{
67			"abyxcdeyx",
68			[256]int{'a': 8, 'b': 7, 'c': 4, 'd': 3, 'e': 2, 'y': 1, 'x': 5},
69			[]int{17, 16, 15, 14, 13, 12, 7, 10, 1},
70		},
71	}
72
73	for _, tc := range testCases {
74		bad, good := DumpTables(tc.pattern)
75
76		for i, got := range bad {
77			want := tc.bad[i]
78			if want == 0 {
79				want = len(tc.pattern)
80			}
81			if got != want {
82				t.Errorf("boyerMoore(%q) bad['%c']: got %d want %d", tc.pattern, i, got, want)
83			}
84		}
85
86		if !reflect.DeepEqual(good, tc.suf) {
87			t.Errorf("boyerMoore(%q) got %v want %v", tc.pattern, good, tc.suf)
88		}
89	}
90}
91