[Refactor] Rename/update MovingAverage to MathematicalSeries

We want the MovingAverage functionality to be more generic and useful
than just doing a moving average calculation. The new functionality
allows for the calculation of the standard deviation and supports a
generic type (so it can be used with integers and floats).

2 files changed, 200 insertions, 0 deletions

diff --git a/ms/ms.go b/ms/ms.go
new file mode 100644
index 0000000..8214025
--- /dev/null
+++ b/ms/ms.go
@@ -0,0 +1,117 @@
+/*
+ * 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 ms
+
+import (
+	"math"
+
+	"github.com/network-quality/goresponsiveness/saturating"
+	"github.com/network-quality/goresponsiveness/utilities"
+	"golang.org/x/exp/constraints"
+)
+
+type MathematicalSeries[T constraints.Float | constraints.Integer] struct {
+	elements_count int
+	elements       []T
+	index          int
+	divisor        *saturating.SaturatingInt
+}
+
+func NewMathematicalSeries[T constraints.Float | constraints.Integer](instants_count int) *MathematicalSeries[T] {
+	return &MathematicalSeries[T]{
+		elements:       make([]T, instants_count),
+		elements_count: instants_count,
+		divisor:        saturating.NewSaturatingInt(instants_count),
+	}
+}
+
+func (ma *MathematicalSeries[T]) AddElement(measurement T) {
+	ma.elements[ma.index] = measurement
+	ma.divisor.Add(1)
+	// Invariant: ma.index always points to the oldest measurement
+	ma.index = (ma.index + 1) % ma.elements_count
+}
+
+func (ma *MathematicalSeries[T]) CalculateAverage() float64 {
+	total := T(0)
+	for i := 0; i < ma.elements_count; i++ {
+		total += ma.elements[i]
+	}
+	return float64(total) / float64(ma.divisor.Value())
+}
+
+func (ma *MathematicalSeries[T]) AllSequentialIncreasesLessThan(limit float64) (_ bool, maximumSequentialIncrease float64) {
+
+	// If we have not yet accumulated a complete set of intervals,
+	// this is false.
+	if ma.divisor.Value() != ma.elements_count {
+		return false, 0
+	}
+
+	// Invariant: ma.index always points to the oldest (see AddMeasurement
+	// above)
+	oldestIndex := ma.index
+	previous := ma.elements[oldestIndex]
+	maximumSequentialIncrease = 0
+	for i := 1; i < ma.elements_count; i++ {
+		currentIndex := (oldestIndex + i) % ma.elements_count
+		current := ma.elements[currentIndex]
+		percentChange := utilities.SignedPercentDifference(current, previous)
+		previous = current
+		if percentChange > limit {
+			return false, percentChange
+		}
+	}
+	return true, maximumSequentialIncrease
+}
+
+func (ma *MathematicalSeries[T]) StandardDeviationLessThan(limit T) (bool, T) {
+
+	// If we have not yet accumulated a complete set of intervals,
+	// we are always false.
+	if ma.divisor.Value() != ma.elements_count {
+		return false, T(0)
+	}
+
+	// From https://www.mathsisfun.com/data/standard-deviation-calculator.html
+	// Yes, for real!
+
+	// Calculate the average of the numbers ...
+	average := ma.CalculateAverage()
+
+	// Calculate the square of each of the elements' differences from the mean.
+	differences_squared := make([]float64, ma.elements_count)
+	for index, value := range ma.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(ma.divisor.Value())
+
+	// Finally, the standard deviation is the square root
+	// of the variance.
+	sd := T(math.Sqrt(variance))
+
+	return T(sd) < limit, sd
+}
diff --git a/ms/ms_test.go b/ms/ms_test.go
new file mode 100644
index 0000000..0ba6da6
--- /dev/null
+++ b/ms/ms_test.go
@@ -0,0 +1,83 @@
+package ms
+
+import (
+	"testing"
+
+	"github.com/network-quality/goresponsiveness/utilities"
+)
+
+func Test_TooFewInstantsSequentialIncreasesLessThanAlwaysFalse(test *testing.T) {
+	series := NewMathematicalSeries[float64](500)
+	series.AddElement(0.0)
+	if islt, _ := series.AllSequentialIncreasesLessThan(6.0); islt {
+		test.Fatalf("Too few instants should always yield false when asking if sequential increases are less than a value.")
+	}
+}
+
+func Test_SequentialIncreasesAlwaysLessThan(test *testing.T) {
+	series := NewMathematicalSeries[float64](40)
+	previous := float64(1.0)
+	for _ = range utilities.Iota(1, 80) {
+		previous *= 1.059
+		series.AddElement(float64(previous))
+	}
+	if islt, maxSeqIncrease := series.AllSequentialIncreasesLessThan(6.0); !islt {
+		test.Fatalf("Sequential increases are not always less than 6.0 (%f).", maxSeqIncrease)
+	}
+}
+
+func Test_SequentialIncreasesAlwaysLessThanWithWraparound(test *testing.T) {
+	series := NewMathematicalSeries[float64](20)
+	previous := float64(1.0)
+	for range utilities.Iota(1, 20) {
+		previous *= 1.15
+		series.AddElement(float64(previous))
+	}
+
+	// All those measurements should be ejected by the following
+	// loop!
+	for range utilities.Iota(1, 20) {
+		previous *= 1.10
+		series.AddElement(float64(previous))
+	}
+
+	if islt, maxSeqIncrease := series.AllSequentialIncreasesLessThan(11.0); !islt {
+		test.Fatalf("Sequential increases are not always less than 11.0 in wraparound situation (%f v 11.0).", maxSeqIncrease)
+	}
+}
+
+func Test_SequentialIncreasesAlwaysLessThanWithWraparoundInverse(test *testing.T) {
+	series := NewMathematicalSeries[float64](20)
+	previous := float64(1.0)
+	for range utilities.Iota(1, 20) {
+		previous *= 1.15
+		series.AddElement(float64(previous))
+	}
+
+	// *Not* all those measurements should be ejected by the following
+	// loop!
+	for range utilities.Iota(1, 15) {
+		previous *= 1.10
+		series.AddElement(float64(previous))
+	}
+
+	if islt, maxSeqIncrease := series.AllSequentialIncreasesLessThan(11.0); islt {
+		test.Fatalf("Sequential increases are (unexpectedly) always less than 11.0 in wraparound situation: %f v 11.0.", maxSeqIncrease)
+	}
+}
+
+func Test_StandardDeviationLessThan_Float(test *testing.T) {
+	series := NewMathematicalSeries[float64](5)
+	// 5.7, 1.0, 8.6, 7.4, 2.2
+	series.AddElement(5.7)
+	series.AddElement(1.0)
+	series.AddElement(8.6)
+	series.AddElement(7.4)
+	series.AddElement(2.2)
+
+	if islt, sd := series.StandardDeviationLessThan(2.94); !islt {
+		test.Fatalf("Standard deviation max calculation failed: %v.", sd)
+	} else {
+		test.Logf("Standard deviation calculation result: %v", sd)
+	}
+}