Removing TimeSparseArray

The only added value in this subclass comes from the added methods to
binary search on its keys. Pulling these methods up to the base class
LongSparseArray so they can be useful for all its instances.

Renamed variables and methods to be more generic and replaced the
handwritten binary search with an equivalent call to
Arrays.binarySearch to reduce maintenance overhead.

All occurrences of TimeSparseArray have been replaced with
LongSparseArray. No behavior change is expected.

Test: Builds, boots.
Test: atest FrameworksCoreTests:LongSparseArrayTest

Bug: 282264041
Change-Id: I6e87560ad5afe85118c9ffaac9ea8a506a181af0

10 files changed, 143 insertions, 243 deletions

diff --git a/core/java/android/util/LongSparseArray.java b/core/java/android/util/LongSparseArray.java
index eefb15604bbc..2f14b2537cf9 100644
--- a/core/java/android/util/LongSparseArray.java
+++ b/core/java/android/util/LongSparseArray.java
@@ -209,6 +209,39 @@ public class LongSparseArray<E> implements Cloneable {
     }
 
     /**
+     * Returns the index of the first element whose key is greater than or equal to the given key.
+     *
+     * @param key The key for which to search the array.
+     * @return The smallest {@code index} for which {@code (keyAt(index) >= key)} is
+     * {@code true}, or {@link #size() size} if no such {@code index} exists.
+     * @hide
+     */
+    public int firstIndexOnOrAfter(long key) {
+        if (mGarbage) {
+            gc();
+        }
+        final int index = Arrays.binarySearch(mKeys, 0, size(), key);
+        return (index >= 0) ? index : -index - 1;
+    }
+
+    /**
+     * Returns the index of the last element whose key is less than or equal to the given key.
+     *
+     * @param key The key for which to search the array.
+     * @return The largest {@code index} for which {@code (keyAt(index) <= key)} is
+     * {@code true}, or {@code -1} if no such {@code index} exists.
+     * @hide
+     */
+    public int lastIndexOnOrBefore(long key) {
+        final int index = firstIndexOnOrAfter(key);
+
+        if (index < size() && keyAt(index) == key) {
+            return index;
+        }
+        return index - 1;
+    }
+
+    /**
      * Adds a mapping from the specified key to the specified value,
      * replacing the previous mapping from the specified key if there
      * was one.
diff --git a/core/java/android/util/TimeSparseArray.java b/core/java/android/util/TimeSparseArray.java
deleted file mode 100644
index 1f49fa24a64a..000000000000
--- a/core/java/android/util/TimeSparseArray.java
+++ /dev/null
@@ -1,99 +0,0 @@
-/**
- * Copyright (C) 2014 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License"); you may not
- * use this file except in compliance with the License. You may obtain a copy
- * of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
- * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
- * License for the specific language governing permissions and limitations
- * under the License.
- */
-
-package android.util;
-
-import java.util.Objects;
-
-/**
- * An array that indexes by a long timestamp, representing milliseconds since the epoch.
- * @param <E> The type of values this container maps to a timestamp.
- *
- * {@hide}
- */
-public class TimeSparseArray<E> extends LongSparseArray<E> {
-    private static final String TAG = TimeSparseArray.class.getSimpleName();
-
-    private boolean mWtfReported;
-
-    /**
-     * Finds the index of the first element whose timestamp is greater or equal to
-     * the given time.
-     *
-     * @param time The timestamp for which to search the array.
-     * @return The smallest {@code index} for which {@code (keyAt(index) >= timeStamp)} is
-     * {@code true}, or {@link #size() size} if no such {@code index} exists.
-     */
-    public int closestIndexOnOrAfter(long time) {
-        final int size = size();
-        int result = size;
-        int lo = 0;
-        int hi = size - 1;
-        while (lo <= hi) {
-            final int mid = lo + ((hi - lo) / 2);
-            final long key = keyAt(mid);
-
-            if (time > key) {
-                lo = mid + 1;
-            } else if (time < key) {
-                hi = mid - 1;
-                result = mid;
-            } else {
-                return mid;
-            }
-        }
-        return result;
-    }
-
-    /**
-     * {@inheritDoc}
-     *
-     * <p> This container can store only one value for each timestamp. And so ideally, the caller
-     * should ensure that there are no collisions. Reporting a {@link Slog#wtf(String, String)}
-     * if that happens, as that will lead to the previous value being overwritten.
-     */
-    @Override
-    public void put(long key, E value) {
-        final int index = indexOfKey(key);
-        if (index >= 0) {
-            final E curValue = valueAt(index);
-            if (Objects.equals(curValue, value)) {
-                Log.w(TAG, "Overwriting value at " + key + " by equal value " + value);
-            } else if (!mWtfReported) {
-                Slog.wtf(TAG, "Overwriting value " + curValue + " by " + value + " at " + key);
-                mWtfReported = true;
-            }
-        }
-        super.put(key, value);
-    }
-
-    /**
-     * Finds the index of the first element whose timestamp is less than or equal to
-     * the given time.
-     *
-     * @param time The timestamp for which to search the array.
-     * @return The largest {@code index} for which {@code (keyAt(index) <= timeStamp)} is
-     * {@code true}, or -1 if no such {@code index} exists.
-     */
-    public int closestIndexOnOrBefore(long time) {
-        final int index = closestIndexOnOrAfter(time);
-
-        if (index < size() && keyAt(index) == time) {
-            return index;
-        }
-        return index - 1;
-    }
-}
diff --git a/core/tests/coretests/src/android/util/LongSparseArrayTest.java b/core/tests/coretests/src/android/util/LongSparseArrayTest.java
index bf3f0f50f4bf..247fe37b5e1f 100644
--- a/core/tests/coretests/src/android/util/LongSparseArrayTest.java
+++ b/core/tests/coretests/src/android/util/LongSparseArrayTest.java
@@ -51,4 +51,73 @@ public class LongSparseArrayTest {
                     .isFalse();
         }
     }
