libgo/go/index/suffixarray/suffixarray_test.go

   1 // Copyright 2010 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 suffixarray
   6
   7 import (
   8         "container/vector"
   9         "sort"
  10         "strings"
  11         "testing"
  12 )
  13
  14
  15 type testCase struct {
  16         name    string   // name of test case
  17         source  string   // source to index
  18         lookups []string // strings to lookup
  19 }
  20
  21
  22 var testCases = []testCase{
  23         {
  24                 "empty string",
  25                 "",
  26                 []string{
  27                         "",
  28                         "foo",
  29                 },
  30         },
  31
  32         {
  33                 "all a's",
  34                 "aaaaaaaaaa", // 10 a's
  35                 []string{
  36                         "",
  37                         "a",
  38                         "aa",
  39                         "aaa",
  40                         "aaaa",
  41                         "aaaaa",
  42                         "aaaaaa",
  43                         "aaaaaaa",
  44                         "aaaaaaaa",
  45                         "aaaaaaaaa",
  46                         "aaaaaaaaaa",
  47                         "aaaaaaaaaaa", // 11 a's
  48                 },
  49         },
  50
  51         {
  52                 "abc",
  53                 "abc",
  54                 []string{
  55                         "a",
  56                         "b",
  57                         "c",
  58                         "ab",
  59                         "bc",
  60                         "abc",
  61                 },
  62         },
  63
  64         {
  65                 "barbara*3",
  66                 "barbarabarbarabarbara",
  67                 []string{
  68                         "a",
  69                         "bar",
  70                         "rab",
  71                         "arab",
  72                         "barbar",
  73                 },
  74         },
  75
  76         {
  77                 "typing drill",
  78                 "Now is the time for all good men to come to the aid of their country.",
  79                 []string{
  80                         "Now",
  81                         "the time",
  82                         "to come the aid",
  83                         "is the time for all good men to come to the aid of their",
  84                 },
  85         },
  86 }
  87
  88
  89 // find all occurences of s in source; report at most n occurences
  90 func find(src, s string, n int) []int {
  91         var res vector.IntVector
  92         if s != "" && n != 0 {
  93                 // find at most n occurences of s in src
  94                 for i := -1; n < 0 || len(res) < n; {
  95                         j := strings.Index(src[i+1:], s)
  96                         if j < 0 {
  97                                 break
  98                         }
  99                         i += j + 1
 100                         res.Push(i)
 101                 }
 102         }
 103         return res
 104 }
 105
 106
 107 func testLookups(t *testing.T, src string, x *Index, tc *testCase, n int) {
 108         for _, s := range tc.lookups {
 109                 res := x.Lookup([]byte(s), n)
 110                 exp := find(tc.source, s, n)
 111
 112                 // check that the lengths match
 113                 if len(res) != len(exp) {
 114                         t.Errorf("test %q, lookup %q (n = %d): expected %d results; got %d", tc.name, s, n, len(exp), len(res))
 115                 }
 116
 117                 // if n >= 0 the number of results is limited --- unless n >= all results,
 118                 // we may obtain different positions from the Index and from find (because
 119                 // Index may not find the results in the same order as find) => in general
 120                 // we cannot simply check that the res and exp lists are equal
 121
 122                 // check that there are no duplicates
 123                 sort.SortInts(res)
 124                 for i, r := range res {
 125                         if i > 0 && res[i-1] == r {
 126                                 t.Errorf("test %q, lookup %q, result %d (n = %d): found duplicate index %d", tc.name, s, i, n, r)
 127                         }
 128                 }
 129
 130                 // check that each result is in fact a correct match
 131                 for i, r := range res {
 132                         if r < 0 || len(src) <= r {
 133                                 t.Errorf("test %q, lookup %q, result %d (n = %d): index %d out of range [0, %d[", tc.name, s, i, n, r, len(src))
 134                         } else if !strings.HasPrefix(src[r:], s) {
 135                                 t.Errorf("test %q, lookup %q, result %d (n = %d): index %d not a match", tc.name, s, i, n, r)
 136                         }
 137                 }
 138
 139                 if n < 0 {
 140                         // all results computed - sorted res and exp must be equal
 141                         for i, r := range res {
 142                                 e := exp[i]
 143                                 if r != e {
 144                                         t.Errorf("test %q, lookup %q, result %d: expected index %d; got %d", tc.name, s, i, e, r)
 145                                         continue
 146                                 }
 147                         }
 148                 }
 149         }
 150 }
 151
 152
 153 func TestIndex(t *testing.T) {
 154         for _, tc := range testCases {
 155                 x := New([]byte(tc.source))
 156                 testLookups(t, tc.source, x, &tc, 0)
 157                 testLookups(t, tc.source, x, &tc, 1)
 158                 testLookups(t, tc.source, x, &tc, 10)
 159                 testLookups(t, tc.source, x, &tc, -1)
 160         }
 161 }