summaryrefslogtreecommitdiff
path: root/src/pkg/index
diff options
context:
space:
mode:
authorRobert Griesemer <gri@golang.org>2011-07-14 14:39:40 -0700
committerRobert Griesemer <gri@golang.org>2011-07-14 14:39:40 -0700
commitb9dab59dc4dd1fa493ab432bb0d83692112e800d (patch)
treec972808a96b43c701b6f2a280fced4166a2ce70c /src/pkg/index
parent2b13c2434b763f8aeb93c17189da7b2d94fecb4c (diff)
downloadgo-b9dab59dc4dd1fa493ab432bb0d83692112e800d.tar.gz
go/printer: changed max. number of newlines from 3 to 2
manual changes in src/pkg/go/printer, src/cmd/gofix/signal_test.go (cd src/cmd/gofix/testdata; gofmt -w *.in *.out) (cd src/pkg/go/printer; gotest -update) gofmt -w misc src runs all tests R=golang-dev, rsc CC=golang-dev http://codereview.appspot.com/4715041
Diffstat (limited to 'src/pkg/index')
-rw-r--r--src/pkg/index/suffixarray/qsufsort.go4
-rw-r--r--src/pkg/index/suffixarray/suffixarray.go7
-rw-r--r--src/pkg/index/suffixarray/suffixarray_test.go9
3 files changed, 0 insertions, 20 deletions
diff --git a/src/pkg/index/suffixarray/qsufsort.go b/src/pkg/index/suffixarray/qsufsort.go
index 9751b5c76..30c110442 100644
--- a/src/pkg/index/suffixarray/qsufsort.go
+++ b/src/pkg/index/suffixarray/qsufsort.go
@@ -72,7 +72,6 @@ func qsufsort(data []byte) []int {
return sa
}
-
func sortedByFirstByte(data []byte) []int {
// total byte counts
var count [256]int
@@ -93,7 +92,6 @@ func sortedByFirstByte(data []byte) []int {
return sa
}
-
func initGroups(sa []int, data []byte) []int {
// label contiguous same-letter groups with the same group number
inv := make([]int, len(data))
@@ -133,7 +131,6 @@ func initGroups(sa []int, data []byte) []int {
return inv
}
-
type suffixSortable struct {
sa []int
inv []int
@@ -144,7 +141,6 @@ func (x *suffixSortable) Len() int { return len(x.sa) }
func (x *suffixSortable) Less(i, j int) bool { return x.inv[x.sa[i]+x.h] < x.inv[x.sa[j]+x.h] }
func (x *suffixSortable) Swap(i, j int) { x.sa[i], x.sa[j] = x.sa[j], x.sa[i] }
-
func (x *suffixSortable) updateGroups(offset int) {
bounds := make([]int, 0, 4)
group := x.inv[x.sa[0]+x.h]
diff --git a/src/pkg/index/suffixarray/suffixarray.go b/src/pkg/index/suffixarray/suffixarray.go
index 9d4e93217..82e98d2ef 100644
--- a/src/pkg/index/suffixarray/suffixarray.go
+++ b/src/pkg/index/suffixarray/suffixarray.go
@@ -22,21 +22,18 @@ import (
"sort"
)
-
// Index implements a suffix array for fast substring search.
type Index struct {
data []byte
sa []int // suffix array for data
}
-
// New creates a new Index for data.
// Index creation time is O(N*log(N)) for N = len(data).
func New(data []byte) *Index {
return &Index{data, qsufsort(data)}
}
-
// Bytes returns the data over which the index was created.
// It must not be modified.
//
@@ -44,12 +41,10 @@ func (x *Index) Bytes() []byte {
return x.data
}
-
func (x *Index) at(i int) []byte {
return x.data[x.sa[i]:]
}
-
// 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 {
@@ -61,7 +56,6 @@ func (x *Index) lookupAll(s []byte) []int {
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.
@@ -82,7 +76,6 @@ func (x *Index) Lookup(s []byte, n int) (result []int) {
return
}
-
// FindAllIndex returns a sorted list of non-overlapping matches of the
// regular expression r, where a match is a pair of indices specifying
// the matched slice of x.Bytes(). If n < 0, all matches are returned
diff --git a/src/pkg/index/suffixarray/suffixarray_test.go b/src/pkg/index/suffixarray/suffixarray_test.go
index 385ff0e56..bd37ba400 100644
--- a/src/pkg/index/suffixarray/suffixarray_test.go
+++ b/src/pkg/index/suffixarray/suffixarray_test.go
@@ -13,14 +13,12 @@ import (
"testing"
)
-
type testCase struct {
name string // name of test case
source string // source to index
patterns []string // patterns to lookup
}
-
var testCases = []testCase{
{
"empty string",
@@ -107,7 +105,6 @@ var testCases = []testCase{
},
}
-
// find all occurrences of s in source; report at most n occurrences
func find(src, s string, n int) []int {
var res vector.IntVector
@@ -125,7 +122,6 @@ func find(src, s string, n int) []int {
return res
}
-
func testLookup(t *testing.T, tc *testCase, x *Index, s string, n int) {
res := x.Lookup([]byte(s), n)
exp := find(tc.source, s, n)
@@ -164,7 +160,6 @@ func testLookup(t *testing.T, tc *testCase, x *Index, s string, n int) {
}
}
-
func testFindAllIndex(t *testing.T, tc *testCase, x *Index, rx *regexp.Regexp, n int) {
res := x.FindAllIndex(rx, n)
exp := rx.FindAllStringIndex(tc.source, n)
@@ -200,7 +195,6 @@ func testFindAllIndex(t *testing.T, tc *testCase, x *Index, rx *regexp.Regexp, n
}
}
-
func testLookups(t *testing.T, tc *testCase, x *Index, n int) {
for _, pat := range tc.patterns {
testLookup(t, tc, x, pat, n)
@@ -210,7 +204,6 @@ func testLookups(t *testing.T, tc *testCase, x *Index, n int) {
}
}
-
// index is used to hide the sort.Interface
type index Index
@@ -219,14 +212,12 @@ func (x *index) Less(i, j int) bool { return bytes.Compare(x.at(i), x.at(j)) < 0
func (x *index) Swap(i, j int) { x.sa[i], x.sa[j] = x.sa[j], x.sa[i] }
func (a *index) at(i int) []byte { return a.data[a.sa[i]:] }
-
func testConstruction(t *testing.T, tc *testCase, x *Index) {
if !sort.IsSorted((*index)(x)) {
t.Errorf("testConstruction failed %s", tc.name)
}
}
-
func TestIndex(t *testing.T) {
for _, tc := range testCases {
x := New([]byte(tc.source))