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