android/app/usage/TimeSparseArray.java

/**
 * Copyright (C) 2014 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy
 * of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations
 * under the License.
 */

package android.app.usage;

import android.util.LongSparseArray;
import android.util.Slog;

/**
 * An array that indexes by a long timestamp, representing milliseconds since the epoch.
 *
 * {@hide}
 */
public class TimeSparseArray<E> extends LongSparseArray<E> {
    private static final String TAG = TimeSparseArray.class.getSimpleName();

    public TimeSparseArray() {
        super();
    }

    public TimeSparseArray(int initialCapacity) {
        super(initialCapacity);
    }

    /**
     * Finds the index of the first element whose timestamp is greater or equal to
     * the given time.
     *
     * @param time The timestamp for which to search the array.
     * @return The index of the matched element, or -1 if no such match exists.
     */
    public int closestIndexOnOrAfter(long time) {
        // This is essentially a binary search, except that if no match is found
        // the closest index is returned.
        final int size = size();
        int lo = 0;
        int hi = size - 1;
        int mid = -1;
        long key = -1;
        while (lo <= hi) {
            mid = lo + ((hi - lo) / 2);
            key = keyAt(mid);

            if (time > key) {
                lo = mid + 1;
            } else if (time < key) {
                hi = mid - 1;
            } else {
                return mid;
            }
        }

        if (time < key) {
            return mid;
        } else if (time > key && lo < size) {
            return lo;
        } else {
            return -1;
        }
    }

    /**
     * {@inheritDoc}
     *
     * Overridden to ensure no collisions. The key (time in milliseconds) is incremented till an
     * empty place is found.
     */
    @Override
    public void put(long key, E value) {
        final long origKey = key;
        int keyIndex = indexOfKey(key);
        if (keyIndex >= 0) {
            final long sz = size();
            while (keyIndex < sz && keyAt(keyIndex) == key) {
                key++;
                keyIndex++;
            }
            if (key >= origKey + 100) {
                Slog.w(TAG, "Value " + value + " supposed to be inserted at " + origKey
                        + " displaced to " + key);
            }
        }
        super.put(key, value);
    }

    /**
     * Finds the index of the first element whose timestamp is less than or equal to
     * the given time.
     *
     * @param time The timestamp for which to search the array.
     * @return The index of the matched element, or -1 if no such match exists.
     */
    public int closestIndexOnOrBefore(long time) {
        final int index = closestIndexOnOrAfter(time);
        if (index < 0) {
            // Everything is larger, so we use the last element, or -1 if the list is empty.
            return size() - 1;
        }

        if (keyAt(index) == time) {
            return index;
        }
        return index - 1;
    }
}