gt:         return binarySearch(mKeys, 0, mSize, key);
context: package utils;
  
  import java.util.StringJoiner;
  
  /**
   * Copied from Android project: android.util.SparseArray.java
   * <p>
   * SparseArrays map integers to Objects. Unlike a normal array of Objects, there can be gaps in the
   * indices. It is intended to be more efficient than using a HashMap to map Integers to Objects.
   */
  public class SparseArray<E> implements Cloneable {
      private static final Object DELETED = new Object();
      private boolean mGarbage = false;
      private int[] mKeys;
      private Object[] mValues;
      private int mSize;
  
      /**
       * Creates a new SparseArray containing no mappings.
       */
      public SparseArray() {
          this(10);
      }
  
      /**
       * Creates a new SparseArray containing no mappings that will not require any additional memory
       * allocation to store the specified number of mappings.
       */
      public SparseArray(int initialCapacity) {
          initialCapacity = idealIntArraySize(initialCapacity);
  
          mKeys = new int[initialCapacity];
          mValues = new Object[initialCapacity];
          mSize = 0;
      }
  
      // Warning: returns ~index and not -(index+1) like trove and jdk do
      private static int binarySearch(int[] a, int start, int len, int key) {
          int high = start + len, low = start - 1, guess;
          while (high - low > 1) {
              // use >>> for average or we could get an integer overflow.
              guess = (high + low) >>> 1;
  
              if (a[guess] < key) {
                  low = guess;
              } else {
                  high = guess;
              }
          }
  
          if (high == start + len) {
              return ~(start + len);
          } else if (a[high] == key) {
              return high;
          } else {
              return ~high;
          }
      }
  
      public static int idealIntArraySize(int need) {
          return idealByteArraySize(need * 4) / 4;
      }
  
      public static int idealByteArraySize(int need) {
          for (int i = 4; i < 32; i++) {
              if (need <= (1 << i) - 12) {
                  return (1 << i) - 12;
              }
          }
          return need;
      }
  
      @Override
      @SuppressWarnings("unchecked")
      public SparseArray<E> clone() {
          SparseArray<E> clone = null;
          try {
              clone = (SparseArray<E>) super.clone();
              clone.mKeys = mKeys.clone();
              clone.mValues = mValues.clone();
          } catch (CloneNotSupportedException cnse) {
              /* ignore */
          }
          return clone;
      }
  
      /**
       * Gets the Object mapped from the specified key, or <code>null</code> if no such mapping has
       * been made.
       */
      public E get(int key) {
          return get(key, null);
      }
  
      /**
       * Gets the Object mapped from the specified key, or the specified Object if no such mapping has
       * been made.
       */
      @SuppressWarnings("unchecked")
      public E get(int key, E valueIfKeyNotFound) {
          int i = binarySearch(mKeys, 0, mSize, key);
  
          if (i < 0 || mValues[i] == DELETED) {
              return valueIfKeyNotFound;
          } else {
              return (E) mValues[i];
          }
      }
  
      /**
       * Removes the mapping from the specified key, if there was any.
       */
      public void remove(int key) {
          int i = binarySearch(mKeys, 0, mSize, key);
          if (i >= 0) {
              if (mValues[i] != DELETED) {
                  mValues[i] = DELETED;
                  mGarbage = true;
              }
          }
      }
  
      /**
       * Removes the mapping at the specified index.
       */
      public void removeAt(int index) {
          if (mValues[index] != DELETED) {
              mValues[index] = DELETED;
              mGarbage = true;
          }
      }
  
      private void gc() {
          // Log.e("SparseArray", "gc start with " + mSize);
  
          int n = mSize;
          int o = 0;
          int[] keys = mKeys;
          Object[] values = mValues;
  
          for (int i = 0; i < n; i++) {
              Object val = values[i];
  
              if (val != DELETED) {
                  if (i != o) {
                      keys[o] = keys[i];
                      values[o] = val;
                      values[i] = null;
                  }
  
                  o++;
              }
          }
  
          mGarbage = false;
          mSize = o;
  
          // Log.e("SparseArray", "gc end with " + mSize);
      }
  
      /**
       * Adds a mapping from the specified key to the specified value, replacing the previous mapping
       * from the specified key if there was one.
       */
      public void put(int key, E value) {
          int i = binarySearch(mKeys, 0, mSize, key);
  
          if (i >= 0) {
              mValues[i] = value;
          } else {
              i = ~i;
  
              if (i < mSize && mValues[i] == DELETED) {
                  mKeys[i] = key;
                  mValues[i] = value;
                  return;
              }
  
              if (mGarbage && mSize >= mKeys.length) {
                  gc();
  
                  // Search again because indices may have changed.
                  i = ~binarySearch(mKeys, 0, mSize, key);
              }
  
              if (mSize >= mKeys.length) {
                  int n = idealIntArraySize(mSize + 1);
  
                  int[] nkeys = new int[n];
                  Object[] nvalues = new Object[n];
  
                  // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);
                  System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
                  System.arraycopy(mValues, 0, nvalues, 0, mValues.length);
  
                  mKeys = nkeys;
                  mValues = nvalues;
              }
  
              if (mSize - i != 0) {
                  // Log.e("SparseArray", "move " + (mSize - i));
                  System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
                  System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
              }
  
              mKeys[i] = key;
              mValues[i] = value;
              mSize++;
          }
      }
  
      /**
       * Returns the number of key-value mappings that this SparseArray currently stores.
       */
      public int getSize() {
          if (mGarbage) {
              gc();
          }
  
          return mSize;
      }
  
      /**
       * Given an index in the range <code>0...size()-1</code>, returns the key from the
       * <code>index</code>th key-value mapping that this SparseArray stores.
       */
      public int keyAt(int index) {
          if (mGarbage) {
              gc();
          }
  
          return mKeys[index];
      }
  
      /**
       * Given an index in the range <code>0...size()-1</code>, returns the value from the
       * <code>index</code>th key-value mapping that this SparseArray stores.
       */
      @SuppressWarnings("unchecked")
      public E valueAt(int index) {
          if (mGarbage) {
              gc();
          }
  
          return (E) mValues[index];
      }
  
      /**
       * Given an index in the range <code>0...size()-1</code>, sets a new value for the
       * <code>index</code>th key-value mapping that this SparseArray stores.
       */
      public void setValueAt(int index, E value) {
          if (mGarbage) {
              gc();
          }
  
          mValues[index] = value;
      }
  
      /**
       * Returns the index for which {@link #keyAt} would return the specified key, or a negative
       * number if the specified key is not mapped.
       */
      public int indexOfKey(int key) {
          if (mGarbage) {
              gc();
          }
  
  