Home | History | Annotate | Download | only in usage 
      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      */
     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