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