1 /*
2  * Copyright (C) 2020 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 com.android.server.people.data;
18 
19 import android.annotation.NonNull;
20 
21 import com.android.internal.util.CollectionUtils;
22 
23 import java.util.ArrayList;
24 import java.util.List;
25 import java.util.Set;
26 
27 /** A container that holds a list of {@link Event}s in chronological order. */
28 class EventList {
29 
30     private final List<Event> mEvents = new ArrayList<>();
31 
32     /**
33      * Adds an event to the list unless there is an existing event with the same timestamp and
34      * type.
35      */
add(@onNull Event event)36     void add(@NonNull Event event) {
37         int index = firstIndexOnOrAfter(event.getTimestamp());
38         if (index < mEvents.size()
39                 && mEvents.get(index).getTimestamp() == event.getTimestamp()
40                 && isDuplicate(event, index)) {
41             return;
42         }
43         mEvents.add(index, event);
44     }
45 
46 
47     /**
48      * Call #add on each event to keep the order.
49      */
addAll(@onNull List<Event> events)50     void addAll(@NonNull List<Event> events) {
51         for (Event event : events) {
52             add(event);
53         }
54     }
55 
56     /**
57      * Returns a {@link List} of {@link Event}s whose timestamps are between the specified {@code
58      * fromTimestamp}, inclusive, and {@code toTimestamp} exclusive, and match the specified event
59      * types.
60      *
61      * @return a {@link List} of matched {@link Event}s in chronological order.
62      */
63     @NonNull
queryEvents(@onNull Set<Integer> eventTypes, long fromTimestamp, long toTimestamp)64     List<Event> queryEvents(@NonNull Set<Integer> eventTypes, long fromTimestamp,
65             long toTimestamp) {
66         int fromIndex = firstIndexOnOrAfter(fromTimestamp);
67         if (fromIndex == mEvents.size()) {
68             return new ArrayList<>();
69         }
70         int toIndex = firstIndexOnOrAfter(toTimestamp);
71         if (toIndex < fromIndex) {
72             return new ArrayList<>();
73         }
74         List<Event> result = new ArrayList<>();
75         for (int i = fromIndex; i < toIndex; i++) {
76             Event e = mEvents.get(i);
77             if (eventTypes.contains(e.getType())) {
78                 result.add(e);
79             }
80         }
81         return result;
82     }
83 
clear()84     void clear() {
85         mEvents.clear();
86     }
87 
88     /**
89      * Returns a copy of events.
90      */
91     @NonNull
getAllEvents()92     List<Event> getAllEvents() {
93         return CollectionUtils.copyOf(mEvents);
94     }
95 
96     /**
97      * Remove events that are older than the specified cut off threshold timestamp.
98      */
removeOldEvents(long cutOffThreshold)99     void removeOldEvents(long cutOffThreshold) {
100 
101         // Everything before the cut off is considered old, and should be removed.
102         int cutOffIndex = firstIndexOnOrAfter(cutOffThreshold);
103         if (cutOffIndex == 0) {
104             return;
105         }
106 
107         // Clear entire list if the cut off is greater than the last element.
108         int eventsSize = mEvents.size();
109         if (cutOffIndex == eventsSize) {
110             mEvents.clear();
111             return;
112         }
113 
114         // Reorder the list starting from the cut off index.
115         int i = 0;
116         for (; cutOffIndex < eventsSize; i++, cutOffIndex++) {
117             mEvents.set(i, mEvents.get(cutOffIndex));
118         }
119 
120         // Clear the list after reordering.
121         if (eventsSize > i) {
122             mEvents.subList(i, eventsSize).clear();
123         }
124     }
125 
126     /** Returns the first index whose timestamp is greater or equal to the provided timestamp. */
firstIndexOnOrAfter(long timestamp)127     private int firstIndexOnOrAfter(long timestamp) {
128         int result = mEvents.size();
129         int low = 0;
130         int high = mEvents.size() - 1;
131         while (low <= high) {
132             int mid = (low + high) >>> 1;
133             if (mEvents.get(mid).getTimestamp() >= timestamp) {
134                 high = mid - 1;
135                 result = mid;
136             } else {
137                 low = mid + 1;
138             }
139         }
140         return result;
141     }
142 
143     /**
144      * Checks whether the {@link Event} is duplicate with one of the existing events. The checking
145      * starts from the {@code startIndex}.
146      */
isDuplicate(Event event, int startIndex)147     private boolean isDuplicate(Event event, int startIndex) {
148         int size = mEvents.size();
149         int index = startIndex;
150         while (index < size && mEvents.get(index).getTimestamp() <= event.getTimestamp()) {
151             if (mEvents.get(index++).getType() == event.getType()) {
152                 return true;
153             }
154         }
155         return false;
156     }
157 }
158