func VarianceValue(f64s []float64) float64 {
	var squareSum float64
	var elts int
	mean := AvgValue(f64s)
	if math.IsNaN(mean) {
		return mean
	}
	for _, v := range f64s {
		if math.IsNaN(v) {
			continue
		}
		elts++
		squareSum += (mean - v) * (mean - v)
	}
	return squareSum / float64(elts)
}
VarianceValue gets variances of list of values
package helper
import (
	"math"
	"strconv"
	"unicode"
	"fmt"
	"github.com/go-graphite/carbonapi/expr/interfaces"
	"github.com/go-graphite/carbonapi/expr/types"
	"github.com/go-graphite/carbonapi/pkg/parser"
	"gonum.org/v1/gonum/mat"
	"strings"
	"unicode/utf8"
	"github.com/wangjohn/quickselect"
	"regexp"
)
var evaluator interfaces.Evaluator
var Backref = regexp.MustCompile(`\\(\d+)`)
type ErrUnknownFunction string
func (e ErrUnknownFunction) Error() string {
	return fmt.Sprintf("unknown function in evalExpr: %q", string(e))
}
func SetEvaluator(e interfaces.Evaluator) {
	evaluator = e
}
func GetSeriesArg(arg parser.Expr, from, until int64, values map[parser.MetricRequest][]*types.MetricData) ([]*types.MetricData, error) {
	if !arg.IsName() && !arg.IsFunc() {
		return nil, parser.ErrMissingTimeseries
	}
	a, err := evaluator.EvalExpr(arg, from, until, values)
	if err != nil {
		return nil, err
	}
	return a, nil
}
func RemoveEmptySeriesFromName(args []*types.MetricData) string {
	var argNames []string
	for _, arg := range args {
		argNames = append(argNames, arg.Name)
	}
	return strings.Join(argNames, ",")
}
func GetSeriesArgs(e []parser.Expr, from, until int64, values map[parser.MetricRequest][]*types.MetricData) ([]*types.MetricData, error) {
	var args []*types.MetricData
	for _, arg := range e {
		a, err := GetSeriesArg(arg, from, until, values)
		if err != nil && err != parser.ErrSeriesDoesNotExist {
			return nil, err
		}
		args = append(args, a...)
	}
	if len(args) == 0 {
		return nil, parser.ErrSeriesDoesNotExist
	}
	return args, nil
}
func GetSeriesArgsAndRemoveNonExisting(e parser.Expr, from, until int64, values map[parser.MetricRequest][]*types.MetricData) ([]*types.MetricData, error) {
	args, err := GetSeriesArgs(e.Args(), from, until, values)
	if err != nil {
		return nil, err
	}
	if len(args) < len(e.Args()) {
		e.SetRawArgs(RemoveEmptySeriesFromName(args))
	}
	return args, nil
}
type seriesFunc func(*types.MetricData, *types.MetricData) *types.MetricData
func ForEachSeriesDo(e parser.Expr, from, until int64, values map[parser.MetricRequest][]*types.MetricData, function seriesFunc) ([]*types.MetricData, error) {
	arg, err := GetSeriesArg(e.Args()[0], from, until, values)
	if err != nil {
		return nil, parser.ErrMissingTimeseries
	}
	var results []*types.MetricData
	for _, a := range arg {
		r := *a
		r.Name = fmt.Sprintf("%s(%s)", e.Target(), a.Name)
		r.Values = make([]float64, len(a.Values))
		results = append(results, function(a, &r))
	}
	return results, nil
}
func AlignSeries(args []*types.MetricData) []*types.MetricData {
	minStart := args[0].StartTime
	maxStop := args[0].StopTime
	maxVals := 0
	minStepTime := args[0].StepTime
	for j := 0; j < 2; j++ {
		if ExtrapolatePoints {
			for _, arg := range args {
				if arg.StepTime < minStepTime {
					minStepTime = arg.StepTime
				}
				if arg.StepTime > minStepTime {
					valsCnt := int(math.Ceil(float64(arg.StopTime-arg.StartTime) / float64(minStepTime)))
					newVals := make([]float64, valsCnt)
					ts := arg.StartTime
					nextTs := arg.StartTime + arg.StepTime
					i := 0
					j := 0
					pointsPerInterval := float64(ts-nextTs) / float64(minStepTime)
					v := arg.Values[0]
					dv := (arg.Values[0] - arg.Values[1]) / pointsPerInterval
					for ts < arg.StopTime {
						newVals[i] = v
						v += dv
						if ts > nextTs {
							j++
							nextTs += arg.StepTime
							v = arg.Values[j]
							dv = (arg.Values[j-1] - v) / pointsPerInterval
						}
						ts += minStepTime
						i++
					}
					arg.Values = newVals
					arg.StepTime = minStepTime
				}
			}
		}
		for _, arg := range args {
			if len(arg.Values) > maxVals {
				maxVals = len(arg.Values)
			}
			if arg.StartTime < minStart {
				minStart = arg.StartTime
			}
			if minStart < arg.StartTime {
				valCnt := (arg.StartTime - minStart) / arg.StepTime
				newVals := make([]float64, valCnt)
				newVals = append(newVals, arg.Values...)
				arg.Values = newVals
				arg.StartTime = minStart
			}
			if arg.StopTime > maxStop {
				maxStop = arg.StopTime
			}
			if maxStop > arg.StopTime {
				valCnt := (maxStop - arg.StopTime) / arg.StepTime
				newVals := make([]float64, valCnt)
				arg.Values = append(arg.Values, newVals...)
				arg.StopTime = maxStop
			}
		}
	}
	return args
}
type AggregateFunc func([]float64) float64
func AggregateSeries(e parser.Expr, args []*types.MetricData, function AggregateFunc) ([]*types.MetricData, error) {
	args = AlignSeries(args)
	length := len(args[0].Values)
	r := *args[0]
	r.Name = fmt.Sprintf("%s(%s)", e.Target(), e.RawArgs())
	r.Values = make([]float64, length)
	for i := range args[0].Values {
		var values []float64
		for _, arg := range args {
			if !math.IsNaN(arg.Values[i]) {
				values = append(values, arg.Values[i])
			}
		}
		r.Values[i] = math.NaN()
		if len(values) > 0 {
			r.Values[i] = function(values)
		}
	}
	return []*types.MetricData{&r}, nil
}
func SummarizeValues(f string, values []float64) float64 {
	rv := 0.0
	if len(values) == 0 {
		return math.NaN()
	}
	switch f {
	case "sum", "total":
		for _, av := range values {
			rv += av
		}
	case "avg":
		for _, av := range values {
			rv += av
		}
		rv /= float64(len(values))
	case "max":
		rv = math.Inf(-1)
		for _, av := range values {
			if av > rv {
				rv = av
			}
		}
	case "min":
		rv = math.Inf(1)
		for _, av := range values {
			if av < rv {
				rv = av
			}
		}
	case "last":
		if len(values) > 0 {
			rv = values[len(values)-1]
		}
	default:
		f = strings.Split(f, "p")[1]
		percent, err := strconv.ParseFloat(f, 64)
		if err == nil {
			rv = Percentile(values, percent, true)
		}
	}
	return rv
}
func ExtractMetric(s string) string {
	var (
		start, braces, i, w int
		r                   rune
	)
FOR:
	for braces, i, w = 0, 0, 0; i < len(s); i += w {
		w = 1
		if parser.IsNameChar(s[i]) {
			continue
		}
		switch s[i] {
		case '{':
			braces++
		case '}':
			if braces == 0 {
				break FOR
			}
			braces--
		case ',':
			if braces == 0 {
				break FOR
			}
		case ')':
			break FOR
		default:
			r, w = utf8.DecodeRuneInString(s[i:])
			if unicode.In(r, parser.RangeTables...) {
				continue
			}
			start = i + 1
		}
	}
	return s[start:i]
}
func Contains(a []int, i int) bool {
	for _, aa := range a {
		if aa == i {
			return true
		}
	}
	return false
}
func Percentile(data []float64, percent float64, interpolate bool) float64 {
	if len(data) == 0 || percent < 0 || percent > 100 {
		return math.NaN()
	}
	if len(data) == 1 {
		return data[0]
	}
	k := (float64(len(data)-1) * percent) / 100
	length := int(math.Ceil(k)) + 1
	quickselect.Float64QuickSelect(data, length)
	top, secondTop := math.Inf(-1), math.Inf(-1)
	for _, val := range data[0:length] {
		if val > top {
			secondTop = top
			top = val
		} else if val > secondTop {
			secondTop = val
		}
	}
	remainder := k - float64(int(k))
	if remainder == 0 || !interpolate {
		return top
	}
	return (top * remainder) + (secondTop * (1 - remainder))
}
func MaxValue(f64s []float64) float64 {
	m := math.Inf(-1)
	for _, v := range f64s {
		if math.IsNaN(v) {
			continue
		}
		if v > m {
			m = v
		}
	}
	return m
}
func MinValue(f64s []float64) float64 {
	m := math.Inf(1)
	for _, v := range f64s {
		if math.IsNaN(v) {
			continue
		}
		if v < m {
			m = v
		}
	}
	return m
}
func AvgValue(f64s []float64) float64 {
	var t float64
	var elts int
	for _, v := range f64s {
		if math.IsNaN(v) {
			continue
		}
		elts++
		t += v
	}
	return t / float64(elts)
}
func CurrentValue(f64s []float64) float64 {
	for i := len(f64s) - 1; i >= 0; i-- {
		if !math.IsNaN(f64s[i]) {
			return f64s[i]
		}
	}
	return math.NaN()
}