+
+    @Test
+    public void firstIndexOnOrAfter() {
+        final LongSparseArray<Object> longSparseArray = new LongSparseArray<>();
+
+        // Values don't matter for this test.
+        longSparseArray.put(51, new Object());
+        longSparseArray.put(10, new Object());
+        longSparseArray.put(59, new Object());
+
+        assertThat(longSparseArray.size()).isEqualTo(3);
+
+        // Testing any number arbitrarily smaller than 10.
+        assertThat(longSparseArray.firstIndexOnOrAfter(-141213)).isEqualTo(0);
+        for (long time = -43; time <= 10; time++) {
+            assertThat(longSparseArray.firstIndexOnOrAfter(time)).isEqualTo(0);
+        }
+
+        for (long time = 11; time <= 51; time++) {
+            assertThat(longSparseArray.firstIndexOnOrAfter(time)).isEqualTo(1);
+        }
+
+        for (long time = 52; time <= 59; time++) {
+            assertThat(longSparseArray.firstIndexOnOrAfter(time)).isEqualTo(2);
+        }
+
+        for (long time = 60; time <= 102; time++) {
+            assertThat(longSparseArray.firstIndexOnOrAfter(time)).isEqualTo(3);
+        }
+        // Testing any number arbitrarily larger than 59.
+        assertThat(longSparseArray.firstIndexOnOrAfter(15332)).isEqualTo(3);
+    }
+
+    @Test
+    public void lastIndexOnOrBefore() {
+        final LongSparseArray<Object> longSparseArray = new LongSparseArray<>();
+
+        // Values don't matter for this test.
+        longSparseArray.put(21, new Object());
+        longSparseArray.put(4, new Object());
+        longSparseArray.put(91, new Object());
+        longSparseArray.put(39, new Object());
+
+        assertThat(longSparseArray.size()).isEqualTo(4);
+
+        // Testing any number arbitrarily smaller than 4.
+        assertThat(longSparseArray.lastIndexOnOrBefore(-1478133)).isEqualTo(-1);
+        for (long time = -42; time < 4; time++) {
+            assertThat(longSparseArray.lastIndexOnOrBefore(time)).isEqualTo(-1);
+        }
+
+        for (long time = 4; time < 21; time++) {
+            assertThat(longSparseArray.lastIndexOnOrBefore(time)).isEqualTo(0);
+        }
+
+        for (long time = 21; time < 39; time++) {
+            assertThat(longSparseArray.lastIndexOnOrBefore(time)).isEqualTo(1);
+        }
+
+        for (long time = 39; time < 91; time++) {
+            assertThat(longSparseArray.lastIndexOnOrBefore(time)).isEqualTo(2);
+        }
+
+        for (long time = 91; time < 109; time++) {
+            assertThat(longSparseArray.lastIndexOnOrBefore(time)).isEqualTo(3);
+        }
+        // Testing any number arbitrarily larger than 91.
+        assertThat(longSparseArray.lastIndexOnOrBefore(1980732)).isEqualTo(3);
+    }
 }
