JAL-3933 configure root logger console appender to stderr (2.11.2 version)
[jalview.git] / src / jalview / ext / android / SparseDoubleArray.java
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   public SparseDoubleArray()
82   {
83     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   public SparseDoubleArray(int initialCapacity)
94   {
95     if (initialCapacity == 0)
96     {
97       mKeys = ContainerHelpers.EMPTY_INTS;
98       mValues = ContainerHelpers.EMPTY_DOUBLES;
99     }
100     else
101     {
102       initialCapacity = idealDoubleArraySize(initialCapacity);
103       mKeys = new int[initialCapacity];
104       mValues = new double[initialCapacity];
105     }
106     mSize = 0;
107   }
108
109   /**
110    * Constructor given an array of double values; stores the non-zero values
111    * 
112    * @param row
113    */
114   public SparseDoubleArray(double[] row)
115   {
116     this();
117     for (int i = 0; i < row.length; i++)
118     {
119       if (row[i] != 0d)
120       {
121         put(i, row[i]);
122       }
123     }
124   }
125
126   @Override
127   public SparseDoubleArray clone()
128   {
129     SparseDoubleArray clone = null;
130     try
131     {
132       clone = (SparseDoubleArray) super.clone();
133       clone.mKeys = mKeys.clone();
134       clone.mValues = mValues.clone();
135     } catch (CloneNotSupportedException cnse)
136     {
137       /* ignore */
138     }
139     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   public double get(int key)
147   {
148     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   public double get(int key, double valueIfKeyNotFound)
156   {
157     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
158     if (i < 0)
159     {
160       return valueIfKeyNotFound;
161     }
162     else
163     {
164       return mValues[i];
165     }
166   }
167
168   /**
169    * Removes the mapping from the specified key, if there was any.
170    */
171   public void delete(int key)
172   {
173     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
174     if (i >= 0)
175     {
176       removeAt(i);
177     }
178   }
179
180   /**
181    * Removes the mapping at the given index.
182    */
183   public void removeAt(int index)
184   {
185     System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
186     System.arraycopy(mValues, index + 1, mValues, index, mSize
187             - (index + 1));
188     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   public void put(int key, double value)
196   {
197     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
198     if (i >= 0)
199     {
200       mValues[i] = value;
201     }
202     else
203     {
204       i = ~i;
205       if (mSize >= mKeys.length)
206       {
207         int n = idealDoubleArraySize(mSize + 1);
208         int[] nkeys = new int[n];
209         double[] nvalues = new double[n];
210         // Log.e("SparseDoubleArray", "grow " + mKeys.length + " to " + n);
211         System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
212         System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
213         mKeys = nkeys;
214         mValues = nvalues;
215       }
216       if (mSize - i != 0)
217       {
218         // Log.e("SparseDoubleArray", "move " + (mSize - i));
219         System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
220         System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
221       }
222       mKeys[i] = key;
223       mValues[i] = value;
224       mSize++;
225     }
226   }
227
228   /**
229    * Returns the number of key-value mappings that this SparseDoubleArray
230    * currently stores.
231    */
232   public int size()
233   {
234     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   public int keyAt(int index)
249   {
250     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   public double valueAt(int index)
267   {
268     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   public int indexOfKey(int key)
276   {
277     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   public int indexOfValue(double value)
287   {
288     for (int i = 0; i < mSize; i++)
289     {
290       if (mValues[i] == value)
291       {
292         return i;
293       }
294     }
295     return -1;
296   }
297
298   /**
299    * Removes all key-value mappings from this SparseDoubleArray.
300    */
301   public void clear()
302   {
303     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   public void append(int key, double value)
311   {
312     if (mSize != 0 && key <= mKeys[mSize - 1])
313     {
314       put(key, value);
315       return;
316     }
317     int pos = mSize;
318     if (pos >= mKeys.length)
319     {
320       int n = idealDoubleArraySize(pos + 1);
321       int[] nkeys = new int[n];
322       double[] nvalues = new double[n];
323       // Log.e("SparseDoubleArray", "grow " + mKeys.length + " to " + n);
324       System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
325       System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
326       mKeys = nkeys;
327       mValues = nvalues;
328     }
329     mKeys[pos] = key;
330     mValues[pos] = value;
331     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   public static int idealDoubleArraySize(int need)
342   {
343     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   public static int idealByteArraySize(int need)
353   {
354     for (int i = 4; i < 32; i++)
355     {
356       if (need <= (1 << i) - 12)
357       {
358         return (1 << i) - 12;
359       }
360     }
361
362     return need;
363   }
364
365   /**
366    * {@inheritDoc}
367    *
368    * <p>
369    * This implementation composes a string by iterating over its mappings.
370    */
371   @Override
372   public String toString()
373   {
374     if (size() <= 0)
375     {
376       return "{}";
377     }
378     StringBuilder buffer = new StringBuilder(mSize * 28);
379     buffer.append('{');
380     for (int i = 0; i < mSize; i++)
381     {
382       if (i > 0)
383       {
384         buffer.append(", ");
385       }
386       int key = keyAt(i);
387       buffer.append(key);
388       buffer.append('=');
389       double value = valueAt(i);
390       buffer.append(value);
391     }
392     buffer.append('}');
393     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   public double add(int key, double toAdd)
406   {
407     double newValue = toAdd;
408     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
409     if (i >= 0)
410     {
411       mValues[i] += toAdd;
412       newValue = mValues[i];
413     }
414     else
415     {
416       i = ~i;
417       if (mSize >= mKeys.length)
418       {
419         int n = idealDoubleArraySize(mSize + 1);
420         int[] nkeys = new int[n];
421         double[] nvalues = new double[n];
422         System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
423         System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
424         mKeys = nkeys;
425         mValues = nvalues;
426       }
427       if (mSize - i != 0)
428       {
429         System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
430         System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
431       }
432       mKeys[i] = key;
433       mValues[i] = toAdd;
434       mSize++;
435     }
436     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   public double divide(int key, double divisor)
449   {
450     double newValue = 0d;
451     if (divisor == 0d)
452     {
453       return newValue;
454     }
455     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
456     if (i >= 0)
457     {
458       mValues[i] /= divisor;
459       newValue = mValues[i];
460     }
461     return newValue;
462   }
463 }