// percentile with argument p \in (0,1), l is the length of given orderedObservations
// It does a simple apporximation of an ordered list of observations.
// Formula: sortedSlice[0.95*length(sortedSlice)]
348727
func percentile(orderedObservations []float64, l int, p float64) float64 {
	return orderedObservations[int(p*float64(l))]
}
1086417
func SamplePercentiles(values int64Slice, ps []float64) []float64 {
	scores := make([]float64, len(ps))
	size := len(values)
	if size > 0 {
		sort.Sort(values)
		for i, p := range ps {
			pos := p * float64(size+1)
			if pos < 1.0 {
				scores[i] = float64(values[0])
			} else if pos >= float64(size) {
				scores[i] = float64(values[size-1])
			} else {
				lower := float64(values[int(pos)-1])
				upper := float64(values[int(pos)])
				scores[i] = lower + (pos-math.Floor(pos))*(upper-lower)
			}
		}
	}
	return scores
}
1179069
func (td *MergingDigest) Quantile(quantile float64) float64 {
	if quantile < 0 || quantile > 1 {
		panic("quantile out of bounds")
	}
	td.mergeAllTemps()

	// add up the weights of centroids in ascending order until we reach a
	// centroid that pushes us over the quantile
	q := quantile * td.mainWeight
	weightSoFar := 0.0
	lowerBound := td.min
	for i, c := range td.mainCentroids {
		upperBound := td.centroidUpperBound(i)
		if q <= weightSoFar+c.Weight {
			// the target quantile is somewhere inside this centroid
			// we compute how much of this centroid's weight falls into the quantile
			proportion := (q - weightSoFar) / c.Weight
			// and interpolate what value that corresponds to inside a uniform
			// distribution
			return lowerBound + (proportion * (upperBound - lowerBound))
		}

		// the quantile is above this centroid, so sum the weight and carry on
		weightSoFar += c.Weight
		lowerBound = upperBound
	}

	// should never be reached unless empty, since the final comparison is
	// q <= td.mainWeight
	return math.NaN()
}
479621
func (s *SampleSnapshot) Percentile(p float64) float64 {
	return SamplePercentile(s.values, p)
}
278667
func Percentile(input Float64Data, percent float64) (percentile float64, err error) {

	if input.Len() == 0 {
		return math.NaN(), EmptyInputErr
	}

	if percent <= 0 || percent > 100 {
		return math.NaN(), BoundsErr
	}

	// Start by sorting a copy of the slice
	c := sortedCopy(input)

	// Multiply percent by length of input
	index := (percent / 100) * float64(len(c))

	// Check if the index is a whole number
	if index == float64(int64(index)) {

		// Convert float to int
		i := int(index)

		// Find the value at the index
		percentile = c[i-1]

	} else if index > 1 {

		// Convert float to int via truncation
		i := int(index)

		// Find the average of the index and following values
		percentile, _ = Mean(Float64Data{c[i-1], c[i]})

	} else {
		return math.NaN(), BoundsErr
	}

	return percentile, nil

}
761414
func (i *Index) SearchLiteral(term string, threshold int) []*Result {
	term = strings.ToLower(term)
	buf := []*Result{}
	for k, v := range i.lines {
		lk := strings.ToLower(k)
		lv := strings.ToLower(v)
		res := strings.Index(lv, term)
		if score := i.calcScore(res, lv); res != -1 && score < threshold {
			parts := strings.Split(lk, verSep) // Remove version, if it is there.
			buf = append(buf, &Result{Name: parts[0], Score: score, Chart: i.charts[k]})
		}
	}
	return buf
}
597933
func InStringSlice(sl []string, val string) bool {
	for _, s := range sl {
		if s == val {
			return true
		}
	}

	return false
}
188855
func EqLit(column, literal string) Cmp {
	return Cmp{
		op:     eq,
		column: column,
		value:  lit(literal),
	}
}
1013765
func ld(s, t string, ignoreCase bool) int {
	if ignoreCase {
		s = strings.ToLower(s)
		t = strings.ToLower(t)
	}
	d := make([][]int, len(s)+1)
	for i := range d {
		d[i] = make([]int, len(t)+1)
	}
	for i := range d {
		d[i][0] = i
	}
	for j := range d[0] {
		d[0][j] = j
	}
	for j := 1; j <= len(t); j++ {
		for i := 1; i <= len(s); i++ {
			if s[i-1] == t[j-1] {
				d[i][j] = d[i-1][j-1]
			} else {
				min := d[i-1][j]
				if d[i][j-1] < min {
					min = d[i][j-1]
				}
				if d[i-1][j-1] < min {
					min = d[i-1][j-1]
				}
				d[i][j] = min + 1
			}
		}

	}
	return d[len(s)][len(t)]
}
812758
func Int64Slice(val, sep string) ([]int64, error) {
	s := strings.Split(val, sep)
	values := make([]int64, len(s))
	for i, v := range s {
		value, err := Int64(v)
		if err != nil {
			return values, err
		}
		values[i] = value
	}
	return values, nil
}
997531
func (l LatencyMetrics) Quantile(nth float64) time.Duration {
	l.init()
	return time.Duration(l.estimator.Get(nth))
}
63231
func (a Aggregations) Percentiles(name string) (*AggregationPercentilesMetric, bool) {
	if raw, found := a[name]; found {
		agg := new(AggregationPercentilesMetric)
		if raw == nil {
			return agg, true
		}
		if err := json.Unmarshal(raw, agg); err == nil {
			return agg, true
		}
	}
	return nil, false
}
1051441
func (s Seq) Median() (median float64) {
	l := s.Len()
	if l == 0 {
		return
	}

	sorted := s.Sort()
	if l%2 == 0 {
		v0 := sorted.GetValue(l/2 - 1)
		v1 := sorted.GetValue(l/2 + 1)
		median = (v0 + v1) / 2
	} else {
		median = float64(sorted.GetValue(l << 1))
	}

	return
}
889314
func PercentileContIntervalFinal(db XODB, v0 pgtypes.Internal, v1 float64) (*time.Duration, error) {
	var err error

	// sql query
	const sqlstr = `SELECT pg_catalog.percentile_cont_interval_final($1, $2)`

	// run query
	var ret *time.Duration
	XOLog(sqlstr, v0, v1)
	err = db.QueryRow(sqlstr, v0, v1).Scan(&ret)
	if err != nil {
		return nil, err
	}

	return ret, nil
}
402782
func (s *UniformSample) Percentile(p float64) float64 {
	s.mutex.Lock()
	defer s.mutex.Unlock()
	return SamplePercentile(s.values, p)
}
1077675
func sortedCopy(input Float64Data) (copy Float64Data) {
	copy = copyslice(input)
	sort.Float64s(copy)
	return
}
78726
func SumIntSlice(slice []int) int {
	sum := 0
	for _, val := range slice {
		sum += val
	}
	return sum
}