Clover icon

Coverage Report

  1. Project Clover database Mon Nov 18 2024 09:38:20 GMT
  2. Package jalview.ext.android

File SparseDoubleArray.java

 

Coverage histogram

../../../img/srcFileCovDistChart0.png
54% of files have more coverage

Code metrics

44
119
21
1
463
252
45
0.38
5.67
21
2.14

Classes

Class Line # Actions
SparseDoubleArray 70 119 45
0.00%
 

Contributing tests

No tests hitting this source file were found.

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