TimeSparseArray.java revision a2cf00a011e634f98b7e86ee025bfe489ec15f4f
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 17package android.app.usage; 18 19import android.util.LongSparseArray; 20import android.util.Slog; 21 22/** 23 * An array that indexes by a long timestamp, representing milliseconds since the epoch. 24 * 25 * {@hide} 26 */ 27public class TimeSparseArray<E> extends LongSparseArray<E> { 28 private static final String TAG = TimeSparseArray.class.getSimpleName(); 29 30 public TimeSparseArray() { 31 super(); 32 } 33 34 public TimeSparseArray(int initialCapacity) { 35 super(initialCapacity); 36 } 37 38 /** 39 * Finds the index of the first element whose timestamp is greater or equal to 40 * the given time. 41 * 42 * @param time The timestamp for which to search the array. 43 * @return The index of the matched element, or -1 if no such match exists. 44 */ 45 public int closestIndexOnOrAfter(long time) { 46 // This is essentially a binary search, except that if no match is found 47 // the closest index is returned. 48 final int size = size(); 49 int lo = 0; 50 int hi = size - 1; 51 int mid = -1; 52 long key = -1; 53 while (lo <= hi) { 54 mid = lo + ((hi - lo) / 2); 55 key = keyAt(mid); 56 57 if (time > key) { 58 lo = mid + 1; 59 } else if (time < key) { 60 hi = mid - 1; 61 } else { 62 return mid; 63 } 64 } 65 66 if (time < key) { 67 return mid; 68 } else if (time > key && lo < size) { 69 return lo; 70 } else { 71 return -1; 72 } 73 } 74 75 /** 76 * {@inheritDoc} 77 * 78 * Overridden to ensure no collisions. The key (time in milliseconds) is incremented till an 79 * empty place is found. 80 */ 81 @Override 82 public void put(long key, E value) { 83 final long origKey = key; 84 int keyIndex = indexOfKey(key); 85 if (keyIndex >= 0) { 86 final long sz = size(); 87 while (keyIndex < sz && keyAt(keyIndex) == key) { 88 key++; 89 keyIndex++; 90 } 91 if (key >= origKey + 10) { 92 Slog.w(TAG, "Value " + value + " supposed to be inserted at " + origKey 93 + " displaced to " + key); 94 } 95 } 96 super.put(key, value); 97 } 98 99 /** 100 * Finds the index of the first element whose timestamp is less than or equal to 101 * the given time. 102 * 103 * @param time The timestamp for which to search the array. 104 * @return The index of the matched element, or -1 if no such match exists. 105 */ 106 public int closestIndexOnOrBefore(long time) { 107 final int index = closestIndexOnOrAfter(time); 108 if (index < 0) { 109 // Everything is larger, so we use the last element, or -1 if the list is empty. 110 return size() - 1; 111 } 112 113 if (keyAt(index) == time) { 114 return index; 115 } 116 return index - 1; 117 } 118} 119