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 
MultiLongSparseArray()38     public MultiLongSparseArray() {
39         mSparseArray = new LongSparseArray<>();
40         mEmptySets = new Set[DEFAULT_MAX_EMPTIES_KEPT];
41     }
42 
MultiLongSparseArray(int initialCapacity, int emptyCacheSize)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      */
put(long key, T value)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      */
remove(long key, T value)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      */
get(long key)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      */
clearEmptyCache()88     public void clearEmptyCache() {
89         while (mEmptyIndex >= 0) {
90             mEmptySets[mEmptyIndex--] = null;
91         }
92     }
93 
94     @VisibleForTesting
getEmptyCacheSize()95     int getEmptyCacheSize() {
96         return mEmptyIndex + 1;
97     }
98 
cacheEmptySet(Set<T> emptySet)99     private void cacheEmptySet(Set<T> emptySet) {
100         if (mEmptyIndex < DEFAULT_MAX_EMPTIES_KEPT - 1) {
101             mEmptySets[++mEmptyIndex] = emptySet;
102         }
103     }
104 
getEmptySet()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
toString()115     public String toString() {
116         return mSparseArray.toString() + "(emptyCacheSize=" + getEmptyCacheSize() + ")";
117     }
118 }
119