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      * 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      */
firstIndexOnOrAfter(long timeStamp)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     /**
108      * Merge the {@link UsageEvents.Event events} in the given {@link EventList list} into this
109      * list while keeping the list sorted based on the event {@link
110      * UsageEvents.Event#mTimeStamp timestamps}.
111      *
112      * @param events The event list to merge
113      */
merge(EventList events)114     public void merge(EventList events) {
115         final int size = events.size();
116         for (int i = 0; i < size; i++) {
117             insert(events.get(i));
118         }
119     }
120 }
121