geode-core/src/main/java/org/apache/geode/internal/cache/IdentityArrayList.java

/*
 * Copyright (C) 2002-2014 Sebastiano Vigna
 *
 * 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.
 */

/*
 * This is a modified version of the fastutil ObjectArrayList. It is modified to use identity checks
 * rather than equality checks for higher performance.
 */
package org.apache.geode.internal.cache;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.RandomAccess;

import it.unimi.dsi.fastutil.objects.AbstractObjectList;
import it.unimi.dsi.fastutil.objects.AbstractObjectListIterator;
import it.unimi.dsi.fastutil.objects.ObjectArrays;
import it.unimi.dsi.fastutil.objects.ObjectCollection;
import it.unimi.dsi.fastutil.objects.ObjectIterator;
import it.unimi.dsi.fastutil.objects.ObjectIterators;
import it.unimi.dsi.fastutil.objects.ObjectList;
import it.unimi.dsi.fastutil.objects.ObjectListIterator;

/**
 *
 *
 * A type-specific array-based list; provides some additional methods that use polymorphism to avoid
 * (un)boxing.
 *
 * <P>
 * This class implements a lightweight, fast, open, optimized, reuse-oriented version of array-based
 * lists. Instances of this class represent a list with an array that is enlarged as needed when new
 * entries are created (by doubling the current length), but is <em>never</em> made smaller (even on
 * a {@link #clear()}). A family of {@linkplain #trim() trimming methods} lets you control the size
 * of the backing array; this is particularly useful if you reuse instances of this class. Range
 * checks are equivalent to those of <code>java.util</code>'s classes, but they are delayed as much
 * as possible.
 *
 * <p>
 * The backing array is exposed by the {@link #elements()} method. If an instance of this class was
 * created {@linkplain #wrap(Object[],int) by wrapping}, backing-array reallocations will be
 * performed using reflection, so that {@link #elements()} can return an array of the same type of
 * the original array; the comments about efficiency made in
 * {@link it.unimi.dsi.fastutil.objects.ObjectArrays} apply here.
 *
 * <p>
 * This class implements the bulk methods <code>removeElements()</code>, <code>addElements()</code>
 * and <code>getElements()</code> using high-performance system calls (e.g.,
 * {@link System#arraycopy(Object,int,Object,int,int) System.arraycopy()} instead of expensive
 * loops.
 *
 * @see java.util.ArrayList
 */