diff --git a/core/tests/coretests/src/android/util/TimeSparseArrayTest.java b/core/tests/coretests/src/android/util/TimeSparseArrayTest.java
deleted file mode 100644
index c8e2364c48cd..000000000000
--- a/core/tests/coretests/src/android/util/TimeSparseArrayTest.java
+++ /dev/null
@@ -1,103 +0,0 @@
-/*
- * Copyright (C) 2020 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package android.util;
-
-import static com.google.common.truth.Truth.assertThat;
-
-import androidx.test.ext.junit.runners.AndroidJUnit4;
-import androidx.test.filters.SmallTest;
-
-import org.junit.Test;
-import org.junit.runner.RunWith;
-
-/**
- * Tests for {@link TimeSparseArray}.
- * This class only tests subclass specific functionality. Tests for the super class
- * {@link LongSparseArray} should be covered under {@link LongSparseArrayTest}.
- */
-@SmallTest
-@RunWith(AndroidJUnit4.class)
-public class TimeSparseArrayTest {
-
-    @Test
-    public void closestIndexOnOrAfter() {
-        final TimeSparseArray<Object> timeSparseArray = new TimeSparseArray<>();
-
-        // Values don't matter for this test.
-        timeSparseArray.put(51, new Object());
-        timeSparseArray.put(10, new Object());
-        timeSparseArray.put(59, new Object());
-
-        assertThat(timeSparseArray.size()).isEqualTo(3);
-
-        // Testing any number arbitrarily smaller than 10.
-        assertThat(timeSparseArray.closestIndexOnOrAfter(-141213)).isEqualTo(0);
-        for (long time = -43; time <= 10; time++) {
-            assertThat(timeSparseArray.closestIndexOnOrAfter(time)).isEqualTo(0);
-        }
-
-        for (long time = 11; time <= 51; time++) {
-            assertThat(timeSparseArray.closestIndexOnOrAfter(time)).isEqualTo(1);
-        }
-
-        for (long time = 52; time <= 59; time++) {
-            assertThat(timeSparseArray.closestIndexOnOrAfter(time)).isEqualTo(2);
-        }
-
-        for (long time = 60; time <= 102; time++) {
-            assertThat(timeSparseArray.closestIndexOnOrAfter(time)).isEqualTo(3);
-        }
-        // Testing any number arbitrarily larger than 59.
-        assertThat(timeSparseArray.closestIndexOnOrAfter(15332)).isEqualTo(3);
-    }
-
-    @Test
-    public void closestIndexOnOrBefore() {
-        final TimeSparseArray<Object> timeSparseArray = new TimeSparseArray<>();
-
-        // Values don't matter for this test.
-        timeSparseArray.put(21, new Object());
-        timeSparseArray.put(4, new Object());
-        timeSparseArray.put(91, new Object());
-        timeSparseArray.put(39, new Object());
-
-        assertThat(timeSparseArray.size()).isEqualTo(4);
-
-        // Testing any number arbitrarily smaller than 4.
-        assertThat(timeSparseArray.closestIndexOnOrBefore(-1478133)).isEqualTo(-1);
-        for (long time = -42; time < 4; time++) {
-            assertThat(timeSparseArray.closestIndexOnOrBefore(time)).isEqualTo(-1);
-        }
-
-        for (long time = 4; time < 21; time++) {
-            assertThat(timeSparseArray.closestIndexOnOrBefore(time)).isEqualTo(0);
-        }
-
-        for (long time = 21; time < 39; time++) {
-            assertThat(timeSparseArray.closestIndexOnOrBefore(time)).isEqualTo(1);
-        }
-
-        for (long time = 39; time < 91; time++) {
-            assertThat(timeSparseArray.closestIndexOnOrBefore(time)).isEqualTo(2);
-        }
-
-        for (long time = 91; time < 109; time++) {
-            assertThat(timeSparseArray.closestIndexOnOrBefore(time)).isEqualTo(3);
-        }
-        // Testing any number arbitrarily larger than 91.
-        assertThat(timeSparseArray.closestIndexOnOrBefore(1980732)).isEqualTo(3);
-    }
-}
diff --git a/services/core/java/com/android/server/power/stats/wakeups/CpuWakeupStats.java b/services/core/java/com/android/server/power/stats/wakeups/CpuWakeupStats.java
index 712a6964e82d..f047f564538d 100644
--- a/services/core/java/com/android/server/power/stats/wakeups/CpuWakeupStats.java
+++ b/services/core/java/com/android/server/power/stats/wakeups/CpuWakeupStats.java
@@ -32,12 +32,12 @@ import android.os.Trace;
 import android.os.UserHandle;
 import android.provider.DeviceConfig;
 import android.util.IndentingPrintWriter;
