gobench 1

find.go

// 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
}