Clover icon

Coverage Report

  1. Project Clover database Mon Nov 11 2024 20:42:03 GMT
  2. Package jalview.ext.android

File SparseShortArray.java

 

Coverage histogram

../../../img/srcFileCovDistChart5.png
42% of files have more coverage

Code metrics

38
119
20
1
462
243
42
0.35
5.95
20
2.1

Classes

Class Line # Actions
SparseShortArray 73 119 42
0.446327744.6%
 

Contributing tests

This file is covered by 32 tests. .

Source view

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 toggle 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  610 toggle public SparseShortArray(int initialCapacity)
97    {
98  610 if (initialCapacity == 0)
99    {
100  0 mKeys = new short[0];
101  0 mValues = new short[0];
102    }
103    else
104    {
105  610 initialCapacity = idealShortArraySize(initialCapacity);
106  610 mKeys = new short[initialCapacity];
107  610 mValues = new short[initialCapacity];
108    }
109  610 mSize = 0;
110    }
111   
 
112  0 toggle @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 toggle 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 toggle 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 toggle 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 toggle 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 toggle 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  1520 toggle public int size()
232    {
233  1520 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  428 toggle public short keyAt(int index)
248    {
249  428 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  856 toggle public short valueAt(int index)
266    {
267  856 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 toggle 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 toggle 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 toggle 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 toggle 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  27979 toggle public static void checkOverflow(int value)
346    {
347  27979 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  610 toggle public static int idealShortArraySize(int need)
360    {
361  610 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  610 toggle public static int idealByteArraySize(int need)
371    {
372  617 for (int i = 4; i < 32; i++)
373    {
374  617 if (need <= (1 << i) - 12)
375    {
376  610 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 toggle @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  13966 toggle public int add(int key, int toAdd)
427    {
428  13966 int newValue = toAdd;
429  13966 checkOverflow(key);
430  13966 int i = ContainerHelpers.binarySearch(mKeys, mSize, (short) key);
431  13965 if (i >= 0)
432    {
433  13133 checkOverflow(toAdd + mValues[i]);
434  13128 mValues[i] += (short) toAdd;
435  13128 newValue = mValues[i];
436    }
437    else
438    {
439  833 checkOverflow(toAdd);
440  833 i = ~i;
441  833 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  833 if (mSize - i != 0)
452    {
453  132 System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
454  132 System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
455    }
456  833 mKeys[i] = (short) key;
457  832 mValues[i] = (short) toAdd;
458  833 mSize++;
459    }
460  13960 return newValue;
461    }
462    }
  • Report generated by OpenClover v 4.4.1 on Mon Nov 11 2024 20:49:40 GMT using coverage data from Mon Nov 11 2024 20:49:29 GMT.
  • OpenClover is free and open-source software.