Class |
Line # |
Actions |
|||
---|---|---|---|---|---|
SparseIntArray | 70 | 114 | 46 |
1 | /* | |
2 | * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$) | |
3 | * Copyright (C) $$Year-Rel$$ The Jalview Authors | |
4 | * | |
5 | * This file is part of Jalview. | |
6 | * | |
7 | * Jalview is free software: you can redistribute it and/or | |
8 | * modify it under the terms of the GNU General Public License | |
9 | * as published by the Free Software Foundation, either version 3 | |
10 | * of the License, or (at your option) any later version. | |
11 | * | |
12 | * Jalview is distributed in the hope that it will be useful, but | |
13 | * WITHOUT ANY WARRANTY; without even the implied warranty | |
14 | * of MERCHANTABILITY or FITNESS FOR A PARTICULAR | |
15 | * PURPOSE. See the GNU General Public License for more details. | |
16 | * | |
17 | * You should have received a copy of the GNU General Public License | |
18 | * along with Jalview. If not, see <http://www.gnu.org/licenses/>. | |
19 | * The Jalview Authors are detailed in the 'AUTHORS' file. | |
20 | */ | |
21 | package jalview.ext.android; | |
22 | ||
23 | /* | |
24 | * Copyright (C) 2006 The Android Open Source Project | |
25 | * | |
26 | * Licensed under the Apache License, Version 2.0 (the "License"); | |
27 | * you may not use this file except in compliance with the License. | |
28 | * You may obtain a copy of the License at | |
29 | * | |
30 | * http://www.apache.org/licenses/LICENSE-2.0 | |
31 | * | |
32 | * Unless required by applicable law or agreed to in writing, software | |
33 | * distributed under the License is distributed on an "AS IS" BASIS, | |
34 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
35 | * See the License for the specific language governing permissions and | |
36 | * limitations under the License. | |
37 | */ | |
38 | /** | |
39 | * SparseIntArrays map integers to integers. Unlike a normal array of integers, | |
40 | * there can be gaps in the indices. It is intended to be more memory efficient | |
41 | * than using a HashMap to map Integers to Integers, both because it avoids | |
42 | * auto-boxing keys and values and its data structure doesn't rely on an extra | |
43 | * entry object for each mapping. | |
44 | * | |
45 | * <p> | |
46 | * Note that this container keeps its mappings in an array data structure, using | |
47 | * a binary search to find keys. The implementation is not intended to be | |
48 | * appropriate for data structures that may contain large numbers of items. It | |
49 | * is generally slower than a traditional HashMap, since lookups require a | |
50 | * binary search and adds and removes require inserting and deleting entries in | |
51 | * the array. For containers holding up to hundreds of items, the performance | |
52 | * difference is not significant, less than 50%. | |
53 | * </p> | |
54 | * | |
55 | * <p> | |
56 | * It is possible to iterate over the items in this container using | |
57 | * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using | |
58 | * <code>keyAt(int)</code> with ascending values of the index will return the | |
59 | * keys in ascending order, or the values corresponding to the keys in ascending | |
60 | * order in the case of <code>valueAt(int)<code>. | |
61 | * </p> | |
62 | */ | |
63 | ||
64 | /* | |
65 | * Imported into Jalview September 2016 | |
66 | * Change log: | |
67 | * Sep 2016 method add(int, int) added for more efficient increment of counts | |
68 | * (a single binary search, rather than one on read and one on write) | |
69 | */ | |
70 | public class SparseIntArray implements Cloneable | |
71 | { | |
72 | private int[] mKeys; | |
73 | ||
74 | private int[] mValues; | |
75 | ||
76 | private int mSize; | |
77 | ||
78 | /** | |
79 | * Creates a new SparseIntArray containing no mappings. | |
80 | */ | |
81 | 2 | public SparseIntArray() |
82 | { | |
83 | 2 | this(10); |
84 | } | |
85 | ||
86 | /** | |
87 | * Creates a new SparseIntArray containing no mappings that will not require | |
88 | * any additional memory allocation to store the specified number of mappings. | |
89 | * If you supply an initial capacity of 0, the sparse array will be | |
90 | * initialized with a light-weight representation not requiring any additional | |
91 | * array allocations. | |
92 | */ | |
93 | 4 | public SparseIntArray(int initialCapacity) |
94 | { | |
95 | 4 | if (initialCapacity == 0) |
96 | { | |
97 | 0 | mKeys = ContainerHelpers.EMPTY_INTS; |
98 | 0 | mValues = ContainerHelpers.EMPTY_INTS; |
99 | } | |
100 | else | |
101 | { | |
102 | 4 | initialCapacity = idealIntArraySize(initialCapacity); |
103 | 4 | mKeys = new int[initialCapacity]; |
104 | 4 | mValues = new int[initialCapacity]; |
105 | } | |
106 | 4 | mSize = 0; |
107 | } | |
108 | ||
109 | 0 | @Override |
110 | public SparseIntArray clone() | |
111 | { | |
112 | 0 | SparseIntArray clone = null; |
113 | 0 | try |
114 | { | |
115 | 0 | clone = (SparseIntArray) super.clone(); |
116 | 0 | clone.mKeys = mKeys.clone(); |
117 | 0 | clone.mValues = mValues.clone(); |
118 | } catch (CloneNotSupportedException cnse) | |
119 | { | |
120 | /* ignore */ | |
121 | } | |
122 | 0 | return clone; |
123 | } | |
124 | ||
125 | /** | |
126 | * Gets the int mapped from the specified key, or <code>0</code> if no such | |
127 | * mapping has been made. | |
128 | */ | |
129 | 2 | public int get(int key) |
130 | { | |
131 | 2 | return get(key, 0); |
132 | } | |
133 | ||
134 | /** | |
135 | * Gets the int mapped from the specified key, or the specified value if no | |
136 | * such mapping has been made. | |
137 | */ | |
138 | 2 | public int get(int key, int valueIfKeyNotFound) |
139 | { | |
140 | 2 | int i = ContainerHelpers.binarySearch(mKeys, mSize, key); |
141 | 2 | if (i < 0) |
142 | { | |
143 | 0 | return valueIfKeyNotFound; |
144 | } | |
145 | else | |
146 | { | |
147 | 2 | return mValues[i]; |
148 | } | |
149 | } | |
150 | ||
151 | /** | |
152 | * Removes the mapping from the specified key, if there was any. | |
153 | */ | |
154 | 0 | public void delete(int key) |
155 | { | |
156 | 0 | int i = ContainerHelpers.binarySearch(mKeys, mSize, key); |
157 | 0 | if (i >= 0) |
158 | { | |
159 | 0 | removeAt(i); |
160 | } | |
161 | } | |
162 | ||
163 | /** | |
164 | * Removes the mapping at the given index. | |
165 | */ | |
166 | 0 | public void removeAt(int index) |
167 | { | |
168 | 0 | System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); |
169 | 0 | System.arraycopy(mValues, index + 1, mValues, index, |
170 | mSize - (index + 1)); | |
171 | 0 | mSize--; |
172 | } | |
173 | ||
174 | /** | |
175 | * Adds a mapping from the specified key to the specified value, replacing the | |
176 | * previous mapping from the specified key if there was one. | |
177 | */ | |
178 | 7 | public void put(int key, int value) |
179 | { | |
180 | 7 | int i = ContainerHelpers.binarySearch(mKeys, mSize, key); |
181 | 7 | if (i >= 0) |
182 | { | |
183 | 0 | mValues[i] = value; |
184 | } | |
185 | else | |
186 | { | |
187 | 7 | i = ~i; |
188 | 7 | if (mSize >= mKeys.length) |
189 | { | |
190 | 0 | int n = idealIntArraySize(mSize + 1); |
191 | 0 | int[] nkeys = new int[n]; |
192 | 0 | int[] nvalues = new int[n]; |
193 | // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n); | |
194 | 0 | System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); |
195 | 0 | System.arraycopy(mValues, 0, nvalues, 0, mValues.length); |
196 | 0 | mKeys = nkeys; |
197 | 0 | mValues = nvalues; |
198 | } | |
199 | 7 | if (mSize - i != 0) |
200 | { | |
201 | // Log.e("SparseIntArray", "move " + (mSize - i)); | |
202 | 1 | System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); |
203 | 1 | System.arraycopy(mValues, i, mValues, i + 1, mSize - i); |
204 | } | |
205 | 7 | mKeys[i] = key; |
206 | 7 | mValues[i] = value; |
207 | 7 | mSize++; |
208 | } | |
209 | } | |
210 | ||
211 | /** | |
212 | * Returns the number of key-value mappings that this SparseIntArray currently | |
213 | * stores. | |
214 | */ | |
215 | 0 | public int size() |
216 | { | |
217 | 0 | return mSize; |
218 | } | |
219 | ||
220 | /** | |
221 | * Given an index in the range <code>0...size()-1</code>, returns the key from | |
222 | * the <code>index</code>th key-value mapping that this SparseIntArray stores. | |
223 | * | |
224 | * <p> | |
225 | * The keys corresponding to indices in ascending order are guaranteed to be | |
226 | * in ascending order, e.g., <code>keyAt(0)</code> will return the smallest | |
227 | * key and <code>keyAt(size()-1)</code> will return the largest key. | |
228 | * </p> | |
229 | */ | |
230 | 0 | public int keyAt(int index) |
231 | { | |
232 | 0 | return mKeys[index]; |
233 | } | |
234 | ||
235 | /** | |
236 | * Given an index in the range <code>0...size()-1</code>, returns the value | |
237 | * from the <code>index</code>th key-value mapping that this SparseIntArray | |
238 | * stores. | |
239 | * | |
240 | * <p> | |
241 | * The values corresponding to indices in ascending order are guaranteed to be | |
242 | * associated with keys in ascending order, e.g., <code>valueAt(0)</code> will | |
243 | * return the value associated with the smallest key and | |
244 | * <code>valueAt(size()-1)</code> will return the value associated with the | |
245 | * largest key. | |
246 | * </p> | |
247 | */ | |
248 | 0 | public int valueAt(int index) |
249 | { | |
250 | 0 | return mValues[index]; |
251 | } | |
252 | ||
253 | /** | |
254 | * Returns the index for which {@link #keyAt} would return the specified key, | |
255 | * or a negative number if the specified key is not mapped. | |
256 | */ | |
257 | 0 | public int indexOfKey(int key) |
258 | { | |
259 | 0 | return ContainerHelpers.binarySearch(mKeys, mSize, key); |
260 | } | |
261 | ||
262 | /** | |
263 | * Returns an index for which {@link #valueAt} would return the specified key, | |
264 | * or a negative number if no keys map to the specified value. Beware that | |
265 | * this is a linear search, unlike lookups by key, and that multiple keys can | |
266 | * map to the same value and this will find only one of them. | |
267 | */ | |
268 | 0 | public int indexOfValue(int value) |
269 | { | |
270 | 0 | for (int i = 0; i < mSize; i++) |
271 | { | |
272 | 0 | if (mValues[i] == value) |
273 | { | |
274 | 0 | return i; |
275 | } | |
276 | } | |
277 | 0 | return -1; |
278 | } | |
279 | ||
280 | /** | |
281 | * Removes all key-value mappings from this SparseIntArray. | |
282 | */ | |
283 | 0 | public void clear() |
284 | { | |
285 | 0 | mSize = 0; |
286 | } | |
287 | ||
288 | /** | |
289 | * Puts a key/value pair into the array, optimizing for the case where the key | |
290 | * is greater than all existing keys in the array. | |
291 | */ | |
292 | 0 | public void append(int key, int value) |
293 | { | |
294 | 0 | if (mSize != 0 && key <= mKeys[mSize - 1]) |
295 | { | |
296 | 0 | put(key, value); |
297 | 0 | return; |
298 | } | |
299 | 0 | int pos = mSize; |
300 | 0 | if (pos >= mKeys.length) |
301 | { | |
302 | 0 | int n = idealIntArraySize(pos + 1); |
303 | 0 | int[] nkeys = new int[n]; |
304 | 0 | int[] nvalues = new int[n]; |
305 | // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n); | |
306 | 0 | System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); |
307 | 0 | System.arraycopy(mValues, 0, nvalues, 0, mValues.length); |
308 | 0 | mKeys = nkeys; |
309 | 0 | mValues = nvalues; |
310 | } | |
311 | 0 | mKeys[pos] = key; |
312 | 0 | mValues[pos] = value; |
313 | 0 | mSize = pos + 1; |
314 | } | |
315 | ||
316 | /** | |
317 | * Inlined here by copying from com.android.internal.util.ArrayUtils | |
318 | * | |
319 | * @param i | |
320 | * @return | |
321 | */ | |
322 | 4 | public static int idealIntArraySize(int need) |
323 | { | |
324 | 4 | return idealByteArraySize(need * 4) / 4; |
325 | } | |
326 | ||
327 | /** | |
328 | * Inlined here by copying from com.android.internal.util.ArrayUtils | |
329 | * | |
330 | * @param i | |
331 | * @return | |
332 | */ | |
333 | 4 | public static int idealByteArraySize(int need) |
334 | { | |
335 | 8 | for (int i = 4; i < 32; i++) |
336 | { | |
337 | 8 | if (need <= (1 << i) - 12) |
338 | { | |
339 | 4 | return (1 << i) - 12; |
340 | } | |
341 | } | |
342 | ||
343 | 0 | return need; |
344 | } | |
345 | ||
346 | /** | |
347 | * {@inheritDoc} | |
348 | * | |
349 | * <p> | |
350 | * This implementation composes a string by iterating over its mappings. | |
351 | */ | |
352 | 0 | @Override |
353 | public String toString() | |
354 | { | |
355 | 0 | if (size() <= 0) |
356 | { | |
357 | 0 | return "{}"; |
358 | } | |
359 | 0 | StringBuilder buffer = new StringBuilder(mSize * 28); |
360 | 0 | buffer.append('{'); |
361 | 0 | for (int i = 0; i < mSize; i++) |
362 | { | |
363 | 0 | if (i > 0) |
364 | { | |
365 | 0 | buffer.append(", "); |
366 | } | |
367 | 0 | int key = keyAt(i); |
368 | 0 | buffer.append(key); |
369 | 0 | buffer.append('='); |
370 | 0 | int value = valueAt(i); |
371 | 0 | buffer.append(value); |
372 | } | |
373 | 0 | buffer.append('}'); |
374 | 0 | return buffer.toString(); |
375 | } | |
376 | ||
377 | /** | |
378 | * Method (copied from put) added for Jalview to efficiently increment a key's | |
379 | * value if present, else add it with the given value. This avoids a double | |
380 | * binary search (once to get the value, again to put the updated value). | |
381 | * | |
382 | * @param key | |
383 | * @oparam toAdd | |
384 | * @return the new value of the count for the key | |
385 | * @throw ArithmeticException if the result would exceed the maximum value of | |
386 | * an int | |
387 | */ | |
388 | 7 | public int add(int key, int toAdd) |
389 | { | |
390 | 7 | int newValue = toAdd; |
391 | 7 | int i = ContainerHelpers.binarySearch(mKeys, mSize, key); |
392 | 7 | if (i >= 0) |
393 | { | |
394 | 6 | checkOverflow(mValues[i], toAdd); |
395 | 4 | mValues[i] += toAdd; |
396 | 4 | newValue = mValues[i]; |
397 | } | |
398 | else | |
399 | { | |
400 | 1 | i = ~i; |
401 | 1 | if (mSize >= mKeys.length) |
402 | { | |
403 | 0 | int n = idealIntArraySize(mSize + 1); |
404 | 0 | int[] nkeys = new int[n]; |
405 | 0 | int[] nvalues = new int[n]; |
406 | 0 | System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); |
407 | 0 | System.arraycopy(mValues, 0, nvalues, 0, mValues.length); |
408 | 0 | mKeys = nkeys; |
409 | 0 | mValues = nvalues; |
410 | } | |
411 | 1 | if (mSize - i != 0) |
412 | { | |
413 | 0 | System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); |
414 | 0 | System.arraycopy(mValues, i, mValues, i + 1, mSize - i); |
415 | } | |
416 | 1 | mKeys[i] = key; |
417 | 1 | mValues[i] = toAdd; |
418 | 1 | mSize++; |
419 | } | |
420 | 5 | return newValue; |
421 | } | |
422 | ||
423 | /** | |
424 | * Throws ArithmeticException if adding addend to value would exceed the range | |
425 | * of int | |
426 | * | |
427 | * @param value | |
428 | * @param addend | |
429 | */ | |
430 | 21 | static void checkOverflow(int value, int addend) |
431 | { | |
432 | /* | |
433 | * test cases being careful to avoid overflow while testing! | |
434 | */ | |
435 | 21 | if (addend > 0) |
436 | { | |
437 | 9 | if (value > 0 && Integer.MAX_VALUE - value < addend) |
438 | { | |
439 | 4 | throw new ArithmeticException( |
440 | "Integer overflow adding " + addend + " to " + value); | |
441 | } | |
442 | } | |
443 | 12 | else if (addend < 0) |
444 | { | |
445 | 10 | if (value < 0 && Integer.MIN_VALUE - value > addend) |
446 | { | |
447 | 4 | throw new ArithmeticException( |
448 | "Integer underflow adding " + addend + " to " + value); | |
449 | } | |
450 | } | |
451 | } | |
452 | } |