TimeSparseArray.java revision 60aa35b756707a16d310c222a36edbcef9d56ed4 
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    private boolean mWtfReported;
31
32    public TimeSparseArray() {
33        super();
34    }
35
36    /**
37     * Finds the index of the first element whose timestamp is greater or equal to
38     * the given time.
39     *
40     * @param time The timestamp for which to search the array.
41     * @return The index of the matched element, or -1 if no such match exists.
42     */
43    public int closestIndexOnOrAfter(long time) {
44        // This is essentially a binary search, except that if no match is found
45        // the closest index is returned.
46        final int size = size();
47        int lo = 0;
48        int hi = size - 1;
49        int mid = -1;
50        long key = -1;
51        while (lo <= hi) {
52            mid = lo + ((hi - lo) / 2);
53            key = keyAt(mid);
54
55            if (time > key) {
56                lo = mid + 1;
57            } else if (time < key) {
58                hi = mid - 1;
59            } else {
60                return mid;
61            }
62        }
63
64        if (time < key) {
65            return mid;
66        } else if (time > key && lo < size) {
67            return lo;
68        } else {
69            return -1;
70        }
71    }
72
73    /**
74     * {@inheritDoc}
75     *
76     * <p> As this container is being used only to keep {@link android.util.AtomicFile files},
77     * there should not be any collisions. Reporting a {@link Slog#wtf(String, String)} in case that
78     * happens, as that will lead to one whole file being dropped.
79     */
80    @Override
81    public void put(long key, E value) {
82        if (indexOfKey(key) >= 0) {
83            if (!mWtfReported) {
84                Slog.wtf(TAG, "Overwriting value " + get(key) + " by " + value);
85                mWtfReported = true;
86            }
87        }
88        super.put(key, value);
89    }
90
91    /**
92     * Finds the index of the first element whose timestamp is less than or equal to
93     * the given time.
94     *
95     * @param time The timestamp for which to search the array.
96     * @return The index of the matched element, or -1 if no such match exists.
97     */
98    public int closestIndexOnOrBefore(long time) {
99        final int index = closestIndexOnOrAfter(time);
100        if (index < 0) {
101            // Everything is larger, so we use the last element, or -1 if the list is empty.
102            return size() - 1;
103        }
104
105        if (keyAt(index) == time) {
106            return index;
107        }
108        return index - 1;
109    }
110}
111