Clover icon

Coverage Report

  1. Project Clover database Thu Nov 28 2024 18:06:40 GMT
  2. Package jalview.ext.android

File SparseIntArray.java

 

Coverage histogram

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

Code metrics

44
114
20
1
452
246
46
0.4
5.7
20
2.3

Classes

Class Line # Actions
SparseIntArray 70 114 46
0.4101123541%
 

Contributing tests

This file is covered by 5 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    * 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 toggle 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 toggle 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 toggle @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 toggle 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 toggle 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 toggle 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 toggle 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 toggle 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 toggle 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 toggle 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 toggle 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 toggle 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 toggle 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 toggle 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 toggle 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 toggle 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 toggle 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 toggle @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 toggle 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 toggle 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    }
  • Report generated by OpenClover v 4.4.1 on Thu Nov 28 2024 18:14:23 GMT using coverage data from Thu Nov 28 2024 18:14:06 GMT.
  • OpenClover is free and open-source software.