<commit_before>// Copyright 2010 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package suffixarray implements substring search in logarithmic time using
// an in-memory suffix array.
//
// Example use:
//
//	// create index for some data
//	index := suffixarray.New(data)
//
//	// lookup byte slice s
//	offsets1 := index.Lookup(s, -1) // the list of all indices where s occurs in data
//	offsets2 := index.Lookup(s, 3)  // the list of at most 3 indices where s occurs in data
//
package suffixarray

import (
	"bytes"
	"encoding/binary"
	"io"
	"regexp"
	"sort"
)

// Index implements a suffix array for fast substring search.
type Index struct {
	data []byte
	sa   []int // suffix array for data; len(sa) == len(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)}
}

// writeInt writes an int x to w using buf to buffer the write.
func writeInt(w io.Writer, buf []byte, x int) error {
	binary.PutVarint(buf, int64(x))
	_, err := w.Write(buf[0:binary.MaxVarintLen64])
	return err
}

// readInt reads an int x from r using buf to buffer the read and returns x.
func readInt(r io.Reader, buf []byte) (int, error) {
	_, err := io.ReadFull(r, buf[0:binary.MaxVarintLen64]) // ok to continue with error
	x, _ := binary.Varint(buf)
	return int(x), err
}

// writeSlice writes data[:n] to w and returns n.
// It uses buf to buffer the write.
func writeSlice(w io.Writer, buf []byte, data []int) (n int, err error) {
	// encode as many elements as fit into buf
	p := binary.MaxVarintLen64
	for ; n < len(data) && p+binary.MaxVarintLen64 <= len(buf); n++ {
		p += binary.PutUvarint(buf[p:], uint64(data[n]))
	}

	// update buffer size
	binary.PutVarint(buf, int64(p))

	// write buffer
	_, err = w.Write(buf[0:p])
	return
}

// readSlice reads data[:n] from r and returns n.
// It uses buf to buffer the read.
func readSlice(r io.Reader, buf []byte, data []int) (n int, err error) {
	// read buffer size
	var size int
	size, err = readInt(r, buf)
	if err != nil {
		return
	}

	// read buffer w/o the size
	if _, err = io.ReadFull(r, buf[binary.MaxVarintLen64:size]); err != nil {
		return
	}

	// decode as many elements as present in buf
	for p := binary.MaxVarintLen64; p < size; n++ {
		x, w := binary.Uvarint(buf[p:])
		data[n] = int(x)
		p += w
	}

	return
}

const bufSize = 16 << 10 // reasonable for BenchmarkSaveRestore

// Read reads the index from r into x; x must not be nil.
func (x *Index) Read(r io.Reader) error {
	// buffer for all reads
	buf := make([]byte, bufSize)

	// read length
	n, err := readInt(r, buf)
	if err != nil {
		return err
	}

	// allocate space
	if 2*n < cap(x.data) || 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([]int, n)<commit_msg>index/suffixarray: fix a typo mistake in comments<commit_after>// Copyright 2010 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package suffixarray implements substring search in logarithmic time using
// an in-memory suffix array.
//
// Example use:
//
//	// create index for some data
//	index := suffixarray.New(data)
//
//	// lookup byte slice s
//	offsets1 := index.Lookup(s, -1) // the list of all indices where s occurs in data
//	offsets2 := index.Lookup(s, 3)  // the list of at most 3 indices where s occurs in data
//
package suffixarray

import (
	"bytes"
	"encoding/binary"
	"io"
	"regexp"
	"sort"
)

// Index implements a suffix array for fast substring search.
type Index struct {
	data []byte
	sa   []int // suffix array for data; len(sa) == len(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)}
}

// writeInt writes an int x to w using buf to buffer the write.
func writeInt(w io.Writer, buf []byte, x int) error {
	binary.PutVarint(buf, int64(x))
	_, err := w.Write(buf[0:binary.MaxVarintLen64])
	return err
}

// readInt reads an int x from r using buf to buffer the read and returns x.
func readInt(r io.Reader, buf []byte) (int, error) {
	_, err := io.ReadFull(r, buf[0:binary.MaxVarintLen64]) // ok to continue with error
	x, _ := binary.Varint(buf)
	return int(x), err
}

// writeSlice writes data[:n] to w and returns n.
// It uses buf to buffer the write.
func writeSlice(w io.Writer, buf []byte, data []int) (n int, err error) {
	// encode as many elements as fit into buf
	p := binary.MaxVarintLen64
	for ; n < len(data) && p+binary.MaxVarintLen64 <= len(buf); n++ {
		p += binary.PutUvarint(buf[p:], uint64(data[n]))
	}

	// update buffer size
	binary.PutVarint(buf, int64(p))

	// write buffer
	_, err = w.Write(buf[0:p])
	return
}

// readSlice reads data[:n] from r and returns n.
// It uses buf to buffer the read.
func readSlice(r io.Reader, buf []byte, data []int) (n int, err error) {
	// read buffer size
	var size int
	size, err = readInt(r, buf)
	if err != nil {
		return
	}

	// read buffer w/o the size
	if _, err = io.ReadFull(r, buf[binary.MaxVarintLen64:size]); err != nil {
		return
	}

	// decode as many elements as present in buf
	for p := binary.MaxVarintLen64; p < size; n++ {
		x, w := binary.Uvarint(buf[p:])
		data[n] = int(x)
		p += w
	}

	return
}

const bufSize = 16 << 10 // reasonable for BenchmarkSaveRestore

// Read reads the index from r into x; x must not be nil.
func (x *Index) Read(r io.Reader) error {
	// buffer for all reads
	buf := make([]byte, bufSize)

	// read length
	n, err := readInt(r, buf)
	if err != nil {
		return err
	}

	// allocate space
	if 2*n < cap(x.data) || cap(x.data) < n {
		// new data is significantly smaller or larger than
		// existing buffers - allocate new ones
		x.data = make([]byte, n)
		x.sa = make([]int, n)
{'fraction_non_alphanumeric': 0.13782796413151777, 'fraction_numerical': 0.011624045167718366, 'mean_word_length': 3.153793103448276, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '393344', 'n_tokens_mistral': 2169, 'n_tokens_neox': 2084, 'n_words': 797}