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 }