Skip to content

Instantly share code, notes, and snippets.

@amitu

amitu/find.go

Created Apr 7, 2015
Embed
What would you like to do?
gobench 1
// Package bench is a package which contains
// programs of Go Benchmark Competition.
package bench
import (
"bufio"
"errors"
"fmt"
"os"
"strings"
)
// LCReader keeps track of line and column counts for a file
type LCReader struct {
*bufio.Reader
l, c int
}
// ReadByte reads a byte from the underlying reader, updating state
func (l *LCReader) ReadByte() (byte, error) {
b, err := l.Reader.ReadByte()
if err != nil {
return byte(0), err
}
// fmt.Println("got byte", b)
if b == '\n' {
l.l += 1
l.c = -1
} else {
l.c += 1
}
return b, nil
}
// NewLCReader creates a new LCReader wrapped around a file
func NewLCReader(file string) (*LCReader, error) {
f, err := os.Open(file)
if err != nil {
return nil, err
}
return &LCReader{bufio.NewReader(f), 1, -1}, nil
}
type Searcher struct {
pos int
l, c int
next *Searcher
}
type SearcherMap struct {
m map[byte]*Searcher
r *LCReader
needle []byte
length int
result []string
}
func (m SearcherMap) Result() string {
if m.result != nil {
return strings.Join(m.result, ",")
}
return ""
}
func (m *SearcherMap) AppendEtc(s *Searcher) {
if s == nil {
// first char found, do the needful
s = &Searcher{0, m.r.l, m.r.c, nil}
}
s.pos += 1
s.next = nil
if s.pos == m.length {
m.result = append(m.result, fmt.Sprintf("%d:%d", s.l, s.c))
return
}
b := m.needle[s.pos]
sfirst, ok := m.m[b]
if ok {
for {
if sfirst.next == nil {
sfirst.next = s
break
}
sfirst = sfirst.next
}
} else {
m.m[b] = s
}
}
func (m *SearcherMap) Next(b byte) {
s := m.m[b]
for k := range m.m {
delete(m.m, k)
}
// now we have a single surviving linked list left, we have to "explode" it
// for each searcher, increment its pos, and place it at end of linked list
// for next char
for {
if s == nil {
break
}
next := s.next
m.AppendEtc(s)
s = next
}
if b == m.needle[0] {
m.AppendEtc(nil)
}
}
func NewSearcherMap(needle string, r *LCReader) *SearcherMap {
return &SearcherMap{
make(map[byte]*Searcher), r, []byte(needle), len(needle), nil,
}
}
// Find reads the text file on the `path`,
// finds the `s` words on the file and
// returns the row numbers and indices
// in the form of `r:c,r:c,...r:c`,
// at which the `s` word exists.
func Find(path, s string) (string, error) {
if s == "" {
return "", errors.New("Search string empty.")
}
r, err := NewLCReader(path)
if err != nil {
return "", err
}
// we can have n number of searches going on, and we have to keep track of
// line and column numbers
// for line numbers and column numbers, we should have a reader.
// now for each searc, we have a map to keep track of searches happening.
// we always have one search going on, which is first char of s.
// if we find first char, now we have two searches going on, one for first
// char and second for second char. after each byte we check if the search
// matches, if it does then we
m := NewSearcherMap(s, r)
b, err := r.ReadByte()
for {
if err != nil {
// fmt.Println(err)
break
}
m.Next(b)
b, err = r.ReadByte()
}
return m.Result(), nil
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.