aboutsummaryrefslogtreecommitdiff
path: root/libgo/go/index
diff options
context:
space:
mode:
authorIan Lance Taylor <ian@gcc.gnu.org>2011-03-16 23:05:44 +0000
committerIan Lance Taylor <ian@gcc.gnu.org>2011-03-16 23:05:44 +0000
commit5133f00ef8baab894d92de1e8b8baae59815a8b6 (patch)
tree44176975832a3faf1626836e70c97d5edd674122 /libgo/go/index
parentf617201f55938fc89b532f2240bdf77bea946471 (diff)
downloadgcc-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.go28
-rw-r--r--libgo/go/index/suffixarray/suffixarray.go28
-rw-r--r--libgo/go/index/suffixarray/suffixarray_test.go6
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{},
+ },
}