JAL-3933 configure root logger console appender to stderr (2.11.2 version)
[jalview.git] / src / jalview / ext / android / SparseIntArray.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  * 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   public SparseIntArray()
82   {
83     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   public SparseIntArray(int initialCapacity)
94   {
95     if (initialCapacity == 0)
96     {
97       mKeys = ContainerHelpers.EMPTY_INTS;
98       mValues = ContainerHelpers.EMPTY_INTS;
99     }
100     else
101     {
102       initialCapacity = idealIntArraySize(initialCapacity);
103       mKeys = new int[initialCapacity];
104       mValues = new int[initialCapacity];
105     }
106     mSize = 0;
107   }
108
109   @Override
110   public SparseIntArray clone()
111   {
112     SparseIntArray clone = null;
113     try
114     {
115       clone = (SparseIntArray) super.clone();
116       clone.mKeys = mKeys.clone();
117       clone.mValues = mValues.clone();
118     } catch (CloneNotSupportedException cnse)
119     {
120       /* ignore */
121     }
122     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   public int get(int key)
130   {
131     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   public int get(int key, int valueIfKeyNotFound)
139   {
140     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
141     if (i < 0)
142     {
143       return valueIfKeyNotFound;
144     }
145     else
146     {
147       return mValues[i];
148     }
149   }
150
151   /**
152    * Removes the mapping from the specified key, if there was any.
153    */
154   public void delete(int key)
155   {
156     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
157     if (i >= 0)
158     {
159       removeAt(i);
160     }
161   }
162
163   /**
164    * Removes the mapping at the given index.
165    */
166   public void removeAt(int index)
167   {
168     System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
169     System.arraycopy(mValues, index + 1, mValues, index, mSize
170             - (index + 1));
171     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   public void put(int key, int value)
179   {
180     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
181     if (i >= 0)
182     {
183       mValues[i] = value;
184     }
185     else
186     {
187       i = ~i;
188       if (mSize >= mKeys.length)
189       {
190         int n = idealIntArraySize(mSize + 1);
191         int[] nkeys = new int[n];
192         int[] nvalues = new int[n];
193         // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n);
194         System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
195         System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
196         mKeys = nkeys;
197         mValues = nvalues;
198       }
199       if (mSize - i != 0)
200       {
201         // Log.e("SparseIntArray", "move " + (mSize - i));
202         System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
203         System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
204       }
205       mKeys[i] = key;
206       mValues[i] = value;
207       mSize++;
208     }
209   }
210
211   /**
212    * Returns the number of key-value mappings that this SparseIntArray currently
213    * stores.
214    */
215   public int size()
216   {
217     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   public int keyAt(int index)
231   {
232     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   public int valueAt(int index)
249   {
250     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   public int indexOfKey(int key)
258   {
259     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   public int indexOfValue(int value)
269   {
270     for (int i = 0; i < mSize; i++)
271     {
272       if (mValues[i] == value)
273       {
274         return i;
275       }
276     }
277     return -1;
278   }
279
280   /**
281    * Removes all key-value mappings from this SparseIntArray.
282    */
283   public void clear()
284   {
285     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   public void append(int key, int value)
293   {
294     if (mSize != 0 && key <= mKeys[mSize - 1])
295     {
296       put(key, value);
297       return;
298     }
299     int pos = mSize;
300     if (pos >= mKeys.length)
301     {
302       int n = idealIntArraySize(pos + 1);
303       int[] nkeys = new int[n];
304       int[] nvalues = new int[n];
305       // Log.e("SparseIntArray", "grow " + mKeys.length + " to " + n);
306       System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
307       System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
308       mKeys = nkeys;
309       mValues = nvalues;
310     }
311     mKeys[pos] = key;
312     mValues[pos] = value;
313     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   public static int idealIntArraySize(int need)
323   {
324     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   public static int idealByteArraySize(int need)
334   {
335     for (int i = 4; i < 32; i++)
336     {
337       if (need <= (1 << i) - 12)
338       {
339         return (1 << i) - 12;
340       }
341     }
342
343     return need;
344   }
345
346   /**
347    * {@inheritDoc}
348    *
349    * <p>
350    * This implementation composes a string by iterating over its mappings.
351    */
352   @Override
353   public String toString()
354   {
355     if (size() <= 0)
356     {
357       return "{}";
358     }
359     StringBuilder buffer = new StringBuilder(mSize * 28);
360     buffer.append('{');
361     for (int i = 0; i < mSize; i++)
362     {
363       if (i > 0)
364       {
365         buffer.append(", ");
366       }
367       int key = keyAt(i);
368       buffer.append(key);
369       buffer.append('=');
370       int value = valueAt(i);
371       buffer.append(value);
372     }
373     buffer.append('}');
374     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   public int add(int key, int toAdd)
389   {
390     int newValue = toAdd;
391     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
392     if (i >= 0)
393     {
394       checkOverflow(mValues[i], toAdd);
395       mValues[i] += toAdd;
396       newValue = mValues[i];
397     }
398     else
399     {
400       i = ~i;
401       if (mSize >= mKeys.length)
402       {
403         int n = idealIntArraySize(mSize + 1);
404         int[] nkeys = new int[n];
405         int[] nvalues = new int[n];
406         System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
407         System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
408         mKeys = nkeys;
409         mValues = nvalues;
410       }
411       if (mSize - i != 0)
412       {
413         System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
414         System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
415       }
416       mKeys[i] = key;
417       mValues[i] = toAdd;
418       mSize++;
419     }
420     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   static void checkOverflow(int value, int addend)
431   {
432     /*
433      * test cases being careful to avoid overflow while testing!
434      */
435     if (addend > 0)
436     {
437       if (value > 0 && Integer.MAX_VALUE - value < addend)
438       {
439         throw new ArithmeticException("Integer overflow adding " + addend
440                 + " to  " + value);
441       }
442     }
443     else if (addend < 0)
444     {
445       if (value < 0 && Integer.MIN_VALUE - value > addend)
446       {
447         throw new ArithmeticException("Integer underflow adding " + addend
448                 + " to  " + value);
449       }
450     }
451   }
452 }