src/jalview/ext/android/SparseDoubleArray.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  * SparseDoubleArray map integers to doubles. 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 Integer to Double, 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  * Change log:
  46  * Jan 2017 cloned from SparseIntArray for Jalview to support SparseMatrix
  47  * - SparseDoubleArray(double[]) constructor added
  48  * - multiply() added for more efficient multiply (or divide) of a value
  49  */
  50 public class SparseDoubleArray implements Cloneable
  51 {
  52   private int[] mKeys;
  53
  54   private double[] mValues;
  55
  56   private int mSize;
  57
  58   /**
  59    * Creates a new SparseDoubleArray containing no mappings.
  60    */
  61   public SparseDoubleArray()
  62   {
  63     this(10);
  64   }
  65
  66   /**
  67    * Creates a new SparseDoubleArray containing no mappings that will not
  68    * require any additional memory allocation to store the specified number of
  69    * mappings. 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 SparseDoubleArray(int initialCapacity)
  74   {
  75     if (initialCapacity == 0)
  76     {
  77       mKeys = ContainerHelpers.EMPTY_INTS;
  78       mValues = ContainerHelpers.EMPTY_DOUBLES;
  79     }
  80     else
  81     {
  82       initialCapacity = idealDoubleArraySize(initialCapacity);
  83       mKeys = new int[initialCapacity];
  84       mValues = new double[initialCapacity];
  85     }
  86     mSize = 0;
  87   }
  88
  89   /**
  90    * Constructor given an array of double values; stores the non-zero values
  91    *
  92    * @param row
  93    */
  94   public SparseDoubleArray(double[] row)
  95   {
  96     this();
  97     for (int i = 0; i < row.length; i++)
  98     {
  99       if (row[i] != 0d)
 100       {
 101         put(i, row[i]);
 102       }
 103     }
 104   }
 105
 106   @Override
 107   public SparseDoubleArray clone()
 108   {
 109     SparseDoubleArray clone = null;
 110     try
 111     {
 112       clone = (SparseDoubleArray) super.clone();
 113       clone.mKeys = mKeys.clone();
 114       clone.mValues = mValues.clone();
 115     } catch (CloneNotSupportedException cnse)
 116     {
 117       /* ignore */
 118     }
 119     return clone;
 120   }
 121
 122   /**
 123    * Gets the value mapped from the specified key, or <code>0</code> if no such
 124    * mapping has been made.
 125    */
 126   public double get(int key)
 127   {
 128     return get(key, 0d);
 129   }
 130
 131   /**
 132    * Gets the int mapped from the specified key, or the specified value if no
 133    * such mapping has been made.
 134    */
 135   public double get(int key, double valueIfKeyNotFound)
 136   {
 137     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 138     if (i < 0)
 139     {
 140       return valueIfKeyNotFound;
 141     }
 142     else
 143     {
 144       return mValues[i];
 145     }
 146   }
 147
 148   /**
 149    * Removes the mapping from the specified key, if there was any.
 150    */
 151   public void delete(int key)
 152   {
 153     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 154     if (i >= 0)
 155     {
 156       removeAt(i);
 157     }
 158   }
 159
 160   /**
 161    * Removes the mapping at the given index.
 162    */
 163   public void removeAt(int index)
 164   {
 165     System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
 166     System.arraycopy(mValues, index + 1, mValues, index, mSize
 167             - (index + 1));
 168     mSize--;
 169   }
 170
 171   /**
 172    * Adds a mapping from the specified key to the specified value, replacing the
 173    * previous mapping from the specified key if there was one.
 174    */
 175   public void put(int key, double value)
 176   {
 177     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 178     if (i >= 0)
 179     {
 180       mValues[i] = value;
 181     }
 182     else
 183     {
 184       i = ~i;
 185       if (mSize >= mKeys.length)
 186       {
 187         int n = idealDoubleArraySize(mSize + 1);
 188         int[] nkeys = new int[n];
 189         double[] nvalues = new double[n];
 190         // Log.e("SparseDoubleArray", "grow " + mKeys.length + " to " + n);
 191         System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
 192         System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
 193         mKeys = nkeys;
 194         mValues = nvalues;
 195       }
 196       if (mSize - i != 0)
 197       {
 198         // Log.e("SparseDoubleArray", "move " + (mSize - i));
 199         System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
 200         System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
 201       }
 202       mKeys[i] = key;
 203       mValues[i] = value;
 204       mSize++;
 205     }
 206   }
 207
 208   /**
 209    * Returns the number of key-value mappings that this SparseDoubleArray
 210    * currently stores.
 211    */
 212   public int size()
 213   {
 214     return mSize;
 215   }
 216
 217   /**
 218    * Given an index in the range <code>0...size()-1</code>, returns the key from
 219    * the <code>index</code>th key-value mapping that this SparseDoubleArray
 220    * stores.
 221    *
 222    * <p>
 223    * The keys corresponding to indices in ascending order are guaranteed to be
 224    * in ascending order, e.g., <code>keyAt(0)</code> will return the smallest
 225    * key and <code>keyAt(size()-1)</code> will return the largest key.
 226    * </p>
 227    */
 228   public int keyAt(int index)
 229   {
 230     return mKeys[index];
 231   }
 232
 233   /**
 234    * Given an index in the range <code>0...size()-1</code>, returns the value
 235    * from the <code>index</code>th key-value mapping that this SparseDoubleArray
 236    * stores.
 237    *
 238    * <p>
 239    * The values corresponding to indices in ascending order are guaranteed to be
 240    * associated with keys in ascending order, e.g., <code>valueAt(0)</code> will
 241    * return the value associated with the smallest key and
 242    * <code>valueAt(size()-1)</code> will return the value associated with the
 243    * largest key.
 244    * </p>
 245    */
 246   public double valueAt(int index)
 247   {
 248     return mValues[index];
 249   }
 250
 251   /**
 252    * Returns the index for which {@link #keyAt} would return the specified key,
 253    * or a negative number if the specified key is not mapped.
 254    */
 255   public int indexOfKey(int key)
 256   {
 257     return ContainerHelpers.binarySearch(mKeys, mSize, 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(double 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 SparseDoubleArray.
 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, double 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 = idealDoubleArraySize(pos + 1);
 301       int[] nkeys = new int[n];
 302       double[] nvalues = new double[n];
 303       // Log.e("SparseDoubleArray", "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     mKeys[pos] = key;
 310     mValues[pos] = value;
 311     mSize = pos + 1;
 312   }
 313
 314   /**
 315    * Created by analogy with
 316    * com.android.internal.util.ArrayUtils#idealLongArraySize
 317    *
 318    * @param i
 319    * @return
 320    */
 321   public static int idealDoubleArraySize(int need)
 322   {
 323     return idealByteArraySize(need * 8) / 8;
 324   }
 325
 326   /**
 327    * Inlined here by copying from com.android.internal.util.ArrayUtils
 328    *
 329    * @param i
 330    * @return
 331    */
 332   public static int idealByteArraySize(int need)
 333   {
 334     for (int i = 4; i < 32; i++)
 335     {
 336       if (need <= (1 << i) - 12)
 337       {
 338         return (1 << i) - 12;
 339       }
 340     }
 341
 342     return need;
 343   }
 344
 345   /**
 346    * {@inheritDoc}
 347    *
 348    * <p>
 349    * This implementation composes a string by iterating over its mappings.
 350    */
 351   @Override
 352   public String toString()
 353   {
 354     if (size() <= 0)
 355     {
 356       return "{}";
 357     }
 358     StringBuilder buffer = new StringBuilder(mSize * 28);
 359     buffer.append('{');
 360     for (int i = 0; i < mSize; i++)
 361     {
 362       if (i > 0)
 363       {
 364         buffer.append(", ");
 365       }
 366       int key = keyAt(i);
 367       buffer.append(key);
 368       buffer.append('=');
 369       double value = valueAt(i);
 370       buffer.append(value);
 371     }
 372     buffer.append('}');
 373     return buffer.toString();
 374   }
 375
 376   /**
 377    * Method (copied from put) added for Jalview to efficiently increment a key's
 378    * value if present, else add it with the given value. This avoids a double
 379    * binary search (once to get the value, again to put the updated value).
 380    *
 381    * @param key
 382    * @oparam toAdd
 383    * @return the new value for the key
 384    */
 385   public double add(int key, double toAdd)
 386   {
 387     double newValue = toAdd;
 388     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 389     if (i >= 0)
 390     {
 391       mValues[i] += toAdd;
 392       newValue = mValues[i];
 393     }
 394     else
 395     {
 396       i = ~i;
 397       if (mSize >= mKeys.length)
 398       {
 399         int n = idealDoubleArraySize(mSize + 1);
 400         int[] nkeys = new int[n];
 401         double[] nvalues = new double[n];
 402         System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
 403         System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
 404         mKeys = nkeys;
 405         mValues = nvalues;
 406       }
 407       if (mSize - i != 0)
 408       {
 409         System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
 410         System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
 411       }
 412       mKeys[i] = key;
 413       mValues[i] = toAdd;
 414       mSize++;
 415     }
 416     return newValue;
 417   }
 418
 419   /**
 420    * Method added for Jalview to efficiently multiply a key's value if present,
 421    * else do nothing. This avoids a double binary search (once to get the value,
 422    * again to put the updated value).
 423    *
 424    * @param key
 425    * @oparam toAdd
 426    * @return the new value for the key
 427    */
 428   public double divide(int key, double divisor)
 429   {
 430     double newValue = 0d;
 431     if (divisor == 0d)
 432     {
 433       return newValue;
 434     }
 435     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 436     if (i >= 0)
 437     {
 438       mValues[i] /= divisor;
 439       newValue = mValues[i];
 440     }
 441     return newValue;
 442   }
 443 }