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