Clover icon

jalviewX

  1. Project Clover database Wed Oct 31 2018 15:13:58 GMT
  2. Package jalview.ext.android

File SparseShortArray.java

 

Coverage histogram

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

Code metrics

38
119
20
1
442
243
42
0.35
5.95
20
2.1

Classes

Class Line # Actions
SparseShortArray 53 119 42 101
0.4293785442.9%
 

Contributing tests

This file is covered by 26 tests. .

Source view

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