public class IdentityArrayList<K> extends AbstractObjectList<K>
    implements RandomAccess, Cloneable, java.io.Serializable {
  private static final long serialVersionUID = 449125332499184497L;

  /** The initial default capacity of an array list. */
  public static final int DEFAULT_INITIAL_CAPACITY = 16;

  /**
   * Whether the backing array was passed to <code>wrap()</code>. In this case, we must reallocate
   * with the same type of array.
   */
  protected final boolean wrapped;

  /** The backing array. */
  protected transient K a[];

  /** The current actual size of the list (never greater than the backing-array length). */
  protected int size;

  private static final boolean ASSERTS = false;

  /**
   * Creates a new array list using a given array.
   *
   * <P>
   * This constructor is only meant to be used by the wrapping methods.
   *
   * @param a the array that will be used to back this array list.
   */
  @SuppressWarnings("unused")
  protected IdentityArrayList(final K a[], boolean dummy) {
    this.a = a;
    this.wrapped = true;
  }

  /**
   * Creates a new array list with given capacity.
   *
   * @param capacity the initial capacity of the array list (may be 0).
   */
  @SuppressWarnings("unchecked")
  public IdentityArrayList(final int capacity) {
    if (capacity < 0)
      throw new IllegalArgumentException("Initial capacity (" + capacity + ") is negative");
    a = (K[]) new Object[capacity];
    wrapped = false;
  }

  /**
   * Creates a new array list with {@link #DEFAULT_INITIAL_CAPACITY} capacity.
   */
  public IdentityArrayList() {
    this(DEFAULT_INITIAL_CAPACITY);
  }

  /**
   * Creates a new array list and fills it with a given collection.
   *
   * @param c a collection that will be used to fill the array list.
   */
  public IdentityArrayList(final Collection<? extends K> c) {
    this(c.size());
    size = ObjectIterators.unwrap(c.iterator(), a);
  }

  /**
   * Creates a new array list and fills it with a given type-specific collection.
   *
   * @param c a type-specific collection that will be used to fill the array list.
   */
  public IdentityArrayList(final ObjectCollection<? extends K> c) {
    this(c.size());
    size = ObjectIterators.unwrap(c.iterator(), a);
  }

  /**
   * Creates a new array list and fills it with a given type-specific list.
   *
   * @param l a type-specific list that will be used to fill the array list.
   */
  public IdentityArrayList(final ObjectList<? extends K> l) {
    this(l.size());
    l.getElements(0, a, 0, size = l.size());
  }

  /**
   * Creates a new array list and fills it with the elements of a given array.
   *
   * @param a an array whose elements will be used to fill the array list.
   */
  public IdentityArrayList(final K a[]) {
    this(a, 0, a.length);
  }

  /**
   * Creates a new array list and fills it with the elements of a given array.
   *
   * @param a an array whose elements will be used to fill the array list.
   * @param offset the first element to use.
   * @param length the number of elements to use.
   */
  public IdentityArrayList(final K a[], final int offset, final int length) {
    this(length);
    System.arraycopy(a, offset, this.a, 0, length);
    size = length;
  }

  /**
   * Creates a new array list and fills it with the elements returned by an iterator..
   *
   * @param i an iterator whose returned elements will fill the array list.
   */
  public IdentityArrayList(final Iterator<? extends K> i) {
    this();
    while (i.hasNext())
      this.add(i.next());
  }

  /**
   * Creates a new array list and fills it with the elements returned by a type-specific iterator..
   *
   * @param i a type-specific iterator whose returned elements will fill the array list.
   */
  public IdentityArrayList(final ObjectIterator<? extends K> i) {
    this();
    while (i.hasNext())
      this.add(i.next());
  }

  /**
   * Returns the backing array of this list.
   *
   * <P>
   * If this array list was created by wrapping a given array, it is guaranteed that the type of the
   * returned array will be the same. Otherwise, the returned array will be of type {@link Object
   * Object[]} (in spite of the declared return type).
   *
   * <strong>Warning</strong>: This behaviour may cause (unfathomable) run-time errors if a method
   * expects an array actually of type <code>K[]</code>, but this methods returns an array of type
   * {@link Object Object[]}.
   *
   * @return the backing array.
   */
  public K[] elements() {
    return a;
  }

  /**
   * Wraps a given array into an array list of given size.
   *
   * @param a an array to wrap.
   * @param length the length of the resulting array list.
   * @return a new array list of the given size, wrapping the given array.
   */
  public static <K> IdentityArrayList<K> wrap(final K a[], final int length) {
    if (length > a.length)
      throw new IllegalArgumentException("The specified length (" + length
          + ") is greater than the array size (" + a.length + ")");
    final IdentityArrayList<K> l = new IdentityArrayList<K>(a, false);
    l.size = length;
    return l;
  }

  /**
   * Wraps a given array into an array list.
   *
   * @param a an array to wrap.
   * @return a new array list wrapping the given array.
   */
  public static <K> IdentityArrayList<K> wrap(final K a[]) {
    return wrap(a, a.length);
  }

  /**
   * Ensures that this array list can contain the given number of entries without resizing.
   *
   * @param capacity the new minimum capacity for this array list.
   */
  @SuppressWarnings("unchecked")
  public void ensureCapacity(final int capacity) {
    if (wrapped)
      a = ObjectArrays.ensureCapacity(a, capacity, size);
    else {
      if (capacity > a.length) {
        final Object t[] = new Object[capacity];
        System.arraycopy(a, 0, t, 0, size);
        a = (K[]) t;
      }
    }
    if (ASSERTS)
      assert size <= a.length;
  }

  /**
   * Grows this array list, ensuring that it can contain the given number of entries without
   * resizing, and in case enlarging it at least by a factor of two.
   *
   * @param capacity the new minimum capacity for this array list.
   */
  @SuppressWarnings("unchecked")
  private void grow(final int capacity) {
    if (wrapped)
      a = ObjectArrays.grow(a, capacity, size);
    else {
      if (capacity > a.length) {
        final int newLength = (int) Math
            .max(Math.min(2L * a.length, it.unimi.dsi.fastutil.Arrays.MAX_ARRAY_SIZE), capacity);
        final Object t[] = new Object[newLength];
        System.arraycopy(a, 0, t, 0, size);
        a = (K[]) t;
      }
    }
    if (ASSERTS)
      assert size <= a.length;
  }

  @Override
  public void add(final int index, final K k) {
    ensureIndex(index);
    grow(size + 1);
    if (index != size)
      System.arraycopy(a, index, a, index + 1, size - index);
    a[index] = k;
    size++;
    if (ASSERTS)
      assert size <= a.length;
  }

  @Override
  public boolean add(final K k) {
    grow(size + 1);
    a[size++] = k;
    if (ASSERTS)
      assert size <= a.length;
    return true;
  }

  @Override
  public K get(final int index) {
    if (index >= size)
      throw new IndexOutOfBoundsException(
          "Index (" + index + ") is greater than or equal to list size (" + size + ")");
    return a[index];
  }

  @Override
  public int indexOf(final Object k) {
    for (int i = 0; i < size; i++)
      if (((k) == null ? (a[i]) == null : (k) == (a[i])))
        return i;
    return -1;
  }

  @Override
  public int lastIndexOf(final Object k) {
    for (int i = size; i-- != 0;)
      if (((k) == null ? (a[i]) == null : (k) == (a[i])))
        return i;
    return -1;
  }

  @Override
  public K remove(final int index) {
    if (index >= size)
      throw new IndexOutOfBoundsException(
          "Index (" + index + ") is greater than or equal to list size (" + size + ")");
    final K old = a[index];
    size--;
    if (index != size)
      System.arraycopy(a, index + 1, a, index, size - index);
    a[size] = null;
    if (ASSERTS)
      assert size <= a.length;
    return old;
  }

  public boolean rem(final Object k) {
    int index = indexOf(k);
    if (index == -1)
      return false;
    remove(index);
    if (ASSERTS)
      assert size <= a.length;
    return true;
  }

  @Override
  public boolean remove(final Object o) {
    return rem(o);
  }

  @Override
  public K set(final int index, final K k) {
    if (index >= size)
      throw new IndexOutOfBoundsException(
          "Index (" + index + ") is greater than or equal to list size (" + size + ")");
    K old = a[index];
    a[index] = k;
    return old;
  }

  @Override
  public void clear() {
    Arrays.fill(a, 0, size, null);
    size = 0;
    if (ASSERTS)
      assert size <= a.length;
  }

  @Override
  public int size() {
    return size;
  }

  @Override
  public void size(final int size) {
    if (size > a.length)
      ensureCapacity(size);
    if (size > this.size)
      Arrays.fill(a, this.size, size, (null));
    else
      Arrays.fill(a, size, this.size, (null));
    this.size = size;
  }

  @Override
  public boolean isEmpty() {
    return size == 0;
  }

  /**
   * Trims this array list so that the capacity is equal to the size.
   *
   * @see java.util.ArrayList#trimToSize()
   */
  public void trim() {
    trim(0);
  }

  /**
   * Trims the backing array if it is too large.
   *
   * If the current array length is smaller than or equal to <code>n</code>, this method does
   * nothing. Otherwise, it trims the array length to the maximum between <code>n</code> and
   * {@link #size()}.
   *
   * <P>
   * This method is useful when reusing lists. {@linkplain #clear() Clearing a list} leaves the
   * array length untouched. If you are reusing a list many times, you can call this method with a
   * typical size to avoid keeping around a very large array just because of a few large transient
   * lists.
   *
   * @param n the threshold for the trimming.
   */
  @SuppressWarnings("unchecked")
  public void trim(final int n) {
    // TODO: use Arrays.trim() and preserve type only if necessary
    if (n >= a.length || size == a.length)
      return;
    final K t[] = (K[]) new Object[Math.max(n, size)];
    System.arraycopy(a, 0, t, 0, size);
    a = t;
    if (ASSERTS)
      assert size <= a.length;
  }

  /**
   * Copies element of this type-specific list into the given array using optimized system calls.
   *
   * @param from the start index (inclusive).
   * @param a the destination array.
   * @param offset the offset into the destination array where to store the first element copied.
   * @param length the number of elements to be copied.
   */
  @Override
  public void getElements(final int from, final Object[] a, final int offset, final int length) {
    ObjectArrays.ensureOffsetLength(a, offset, length);
    System.arraycopy(this.a, from, a, offset, length);
  }

  /**
   * Removes elements of this type-specific list using optimized system calls.
   *
   * @param from the start index (inclusive).
   * @param to the end index (exclusive).
   */
  @Override
  public void removeElements(final int from, final int to) {
    it.unimi.dsi.fastutil.Arrays.ensureFromTo(size, from, to);
    System.arraycopy(a, to, a, from, size - to);
    size -= (to - from);
    int i = to - from;
    while (i-- != 0)
      a[size + i] = null;
  }

  /**
   * Adds elements to this type-specific list using optimized system calls.
   *
   * @param index the index at which to add elements.
   * @param a the array containing the elements.
   * @param offset the offset of the first element to add.
   * @param length the number of elements to add.
   */
  @Override
  public void addElements(final int index, final K a[], final int offset, final int length) {
    ensureIndex(index);
    ObjectArrays.ensureOffsetLength(a, offset, length);
    grow(size + length);
    System.arraycopy(this.a, index, this.a, index + length, size - index);
    System.arraycopy(a, offset, this.a, index, length);
    size += length;
  }

  @Override
  public ObjectListIterator<K> listIterator(final int index) {
    ensureIndex(index);
    return new AbstractObjectListIterator<K>() {
      int pos = index, last = -1;

      @Override
      public boolean hasNext() {
        return pos < size;
      }

      @Override
      public boolean hasPrevious() {
        return pos > 0;
      }

      @Override
      public K next() {
        if (!hasNext())
          throw new NoSuchElementException();
        return a[last = pos++];
      }

      @Override
      public K previous() {
        if (!hasPrevious())
          throw new NoSuchElementException();
        return a[last = --pos];
      }

      @Override
      public int nextIndex() {
        return pos;
      }

      @Override
      public int previousIndex() {
        return pos - 1;
      }

      @Override
      public void add(K k) {
        if (last == -1)
          throw new IllegalStateException();
        IdentityArrayList.this.add(pos++, k);
        last = -1;
      }

      @Override
      public void set(K k) {
        if (last == -1)
          throw new IllegalStateException();
        IdentityArrayList.this.set(last, k);
      }

      @Override
      public void remove() {
        if (last == -1)
          throw new IllegalStateException();
        IdentityArrayList.this.remove(last);
        /*
         * If the last operation was a next(), we are removing an element *before* us, and we must
         * decrease pos correspondingly.
         */
        if (last < pos)
          pos--;
        last = -1;
      }
    };
  }

  @Override
  @SuppressWarnings("unchecked")
  public IdentityArrayList<K> clone() {
    IdentityArrayList<K> c = new IdentityArrayList<K>(size);
    System.arraycopy(a, 0, c.a, 0, size);
    c.size = size;
    return c;
  }

  private boolean valEquals(final K a, final K b) {
    return a == b;
  }

  /**
   * Compares this type-specific array list to another one.
   *
   * <P>
   * This method exists only for sake of efficiency. The implementation inherited from the abstract
   * implementation would already work.
   *
   * @param l a type-specific array list.
   * @return true if the argument contains the same elements of this type-specific array list.
   */
  public boolean equals(final IdentityArrayList<K> l) {
    if (l == this)
      return true;
    int s = size();
    if (s != l.size())
      return false;
    final K[] a1 = a;
    final K[] a2 = l.a;
    while (s-- != 0)
      if (!valEquals(a1[s], a2[s]))
        return false;
    return true;
  }

  /**
   * Compares this array list to another array list.
   *
   * <P>
   * This method exists only for sake of efficiency. The implementation inherited from the abstract
   * implementation would already work.
   *
   * @param l an array list.
   * @return a negative integer, zero, or a positive integer as this list is lexicographically less
   *         than, equal to, or greater than the argument.
   */
  @SuppressWarnings("unchecked")
  public int compareTo(final IdentityArrayList<? extends K> l) {
    final int s1 = size(), s2 = l.size();
    final K a1[] = a, a2[] = l.a;
    K e1, e2;
    int r, i;
    for (i = 0; i < s1 && i < s2; i++) {
      e1 = a1[i];
      e2 = a2[i];
      if ((r = (((Comparable<K>) (e1)).compareTo(e2))) != 0)
        return r;
    }
    return i < s2 ? -1 : (i < s1 ? 1 : 0);
  }

  private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    s.defaultWriteObject();
    for (int i = 0; i < size; i++)
      s.writeObject(a[i]);
  }

  @SuppressWarnings("unchecked")
  private void readObject(java.io.ObjectInputStream s)
      throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    a = (K[]) new Object[size];
    for (int i = 0; i < size; i++)
      a[i] = (K) s.readObject();
  }

  /**
   * For highest performance we sometimes must iterate over the actual Object array. This should
   * only be used in carefully controlled circumstances.
   */
  public Object[] getArrayRef() {
    return a;
  }

}