gistfile1.go

// Package bench is a package which contains
// programs of Go Benchmark Competition.
package bench

import (
	"bufio"
	"bytes"
	"errors"
	"io"
	"os"
	"strconv"
)

// 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("s is empty")
	}
	sLen := len(s)
	f, err := os.Open(path)
	if err != nil {
		return "", err
	}
	r := bufio.NewReaderSize(f, sLen)

	// Implementation of the Boyer-Moore-Horspool algorithm on a reader.
	var (
		lineNum   = 1
		charNum   int
		index     int
		skip      = sLen
		comma, ok bool
		c         byte
		sLenBuf   = make([]byte, sLen)
		skipMap   = map[byte]int{}
		output    = bytes.Buffer{}
	)
	// Create skip map for all except last char.
	for i := 0; i < sLen-1; i++ {
		skipMap[s[i]] = sLen - 1 - i
	}
	for {
		if _, err = io.ReadFull(r, sLenBuf[sLen-skip:]); err != nil {
			if err == io.EOF || err == io.ErrUnexpectedEOF {
				// We've hit the end of the reader.
				break
			}
			return "", err
		}
		index = sLen - 1
		for index >= 0 && sLenBuf[index] == s[index] {
			if index == 0 {
				// Match!
				if comma {
					output.WriteByte(',')
				}
				output.WriteString(strconv.Itoa(lineNum))
				output.WriteByte(':')
				output.WriteString(strconv.Itoa(charNum))
				comma = true
				break
			}
			index--
		}
		// Skip ahead based on skip table and last char.
		skip, ok = skipMap[sLenBuf[sLen-1]]
		if !ok {
			skip = sLen
		}
		for _, c = range sLenBuf[:skip] {
			if c == '\n' {
				lineNum++
				charNum = 0
			} else {
				charNum++
			}
		}
		if skip != sLen {
			copy(sLenBuf, sLenBuf[skip:])
		}
	}
	return output.String(), nil
}