Class |
Line # |
Actions |
|||
---|---|---|---|---|---|
SparseShortArray | 73 | 119 | 42 |
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 | * SparseShortArrays map shorts to shorts. Unlike a normal array of shorts, | |
40 | * there can be gaps in the indices. It is intended to be more memory efficient | |
41 | * than using a HashMap to map Shorts to Shorts, 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 | * Added to Jalview September 2016. A copy of SparseIntArray designed to store | |
66 | * short values (to minimise space usage). | |
67 | * <p> | |
68 | * Note that operations append, put, add throw ArithmeticException if either the | |
69 | * key or the resulting value overflows the range of a short. Calling code | |
70 | * should trap and handle this, for example by switching to using a | |
71 | * SparseIntArray instead. | |
72 | */ | |
73 | public class SparseShortArray implements Cloneable | |
74 | { | |
75 | private short[] mKeys; | |
76 | ||
77 | private short[] mValues; | |
78 | ||
79 | private int mSize; | |
80 | ||
81 | /** | |
82 | * Creates a new SparseShortArray containing no mappings. | |
83 | */ | |
84 | 2 | public SparseShortArray() |
85 | { | |
86 | 2 | this(10); |
87 | } | |
88 | ||
89 | /** | |
90 | * Creates a new SparseShortArray containing no mappings that will not require | |
91 | * any additional memory allocation to store the specified number of mappings. | |
92 | * If you supply an initial capacity of 0, the sparse array will be | |
93 | * initialized with a light-weight representation not requiring any additional | |
94 | * array allocations. | |
95 | */ | |
96 | 438 | public SparseShortArray(int initialCapacity) |
97 | { | |
98 | 438 | if (initialCapacity == 0) |
99 | { | |
100 | 0 | mKeys = new short[0]; |
101 | 0 | mValues = new short[0]; |
102 | } | |
103 | else | |
104 | { | |
105 | 438 | initialCapacity = idealShortArraySize(initialCapacity); |
106 | 438 | mKeys = new short[initialCapacity]; |
107 | 438 | mValues = new short[initialCapacity]; |
108 | } | |
109 | 438 | mSize = 0; |
110 | } | |
111 | ||
112 | 0 | @Override |
113 | public SparseShortArray clone() | |
114 | { | |
115 | 0 | SparseShortArray clone = null; |
116 | 0 | try |
117 | { | |
118 | 0 | clone = (SparseShortArray) super.clone(); |
119 | 0 | clone.mKeys = mKeys.clone(); |
120 | 0 | clone.mValues = mValues.clone(); |
121 | } catch (CloneNotSupportedException cnse) | |
122 | { | |
123 | /* ignore */ | |
124 | } | |
125 | 0 | return clone; |
126 | } | |
127 | ||
128 | /** | |
129 | * Gets the int mapped from the specified key, or <code>0</code> if no such | |
130 | * mapping has been made. | |
131 | */ | |
132 | 9 | public int get(int key) |
133 | { | |
134 | 9 | return get(key, 0); |
135 | } | |
136 | ||
137 | /** | |
138 | * Gets the int mapped from the specified key, or the specified value if no | |
139 | * such mapping has been made. | |
140 | * | |
141 | * @throws ArithmeticException | |
142 | * if key is outside the range of a short value | |
143 | */ | |
144 | 9 | public int get(int key, int valueIfKeyNotFound) |
145 | { | |
146 | 9 | checkOverflow(key); |
147 | 9 | int i = ContainerHelpers.binarySearch(mKeys, mSize, (short) key); |
148 | 9 | if (i < 0) |
149 | { | |
150 | 0 | return valueIfKeyNotFound; |
151 | } | |
152 | else | |
153 | { | |
154 | 9 | return mValues[i]; |
155 | } | |
156 | } | |
157 | ||
158 | /** | |
159 | * Removes the mapping from the specified key, if there was any. | |
160 | * | |
161 | * @throws ArithmeticException | |
162 | * if key is outside the range of a short value | |
163 | */ | |
164 | 0 | public void delete(int key) |
165 | { | |
166 | 0 | checkOverflow(key); |
167 | 0 | int i = ContainerHelpers.binarySearch(mKeys, mSize, (short) key); |
168 | 0 | if (i >= 0) |
169 | { | |
170 | 0 | removeAt(i); |
171 | } | |
172 | } | |
173 | ||
174 | /** | |
175 | * Removes the mapping at the given index. | |
176 | */ | |
177 | 0 | public void removeAt(int index) |
178 | { | |
179 | 0 | System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1)); |
180 | 0 | System.arraycopy(mValues, index + 1, mValues, index, |
181 | mSize - (index + 1)); | |
182 | 0 | mSize--; |
183 | } | |
184 | ||
185 | /** | |
186 | * Adds a mapping from the specified key to the specified value, replacing the | |
187 | * previous mapping from the specified key if there was one. | |
188 | * | |
189 | * @throws ArithmeticException | |
190 | * if either argument is outside the range of a short value | |
191 | */ | |
192 | 21 | public void put(int key, int value) |
193 | { | |
194 | 21 | checkOverflow(key); |
195 | 19 | checkOverflow(value); |
196 | 17 | int i = ContainerHelpers.binarySearch(mKeys, mSize, (short) key); |
197 | 17 | if (i >= 0) |
198 | { | |
199 | 2 | mValues[i] = (short) value; |
200 | } | |
201 | else | |
202 | { | |
203 | 15 | i = ~i; |
204 | 15 | if (mSize >= mKeys.length) |
205 | { | |
206 | 0 | int n = idealShortArraySize(mSize + 1); |
207 | 0 | short[] nkeys = new short[n]; |
208 | 0 | short[] nvalues = new short[n]; |
209 | // Log.e("SparseShortArray", "grow " + mKeys.length + " to " + n); | |
210 | 0 | System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); |
211 | 0 | System.arraycopy(mValues, 0, nvalues, 0, mValues.length); |
212 | 0 | mKeys = nkeys; |
213 | 0 | mValues = nvalues; |
214 | } | |
215 | 15 | if (mSize - i != 0) |
216 | { | |
217 | // Log.e("SparseShortArray", "move " + (mSize - i)); | |
218 | 4 | System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); |
219 | 4 | System.arraycopy(mValues, i, mValues, i + 1, mSize - i); |
220 | } | |
221 | 15 | mKeys[i] = (short) key; |
222 | 15 | mValues[i] = (short) value; |
223 | 15 | mSize++; |
224 | } | |
225 | } | |
226 | ||
227 | /** | |
228 | * Returns the number of key-value mappings that this SparseShortArray | |
229 | * currently stores. | |
230 | */ | |
231 | 1100 | public int size() |
232 | { | |
233 | 1100 | return mSize; |
234 | } | |
235 | ||
236 | /** | |
237 | * Given an index in the range <code>0...size()-1</code>, returns the key from | |
238 | * the <code>index</code>th key-value mapping that this SparseShortArray | |
239 | * stores. | |
240 | * | |
241 | * <p> | |
242 | * The keys corresponding to indices in ascending order are guaranteed to be | |
243 | * in ascending order, e.g., <code>keyAt(0)</code> will return the smallest | |
244 | * key and <code>keyAt(size()-1)</code> will return the largest key. | |
245 | * </p> | |
246 | */ | |
247 | 322 | public short keyAt(int index) |
248 | { | |
249 | 322 | return mKeys[index]; |
250 | } | |
251 | ||
252 | /** | |
253 | * Given an index in the range <code>0...size()-1</code>, returns the value | |
254 | * from the <code>index</code>th key-value mapping that this SparseShortArray | |
255 | * stores. | |
256 | * | |
257 | * <p> | |
258 | * The values corresponding to indices in ascending order are guaranteed to be | |
259 | * associated with keys in ascending order, e.g., <code>valueAt(0)</code> will | |
260 | * return the value associated with the smallest key and | |
261 | * <code>valueAt(size()-1)</code> will return the value associated with the | |
262 | * largest key. | |
263 | * </p> | |
264 | */ | |
265 | 608 | public short valueAt(int index) |
266 | { | |
267 | 608 | return mValues[index]; |
268 | } | |
269 | ||
270 | /** | |
271 | * Returns the index for which {@link #keyAt} would return the specified key, | |
272 | * or a negative number if the specified key is not mapped. | |
273 | * | |
274 | * @throws ArithmeticException | |
275 | * if key is outside the range of a short value | |
276 | */ | |
277 | 0 | public int indexOfKey(int key) |
278 | { | |
279 | 0 | checkOverflow(key); |
280 | 0 | return ContainerHelpers.binarySearch(mKeys, mSize, (short) key); |
281 | } | |
282 | ||
283 | /** | |
284 | * Returns an index for which {@link #valueAt} would return the specified key, | |
285 | * or a negative number if no keys map to the specified value. Beware that | |
286 | * this is a linear search, unlike lookups by key, and that multiple keys can | |
287 | * map to the same value and this will find only one of them. | |
288 | */ | |
289 | 0 | public int indexOfValue(int value) |
290 | { | |
291 | 0 | for (int i = 0; i < mSize; i++) |
292 | { | |
293 | 0 | if (mValues[i] == value) |
294 | { | |
295 | 0 | return i; |
296 | } | |
297 | } | |
298 | 0 | return -1; |
299 | } | |
300 | ||
301 | /** | |
302 | * Removes all key-value mappings from this SparseShortArray. | |
303 | */ | |
304 | 0 | public void clear() |
305 | { | |
306 | 0 | mSize = 0; |
307 | } | |
308 | ||
309 | /** | |
310 | * Puts a key/value pair into the array, optimizing for the case where the key | |
311 | * is greater than all existing keys in the array. | |
312 | */ | |
313 | 0 | public void append(int key, int value) |
314 | { | |
315 | 0 | if (mSize != 0 && key <= mKeys[mSize - 1]) |
316 | { | |
317 | 0 | put(key, value); |
318 | 0 | return; |
319 | } | |
320 | 0 | int pos = mSize; |
321 | 0 | if (pos >= mKeys.length) |
322 | { | |
323 | 0 | int n = idealShortArraySize(pos + 1); |
324 | 0 | short[] nkeys = new short[n]; |
325 | 0 | short[] nvalues = new short[n]; |
326 | // Log.e("SparseShortArray", "grow " + mKeys.length + " to " + n); | |
327 | 0 | System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); |
328 | 0 | System.arraycopy(mValues, 0, nvalues, 0, mValues.length); |
329 | 0 | mKeys = nkeys; |
330 | 0 | mValues = nvalues; |
331 | } | |
332 | 0 | checkOverflow(key); |
333 | 0 | checkOverflow(value); |
334 | 0 | mKeys[pos] = (short) key; |
335 | 0 | mValues[pos] = (short) value; |
336 | 0 | mSize = pos + 1; |
337 | } | |
338 | ||
339 | /** | |
340 | * Throws an exception if the value is outside the range of a short. | |
341 | * | |
342 | * @param value | |
343 | * @throws ArithmeticException | |
344 | */ | |
345 | 18749 | public static void checkOverflow(int value) |
346 | { | |
347 | 18749 | if (value > Short.MAX_VALUE || value < Short.MIN_VALUE) |
348 | { | |
349 | 8 | throw new ArithmeticException(String.valueOf(value)); |
350 | } | |
351 | } | |
352 | ||
353 | /** | |
354 | * Inlined here by copying from com.android.internal.util.ArrayUtils | |
355 | * | |
356 | * @param i | |
357 | * @return | |
358 | */ | |
359 | 438 | public static int idealShortArraySize(int need) |
360 | { | |
361 | 438 | return idealByteArraySize(need * 2) / 2; |
362 | } | |
363 | ||
364 | /** | |
365 | * Inlined here by copying from com.android.internal.util.ArrayUtils | |
366 | * | |
367 | * @param i | |
368 | * @return | |
369 | */ | |
370 | 438 | public static int idealByteArraySize(int need) |
371 | { | |
372 | 445 | for (int i = 4; i < 32; i++) |
373 | { | |
374 | 445 | if (need <= (1 << i) - 12) |
375 | { | |
376 | 438 | return (1 << i) - 12; |
377 | } | |
378 | } | |
379 | ||
380 | 0 | return need; |
381 | } | |
382 | ||
383 | /** | |
384 | * {@inheritDoc} | |
385 | * | |
386 | * <p> | |
387 | * This implementation composes a string by iterating over its mappings. | |
388 | */ | |
389 | 0 | @Override |
390 | public String toString() | |
391 | { | |
392 | 0 | if (size() <= 0) |
393 | { | |
394 | 0 | return "{}"; |
395 | } | |
396 | 0 | StringBuilder buffer = new StringBuilder(mSize * 28); |
397 | 0 | buffer.append('{'); |
398 | 0 | for (int i = 0; i < mSize; i++) |
399 | { | |
400 | 0 | if (i > 0) |
401 | { | |
402 | 0 | buffer.append(", "); |
403 | } | |
404 | 0 | int key = keyAt(i); |
405 | 0 | buffer.append(key); |
406 | 0 | buffer.append('='); |
407 | 0 | int value = valueAt(i); |
408 | 0 | buffer.append(value); |
409 | } | |
410 | 0 | buffer.append('}'); |
411 | 0 | return buffer.toString(); |
412 | } | |
413 | ||
414 | /** | |
415 | * Method (copied from put) added for Jalview to efficiently increment a key's | |
416 | * value if present, else add it with the given value. This avoids a double | |
417 | * binary search (once to get the value, again to put the updated value). | |
418 | * | |
419 | * @param key | |
420 | * @oparam toAdd | |
421 | * @return the new value of the count for the key | |
422 | * @throws ArithmeticException | |
423 | * if key, or result of adding toAdd, is outside the range of a | |
424 | * short value | |
425 | */ | |
426 | 9350 | public int add(int key, int toAdd) |
427 | { | |
428 | 9350 | int newValue = toAdd; |
429 | 9350 | checkOverflow(key); |
430 | 9350 | int i = ContainerHelpers.binarySearch(mKeys, mSize, (short) key); |
431 | 9350 | if (i >= 0) |
432 | { | |
433 | 8765 | checkOverflow(toAdd + mValues[i]); |
434 | 8761 | mValues[i] += (short) toAdd; |
435 | 8761 | newValue = mValues[i]; |
436 | } | |
437 | else | |
438 | { | |
439 | 585 | checkOverflow(toAdd); |
440 | 585 | i = ~i; |
441 | 585 | if (mSize >= mKeys.length) |
442 | { | |
443 | 0 | int n = idealShortArraySize(mSize + 1); |
444 | 0 | short[] nkeys = new short[n]; |
445 | 0 | short[] nvalues = new short[n]; |
446 | 0 | System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length); |
447 | 0 | System.arraycopy(mValues, 0, nvalues, 0, mValues.length); |
448 | 0 | mKeys = nkeys; |
449 | 0 | mValues = nvalues; |
450 | } | |
451 | 585 | if (mSize - i != 0) |
452 | { | |
453 | 88 | System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i); |
454 | 88 | System.arraycopy(mValues, i, mValues, i + 1, mSize - i); |
455 | } | |
456 | 585 | mKeys[i] = (short) key; |
457 | 585 | mValues[i] = (short) toAdd; |
458 | 585 | mSize++; |
459 | } | |
460 | 9346 | return newValue; |
461 | } | |
462 | } |