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 
MultiLongSparseArray()36     public MultiLongSparseArray() {
37         mSparseArray = new LongSparseArray<>();
38         mEmptySets = new Set[DEFAULT_MAX_EMPTIES_KEPT];
39     }
40 
MultiLongSparseArray(int initialCapacity, int emptyCacheSize)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      */
put(long key, T value)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. */
remove(long key, T value)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      */
get(long key)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. */
clearEmptyCache()81     public void clearEmptyCache() {
82         while (mEmptyIndex >= 0) {
83             mEmptySets[mEmptyIndex--] = null;
84         }
85     }
86 
87     @VisibleForTesting
getEmptyCacheSize()88     int getEmptyCacheSize() {
89         return mEmptyIndex + 1;
90     }
91 
cacheEmptySet(Set<T> emptySet)92     private void cacheEmptySet(Set<T> emptySet) {
93         if (mEmptyIndex < DEFAULT_MAX_EMPTIES_KEPT - 1) {
94             mEmptySets[++mEmptyIndex] = emptySet;
95         }
96     }
97 
getEmptySet()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
toString()108     public String toString() {
109         return mSparseArray.toString() + "(emptyCacheSize=" + getEmptyCacheSize() + ")";
110     }
111 }
112