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 
17 package android.app.usage;
18 
19 import 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  */
27 public class EventList {
28 
29     private final ArrayList<UsageEvents.Event> mEvents;
30 
31     /**
32      * Create a new event list with default capacity
33      */
EventList()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      */
size()42     public int size() {
43         return mEvents.size();
44     }
45 
46     /**
47      * Removes all events from the list
48      */
clear()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      */
get(int index)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      */
insert(UsageEvents.Event event)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      * Removes the event at the given index.
83      *
84      * @param index the index of the event to remove
85      * @return the event removed, or {@code null} if the index was out of bounds
86      */
remove(int index)87     public UsageEvents.Event remove(int index) {
88         try {
89             return mEvents.remove(index);
90         } catch (IndexOutOfBoundsException e) {
91             // catch and handle the exception here instead of throwing it to the client
92             return null;
93         }
94     }
95 
96     /**
97      * Finds the index of the first event whose timestamp is greater than or equal to the given
98      * timestamp.
99      *
100      * @param timeStamp The timestamp for which to search the list.
101      * @return The smallest {@code index} for which {@code (get(index).mTimeStamp >= timeStamp)} is
102      * {@code true}, or {@link #size() size} if no such {@code index} exists.
103      */
firstIndexOnOrAfter(long timeStamp)104     public int firstIndexOnOrAfter(long timeStamp) {
105         final int size = mEvents.size();
106         int result = size;
107         int lo = 0;
108         int hi = size - 1;
109         while (lo <= hi) {
110             final int mid = (lo + hi) >>> 1;
111             final long midTimeStamp = mEvents.get(mid).mTimeStamp;
112             if (midTimeStamp >= timeStamp) {
113                 hi = mid - 1;
114                 result = mid;
115             } else {
116                 lo = mid + 1;
117             }
118         }
119         return result;
120     }
121 
122     /**
123      * Merge the {@link UsageEvents.Event events} in the given {@link EventList list} into this
124      * list while keeping the list sorted based on the event {@link
125      * UsageEvents.Event#mTimeStamp timestamps}.
126      *
127      * @param events The event list to merge
128      */
merge(EventList events)129     public void merge(EventList events) {
130         final int size = events.size();
131         for (int i = 0; i < size; i++) {
132             insert(events.get(i));
133         }
134     }
135 }
136