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