EventList.java revision 60aa35b756707a16d310c222a36edbcef9d56ed4 
1/*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy 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,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package android.app.usage;
18
19import java.util.ArrayList;
20
21/**
22 * A container to keep {@link UsageEvents.Event usage events} in non-descending order of their
23 * {@link UsageEvents.Event#mTimeStamp timestamps}.
24 *
25 * @hide
26 */
27public class EventList {
28
29    private final ArrayList<UsageEvents.Event> mEvents;
30
31    /**
32     * Create a new event list with default capacity
33     */
34    public EventList() {
35        mEvents = new ArrayList<>();
36    }
37
38    /**
39     * Returns the size of the list
40     * @return the number of events in the list
41     */
42    public int size() {
43        return mEvents.size();
44    }
45
46    /**
47     * Removes all events from the list
48     */
49    public void clear() {
50        mEvents.clear();
51    }
52
53    /**
54     * Returns the {@link UsageEvents.Event event} at the specified position in this list.
55     * @param index the index of the event to return, such that {@code 0 <= index < size()}
56     * @return The {@link UsageEvents.Event event} at position {@code index}
57     */
58    public UsageEvents.Event get(int index) {
59        return mEvents.get(index);
60    }
61
62    /**
63     * Inserts the given {@link UsageEvents.Event event} into the list while keeping the list sorted
64     * based on the event {@link UsageEvents.Event#mTimeStamp timestamps}.
65     *
66     * @param event The event to insert
67     */
68    public void insert(UsageEvents.Event event) {
69        final int size = mEvents.size();
70        // fast case: just append if this is the latest event
71        if (size == 0 || event.mTimeStamp >= mEvents.get(size - 1).mTimeStamp) {
72            mEvents.add(event);
73            return;
74        }
75        // To minimize number of elements being shifted, insert at the first occurrence of the next
76        // greatest timestamp in the list.
77        final int insertIndex = firstIndexOnOrAfter(event.mTimeStamp + 1);
78        mEvents.add(insertIndex, event);
79    }
80
81    /**
82     * Finds the index of the first event whose timestamp is greater than or equal to the given
83     * timestamp.
84     *
85     * @param timeStamp The timestamp for which to search the list.
86     * @return The smallest {@code index} for which {@code (get(index).mTimeStamp >= timeStamp)} is
87     * {@code true}, or {@link #size() size} if no such {@code index} exists.
88     */
89    public int firstIndexOnOrAfter(long timeStamp) {
90        final int size = mEvents.size();
91        int result = size;
92        int lo = 0;
93        int hi = size - 1;
94        while (lo <= hi) {
95            final int mid = (lo + hi) >>> 1;
96            final long midTimeStamp = mEvents.get(mid).mTimeStamp;
97            if (midTimeStamp >= timeStamp) {
98                hi = mid - 1;
99                result = mid;
100            } else {
101                lo = mid + 1;
102            }
103        }
104        return result;
105    }
106}
107