Home | History | Annotate | Download | only in usage 
      1 /**
      2  * Copyright (C) 2014 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
      5  * use this file except in compliance with the License. You may obtain a copy
      6  * 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, WITHOUT
     12  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
     13  * License for the specific language governing permissions and limitations
     14  * under the License.
     15  */
     16 
     17 package android.app.usage;
     18 
     19 import android.util.LongSparseArray;
     20 
     21 /**
     22  * An array that indexes by a long timestamp, representing milliseconds since the epoch.
     23  *
     24  * {@hide}
     25  */
     26 public class TimeSparseArray<E> extends LongSparseArray<E> {
     27     public TimeSparseArray() {
     28         super();
     29     }
     30 
     31     public TimeSparseArray(int initialCapacity) {
     32         super(initialCapacity);
     33     }
     34 
     35     /**
     36      * Finds the index of the first element whose timestamp is greater or equal to
     37      * the given time.
     38      *
     39      * @param time The timestamp for which to search the array.
     40      * @return The index of the matched element, or -1 if no such match exists.
     41      */
     42     public int closestIndexOnOrAfter(long time) {
     43         // This is essentially a binary search, except that if no match is found
     44         // the closest index is returned.
     45         final int size = size();
     46         int lo = 0;
     47         int hi = size - 1;
     48         int mid = -1;
     49         long key = -1;
     50         while (lo <= hi) {
     51             mid = lo + ((hi - lo) / 2);
     52             key = keyAt(mid);
     53 
     54             if (time > key) {
     55                 lo = mid + 1;
     56             } else if (time < key) {
     57                 hi = mid - 1;
     58             } else {
     59                 return mid;
     60             }
     61         }
     62 
     63         if (time < key) {
     64             return mid;
     65         } else if (time > key && lo < size) {
     66             return lo;
     67         } else {
     68             return -1;
     69         }
     70     }
     71 
     72     /**
     73      * Finds the index of the first element whose timestamp is less than or equal to
     74      * the given time.
     75      *
     76      * @param time The timestamp for which to search the array.
     77      * @return The index of the matched element, or -1 if no such match exists.
     78      */
     79     public int closestIndexOnOrBefore(long time) {
     80         final int index = closestIndexOnOrAfter(time);
     81         if (index < 0) {
     82             // Everything is larger, so we use the last element, or -1 if the list is empty.
     83             return size() - 1;
     84         }
     85 
     86         if (keyAt(index) == time) {
     87             return index;
     88         }
     89         return index - 1;
     90     }
     91 }
     92