MultiLongSparseArray.java revision 48dadb49248271b01997862e1335912a4f2e189f 
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
17package com.android.tv.util;
18
19import android.support.annotation.VisibleForTesting;
20import android.util.ArraySet;
21import android.util.LongSparseArray;
22
23import java.util.Collections;
24import 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 */
31public 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