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