1 /*
2  * Copyright (C) 2022 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.server;
18 
19 import android.annotation.Nullable;
20 import android.util.ArrayMap;
21 
22 import java.util.Collection;
23 import java.util.LinkedList;
24 
25 /**
26  * CircularQueue of length limit which puts keys in a circular LinkedList and values in an ArrayMap.
27  * @param <K> key
28  * @param <V> value
29  */
30 public class CircularQueue<K, V> extends LinkedList<K> {
31     private final int mLimit;
32     private final ArrayMap<K, V> mArrayMap = new ArrayMap<>();
33 
CircularQueue(int limit)34     public CircularQueue(int limit) {
35         this.mLimit = limit;
36     }
37 
38     @Override
add(K k)39     public boolean add(K k) throws IllegalArgumentException {
40         throw new IllegalArgumentException("Call of add(key) prohibited. Please call put(key, "
41                 + "value) instead. ");
42     }
43 
44     /**
45      * Put a (key|value) pair in the CircularQueue. Only the key will be added to the queue. Value
46      * will be added to the ArrayMap.
47      * @return the most recently removed value if keys were removed, or {@code null} if no keys were
48      * removed.
49      */
50     @Nullable
put(K key, V value)51     public V put(K key, V value) {
52         super.add(key);
53         mArrayMap.put(key, value);
54         V removedValue = null;
55         while (size() > mLimit) {
56             K removedKey = super.remove();
57             removedValue = mArrayMap.remove(removedKey);
58         }
59         return removedValue;
60     }
61 
62     /**
63      * Removes the element for the provided key from the data structure.
64      * @param key which should be removed
65      * @return the value which was removed
66      */
removeElement(K key)67     public V removeElement(K key) {
68         super.remove(key);
69         return mArrayMap.remove(key);
70     }
71 
72     /**
73      * Retrieve a value from the array.
74      * @param key The key of the value to retrieve.
75      * @return Returns the value associated with the given key,
76      * or null if there is no such key.
77      */
getElement(K key)78     public V getElement(K key) {
79         return mArrayMap.get(key);
80     }
81 
82     /**
83      * Check whether a key exists in the array.
84      *
85      * @param key The key to search for.
86      * @return Returns true if the key exists, else false.
87      */
containsKey(K key)88     public boolean containsKey(K key) {
89         return mArrayMap.containsKey(key);
90     }
91 
92     /**
93      * Return a {@link java.util.Collection} for iterating over and interacting with all values
94      * in the array map.
95      *
96      * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it
97      * requires generating a number of temporary objects and allocates additional state
98      * information associated with the container that will remain for the life of the container.</p>
99      */
values()100     public Collection<V> values() {
101         return mArrayMap.values();
102     }
103 }
104