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