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 public class SparseDoubleArray implements Cloneable {
45     /**
46      * The int->double map, but storing the doubles as longs using
47      * {@link Double#doubleToRawLongBits(double)}.
48      */
49     private SparseLongArray mValues;
50 
51     /** Creates a new SparseDoubleArray containing no mappings. */
SparseDoubleArray()52     public SparseDoubleArray() {
53         this(10);
54     }
55 
56     /**
57      * Creates a new SparseDoubleArray, containing no mappings, that will not
58      * require any additional memory allocation to store the specified
59      * number of mappings.  If you supply an initial capacity of 0, the
60      * sparse array will be initialized with a light-weight representation
61      * not requiring any additional array allocations.
62      */
SparseDoubleArray(int initialCapacity)63     public SparseDoubleArray(int initialCapacity) {
64         mValues = new SparseLongArray(initialCapacity);
65     }
66 
67     @Override
clone()68     public SparseDoubleArray clone() {
69         SparseDoubleArray clone = null;
70         try {
71             clone = (SparseDoubleArray) super.clone();
72             clone.mValues = mValues.clone();
73         } catch (CloneNotSupportedException cnse) {
74             /* ignore */
75         }
76         return clone;
77     }
78 
79     /**
80      * Gets the double mapped from the specified key, or <code>0</code>
81      * if no such mapping has been made.
82      */
get(int key)83     public double get(int key) {
84         final int index = mValues.indexOfKey(key);
85         if (index < 0) {
86             return 0.0d;
87         }
88         return valueAt(index);
89     }
90 
91     /**
92      * Adds a mapping from the specified key to the specified value,
93      * replacing the previous mapping from the specified key if there
94      * was one.
95      */
put(int key, double value)96     public void put(int key, double value) {
97         mValues.put(key, Double.doubleToRawLongBits(value));
98     }
99 
100     /**
101      * Adds a mapping from the specified key to the specified value,
102      * <b>adding</b> its value to the previous mapping from the specified key if there
103      * was one.
104      *
105      * <p>This differs from {@link #put} because instead of replacing any previous value, it adds
106      * (in the numerical sense) to it.
107      */
add(int key, double summand)108     public void add(int key, double summand) {
109         final double oldValue = get(key);
110         put(key, oldValue + summand);
111     }
112 
113     /** Returns the number of key-value mappings that this SparseDoubleArray currently stores. */
size()114     public int size() {
115         return mValues.size();
116     }
117 
118     /**
119      * Given an index in the range <code>0...size()-1</code>, returns
120      * the key from the <code>index</code>th key-value mapping that this
121      * SparseDoubleArray stores.
122      *
123      * @see SparseLongArray#keyAt(int)
124      */
keyAt(int index)125     public int keyAt(int index) {
126         return mValues.keyAt(index);
127     }
128 
129     /**
130      * Given an index in the range <code>0...size()-1</code>, returns
131      * the value from the <code>index</code>th key-value mapping that this
132      * SparseDoubleArray stores.
133      *
134      * @see SparseLongArray#valueAt(int)
135      */
valueAt(int index)136     public double valueAt(int index) {
137         return Double.longBitsToDouble(mValues.valueAt(index));
138     }
139 
140     /**
141      * {@inheritDoc}
142      *
143      * <p>This implementation composes a string by iterating over its mappings.
144      */
145     @Override
toString()146     public String toString() {
147         if (size() <= 0) {
148             return "{}";
149         }
150 
151         StringBuilder buffer = new StringBuilder(size() * 34);
152         buffer.append('{');
153         for (int i = 0; i < size(); i++) {
154             if (i > 0) {
155                 buffer.append(", ");
156             }
157             int key = keyAt(i);
158             buffer.append(key);
159             buffer.append('=');
160             double value = valueAt(i);
161             buffer.append(value);
162         }
163         buffer.append('}');
164         return buffer.toString();
165     }
166 }
167