content: /*
   * Copyright (C) 2006 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package im.actor.runtime.collections;
  
  /**
   * SparseArrays map integers to Objects.  Unlike a normal array of Objects,
   * there can be gaps in the indices.  It is intended to be more memory efficient
   * than using a HashMap to map Integers to Objects, both because it avoids
   * auto-boxing keys and its data structure doesn't rely on an extra entry object
   * for each mapping.
   * <p></p>
   * <p>Note that this container keeps its mappings in an array data structure,
   * using a binary search to find keys.  The implementation is not intended to be appropriate for
   * data structures
   * that may contain large numbers of items.  It is generally slower than a traditional
   * HashMap, since lookups require a binary search and adds and removes require inserting
   * and deleting entries in the array.  For containers holding up to hundreds of items,
   * the performance difference is not significant, less than 50%.</p>
   * <p></p>
   * <p>To help with performance, the container includes an optimization when removing
   * keys: instead of compacting its array immediately, it leaves the removed entry marked
   * as deleted.  The entry can then be re-used for the same key, or compacted later in
   * a single garbage collection step of all removed entries.  This garbage collection will
   * need to be performed at any time the array needs to be grown or the the map size or
   * entry values are retrieved.</p>
   * <p></p>
   * <p>It is possible to iterate over the items in this container using
   * {@link #keyAt(int)} and {@link #valueAt(int)}. Iterating over the keys using
   * <code>keyAt(int)</code> with ascending values of the index will return the
   * keys in ascending order, or the values corresponding to the keys in ascending
   * order in the case of <code>valueAt(int)</code>.</p>
   */
  
  // Disabling Bounds checks for speeding up calculations
  
  /*-[
  #define J2OBJC_DISABLE_ARRAY_BOUND_CHECKS 1
  ]-*/
  
  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.  If you supply an initial capacity of 0, the
       * sparse array will be initialized with a light-weight representation
       * not requiring any additional array allocations.
       */
      public SparseArray(int initialCapacity) {
          if (initialCapacity == 0) {
              mKeys = ContainerHelpers.EMPTY_INTS;
              mValues = ContainerHelpers.EMPTY_OBJECTS;
          } else {
              initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
              mKeys = new int[initialCapacity];
              mValues = new Object[initialCapacity];
          }
          mSize = 0;
      }
  
  
      /**
       * 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 = ContainerHelpers.binarySearch(mKeys, 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 delete(int key) {
          int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
  
          if (i >= 0) {
              if (mValues[i] != DELETED) {
                  mValues[i] = DELETED;
                  mGarbage = true;
              }
          }
      }
  
      /**
       * Alias for {@link #delete(int)}.
       */
      public void remove(int key) {
          delete(key);
      }
  
      /**
       * Removes the mapping at the specified index.
       */
      public void removeAt(int index) {
          if (mValues[index] != DELETED) {
              mValues[index] = DELETED;
              mGarbage = true;
          }
      }
  
      /**
       * Remove a range of mappings as a batch.
       *
       * @param index Index to begin at
       * @param size  Number of mappings to remove
       */
      public void removeAtRange(int index, int size) {
          final int end = Math.min(mSize, index + size);
          for (int i = index; i < end; i++) {
              removeAt(i);
          }
      }
  
      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 = ContainerHelpers.binarySearch(mKeys, 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 = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
              }
  
              if (mSize >= mKeys.length) {
                  int n = ArrayUtils.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 size() {
          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.
       * <p></p>
       * <p>The keys corresponding to indices in ascending order are guaranteed to
       * be in ascending order, e.g., <code>keyAt(0)</code> will return the
       * smallest key and <code>keyAt(size()-1)</code> will return the largest
       * key.</p>
       */
      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.
       * <p></p>
       * <p>The values corresponding to indices in ascending order are guaranteed
       * to be associated with keys in ascending order, e.g.,
       * <code>valueAt(0)</code> will return the value associated with the
       * smallest key and <code>valueAt(size()-1)</code> will return the value
       * associated with the largest key.</p>
       */
      @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();
          }
  
          return ContainerHelpers.binarySearch(mKeys, mSize, key);
      }
  
      public boolean containsKey(int key) {
          return indexOfKey(key) >= 0;
      }
  
      /**
       * Returns an index for which {@link #valueAt} would return the
       * specified key, or a negative number if no keys map to the
       * specified value.
       * <p>Beware that this is a linear search, unlike lookups by key,
       * and that multiple keys can map to the same value and this will
       * find only one of them.
       * <p>Note also that unlike most collections' {@code indexOf} methods,
       * this method compares values using {@code ==} rather than {@code equals}.
       */
      public int indexOfValue(E value) {
          if (mGarbage) {
              gc();
          }
  
          for (int i = 0; i < mSize; i++)
              if (mValues[i] == value)
                  return i;
  
          return -1;
      }
  
      /**
       * Removes all key-value mappings from this SparseArray.
       */
      public void clear() {
          int n = mSize;
          Object[] values = mValues;
  
          for (int i = 0; i < n; i++) {
              values[i] = null;
          }
  
          mSize = 0;
          mGarbage = false;
      }
  
      /**
       * Puts a key/value pair into the array, optimizing for the case where
       * the key is greater than all existing keys in the array.
       */
      public void append(int key, E value) {
          if (mSize != 0 && key <= mKeys[mSize - 1]) {
              put(key, value);
              return;
          }
  
          if (mGarbage && mSize >= mKeys.length) {
              gc();
          }
  
          int pos = mSize;
          if (pos >= mKeys.length) {
              int n = ArrayUtils.idealIntArraySize(pos + 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;
          }
  
          mKeys[pos] = key;
          mValues[pos] = value;
          mSize = pos + 1;
      }
  
      /**
       * {@inheritDoc}
       * <p></p>
       * <p>This implementation composes a string by iterating over its mappings. If
       * this map contains itself as a value, the string "(this Map)"
       * will appear in its place.
       */
      @Override
      public String toString() {
          if (size() <= 0) {
              return "{}";
          }
  
          StringBuilder buffer = new StringBuilder(mSize * 28);
          buffer.append('{');
          for (int i = 0; i < mSize; i++) {
              if (i > 0) {
                  buffer.append(", ");
              }
              int key = keyAt(i);
              buffer.append(key);
              buffer.append('=');
              Object value = valueAt(i);
              if (value != this) {
                  buffer.append(value);
              } else {
                  buffer.append("(this Map)");
              }
          }
          buffer.append('}');
          return buffer.toString();
      }
  }
  