1 /*
2  * Copyright (C) 2021 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 android.util;
18 
19 /**
20  * SparseDoubleArrays map integers to doubles.  Unlike a normal array of doubles,
21  * there can be gaps in the indices.  It is intended to be more memory efficient
22  * than using a HashMap to map Integers to Doubles, both because it avoids
23  * auto-boxing keys and values and its data structure doesn't rely on an extra entry object
24  * for each mapping.
25  *
26  * <p>Note that this container keeps its mappings in an array data structure,
27  * using a binary search to find keys.  The implementation is not intended to be appropriate for
28  * data structures
29  * that may contain large numbers of items.  It is generally slower than a traditional
30  * HashMap, since lookups require a binary search and adds and removes require inserting
31  * and deleting entries in the array.  For containers holding up to hundreds of items,
32  * the performance difference is not significant, less than 50%.</p>
33  *
34  * <p>It is possible to iterate over the items in this container using
35  * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using
36  * <code>keyAt(int)</code> with ascending values of the index will return the
37  * keys in ascending order, or the values corresponding to the keys in ascending
38  * order in the case of <code>valueAt(int)</code>.</p>
39  *
40  * @see SparseLongArray
41  *
42  * @hide
43  */
44 @android.ravenwood.annotation.RavenwoodKeepWholeClass
45 public class SparseDoubleArray implements Cloneable {
46     /**
47      * The int->double map, but storing the doubles as longs using
48      * {@link Double#doubleToRawLongBits(double)}.
49      */
50     private SparseLongArray mValues;
51 
52     /** Creates a new SparseDoubleArray containing no mappings. */
SparseDoubleArray()53     public SparseDoubleArray() {
54         this(0);
55     }
56 
57     /**
58      * Creates a new SparseDoubleArray, containing no mappings, that will not
59      * require any additional memory allocation to store the specified
60      * number of mappings.  If you supply an initial capacity of 0, the
61      * sparse array will be initialized with a light-weight representation
62      * not requiring any additional array allocations.
63      */
SparseDoubleArray(int initialCapacity)64     public SparseDoubleArray(int initialCapacity) {
65         mValues = new SparseLongArray(initialCapacity);
66     }
67 
68     @Override
clone()69     public SparseDoubleArray clone() {
70         SparseDoubleArray clone = null;
71         try {
72             clone = (SparseDoubleArray) super.clone();
73             clone.mValues = mValues.clone();
74         } catch (CloneNotSupportedException cnse) {
75             /* ignore */
76         }
77         return clone;
78     }
79 
80     /**
81      * Gets the double mapped from the specified key, or <code>0</code>
82      * if no such mapping has been made.
83      */
get(int key)84     public double get(int key) {
85         return get(key, 0);
86     }
87 
88     /**
89      * Gets the double mapped from the specified key, or the specified value
90      * if no such mapping has been made.
91      */
get(int key, double valueIfKeyNotFound)92     public double get(int key, double valueIfKeyNotFound) {
93         final int index = mValues.indexOfKey(key);
94         if (index < 0) {
95             return valueIfKeyNotFound;
96         }
97         return valueAt(index);
98     }
99 
100     /**
101      * Adds a mapping from the specified key to the specified value,
102      * replacing the previous mapping from the specified key if there
103      * was one.
104      */
put(int key, double value)105     public void put(int key, double value) {
106         mValues.put(key, Double.doubleToRawLongBits(value));
107     }
108 
109     /**
110      * Adds a mapping from the specified key to the specified value,
111      * <b>adding</b> its value to the previous mapping from the specified key if there
112      * was one.
113      *
114      * <p>This differs from {@link #put} because instead of replacing any previous value, it adds
115      * (in the numerical sense) to it.
116      */
incrementValue(int key, double summand)117     public void incrementValue(int key, double summand) {
118         final double oldValue = get(key);
119         put(key, oldValue + summand);
120     }
121 
122     /** Returns the number of key-value mappings that this SparseDoubleArray currently stores. */
size()123     public int size() {
124         return mValues.size();
125     }
126 
127     /**
128      * Returns the index for which {@link #keyAt} would return the
129      * specified key, or a negative number if the specified
130      * key is not mapped.
131      */
indexOfKey(int key)132     public int indexOfKey(int key) {
133         return mValues.indexOfKey(key);
134     }
135 
136     /**
137      * Given an index in the range <code>0...size()-1</code>, returns
138      * the key from the <code>index</code>th key-value mapping that this
139      * SparseDoubleArray stores.
140      *
141      * @see SparseLongArray#keyAt(int)
142      */
keyAt(int index)143     public int keyAt(int index) {
144         return mValues.keyAt(index);
145     }
146 
147     /**
148      * Given an index in the range <code>0...size()-1</code>, returns
149      * the value from the <code>index</code>th key-value mapping that this
150      * SparseDoubleArray stores.
151      *
152      * @see SparseLongArray#valueAt(int)
153      */
valueAt(int index)154     public double valueAt(int index) {
155         return Double.longBitsToDouble(mValues.valueAt(index));
156     }
157 
158     /**
159      * Given an index in the range <code>0...size()-1</code>, sets a new
160      * value for the <code>index</code>th key-value mapping that this
161      * SparseDoubleArray stores.
162      *
163      * <p>For indices outside of the range <code>0...size()-1</code>, the behavior is undefined for
164      * apps targeting {@link android.os.Build.VERSION_CODES#P} and earlier, and an
165      * {@link ArrayIndexOutOfBoundsException} is thrown for apps targeting
166      * {@link android.os.Build.VERSION_CODES#Q} and later.</p>
167      */
setValueAt(int index, double value)168     public void setValueAt(int index, double value) {
169         mValues.setValueAt(index, Double.doubleToRawLongBits(value));
170     }
171 
172     /**
173      * Removes the mapping at the given index.
174      */
removeAt(int index)175     public void removeAt(int index) {
176         mValues.removeAt(index);
177     }
178 
179     /**
180      * Removes the mapping from the specified key, if there was any.
181      */
delete(int key)182     public void delete(int key) {
183         mValues.delete(key);
184     }
185 
186     /**
187      * Removes all key-value mappings from this SparseDoubleArray.
188      */
clear()189     public void clear() {
190         mValues.clear();
191     }
192 
193     /**
194      * {@inheritDoc}
195      *
196      * <p>This implementation composes a string by iterating over its mappings.
197      */
198     @Override
toString()199     public String toString() {
200         if (size() <= 0) {
201             return "{}";
202         }
203 
204         StringBuilder buffer = new StringBuilder(size() * 34);
205         buffer.append('{');
206         for (int i = 0; i < size(); i++) {
207             if (i > 0) {
208                 buffer.append(", ");
209             }
210             int key = keyAt(i);
211             buffer.append(key);
212             buffer.append('=');
213             double value = valueAt(i);
214             buffer.append(value);
215         }
216         buffer.append('}');
217         return buffer.toString();
218     }
219 }
220