<commit_before>// Package global provides an algorithm for globally adaptive hierarchical
// interpolation.
package global

import (
	"math"

	"github.com/ready-steady/adapt/algorithm/internal"
)

var (
	infinity = math.Inf(1.0)
)

// Basis is a functional basis.
type Basis interface {
	// Compute evaluates the value of a basis function.
	Compute([]uint64, []float64) float64
}

// Grid is a sparse grid.
type Grid interface {
	// Compute returns the nodes corresponding to a set of indices.
	Compute([]uint64) []float64

	// Index returns the indices of a set of levels.
	Index([]uint8) []uint64
}

// Interpolator is an instance of the algorithm.
type Interpolator struct {
	config Config
	basis  Basis
	grid   Grid
}

// Progress contains information about the interpolation process.
type Progress struct {
	Level       uint8 // Reached level
	Active      uint  // The number of active indices
	Passive     uint  // The number of passive indices
	Evaluations uint  // The number of function evaluations
}

type cursor map[uint]bool

// New creates an interpolator.
func New(grid Grid, basis Basis, config *Config) *Interpolator {
	return &Interpolator{
		config: *config,
		basis:  basis,
		grid:   grid,
	}
}

// Compute constructs an interpolant for a function.
func (self *Interpolator) Compute(target Target) *Surrogate {
	config := &self.config

	ni, no := target.Dimensions()
	nw := config.Workers

	surrogate := newSurrogate(ni, no)
	accuracy := newAccuracy(no, config)
	tracker := newTracker(ni, config)

	progress := &Progress{}
	for {
		lindices := tracker.pull()
		nn := uint(len(lindices)) / ni

		progress.Active = uint(len(tracker.active))
		progress.Passive = tracker.nn - progress.Active
		if level := maxUint8(lindices); level > progress.Level {
			progress.Level = level
		}

		target.Monitor(progress)

		indices, counts := make([]uint64, 0), make([]uint, 0, nn)
		for i := uint(0); i < nn; i++ {
			newIndices := self.grid.Index(lindices[i*ni : (i+1)*ni])
			indices = append(indices, newIndices...)
			counts = append(counts, uint(len(newIndices))/ni)
		}

		progress.Evaluations += uint(len(indices)) / ni
		if progress.Evaluations > config.MaxEvaluations {
			break
		}

		nodes := self.grid.Compute(indices)
		values := internal.Invoke(target.Compute, nodes, ni, no, nw)
		surpluses := internal.Subtract(values, internal.Approximate(self.basis,
			surrogate.Indices, surrogate.Surpluses, nodes, ni, no, nw))

		surrogate.push(indices, surpluses)
		accuracy.push(values, surpluses, counts)
		tracker.push(assess(target.Score, surpluses, counts, no))

		if accuracy.enough(tracker.active) {
			break
		}
	}
<commit_msg>a/global: make a cosmetic adjustment<commit_after>// Package global provides an algorithm for globally adaptive hierarchical
// interpolation.
package global

import (
	"math"

	"github.com/ready-steady/adapt/algorithm/internal"
)

var (
	infinity = math.Inf(1.0)
)

// Basis is a functional basis.
type Basis interface {
	// Compute evaluates the value of a basis function.
	Compute([]uint64, []float64) float64
}

// Grid is a sparse grid.
type Grid interface {
	// Compute returns the nodes corresponding to a set of indices.
	Compute([]uint64) []float64

	// Index returns the indices of a set of levels.
	Index([]uint8) []uint64
}

// Interpolator is an instance of the algorithm.
type Interpolator struct {
	config Config
	basis  Basis
	grid   Grid
}

// Progress contains information about the interpolation process.
type Progress struct {
	Level       uint8 // Reached level
	Active      uint  // The number of active indices
	Passive     uint  // The number of passive indices
	Evaluations uint  // The number of function evaluations
}

type cursor map[uint]bool

// New creates an interpolator.
func New(grid Grid, basis Basis, config *Config) *Interpolator {
	return &Interpolator{
		config: *config,
		basis:  basis,
		grid:   grid,
	}
}

// Compute constructs an interpolant for a function.
func (self *Interpolator) Compute(target Target) *Surrogate {
	config := &self.config

	ni, no := target.Dimensions()
	nw := config.Workers

	surrogate := newSurrogate(ni, no)
	accuracy := newAccuracy(no, config)
	tracker := newTracker(ni, config)

	progress := &Progress{}
	for {
		lindices := tracker.pull()

		progress.Active = uint(len(tracker.active))
		progress.Passive = tracker.nn - progress.Active
		if level := maxUint8(lindices); level > progress.Level {
			progress.Level = level
		}

		target.Monitor(progress)

		nn := uint(len(lindices)) / ni
		indices, counts := []uint64(nil), make([]uint, nn)
		for i := uint(0); i < nn; i++ {
			newIndices := self.grid.Index(lindices[i*ni : (i+1)*ni])
			indices = append(indices, newIndices...)
			counts[i] = uint(len(newIndices)) / ni
		}

		progress.Evaluations += uint(len(indices)) / ni
		if progress.Evaluations > config.MaxEvaluations {
			break
		}

		nodes := self.grid.Compute(indices)
		values := internal.Invoke(target.Compute, nodes, ni, no, nw)
		surpluses := internal.Subtract(values, internal.Approximate(self.basis,
			surrogate.Indices, surrogate.Surpluses, nodes, ni, no, nw))

		surrogate.push(indices, surpluses)
		accuracy.push(values, surpluses, counts)
		tracker.push(assess(target.Score, surpluses, counts, no))

		if accuracy.enough(tracker.active) {
			break
		}
	}

{'fraction_non_alphanumeric': 0.11912403247121012, 'fraction_numerical': 0.008306588635076459, 'mean_word_length': 3.803263825929284, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, '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': '2815716', 'n_tokens_mistral': 1840, 'n_tokens_neox': 1668, 'n_words': 504}