src/strings/search_test.go

   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
   5 package strings_test
   6
   7 import (
   8         "reflect"
   9         . "strings"
  10         "testing"
  11 )
  12
  13 func 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
  44 func 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 }