diff options
author | Russ Cox <rsc@golang.org> | 2010-11-19 16:04:25 -0500 |
---|---|---|
committer | Russ Cox <rsc@golang.org> | 2010-11-19 16:04:25 -0500 |
commit | b51f0c5cca0074257b76518dbe169d7cc2a30f00 (patch) | |
tree | 3f3d0ac27dd4d1da593c2815223c5842b602f80e | |
parent | 07791d04d6a746ac1fbced541e46bae9e85178b4 (diff) | |
download | go-b51f0c5cca0074257b76518dbe169d7cc2a30f00.tar.gz go-b51f0c5cca0074257b76518dbe169d7cc2a30f00.zip |
index/suffixarray: use sort.Search
R=gri
CC=golang-dev
https://golang.org/cl/3200041
-rw-r--r-- | src/pkg/index/suffixarray/suffixarray.go | 22 |
1 files changed, 2 insertions, 20 deletions
diff --git a/src/pkg/index/suffixarray/suffixarray.go b/src/pkg/index/suffixarray/suffixarray.go index 0a17472962..4839dbb146 100644 --- a/src/pkg/index/suffixarray/suffixarray.go +++ b/src/pkg/index/suffixarray/suffixarray.go @@ -54,21 +54,8 @@ func (x *Index) at(i int) []byte { } -// Binary search according to "A Method of Programming", E.W. Dijkstra. func (x *Index) search(s []byte) int { - i, j := 0, len(x.sa) - // i < j for non-empty x - for i+1 < j { - // 0 <= i < j <= len(x.sa) && (x.at(i) <= s < x.at(j) || (s is not in x)) - h := i + (j-i)/2 // i < h < j - if bytes.Compare(x.at(h), s) <= 0 { - i = h - } else { // s < x.at(h) - j = h - } - } - // i+1 == j for non-empty x - return i + return sort.Search(len(x.sa), func(i int) bool { return bytes.Compare(x.at(i), s) >= 0 }) } @@ -84,12 +71,7 @@ func (x *Index) Lookup(s []byte, n int) []int { if len(s) > 0 && n != 0 { // find matching suffix index i i := x.search(s) - // x.at(i) <= s < x.at(i+1) - - // ignore the first suffix if it is < s - if i < len(x.sa) && bytes.Compare(x.at(i), s) < 0 { - i++ - } + // x.at(i-1) < s <= x.at(i) // collect the following suffixes with matching prefixes for (n < 0 || len(res) < n) && i < len(x.sa) && bytes.HasPrefix(x.at(i), s) { |