Home | History | Annotate | Download | only in util 
      1 /*
      2  * Copyright (C) 2015 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.tv.util;
     18 
     19 import android.support.annotation.VisibleForTesting;
     20 import android.util.ArraySet;
     21 import android.util.LongSparseArray;
     22 import java.util.Collections;
     23 import java.util.Set;
     24 
     25 /**
     26  * Uses a {@link LongSparseArray} to hold sets of {@code T}.
     27  *
     28  * <p>This has the same memory and performance trade offs listed in {@link LongSparseArray}.
     29  */
     30 public class MultiLongSparseArray<T> {
     31     @VisibleForTesting static final int DEFAULT_MAX_EMPTIES_KEPT = 4;
     32     private final LongSparseArray<Set<T>> mSparseArray;
     33     private final Set<T>[] mEmptySets;
     34     private int mEmptyIndex = -1;
     35 
     36     public MultiLongSparseArray() {
     37         mSparseArray = new LongSparseArray<>();
     38         mEmptySets = new Set[DEFAULT_MAX_EMPTIES_KEPT];
     39     }
     40 
     41     public MultiLongSparseArray(int initialCapacity, int emptyCacheSize) {
     42         mSparseArray = new LongSparseArray<>(initialCapacity);
     43         mEmptySets = new Set[emptyCacheSize];
     44     }
     45 
     46     /**
     47      * Adds a mapping from the specified key to the specified value, replacing the previous mapping
     48      * from the specified key if there was one.
     49      */
     50     public void put(long key, T value) {
     51         Set<T> values = mSparseArray.get(key);
     52         if (values == null) {
     53             values = getEmptySet();
     54             mSparseArray.put(key, values);
     55         }
     56         values.add(value);
     57     }
     58 
     59     /** Removes the value at the specified index. */
     60     public void remove(long key, T value) {
     61         Set<T> values = mSparseArray.get(key);
     62         if (values != null) {
     63             values.remove(value);
     64             if (values.isEmpty()) {
     65                 mSparseArray.remove(key);
     66                 cacheEmptySet(values);
     67             }
     68         }
     69     }
     70 
     71     /**
     72      * Gets the set of Objects mapped from the specified key, or an empty set if no such mapping has
     73      * been made.
     74      */
     75     public Iterable<T> get(long key) {
     76         Set<T> values = mSparseArray.get(key);
     77         return values == null ? Collections.EMPTY_SET : values;
     78     }
     79 
     80     /** Clears cached empty sets. */
     81     public void clearEmptyCache() {
     82         while (mEmptyIndex >= 0) {
     83             mEmptySets[mEmptyIndex--] = null;
     84         }
     85     }
     86 
     87     @VisibleForTesting
     88     int getEmptyCacheSize() {
     89         return mEmptyIndex + 1;
     90     }
     91 
     92     private void cacheEmptySet(Set<T> emptySet) {
     93         if (mEmptyIndex < DEFAULT_MAX_EMPTIES_KEPT - 1) {
     94             mEmptySets[++mEmptyIndex] = emptySet;
     95         }
     96     }
     97 
     98     private Set<T> getEmptySet() {
     99         if (mEmptyIndex < 0) {
    100             return new ArraySet<>();
    101         }
    102         Set<T> emptySet = mEmptySets[mEmptyIndex];
    103         mEmptySets[mEmptyIndex--] = null;
    104         return emptySet;
    105     }
    106 
    107     @Override
    108     public String toString() {
    109         return mSparseArray.toString() + "(emptyCacheSize=" + getEmptyCacheSize() + ")";
    110     }
    111 }
    112