diff options
author | Ian Lance Taylor <ian@gcc.gnu.org> | 2011-03-16 23:05:44 +0000 |
---|---|---|
committer | Ian Lance Taylor <ian@gcc.gnu.org> | 2011-03-16 23:05:44 +0000 |
commit | 5133f00ef8baab894d92de1e8b8baae59815a8b6 (patch) | |
tree | 44176975832a3faf1626836e70c97d5edd674122 /libgo/go/index | |
parent | f617201f55938fc89b532f2240bdf77bea946471 (diff) | |
download | gcc-5133f00ef8baab894d92de1e8b8baae59815a8b6.zip gcc-5133f00ef8baab894d92de1e8b8baae59815a8b6.tar.gz gcc-5133f00ef8baab894d92de1e8b8baae59815a8b6.tar.bz2 |
Update to current version of Go library (revision 94d654be2064).
From-SVN: r171076
Diffstat (limited to 'libgo/go/index')
-rw-r--r-- | libgo/go/index/suffixarray/qsufsort.go | 28 | ||||
-rw-r--r-- | libgo/go/index/suffixarray/suffixarray.go | 28 | ||||
-rw-r--r-- | libgo/go/index/suffixarray/suffixarray_test.go | 6 |
3 files changed, 40 insertions, 22 deletions
diff --git a/libgo/go/index/suffixarray/qsufsort.go b/libgo/go/index/suffixarray/qsufsort.go index 0e6894a..9751b5c 100644 --- a/libgo/go/index/suffixarray/qsufsort.go +++ b/libgo/go/index/suffixarray/qsufsort.go @@ -146,19 +146,25 @@ func (x *suffixSortable) Swap(i, j int) { x.sa[i], x.sa[j] = x.sa[j], x.sa[ func (x *suffixSortable) updateGroups(offset int) { - prev := len(x.sa) - 1 - group := x.inv[x.sa[prev]+x.h] - for i := prev; i >= 0; i-- { - if g := x.inv[x.sa[i]+x.h]; g < group { - if prev == i+1 { // previous group had size 1 and is thus sorted - x.sa[i+1] = -1 - } + bounds := make([]int, 0, 4) + group := x.inv[x.sa[0]+x.h] + for i := 1; i < len(x.sa); i++ { + if g := x.inv[x.sa[i]+x.h]; g > group { + bounds = append(bounds, i) group = g - prev = i } - x.inv[x.sa[i]] = prev + offset - if prev == 0 { // first group has size 1 and is thus sorted - x.sa[0] = -1 + } + bounds = append(bounds, len(x.sa)) + + // update the group numberings after all new groups are determined + prev := 0 + for _, b := range bounds { + for i := prev; i < b; i++ { + x.inv[x.sa[i]] = offset + b - 1 + } + if b-prev == 1 { + x.sa[prev] = -1 } + prev = b } } diff --git a/libgo/go/index/suffixarray/suffixarray.go b/libgo/go/index/suffixarray/suffixarray.go index 628e000..d8c6fc9 100644 --- a/libgo/go/index/suffixarray/suffixarray.go +++ b/libgo/go/index/suffixarray/suffixarray.go @@ -50,27 +50,33 @@ func (x *Index) at(i int) []byte { } -func (x *Index) search(s []byte) int { - return sort.Search(len(x.sa), func(i int) bool { return bytes.Compare(x.at(i), s) >= 0 }) +// lookupAll returns a slice into the matching region of the index. +// The runtime is O(log(N)*len(s)). +func (x *Index) lookupAll(s []byte) []int { + // find matching suffix index range [i:j] + // find the first index where s would be the prefix + i := sort.Search(len(x.sa), func(i int) bool { return bytes.Compare(x.at(i), s) >= 0 }) + // starting at i, find the first index at which s is not a prefix + j := i + sort.Search(len(x.sa)-i, func(j int) bool { return !bytes.HasPrefix(x.at(j+i), s) }) + return x.sa[i:j] } // Lookup returns an unsorted list of at most n indices where the byte string s // occurs in the indexed data. If n < 0, all occurrences are returned. // The result is nil if s is empty, s is not found, or n == 0. -// Lookup time is O((log(N) + len(result))*len(s)) where N is the +// Lookup time is O(log(N)*len(s) + len(result)) where N is the // size of the indexed data. // func (x *Index) Lookup(s []byte, n int) (result []int) { if len(s) > 0 && n != 0 { - // find matching suffix index i - i := x.search(s) - // x.at(i-1) < s <= x.at(i) - - // collect the following suffixes with matching prefixes - for (n < 0 || len(result) < n) && i < len(x.sa) && bytes.HasPrefix(x.at(i), s) { - result = append(result, x.sa[i]) - i++ + matches := x.lookupAll(s) + if len(matches) < n || n < 0 { + n = len(matches) + } + if n > 0 { + result = make([]int, n) + copy(result, matches) } } return diff --git a/libgo/go/index/suffixarray/suffixarray_test.go b/libgo/go/index/suffixarray/suffixarray_test.go index b3486a9..e85267f 100644 --- a/libgo/go/index/suffixarray/suffixarray_test.go +++ b/libgo/go/index/suffixarray/suffixarray_test.go @@ -99,6 +99,12 @@ var testCases = []testCase{ "to (come|the)?", }, }, + + { + "godoc simulation", + "package main\n\nimport(\n \"rand\"\n ", + []string{}, + }, } |