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