+import android.util.LongSparseArray;
 import android.util.Slog;
 import android.util.SparseArray;
 import android.util.SparseBooleanArray;
 import android.util.SparseIntArray;
 import android.util.SparseLongArray;
-import android.util.TimeSparseArray;
 import android.util.TimeUtils;
 
 import com.android.internal.annotations.VisibleForTesting;
@@ -74,12 +74,12 @@ public class CpuWakeupStats {
     private final WakingActivityHistory mRecentWakingActivity;
 
     @VisibleForTesting
-    final TimeSparseArray<Wakeup> mWakeupEvents = new TimeSparseArray<>();
+    final LongSparseArray<Wakeup> mWakeupEvents = new LongSparseArray<>();
 
     /* Maps timestamp -> {subsystem  -> {uid -> procState}} */
     @VisibleForTesting
-    final TimeSparseArray<SparseArray<SparseIntArray>> mWakeupAttribution =
-            new TimeSparseArray<>();
+    final LongSparseArray<SparseArray<SparseIntArray>> mWakeupAttribution =
+            new LongSparseArray<>();
 
     final SparseIntArray mUidProcStates = new SparseIntArray();
     private final SparseIntArray mReusableUidProcStates = new SparseIntArray(4);
@@ -218,11 +218,11 @@ public class CpuWakeupStats {
         // the last wakeup and its attribution (if computed) is always stored, even if that wakeup
         // had occurred before retentionDuration.
         final long retentionDuration = mConfig.WAKEUP_STATS_RETENTION_MS;
-        int lastIdx = mWakeupEvents.closestIndexOnOrBefore(elapsedRealtime - retentionDuration);
+        int lastIdx = mWakeupEvents.lastIndexOnOrBefore(elapsedRealtime - retentionDuration);
         for (int i = lastIdx; i >= 0; i--) {
             mWakeupEvents.removeAt(i);
         }
-        lastIdx = mWakeupAttribution.closestIndexOnOrBefore(elapsedRealtime - retentionDuration);
+        lastIdx = mWakeupAttribution.lastIndexOnOrBefore(elapsedRealtime - retentionDuration);
         for (int i = lastIdx; i >= 0; i--) {
             mWakeupAttribution.removeAt(i);
         }
@@ -273,9 +273,9 @@ public class CpuWakeupStats {
             SparseIntArray uidProcStates) {
         final long matchingWindowMillis = mConfig.WAKEUP_MATCHING_WINDOW_MS;
 
-        final int startIdx = mWakeupEvents.closestIndexOnOrAfter(
+        final int startIdx = mWakeupEvents.firstIndexOnOrAfter(
                 activityElapsed - matchingWindowMillis);
-        final int endIdx = mWakeupEvents.closestIndexOnOrBefore(
+        final int endIdx = mWakeupEvents.lastIndexOnOrBefore(
                 activityElapsed + matchingWindowMillis);
 
         for (int wakeupIdx = startIdx; wakeupIdx <= endIdx; wakeupIdx++) {
@@ -404,7 +404,7 @@ public class CpuWakeupStats {
     static final class WakingActivityHistory {
         private LongSupplier mRetentionSupplier;
         @VisibleForTesting
-        final SparseArray<TimeSparseArray<SparseIntArray>> mWakingActivity = new SparseArray<>();
+        final SparseArray<LongSparseArray<SparseIntArray>> mWakingActivity = new SparseArray<>();
 
         WakingActivityHistory(LongSupplier retentionSupplier) {
             mRetentionSupplier = retentionSupplier;
@@ -414,9 +414,9 @@ public class CpuWakeupStats {
             if (uidProcStates == null) {
                 return;
             }
-            TimeSparseArray<SparseIntArray> wakingActivity = mWakingActivity.get(subsystem);
+            LongSparseArray<SparseIntArray> wakingActivity = mWakingActivity.get(subsystem);
             if (wakingActivity == null) {
-                wakingActivity = new TimeSparseArray<>();
+                wakingActivity = new LongSparseArray<>();
                 mWakingActivity.put(subsystem, wakingActivity);
             }
             final SparseIntArray uidsToBlame = wakingActivity.get(elapsedRealtime);
@@ -435,7 +435,7 @@ public class CpuWakeupStats {
             // Limit activity history per subsystem to the last retention period as supplied by
             // mRetentionSupplier. Note that the last activity is always present, even if it
             // occurred before the retention period.
-            final int endIdx = wakingActivity.closestIndexOnOrBefore(
+            final int endIdx = wakingActivity.lastIndexOnOrBefore(
                     elapsedRealtime - mRetentionSupplier.getAsLong());
             for (int i = endIdx; i >= 0; i--) {
                 wakingActivity.removeAt(i);
@@ -445,11 +445,11 @@ public class CpuWakeupStats {
         SparseIntArray removeBetween(int subsystem, long startElapsed, long endElapsed) {
             final SparseIntArray uidsToReturn = new SparseIntArray();
 
-            final TimeSparseArray<SparseIntArray> activityForSubsystem =
+            final LongSparseArray<SparseIntArray> activityForSubsystem =
                     mWakingActivity.get(subsystem);
             if (activityForSubsystem != null) {
-                final int startIdx = activityForSubsystem.closestIndexOnOrAfter(startElapsed);
-                final int endIdx = activityForSubsystem.closestIndexOnOrBefore(endElapsed);
+                final int startIdx = activityForSubsystem.firstIndexOnOrAfter(startElapsed);
+                final int endIdx = activityForSubsystem.lastIndexOnOrBefore(endElapsed);
                 for (int i = endIdx; i >= startIdx; i--) {
                     final SparseIntArray uidsForTime = activityForSubsystem.valueAt(i);
                     for (int j = 0; j < uidsForTime.size(); j++) {
@@ -463,8 +463,8 @@ public class CpuWakeupStats {
                     activityForSubsystem.removeAt(i);
                 }
                 // Generally waking activity is a high frequency occurrence for any subsystem, so we
-                // don't delete the TimeSparseArray even if it is now empty, to avoid object churn.
-                // This will leave one TimeSparseArray per subsystem, which are few right now.
+                // don't delete the LongSparseArray even if it is now empty, to avoid object churn.
+                // This will leave one LongSparseArray per subsystem, which are few right now.
             }
             return uidsToReturn.size() > 0 ? uidsToReturn : null;
         }
@@ -474,7 +474,7 @@ public class CpuWakeupStats {
             pw.increaseIndent();
             for (int i = 0; i < mWakingActivity.size(); i++) {
                 pw.println("Subsystem " + subsystemToString(mWakingActivity.keyAt(i)) + ":");
-                final TimeSparseArray<SparseIntArray> wakingActivity = mWakingActivity.valueAt(i);
+                final LongSparseArray<SparseIntArray> wakingActivity = mWakingActivity.valueAt(i);
                 if (wakingActivity == null) {
                     continue;
                 }
diff --git a/services/tests/servicestests/src/com/android/server/power/stats/wakeups/CpuWakeupStatsTest.java b/services/tests/servicestests/src/com/android/server/power/stats/wakeups/CpuWakeupStatsTest.java
index d1814199a0b1..b81b776019f9 100644
--- a/services/tests/servicestests/src/com/android/server/power/stats/wakeups/CpuWakeupStatsTest.java
+++ b/services/tests/servicestests/src/com/android/server/power/stats/wakeups/CpuWakeupStatsTest.java
@@ -106,7 +106,7 @@ public class CpuWakeupStatsTest {
         for (int i = 0; i < 100; i++) {
             final long now = mRandom.nextLong(retention + 1, 100 * retention);
             obj.noteWakeupTimeAndReason(now, i, KERNEL_REASON_SOUND_TRIGGER_IRQ);
-            assertThat(obj.mWakeupEvents.closestIndexOnOrBefore(now - retention)).isLessThan(0);
+            assertThat(obj.mWakeupEvents.lastIndexOnOrBefore(now - retention)).isLessThan(0);
         }
     }
 
diff --git a/services/tests/servicestests/src/com/android/server/power/stats/wakeups/WakingActivityHistoryTest.java b/services/tests/servicestests/src/com/android/server/power/stats/wakeups/WakingActivityHistoryTest.java
index b02618e97b11..99bc25abc4a1 100644
--- a/services/tests/servicestests/src/com/android/server/power/stats/wakeups/WakingActivityHistoryTest.java
+++ b/services/tests/servicestests/src/com/android/server/power/stats/wakeups/WakingActivityHistoryTest.java
@@ -18,8 +18,8 @@ package com.android.server.power.stats.wakeups;
 
 import static com.google.common.truth.Truth.assertThat;
 
+import android.util.LongSparseArray;
 import android.util.SparseIntArray;
-import android.util.TimeSparseArray;
 
 import androidx.test.ext.junit.runners.AndroidJUnit4;
 
@@ -73,7 +73,7 @@ public class WakingActivityHistoryTest {
         assertThat(history.mWakingActivity.contains(subsystem + 1)).isFalse();
         assertThat(history.mWakingActivity.contains(subsystem - 1)).isFalse();
 
-        final TimeSparseArray<SparseIntArray> recordedHistory = history.mWakingActivity.get(
+        final LongSparseArray<SparseIntArray> recordedHistory = history.mWakingActivity.get(
                 subsystem);
 
         assertThat(recordedHistory.size()).isEqualTo(1);
@@ -119,7 +119,7 @@ public class WakingActivityHistoryTest {
         assertThat(history.mWakingActivity.contains(subsystem + 1)).isFalse();
         assertThat(history.mWakingActivity.contains(subsystem - 1)).isFalse();
 
-        final TimeSparseArray<SparseIntArray> recordedHistory = history.mWakingActivity.get(
+        final LongSparseArray<SparseIntArray> recordedHistory = history.mWakingActivity.get(
                 subsystem);
 
         assertThat(recordedHistory.size()).isEqualTo(1);
@@ -266,7 +266,7 @@ public class WakingActivityHistoryTest {
             final long time = random.nextLong(firstTime + mTestRetention + 100,
                     456 * mTestRetention);
             history.recordActivity(subsystem, time, new SparseIntArray());
-            assertThat(history.mWakingActivity.get(subsystem).closestIndexOnOrBefore(
+            assertThat(history.mWakingActivity.get(subsystem).lastIndexOnOrBefore(
                     time - mTestRetention)).isLessThan(0);
         }
     }
diff --git a/services/tests/servicestests/src/com/android/server/usage/UsageStatsDatabaseTest.java b/services/tests/servicestests/src/com/android/server/usage/UsageStatsDatabaseTest.java
index 3adee0f06761..83fa29a5dd66 100644
--- a/services/tests/servicestests/src/com/android/server/usage/UsageStatsDatabaseTest.java
+++ b/services/tests/servicestests/src/com/android/server/usage/UsageStatsDatabaseTest.java
@@ -31,7 +31,7 @@ import android.content.Context;
 import android.content.res.Configuration;
 import android.test.suitebuilder.annotation.SmallTest;
 import android.util.AtomicFile;
-import android.util.TimeSparseArray;
+import android.util.LongSparseArray;
 
 import androidx.test.InstrumentationRegistry;
 import androidx.test.runner.AndroidJUnit4;
@@ -568,7 +568,7 @@ public class UsageStatsDatabaseTest {
         mUsageStatsDatabase.forceIndexFiles();
         final int len = mUsageStatsDatabase.mSortedStatFiles.length;
         for (int i = 0; i < len; i++) {
-            final TimeSparseArray<AtomicFile> files =  mUsageStatsDatabase.mSortedStatFiles[i];
+            final LongSparseArray<AtomicFile> files =  mUsageStatsDatabase.mSortedStatFiles[i];
             // The stats file for each interval type equals to max allowed.
             assertEquals(UsageStatsDatabase.MAX_FILES_PER_INTERVAL_TYPE[i],
                     files.size());
diff --git a/services/usage/java/com/android/server/usage/UsageStatsDatabase.java b/services/usage/java/com/android/server/usage/UsageStatsDatabase.java
index a8e374f0edc2..f1c5865fff73 100644
--- a/services/usage/java/com/android/server/usage/UsageStatsDatabase.java
+++ b/services/usage/java/com/android/server/usage/UsageStatsDatabase.java
@@ -26,9 +26,9 @@ import android.os.SystemProperties;
 import android.util.ArrayMap;
 import android.util.ArraySet;
 import android.util.AtomicFile;
+import android.util.LongSparseArray;
 import android.util.Slog;
 import android.util.SparseArray;
-import android.util.TimeSparseArray;
 import android.util.TimeUtils;
 
 import com.android.internal.annotations.VisibleForTesting;
@@ -117,8 +117,8 @@ public class UsageStatsDatabase {
 
     private final Object mLock = new Object();
     private final File[] mIntervalDirs;
-    @VisibleForTesting
-    final TimeSparseArray<AtomicFile>[] mSortedStatFiles;
+    @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
+    final LongSparseArray<AtomicFile>[] mSortedStatFiles;
     private final UnixCalendar mCal;
     private final File mVersionFile;
     private final File mBackupsDir;
@@ -155,7 +155,7 @@ public class UsageStatsDatabase {
         mVersionFile = new File(dir, "version");
         mBackupsDir = new File(dir, "backups");
         mUpdateBreadcrumb = new File(dir, "breadcrumb");
-        mSortedStatFiles = new TimeSparseArray[mIntervalDirs.length];
+        mSortedStatFiles = new LongSparseArray[mIntervalDirs.length];
         mPackageMappingsFile = new File(dir, "mappings");
         mCal = new UnixCalendar(0);
     }
@@ -186,8 +186,8 @@ public class UsageStatsDatabase {
             }
 
             // Delete files that are in the future.
-            for (TimeSparseArray<AtomicFile> files : mSortedStatFiles) {
-                final int startIndex = files.closestIndexOnOrAfter(currentTimeMillis);
+            for (LongSparseArray<AtomicFile> files : mSortedStatFiles) {
+                final int startIndex = files.firstIndexOnOrAfter(currentTimeMillis);
                 if (startIndex < 0) {
                     continue;
                 }
@@ -221,7 +221,7 @@ public class UsageStatsDatabase {
      */
     public boolean checkinDailyFiles(CheckinAction checkinAction) {
         synchronized (mLock) {
-            final TimeSparseArray<AtomicFile> files =
+            final LongSparseArray<AtomicFile> files =
                     mSortedStatFiles[UsageStatsManager.INTERVAL_DAILY];
             final int fileCount = files.size();
 
@@ -292,7 +292,7 @@ public class UsageStatsDatabase {
         // Index the available usage stat files on disk.
         for (int i = 0; i < mSortedStatFiles.length; i++) {
             if (mSortedStatFiles[i] == null) {
-                mSortedStatFiles[i] = new TimeSparseArray<>();
+                mSortedStatFiles[i] = new LongSparseArray<>();
             } else {
                 mSortedStatFiles[i].clear();
             }
@@ -700,7 +700,7 @@ public class UsageStatsDatabase {
             int filesDeleted = 0;
             int filesMoved = 0;
 
-            for (TimeSparseArray<AtomicFile> files : mSortedStatFiles) {
+            for (LongSparseArray<AtomicFile> files : mSortedStatFiles) {
                 final int fileCount = files.size();
                 for (int i = 0; i < fileCount; i++) {
                     final AtomicFile file = files.valueAt(i);
@@ -834,9 +834,9 @@ public class UsageStatsDatabase {
         }
 
         synchronized (mLock) {
-            final TimeSparseArray<AtomicFile> intervalStats = mSortedStatFiles[intervalType];
+            final LongSparseArray<AtomicFile> intervalStats = mSortedStatFiles[intervalType];
 
-            int endIndex = intervalStats.closestIndexOnOrBefore(endTime);
+            int endIndex = intervalStats.lastIndexOnOrBefore(endTime);
             if (endIndex < 0) {
                 // All the stats start after this range ends, so nothing matches.
                 if (DEBUG) {
@@ -857,7 +857,7 @@ public class UsageStatsDatabase {
                 }
             }
 
-            int startIndex = intervalStats.closestIndexOnOrBefore(beginTime);
+            int startIndex = intervalStats.lastIndexOnOrBefore(beginTime);
             if (startIndex < 0) {
                 // All the stats available have timestamps after beginTime, which means they all
                 // match.
@@ -899,7 +899,7 @@ public class UsageStatsDatabase {
             int bestBucket = -1;
             long smallestDiff = Long.MAX_VALUE;
             for (int i = mSortedStatFiles.length - 1; i >= 0; i--) {
-                final int index = mSortedStatFiles[i].closestIndexOnOrBefore(beginTimeStamp);
+                final int index = mSortedStatFiles[i].lastIndexOnOrBefore(beginTimeStamp);
                 int size = mSortedStatFiles[i].size();
                 if (index >= 0 && index < size) {
                     // We have some results here, check if they are better than our current match.
@@ -1523,7 +1523,7 @@ public class UsageStatsDatabase {
             pw.println("Database Summary:");
             pw.increaseIndent();
             for (int i = 0; i < mSortedStatFiles.length; i++) {
-                final TimeSparseArray<AtomicFile> files = mSortedStatFiles[i];
+                final LongSparseArray<AtomicFile> files = mSortedStatFiles[i];
                 final int size = files.size();
                 pw.print(UserUsageStatsService.intervalToString(i));
                 pw.print(" stats files: ");
diff --git a/services/usage/java/com/android/server/usage/UserUsageStatsService.java b/services/usage/java/com/android/server/usage/UserUsageStatsService.java
index 92032086dc24..fd56b6ed1074 100644
--- a/services/usage/java/com/android/server/usage/UserUsageStatsService.java
+++ b/services/usage/java/com/android/server/usage/UserUsageStatsService.java
@@ -46,10 +46,10 @@ import android.text.format.DateUtils;
 import android.util.ArrayMap;
 import android.util.ArraySet;
 import android.util.AtomicFile;
+import android.util.LongSparseArray;
 import android.util.Slog;
 import android.util.SparseArrayMap;
 import android.util.SparseIntArray;
-import android.util.TimeSparseArray;
 
 import com.android.internal.util.ArrayUtils;
 import com.android.internal.util.CollectionUtils;
@@ -1024,7 +1024,7 @@ class UserUsageStatsService {
     }
 
     private void dumpFileDetailsForInterval(IndentingPrintWriter ipw, int interval) {
-        final TimeSparseArray<AtomicFile> files = mDatabase.mSortedStatFiles[interval];
+        final LongSparseArray<AtomicFile> files = mDatabase.mSortedStatFiles[interval];
         final int numFiles = files.size();
         for (int i = 0; i < numFiles; i++) {
             final long filename = files.keyAt(i);