1 /** 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not 5 * use this file except in compliance with the License. You may obtain a copy 6 * of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 13 * License for the specific language governing permissions and limitations 14 * under the License. 15 */ 16 17 package android.util; 18 19 /** 20 * An array that indexes by a long timestamp, representing milliseconds since the epoch. 21 * @param <E> The type of values this container maps to a timestamp. 22 * 23 * {@hide} 24 */ 25 public class TimeSparseArray<E> extends LongSparseArray<E> { 26 private static final String TAG = TimeSparseArray.class.getSimpleName(); 27 28 private boolean mWtfReported; 29 30 /** 31 * Finds the index of the first element whose timestamp is greater or equal to 32 * the given time. 33 * 34 * @param time The timestamp for which to search the array. 35 * @return The smallest {@code index} for which {@code (keyAt(index) >= timeStamp)} is 36 * {@code true}, or {@link #size() size} if no such {@code index} exists. 37 */ closestIndexOnOrAfter(long time)38 public int closestIndexOnOrAfter(long time) { 39 final int size = size(); 40 int result = size; 41 int lo = 0; 42 int hi = size - 1; 43 while (lo <= hi) { 44 final int mid = lo + ((hi - lo) / 2); 45 final long key = keyAt(mid); 46 47 if (time > key) { 48 lo = mid + 1; 49 } else if (time < key) { 50 hi = mid - 1; 51 result = mid; 52 } else { 53 return mid; 54 } 55 } 56 return result; 57 } 58 59 /** 60 * {@inheritDoc} 61 * 62 * <p> This container can store only one value for each timestamp. And so ideally, the caller 63 * should ensure that there are no collisions. Reporting a {@link Slog#wtf(String, String)} 64 * if that happens, as that will lead to the previous value being overwritten. 65 */ 66 @Override put(long key, E value)67 public void put(long key, E value) { 68 if (indexOfKey(key) >= 0) { 69 if (!mWtfReported) { 70 Slog.wtf(TAG, "Overwriting value " + get(key) + " by " + value); 71 mWtfReported = true; 72 } 73 } 74 super.put(key, value); 75 } 76 77 /** 78 * Finds the index of the first element whose timestamp is less than or equal to 79 * the given time. 80 * 81 * @param time The timestamp for which to search the array. 82 * @return The largest {@code index} for which {@code (keyAt(index) <= timeStamp)} is 83 * {@code true}, or -1 if no such {@code index} exists. 84 */ closestIndexOnOrBefore(long time)85 public int closestIndexOnOrBefore(long time) { 86 final int index = closestIndexOnOrAfter(time); 87 88 if (index < size() && keyAt(index) == time) { 89 return index; 90 } 91 return index - 1; 92 } 93 } 94