index/suffixarray: support for serialization
R=r
CC=golang-dev
https://golang.org/cl/5040041
diff --git a/src/pkg/index/suffixarray/suffixarray.go b/src/pkg/index/suffixarray/suffixarray.go
index c78de85..c2a9994 100644
--- a/src/pkg/index/suffixarray/suffixarray.go
+++ b/src/pkg/index/suffixarray/suffixarray.go
@@ -18,14 +18,17 @@
import (
"bytes"
+ "encoding/binary"
"exp/regexp"
+ "io"
+ "os"
"sort"
)
// Index implements a suffix array for fast substring search.
type Index struct {
data []byte
- sa []int // suffix array for data
+ sa []int32 // suffix array for data; len(sa) == len(data)
}
// New creates a new Index for data.
@@ -34,6 +37,48 @@
return &Index{data, qsufsort(data)}
}
+// Read reads the index from r into x; x must not be nil.
+func (x *Index) Read(r io.Reader) os.Error {
+ var n int32
+ if err := binary.Read(r, binary.LittleEndian, &n); err != nil {
+ return err
+ }
+ if 2*n < int32(cap(x.data)) || int32(cap(x.data)) < n {
+ // new data is significantly smaller or larger then
+ // existing buffers - allocate new ones
+ x.data = make([]byte, n)
+ x.sa = make([]int32, n)
+ } else {
+ // re-use existing buffers
+ x.data = x.data[0:n]
+ x.sa = x.sa[0:n]
+ }
+
+ if err := binary.Read(r, binary.LittleEndian, x.data); err != nil {
+ return err
+ }
+ if err := binary.Read(r, binary.LittleEndian, x.sa); err != nil {
+ return err
+ }
+
+ return nil
+}
+
+// Write writes the index x to w.
+func (x *Index) Write(w io.Writer) os.Error {
+ n := int32(len(x.data))
+ if err := binary.Write(w, binary.LittleEndian, n); err != nil {
+ return err
+ }
+ if err := binary.Write(w, binary.LittleEndian, x.data); err != nil {
+ return err
+ }
+ if err := binary.Write(w, binary.LittleEndian, x.sa); err != nil {
+ return err
+ }
+ return nil
+}
+
// Bytes returns the data over which the index was created.
// It must not be modified.
//
@@ -47,7 +92,7 @@
// 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 {
+func (x *Index) lookupAll(s []byte) []int32 {
// 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 })
@@ -65,12 +110,15 @@
func (x *Index) Lookup(s []byte, n int) (result []int) {
if len(s) > 0 && n != 0 {
matches := x.lookupAll(s)
- if len(matches) < n || n < 0 {
+ if n < 0 || len(matches) < n {
n = len(matches)
}
+ // 0 <= n <= len(matches)
if n > 0 {
result = make([]int, n)
- copy(result, matches)
+ for i, x := range matches[0:n] {
+ result[i] = int(x)
+ }
}
}
return
