[Feature] Major update: Track measurements that may be delayed

Among other major feature additions, this version of the client tracks
any measurements that may be long delayed and considers their presence
or absence as part of a stability measurement.

This version of the client also more closely tracks the spec. In
particular, it performs a sinle-sided trimmed mean rather than a
double-sided trimmed mean.

Signed-off-by: Will Hawkins <[email protected]>

3 files changed, 229 insertions, 38 deletions

diff --git a/utilities/math.go b/utilities/math.go
new file mode 100644
index 0000000..1ecca61
--- /dev/null
+++ b/utilities/math.go
@@ -0,0 +1,144 @@
+/*
+ * This file is part of Go Responsiveness.
+ *
+ * Go Responsiveness is free software: you can redistribute it and/or modify it under
+ * the terms of the GNU General Public License as published by the Free Software Foundation,
+ * either version 2 of the License, or (at your option) any later version.
+ * Go Responsiveness is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+ * PARTICULAR PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with Go Responsiveness. If not, see <https://www.gnu.org/licenses/>.
+ */
+
+package utilities
+
+import (
+	"math"
+	"sort"
+
+	"golang.org/x/exp/constraints"
+	"golang.org/x/exp/slices"
+)
+
+type Number interface {
+	constraints.Float | constraints.Integer
+}
+
+func CalculateAverage[T Number](elements []T) float64 {
+	total := T(0)
+	for i := 0; i < len(elements); i++ {
+		total += elements[i]
+	}
+	return float64(total) / float64(len(elements))
+}
+
+func CalculatePercentile[T Number](
+	elements []T,
+	p int,
+) (result T) {
+	result = T(0)
+	if p < 0 || p > 100 {
+		return
+	}
+
+	sort.Slice(elements, func(l int, r int) bool { return elements[l] < elements[r] })
+	pindex := int64((float64(p) / float64(100)) * float64(len(elements)))
+	result = elements[pindex]
+	return
+}
+
+func Max(x, y uint64) uint64 {
+	if x > y {
+		return x
+	}
+	return y
+}
+
+func SignedPercentDifference[T constraints.Float | constraints.Integer](
+	current T,
+	previous T,
+) (difference float64) {
+	fCurrent := float64(current)
+	fPrevious := float64(previous)
+	return ((fCurrent - fPrevious) / fPrevious) * 100.0
+}
+
+func AbsPercentDifference(
+	current float64,
+	previous float64,
+) (difference float64) {
+	return (math.Abs(current-previous) / (float64(current+previous) / 2.0)) * float64(
+		100,
+	)
+}
+
+func CalculateStandardDeviation[T constraints.Float | constraints.Integer](elements []T) float64 {
+	// From https://www.mathsisfun.com/data/standard-deviation-calculator.html
+	// Yes, for real!
+
+	// Calculate the average of the numbers ...
+	average := CalculateAverage(elements)
+
+	// Calculate the square of each of the elements' differences from the mean.
+	differences_squared := make([]float64, len(elements))
+	for index, value := range elements {
+		differences_squared[index] = math.Pow(float64(value-T(average)), 2)
+	}
+
+	// The variance is the average of the squared differences.
+	// So, we need to ...
+
+	// Accumulate all those squared differences.
+	sds := float64(0)
+	for _, dss := range differences_squared {
+		sds += dss
+	}
+
+	// And then divide that total by the number of elements
+	variance := sds / float64(len(elements))
+
+	// Finally, the standard deviation is the square root
+	// of the variance.
+	sd := float64(math.Sqrt(variance))
+	// sd := T(variance)
+
+	return sd
+}
+
+func AllSequentialIncreasesLessThan[T Number](elements []T, limit float64) (bool, float64) {
+	if len(elements) < 2 {
+		return false, 0.0
+	}
+
+	maximumSequentialIncrease := float64(0)
+	for i := 1; i < len(elements); i++ {
+		current := elements[i]
+		previous := elements[i-1]
+		percentChange := SignedPercentDifference(current, previous)
+		if percentChange > limit {
+			return false, percentChange
+		}
+		if percentChange > float64(maximumSequentialIncrease) {
+			maximumSequentialIncrease = percentChange
+		}
+	}
+	return true, maximumSequentialIncrease
+}
+
+// elements must already be sorted!
+func TrimBy[T Number](elements []T, trim int) []T {
+	numberToKeep := int(float32(len(elements)) * (float32(trim) / 100.0))
+
+	return elements[:numberToKeep]
+}
+
+func TrimmedMean[T Number](elements []T, trim int) (float64, []T) {
+	sortedElements := make([]T, len(elements))
+	copy(sortedElements, elements)
+	slices.Sort(sortedElements)
+
+	trimmedElements := TrimBy(sortedElements, trim)
+	return CalculateAverage(trimmedElements), trimmedElements
+}
diff --git a/utilities/utilities.go b/utilities/utilities.go
index ff04023..b976f77 100644
--- a/utilities/utilities.go
+++ b/utilities/utilities.go
@@ -21,13 +21,10 @@ import (
 	"math/rand"
 	"os"
 	"reflect"
-	"sort"
 	"strings"
 	"sync"
 	"sync/atomic"
 	"time"
-
-	"golang.org/x/exp/constraints"
 )
 
 // GitVersion is the Git revision hash
@@ -46,24 +43,6 @@ func IsInterfaceNil(ifc interface{}) bool {
 		(reflect.ValueOf(ifc).Kind() == reflect.Ptr && reflect.ValueOf(ifc).IsNil())
 }
 
