Merge "Add quantileFunction method to IntHistogram"

2 files changed, 82 insertions, 0 deletions

diff --git a/service/java/com/android/server/wifi/util/IntHistogram.java b/service/java/com/android/server/wifi/util/IntHistogram.java
index 83a491355..8e8700a8c 100644
--- a/service/java/com/android/server/wifi/util/IntHistogram.java
+++ b/service/java/com/android/server/wifi/util/IntHistogram.java
@@ -142,6 +142,47 @@ public class IntHistogram implements Iterable<IntHistogram.Bucket> {
         mBuckets.put(bucketKey, curBucketValue + count);
     }
 
+
+    /**
+     * Computes the inverse of the cumulative probability distribution for the histogram.
+     *
+     * This is the value v such that the probability of a randomly selected datum being
+     * less than or equal to v is the provided probability. The answer is constrained to
+     * lie in the interval [minimum..maximum].
+     */
+    public double quantileFunction(double probability, int minimum, int maximum) {
+        if (minimum > maximum) {
+            throw new IllegalArgumentException("bad bounds");
+        }
+        if (probability < 0.0 || probability > 1.0) {
+            throw new IllegalArgumentException("bad roll, try again");
+        }
+        long sum = 0;
+        for (Bucket bucket : this) {
+            sum += bucket.count;
+        }
+        final double target = sum * probability;
+        double partialSum = 0.0;
+        Bucket hitBucket = null;
+        for (Bucket bucket : this) {
+            if (partialSum + bucket.count >= target) {
+                hitBucket = bucket;
+                break;
+            }
+            partialSum += bucket.count;
+        }
+        if (hitBucket == null) {
+            // No data at all; assume uniform between given limits
+            return minimum + probability * (maximum - minimum);
+        }
+        double highValue = Math.min(hitBucket.end, maximum);
+        double value = Math.max(hitBucket.start, minimum);
+        if (value >= highValue - 1.0 || hitBucket.count == 0) return Math.min(value, highValue);
+        // interpolate to estimate the value
+        value += (highValue - value) * (target - partialSum) / hitBucket.count;
+        return Math.min(Math.max(value, minimum), maximum);
+    }
+
     /**
      * Given a value, returns the key of the bucket where it should fall into.
      */
diff --git a/tests/wifitests/src/com/android/server/wifi/util/IntHistogramTest.java b/tests/wifitests/src/com/android/server/wifi/util/IntHistogramTest.java
index 9e291af16..193f011a1 100644
--- a/tests/wifitests/src/com/android/server/wifi/util/IntHistogramTest.java
+++ b/tests/wifitests/src/com/android/server/wifi/util/IntHistogramTest.java
@@ -20,6 +20,7 @@ import static com.android.server.wifi.WifiMetricsTestUtil.assertHistogramBuckets
 import static com.android.server.wifi.WifiMetricsTestUtil.buildHistogramBucketInt32;
 
 import static org.hamcrest.core.IsEqual.equalTo;
+import static org.junit.Assert.assertEquals;
 
 import androidx.test.filters.SmallTest;
 
@@ -263,4 +264,44 @@ public class IntHistogramTest extends WifiBaseTest {
     public void testNonMonotonicBucketBoundaries() {
         new IntHistogram(new int[] {1, 2, 3, 3});
     }
+
+    @Test
+    public void testEmptyQuantile() {
+        mHistogram = new IntHistogram(TEST_BUCKET_BOUNDARIES);
+        double q = mHistogram.quantileFunction(0.2, 0, 50);
+        assertEquals(q, 10.0, 0.01);
+    }
+
+    @Test
+    public void testQuantileUniformDistribution() {
+        mHistogram = new IntHistogram(TEST_BUCKET_BOUNDARIES);
+        for (int i = 0; i < 111; i++) {
+            mHistogram.increment(i);
+        }
+        String diagnose = mHistogram.toString();
+        double q;
+
+        for (double i = 0.0; i <= 111.0; i++) {
+            q = mHistogram.quantileFunction(i / 111.0, 0,  111);
+            assertEquals(diagnose, i, q, 0.01);
+        }
+
+        q = mHistogram.quantileFunction(.8, 0, 42);
+        assertEquals(42.0, q, 0.01);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void backwardsBoundsShouldFail() {
+        new IntHistogram(TEST_BUCKET_BOUNDARIES).quantileFunction(0.5, 80, 40);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void negativeProbablilityShouldFail() {
+        new IntHistogram(TEST_BUCKET_BOUNDARIES).quantileFunction(-0.1, 0, 50);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void largerThanUnityProbablilityShouldFail() {
+        new IntHistogram(TEST_BUCKET_BOUNDARIES).quantileFunction(1.1, 0, 50);
+    }
 }