src/jalview/ext/android/SparseDoubleArray.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.ext.android;
  22
  23 /*
  24  * Copyright (C) 2006 The Android Open Source Project
  25  *
  26  * Licensed under the Apache License, Version 2.0 (the "License");
  27  * you may not use this file except in compliance with the License.
  28  * You may obtain a copy of the License at
  29  *
  30  *      http://www.apache.org/licenses/LICENSE-2.0
  31  *
  32  * Unless required by applicable law or agreed to in writing, software
  33  * distributed under the License is distributed on an "AS IS" BASIS,
  34  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  35  * See the License for the specific language governing permissions and
  36  * limitations under the License.
  37  */
  38 /**
  39  * SparseDoubleArray map integers to doubles. Unlike a normal array of integers,
  40  * there can be gaps in the indices. It is intended to be more memory efficient
  41  * than using a HashMap to map Integer to Double, both because it avoids
  42  * auto-boxing keys and values and its data structure doesn't rely on an extra
  43  * entry object for each mapping.
  44  *
  45  * <p>
  46  * Note that this container keeps its mappings in an array data structure, using
  47  * a binary search to find keys. The implementation is not intended to be
  48  * appropriate for data structures that may contain large numbers of items. It
  49  * is generally slower than a traditional HashMap, since lookups require a
  50  * binary search and adds and removes require inserting and deleting entries in
  51  * the array. For containers holding up to hundreds of items, the performance
  52  * difference is not significant, less than 50%.
  53  * </p>
  54  *
  55  * <p>
  56  * It is possible to iterate over the items in this container using
  57  * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using
  58  * <code>keyAt(int)</code> with ascending values of the index will return the
  59  * keys in ascending order, or the values corresponding to the keys in ascending
  60  * order in the case of <code>valueAt(int)<code>.
  61  * </p>
  62  */
  63
  64 /*
  65  * Change log:
  66  * Jan 2017 cloned from SparseIntArray for Jalview to support SparseMatrix
  67  * - SparseDoubleArray(double[]) constructor added
  68  * - multiply() added for more efficient multiply (or divide) of a value
  69  */
  70 public class SparseDoubleArray implements Cloneable
  71 {
  72   private int[] mKeys;
  73
  74   private double[] mValues;
  75
  76   private int mSize;
  77
  78   /**
  79    * Creates a new SparseDoubleArray containing no mappings.
  80    */
  81   public SparseDoubleArray()
  82   {
  83     this(10);
  84   }
  85
  86   /**
  87    * Creates a new SparseDoubleArray containing no mappings that will not
  88    * require any additional memory allocation to store the specified number of
  89    * mappings. If you supply an initial capacity of 0, the sparse array will be
  90    * initialized with a light-weight representation not requiring any additional
  91    * array allocations.
  92    */
  93   public SparseDoubleArray(int initialCapacity)
  94   {
  95     if (initialCapacity == 0)
  96     {
  97       mKeys = ContainerHelpers.EMPTY_INTS;
  98       mValues = ContainerHelpers.EMPTY_DOUBLES;
  99     }
 100     else
 101     {
 102       initialCapacity = idealDoubleArraySize(initialCapacity);
 103       mKeys = new int[initialCapacity];
 104       mValues = new double[initialCapacity];
 105     }
 106     mSize = 0;
 107   }
 108
 109   /**
 110    * Constructor given an array of double values; stores the non-zero values
 111    *
 112    * @param row
 113    */
 114   public SparseDoubleArray(double[] row)
 115   {
 116     this();
 117     for (int i = 0; i < row.length; i++)
 118     {
 119       if (row[i] != 0d)
 120       {
 121         put(i, row[i]);
 122       }
 123     }
 124   }
 125
 126   @Override
 127   public SparseDoubleArray clone()
 128   {
 129     SparseDoubleArray clone = null;
 130     try
 131     {
 132       clone = (SparseDoubleArray) super.clone();
 133       clone.mKeys = mKeys.clone();
 134       clone.mValues = mValues.clone();
 135     } catch (CloneNotSupportedException cnse)
 136     {
 137       /* ignore */
 138     }
 139     return clone;
 140   }
 141
 142   /**
 143    * Gets the value mapped from the specified key, or <code>0</code> if no such
 144    * mapping has been made.
 145    */
 146   public double get(int key)
 147   {
 148     return get(key, 0d);
 149   }
 150
 151   /**
 152    * Gets the int mapped from the specified key, or the specified value if no
 153    * such mapping has been made.
 154    */
 155   public double get(int key, double valueIfKeyNotFound)
 156   {
 157     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 158     if (i < 0)
 159     {
 160       return valueIfKeyNotFound;
 161     }
 162     else
 163     {
 164       return mValues[i];
 165     }
 166   }
 167
 168   /**
 169    * Removes the mapping from the specified key, if there was any.
 170    */
 171   public void delete(int key)
 172   {
 173     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 174     if (i >= 0)
 175     {
 176       removeAt(i);
 177     }
 178   }
 179
 180   /**
 181    * Removes the mapping at the given index.
 182    */
 183   public void removeAt(int index)
 184   {
 185     System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
 186     System.arraycopy(mValues, index + 1, mValues, index,
 187             mSize - (index + 1));
 188     mSize--;
 189   }
 190
 191   /**
 192    * Adds a mapping from the specified key to the specified value, replacing the
 193    * previous mapping from the specified key if there was one.
 194    */
 195   public void put(int key, double value)
 196   {
 197     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 198     if (i >= 0)
 199     {
 200       mValues[i] = value;
 201     }
 202     else
 203     {
 204       i = ~i;
 205       if (mSize >= mKeys.length)
 206       {
 207         int n = idealDoubleArraySize(mSize + 1);
 208         int[] nkeys = new int[n];
 209         double[] nvalues = new double[n];
 210         // Log.e("SparseDoubleArray", "grow " + mKeys.length + " to " + n);
 211         System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
 212         System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
 213         mKeys = nkeys;
 214         mValues = nvalues;
 215       }
 216       if (mSize - i != 0)
 217       {
 218         // Log.e("SparseDoubleArray", "move " + (mSize - i));
 219         System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
 220         System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
 221       }
 222       mKeys[i] = key;
 223       mValues[i] = value;
 224       mSize++;
 225     }
 226   }
 227
 228   /**
 229    * Returns the number of key-value mappings that this SparseDoubleArray
 230    * currently stores.
 231    */
 232   public int size()
 233   {
 234     return mSize;
 235   }
 236
 237   /**
 238    * Given an index in the range <code>0...size()-1</code>, returns the key from
 239    * the <code>index</code>th key-value mapping that this SparseDoubleArray
 240    * stores.
 241    *
 242    * <p>
 243    * The keys corresponding to indices in ascending order are guaranteed to be
 244    * in ascending order, e.g., <code>keyAt(0)</code> will return the smallest
 245    * key and <code>keyAt(size()-1)</code> will return the largest key.
 246    * </p>
 247    */
 248   public int keyAt(int index)
 249   {
 250     return mKeys[index];
 251   }
 252
 253   /**
 254    * Given an index in the range <code>0...size()-1</code>, returns the value
 255    * from the <code>index</code>th key-value mapping that this SparseDoubleArray
 256    * stores.
 257    *
 258    * <p>
 259    * The values corresponding to indices in ascending order are guaranteed to be
 260    * associated with keys in ascending order, e.g., <code>valueAt(0)</code> will
 261    * return the value associated with the smallest key and
 262    * <code>valueAt(size()-1)</code> will return the value associated with the
 263    * largest key.
 264    * </p>
 265    */
 266   public double valueAt(int index)
 267   {
 268     return mValues[index];
 269   }
 270
 271   /**
 272    * Returns the index for which {@link #keyAt} would return the specified key,
 273    * or a negative number if the specified key is not mapped.
 274    */
 275   public int indexOfKey(int key)
 276   {
 277     return ContainerHelpers.binarySearch(mKeys, mSize, key);
 278   }
 279
 280   /**
 281    * Returns an index for which {@link #valueAt} would return the specified key,
 282    * or a negative number if no keys map to the specified value. Beware that
 283    * this is a linear search, unlike lookups by key, and that multiple keys can
 284    * map to the same value and this will find only one of them.
 285    */
 286   public int indexOfValue(double value)
 287   {
 288     for (int i = 0; i < mSize; i++)
 289     {
 290       if (mValues[i] == value)
 291       {
 292         return i;
 293       }
 294     }
 295     return -1;
 296   }
 297
 298   /**
 299    * Removes all key-value mappings from this SparseDoubleArray.
 300    */
 301   public void clear()
 302   {
 303     mSize = 0;
 304   }
 305
 306   /**
 307    * Puts a key/value pair into the array, optimizing for the case where the key
 308    * is greater than all existing keys in the array.
 309    */
 310   public void append(int key, double value)
 311   {
 312     if (mSize != 0 && key <= mKeys[mSize - 1])
 313     {
 314       put(key, value);
 315       return;
 316     }
 317     int pos = mSize;
 318     if (pos >= mKeys.length)
 319     {
 320       int n = idealDoubleArraySize(pos + 1);
 321       int[] nkeys = new int[n];
 322       double[] nvalues = new double[n];
 323       // Log.e("SparseDoubleArray", "grow " + mKeys.length + " to " + n);
 324       System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
 325       System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
 326       mKeys = nkeys;
 327       mValues = nvalues;
 328     }
 329     mKeys[pos] = key;
 330     mValues[pos] = value;
 331     mSize = pos + 1;
 332   }
 333
 334   /**
 335    * Created by analogy with
 336    * com.android.internal.util.ArrayUtils#idealLongArraySize
 337    *
 338    * @param i
 339    * @return
 340    */
 341   public static int idealDoubleArraySize(int need)
 342   {
 343     return idealByteArraySize(need * 8) / 8;
 344   }
 345
 346   /**
 347    * Inlined here by copying from com.android.internal.util.ArrayUtils
 348    *
 349    * @param i
 350    * @return
 351    */
 352   public static int idealByteArraySize(int need)
 353   {
 354     for (int i = 4; i < 32; i++)
 355     {
 356       if (need <= (1 << i) - 12)
 357       {
 358         return (1 << i) - 12;
 359       }
 360     }
 361
 362     return need;
 363   }
 364
 365   /**
 366    * {@inheritDoc}
 367    *
 368    * <p>
 369    * This implementation composes a string by iterating over its mappings.
 370    */
 371   @Override
 372   public String toString()
 373   {
 374     if (size() <= 0)
 375     {
 376       return "{}";
 377     }
 378     StringBuilder buffer = new StringBuilder(mSize * 28);
 379     buffer.append('{');
 380     for (int i = 0; i < mSize; i++)
 381     {
 382       if (i > 0)
 383       {
 384         buffer.append(", ");
 385       }
 386       int key = keyAt(i);
 387       buffer.append(key);
 388       buffer.append('=');
 389       double value = valueAt(i);
 390       buffer.append(value);
 391     }
 392     buffer.append('}');
 393     return buffer.toString();
 394   }
 395
 396   /**
 397    * Method (copied from put) added for Jalview to efficiently increment a key's
 398    * value if present, else add it with the given value. This avoids a double
 399    * binary search (once to get the value, again to put the updated value).
 400    *
 401    * @param key
 402    * @oparam toAdd
 403    * @return the new value for the key
 404    */
 405   public double add(int key, double toAdd)
 406   {
 407     double newValue = toAdd;
 408     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 409     if (i >= 0)
 410     {
 411       mValues[i] += toAdd;
 412       newValue = mValues[i];
 413     }
 414     else
 415     {
 416       i = ~i;
 417       if (mSize >= mKeys.length)
 418       {
 419         int n = idealDoubleArraySize(mSize + 1);
 420         int[] nkeys = new int[n];
 421         double[] nvalues = new double[n];
 422         System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
 423         System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
 424         mKeys = nkeys;
 425         mValues = nvalues;
 426       }
 427       if (mSize - i != 0)
 428       {
 429         System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
 430         System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
 431       }
 432       mKeys[i] = key;
 433       mValues[i] = toAdd;
 434       mSize++;
 435     }
 436     return newValue;
 437   }
 438
 439   /**
 440    * Method added for Jalview to efficiently multiply a key's value if present,
 441    * else do nothing. This avoids a double binary search (once to get the value,
 442    * again to put the updated value).
 443    *
 444    * @param key
 445    * @oparam toAdd
 446    * @return the new value for the key
 447    */
 448   public double divide(int key, double divisor)
 449   {
 450     double newValue = 0d;
 451     if (divisor == 0d)
 452     {
 453       return newValue;
 454     }
 455     int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 456     if (i >= 0)
 457     {
 458       mValues[i] /= divisor;
 459       newValue = mValues[i];
 460     }
 461     return newValue;
 462   }
 463 }