-func SignedPercentDifference[T constraints.Float | constraints.Integer](
-	current T,
-	previous T,
-) (difference float64) {
-	fCurrent := float64(current)
-	fPrevious := float64(previous)
-	return ((fCurrent - fPrevious) / fPrevious) * 100.0
-}
-
-func AbsPercentDifference(
-	current float64,
-	previous float64,
-) (difference float64) {
-	return (math.Abs(current-previous) / (float64(current+previous) / 2.0)) * float64(
-		100,
-	)
-}
-
 func Conditional[T any](condition bool, t T, f T) T {
 	if condition {
 		return t
@@ -137,13 +116,6 @@ func RandBetween(max int) int {
 	return rand.New(rand.NewSource(int64(time.Now().Nanosecond()))).Int() % max
 }
 
-func Max(x, y uint64) uint64 {
-	if x > y {
-		return x
-	}
-	return y
-}
-
 func ChannelToSlice[S any](channel <-chan S) (slice []S) {
 	slice = make([]S, 0)
 	for element := range channel {
@@ -152,6 +124,26 @@ func ChannelToSlice[S any](channel <-chan S) (slice []S) {
 	return
 }
 
+func Reverse[T any](elements []T) []T {
+	result := make([]T, len(elements))
+	iterator := len(elements) - 1
+	for _, v := range elements {
+		result[iterator] = v
+		iterator--
+	}
+	return result
+}
+
+func Filter[S any](elements []S, filterer func(S) bool) []S {
+	result := make([]S, 0)
+	for _, s := range elements {
+		if filterer(s) {
+			result = append(result, s)
+		}
+	}
+	return result
+}
+
 func Fmap[S any, F any](elements []S, mapper func(S) F) []F {
 	result := make([]F, 0)
 	for _, s := range elements {
@@ -160,13 +152,6 @@ func Fmap[S any, F any](elements []S, mapper func(S) F) []F {
 	return result
 }
 
-func CalculatePercentile[S float32 | int32 | float64 | int64](elements []S, percentile int) S {
-	sort.Slice(elements, func(a, b int) bool { return elements[a] < elements[b] })
-	elementsCount := len(elements)
-	percentileIdx := elementsCount * (percentile / 100)
-	return elements[percentileIdx]
-}
-
 func OrTimeout(f func(), timeout time.Duration) {
 	completeChannel := func() chan interface{} {
 		completed := make(chan interface{})
@@ -227,9 +212,9 @@ func ContextSignaler(ctxt context.Context, st time.Duration, condition *func() b
 	}
 }
 
-type Pair[T any] struct {
-	First  T
-	Second T
+type Pair[T1, T2 any] struct {
+	First  T1
+	Second T2
 }
 
 func PerSecondToInterval(rate int64) time.Duration {
diff --git a/utilities/utilities_test.go b/utilities/utilities_test.go
index 9cd4ef0..7f3d83a 100644
--- a/utilities/utilities_test.go
+++ b/utilities/utilities_test.go
@@ -126,3 +126,65 @@ func TestPerSecondToInterval(t *testing.T) {
 		t.Fatalf("Something that happens twice per second should happen every 5000ns.")
 	}
 }
+
+func TestTrim(t *testing.T) {
+	elements := Iota(1, 101)
+
+	trimmedElements := TrimBy(elements, 75)
+
+	trimmedLength := len(trimmedElements)
+	trimmedLast := trimmedElements[trimmedLength-1]
+
+	if trimmedLength != 75 || trimmedLast != 75 {
+		t.Fatalf("When trimming, the length should be 75 but it is %d and/or the last element should be 75 but it is %d", trimmedLength, trimmedLast)
+	}
+}
+
+func TestTrim2(t *testing.T) {
+	elements := Iota(1, 11)
+
+	trimmedElements := TrimBy(elements, 75)
+
+	trimmedLength := len(trimmedElements)
+	trimmedLast := trimmedElements[trimmedLength-1]
+
+	if trimmedLength != 7 || trimmedLast != 7 {
+		t.Fatalf("When trimming, the length should be 7 but it is %d and/or the last element should be 7 but it is %d", trimmedLength, trimmedLast)
+	}
+}
+
+func TestTrim3(t *testing.T) {
+	elements := Iota(1, 6)
+
+	trimmedElements := TrimBy(elements, 101)
+
+	trimmedLength := len(trimmedElements)
+	trimmedLast := trimmedElements[trimmedLength-1]
+
+	if trimmedLength != 5 || trimmedLast != 5 {
+		t.Fatalf("When trimming, the length should be 5 but it is %d and/or the last element should be 5 but it is %d", trimmedLength, trimmedLast)
+	}
+}
+
+func TestTrim4(t *testing.T) {
+	elements := Iota(1, 11)
+
+	trimmedElements := TrimBy(elements, 81)
+
+	trimmedLength := len(trimmedElements)
+	trimmedLast := trimmedElements[trimmedLength-1]
+
+	if trimmedLength != 8 || trimmedLast != 8 {
+		t.Fatalf("When trimming, the length should be 8 but it is %d and/or the last element should be 8 but it is %d", trimmedLength, trimmedLast)
+	}
+}
+
+func TestTrimmedMean(t *testing.T) {
+	expected := 2.5
+	elements := []int{5, 4, 3, 2, 1}
+
+	result, elements := TrimmedMean(elements, 80)
+	if result != expected || len(elements) != 4 || elements[len(elements)-1] != 4 {
+		t.Fatalf("The trimmed mean result %v does not match the expected value %v", result, expected)
+	}
+}