package com.carrotsearch.hppc;

import java.util.*;

import com.carrotsearch.hppc.cursors.*;
import com.carrotsearch.hppc.predicates.ObjectPredicate;
import com.carrotsearch.hppc.procedures.*;

import static com.carrotsearch.hppc.Containers.*;

An array-backed list of Objects.
/**
 * An array-backed list of Objects.
 */
  @SuppressWarnings("unchecked")  
 @com.carrotsearch.hppc.Generated(
    date = "2018-05-21T12:24:05+0200",
    value = "KTypeArrayList.java") 
public class ObjectArrayList<KType>
  extends AbstractObjectCollection<KType> 
  implements ObjectIndexedContainer<KType>,
             Preallocable,
             Cloneable
{
  
An immutable empty buffer (array).
/**
   * An immutable empty buffer (array).
   */
  public final static 
         
          Object [] 
         
          EMPTY_ARRAY = 
         
          new Object [0]; 
        ; 

  
Internal array for storing the list. The array may be larger than the current size (size()). /**
   * Internal array for storing the list. The array may be larger than the current size
   * ({@link #size()}).
   */
  public 
         
          Object [] 
        
          buffer = EMPTY_ARRAY;

  
Current number of elements stored in ObjectArrayList<KType>.buffer. /**
   * Current number of elements stored in {@link #buffer}.
   */
  public int elementsCount;

  
Buffer resizing strategy.
/**
   * Buffer resizing strategy.
   */
  protected final ArraySizingStrategy resizer;

  
New instance with sane defaults.
/**
   * New instance with sane defaults.
   */
  public ObjectArrayList() {
    this(DEFAULT_EXPECTED_ELEMENTS);
  }

  
New instance with sane defaults.
Params:
expectedElements – 
         The expected number of elements guaranteed not to cause buffer
         expansion (inclusive)./**
   * New instance with sane defaults.
   * 
   * @param expectedElements
   *          The expected number of elements guaranteed not to cause buffer
   *          expansion (inclusive).
   */
  public ObjectArrayList(int expectedElements) {
    this(expectedElements, new BoundedProportionalArraySizingStrategy());
  }


  
New instance with sane defaults.
Params:
expectedElements – 
         The expected number of elements guaranteed not to cause buffer
         expansion (inclusive).
resizer – 
         Underlying buffer sizing strategy./**
   * New instance with sane defaults.
   * 
   * @param expectedElements
   *          The expected number of elements guaranteed not to cause buffer
   *          expansion (inclusive).
   * 
   * @param resizer
   *          Underlying buffer sizing strategy.
   */
  public ObjectArrayList(int expectedElements, ArraySizingStrategy resizer) {
    assert resizer != null;
    this.resizer = resizer;
    ensureCapacity(expectedElements);
  }

  
Creates a new list from the elements of another container in its
iteration order.
/**
   * Creates a new list from the elements of another container in its
   * iteration order.
   */
  public ObjectArrayList(ObjectContainer<? extends KType> container) {
    this(container.size());
    addAll(container);
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public void add(KType e1) {
    ensureBufferSpace(1);
    buffer[elementsCount++] = e1;
  }

  
Appends two elements at the end of the list. To add more than two elements,
use add (vararg-version) or access the buffer directly (tight
loop).
/**
   * Appends two elements at the end of the list. To add more than two elements,
   * use <code>add</code> (vararg-version) or access the buffer directly (tight
   * loop).
   */
  public void add(KType e1, KType e2) {
    ensureBufferSpace(2);
    buffer[elementsCount++] = e1;
    buffer[elementsCount++] = e2;
  }

  
Add all elements from a range of given array to the list.
/**
   * Add all elements from a range of given array to the list.
   */
  public void add(KType[] elements, int start, int length) {
    assert length >= 0 : "Length must be >= 0";

    ensureBufferSpace(length);
    System.arraycopy(elements, start, buffer, elementsCount, length);
    elementsCount += length;
  }

  
Vararg-signature method for adding elements at the end of the list.

This method is handy, but costly if used in tight loops (anonymous array
passing)

/**
   * Vararg-signature method for adding elements at the end of the list.
   * <p>
   * <b>This method is handy, but costly if used in tight loops (anonymous array
   * passing)</b>
   * </p>
   */
  /*  */
  @SafeVarargs
  /*  */
  public final void add(KType... elements) {
    add(elements, 0, elements.length);
  }

  
Adds all elements from another container.
/**
   * Adds all elements from another container.
   */
  public int addAll(ObjectContainer<? extends KType> container) {
    final int size = container.size();
    ensureBufferSpace(size);

    for (ObjectCursor<? extends KType> cursor : container) {
      add(cursor.value);
    }

    return size;
  }

  
Adds all elements from another iterable.
/**
   * Adds all elements from another iterable.
   */
  public int addAll(Iterable<? extends ObjectCursor<? extends KType>> iterable) {
    int size = 0;
    for (ObjectCursor<? extends KType> cursor : iterable) {
      add(cursor.value);
      size++;
    }
    return size;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public void insert(int index, KType e1) {
    assert (index >= 0 && index <= size()) : "Index " + index + " out of bounds [" + 0 + ", " + size() + "].";

    ensureBufferSpace(1);
    System.arraycopy(buffer, index, buffer, index + 1, elementsCount - index);
    buffer[index] = e1;
    elementsCount++;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public KType get(int index) {
    assert (index >= 0 && index < size()) : "Index " + index + " out of bounds [" + 0 + ", " + size() + ").";

    return (KType) buffer[index];
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public KType set(int index, KType e1) {
    assert (index >= 0 && index < size()) : "Index " + index + " out of bounds [" + 0 + ", " + size() + ").";

    final KType v = (KType) buffer[index];
    buffer[index] = e1;
    return v;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public KType remove(int index) {
    assert (index >= 0 && index < size()) : "Index " + index + " out of bounds [" + 0 + ", " + size() + ").";

    final KType v = (KType) buffer[index];
    if (index + 1 < elementsCount) {
      System.arraycopy(buffer, index + 1, buffer, index, elementsCount - index - 1);
    }
    elementsCount--;
    buffer[elementsCount] = null;
    return v;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public void removeRange(int fromIndex, int toIndex) {
    assert (fromIndex >= 0 && fromIndex <= size()) 
      : "Index " + fromIndex + " out of bounds [" + 0 + ", " + size() + ").";
    assert (toIndex >= 0 && toIndex <= size()) 
      : "Index " + toIndex + " out of bounds [" + 0 + ", " + size() + "].";
    assert fromIndex <= toIndex 
      : "fromIndex must be <= toIndex: " + fromIndex + ", " + toIndex;

    System.arraycopy(buffer, toIndex, buffer, fromIndex, elementsCount - toIndex);
    final int count = toIndex - fromIndex;
    elementsCount -= count;
    Arrays.fill(buffer, elementsCount, elementsCount + count, null);
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public int removeFirst(KType e1) {
    final int index = indexOf(e1);
    if (index >= 0)
      remove(index);
    return index;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public int removeLast(KType e1) {
    final int index = lastIndexOf(e1);
    if (index >= 0)
      remove(index);
    return index;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public int removeAll(KType e1) {
    int to = 0;
    for (int from = 0; from < elementsCount; from++) {
      if (this.equals(buffer[from],  e1)) {
        buffer[from] = null;
        continue;
      }

      if (to != from) {
        buffer[to] = buffer[from];
        buffer[from] = null;
      }
      to++;
    }

    final int deleted = elementsCount - to;
    this.elementsCount = to;
    return deleted;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public boolean contains(KType e1) {
    return indexOf(e1) >= 0;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public int indexOf(KType e1) {
    for (int i = 0; i < elementsCount; i++) {
      if (this.equals(buffer[i],  e1)) {
        return i;
      }
    }

    return -1;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public int lastIndexOf(KType e1) {
    for (int i = elementsCount - 1; i >= 0; i--) {
      if (this.equals(buffer[i],  e1)) {
        return i;
      }
    }

    return -1;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public boolean isEmpty() {
    return elementsCount == 0;
  }

  
Ensure this container can hold at least the given number of elements
without resizing its buffers.
Params:
expectedElements – 
         The total number of elements, inclusive./**
   * Ensure this container can hold at least the given number of elements
   * without resizing its buffers.
   * 
   * @param expectedElements
   *          The total number of elements, inclusive.
   */
  @Override
  public void ensureCapacity(int expectedElements) {
    final int bufferLen = (buffer == null ? 0 : buffer.length);
    if (expectedElements > bufferLen) {
      ensureBufferSpace(expectedElements - size());
    }
  }

  
Ensures the internal buffer has enough free slots to store
expectedAdditions. Increases internal buffer size if needed.
/**
   * Ensures the internal buffer has enough free slots to store
   * <code>expectedAdditions</code>. Increases internal buffer size if needed.
   */
  protected void ensureBufferSpace(int expectedAdditions) {
    final int bufferLen = (buffer == null ? 0 : buffer.length);
    if (elementsCount + expectedAdditions > bufferLen) {
      final int newSize = resizer.grow(bufferLen, elementsCount, expectedAdditions);
      assert newSize >= elementsCount + expectedAdditions : "Resizer failed to" + " return sensible new size: "
          + newSize + " <= " + (elementsCount + expectedAdditions);

      this.buffer = Arrays.copyOf(buffer, newSize);
    }
  }

  
Truncate or expand the list to the new size. If the list is truncated, the buffer will not be reallocated (use trimToSize() if you need a truncated buffer), but the truncated values will be reset to the default value (zero). If the list is expanded, the elements beyond the current size are initialized with JVM-defaults (zero or null values).
/**
   * Truncate or expand the list to the new size. If the list is truncated, the
   * buffer will not be reallocated (use {@link #trimToSize()} if you need a
   * truncated buffer), but the truncated values will be reset to the default
   * value (zero). If the list is expanded, the elements beyond the current size
   * are initialized with JVM-defaults (zero or <code>null</code> values).
   */
  public void resize(int newSize) {
    if (newSize <= buffer.length) {
      if (newSize < elementsCount) {
        Arrays.fill(buffer, newSize, elementsCount, null);
      } else {
        Arrays.fill(buffer, elementsCount, newSize, null);
      }
    } else {
      ensureCapacity(newSize);
    }
    this.elementsCount = newSize;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public int size() {
    return elementsCount;
  }

  
Trim the internal buffer to the current size.
/**
   * Trim the internal buffer to the current size.
   */
  public void trimToSize() {
    if (size() != this.buffer.length) {
      this.buffer = (KType[]) toArray();
    }
  }

  
Sets the number of stored elements to zero. Releases and initializes the internal storage array to default values. To clear the list without cleaning the buffer, simply set the ObjectArrayList<KType>.elementsCount field to zero. /**
   * Sets the number of stored elements to zero. Releases and initializes the
   * internal storage array to default values. To clear the list without
   * cleaning the buffer, simply set the {@link #elementsCount} field to zero.
   */
  @Override
  public void clear() {
    Arrays.fill(buffer, 0, elementsCount, null);
    this.elementsCount = 0;
  }

  
Sets the number of stored elements to zero and releases the internal
storage array.
/**
   * Sets the number of stored elements to zero and releases the internal
   * storage array.
   */
  @Override
  public void release() {
    this.buffer = (KType[]) EMPTY_ARRAY;
    this.elementsCount = 0;
  }

  
{@inheritDoc}
The returned array is sized to match exactly
the number of elements of the stack.
/**
   * {@inheritDoc}
   * 
   * <p>The returned array is sized to match exactly
   * the number of elements of the stack.</p>
   */
  @Override
    
  public Object [] toArray()
    
  {
    return Arrays.copyOf(buffer, elementsCount);
  }

  
Clone this object. The returned clone will reuse the same hash function and
array resizing strategy.
/**
   * Clone this object. The returned clone will reuse the same hash function and
   * array resizing strategy.
   */
  @Override
  public ObjectArrayList<KType> clone() {
    try {
      /*  */
      final ObjectArrayList<KType> cloned = (ObjectArrayList<KType>) super.clone();
      cloned.buffer = buffer.clone();
      return cloned;
    } catch (CloneNotSupportedException e) {
      throw new RuntimeException(e);
    }
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public int hashCode() {
    int h = 1, max = elementsCount;
    for (int i = 0; i < max; i++) {
      h = 31 * h + BitMixer.mix(this.buffer[i]);
    }
    return h;
  }

  
Returns true only if the other object is an instance of the same class and with the same elements. Equality comparison is performed with this object's AbstractObjectCollection.equals(Object, Object) method. /**
   * Returns <code>true</code> only if the other object is an instance of 
   * the same class and with the same elements. 
   * Equality comparison is performed with this object's {@link #equals(Object, Object)} 
   * method.
     */
  @Override
  public boolean equals(Object obj) {
      return obj != null &&
             getClass() == obj.getClass() &&
             equalElements(getClass().cast(obj));
  }

  
Compare index-aligned elements against another ObjectIndexedContainer. Equality comparison is performed with this object's AbstractObjectCollection.equals(Object, Object) method. /**
   * Compare index-aligned elements against another 
   * {@link ObjectIndexedContainer}. 
   * Equality comparison is performed with this object's {@link #equals(Object, Object)} 
   * method.
   */
  protected boolean equalElements(ObjectArrayList<?> other) {
    int max = size();
    if (other.size() != max) {
      return false;
    }

    for (int i = 0; i < max; i++) {
      if (!this.equals(other.get(i),  get(i))) {
        return false;
      }
    }

    return true;
  }

  
An iterator implementation for ObjectArrayList.iterator. /**
   * An iterator implementation for {@link ObjectArrayList#iterator}.
   */
  final static class ValueIterator<KType> extends AbstractIterator<ObjectCursor<KType>> {
    private final ObjectCursor<KType> cursor;

    private final KType[] buffer;
    private final int size;

    public ValueIterator(KType[] buffer, int size) {
      this.cursor = new ObjectCursor<KType>();
      this.cursor.index = -1;
      this.size = size;
      this.buffer = buffer;
    }

    @Override
    protected ObjectCursor<KType> fetch() {
      if (cursor.index + 1 == size)
        return done();

      cursor.value = buffer[++cursor.index];
      return cursor;
    }
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public Iterator<ObjectCursor<KType>> iterator() {
    return new ValueIterator<KType>((KType[]) buffer, size());
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public <T extends ObjectProcedure<? super KType>> T forEach(T procedure) {
    return forEach(procedure, 0, size());
  }

  
Applies procedure to a slice of the list,
fromIndex, inclusive, to toIndex, exclusive.
/**
   * Applies <code>procedure</code> to a slice of the list,
   * <code>fromIndex</code>, inclusive, to <code>toIndex</code>, exclusive.
   */
  public <T extends ObjectProcedure<? super KType>> T forEach(T procedure, int fromIndex, final int toIndex) {
    assert (fromIndex >= 0 && fromIndex <= size()) :
        "Index " + fromIndex + " out of bounds [" + 0 + ", " + size() + ").";

    assert (toIndex >= 0 && toIndex <= size()) :
        "Index " + toIndex + " out of bounds [" + 0 + ", " + size() + "].";
    
    assert fromIndex <= toIndex : "fromIndex must be <= toIndex: "
        + fromIndex + ", " + toIndex;

    final KType [] buffer = (KType[]) this.buffer;
    for (int i = fromIndex; i < toIndex; i++) {
        procedure.apply(buffer[i]);
    }

    return procedure;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public int removeAll(ObjectPredicate<? super KType> predicate) {
    final KType[] buffer = (KType[]) this.buffer;
    final int elementsCount = this.elementsCount;
    int to = 0;
    int from = 0;
    try {
      for (; from < elementsCount; from++) {
        if (predicate.apply(buffer[from])) {
          buffer[from] = null;
          continue;
        }

        if (to != from) {
          buffer[to] = buffer[from];
          buffer[from] = null;
        }
        to++;
      }
    } finally {
      // Keep the list in a consistent state, even if the predicate throws an exception.
      for (; from < elementsCount; from++) {
        if (to != from) {
          buffer[to] = buffer[from];
          buffer[from] = null;
        }
        to++;
      }

      this.elementsCount = to;
    }

    return elementsCount - to;
  }

  
{@inheritDoc}
/**
   * {@inheritDoc}
   */
  @Override
  public <T extends ObjectPredicate<? super KType>> T forEach(T predicate) {
    return forEach(predicate, 0, size());
  }

  
Applies predicate to a slice of the list,
fromIndex, inclusive, to toIndex, exclusive, or
until predicate returns false.
/**
   * Applies <code>predicate</code> to a slice of the list,
   * <code>fromIndex</code>, inclusive, to <code>toIndex</code>, exclusive, or
   * until predicate returns <code>false</code>.
   */
  public <T extends ObjectPredicate<? super KType>> T forEach(T predicate, int fromIndex, final int toIndex) {
    assert (fromIndex >= 0 && fromIndex <= size()) 
      : "Index " + fromIndex + " out of bounds [" + 0 + ", " + size() + ").";
    assert (toIndex >= 0 && toIndex <= size()) 
      : "Index " + toIndex + " out of bounds [" + 0 + ", " + size() + "].";
    assert fromIndex <= toIndex 
      : "fromIndex must be <= toIndex: " + fromIndex + ", " + toIndex;

    final KType[] buffer = (KType[]) this.buffer;
    for (int i = fromIndex; i < toIndex; i++) {
      if (!predicate.apply(buffer[i]))
        break;
    }
    
    return predicate;
  }

    
Create a list from a variable number of arguments or an array of Object.
The elements are copied from the argument to the internal buffer.
/**
     * Create a list from a variable number of arguments or an array of <code>Object</code>.
     * The elements are copied from the argument to the internal buffer.
     */
    /*  */
    @SafeVarargs
    /*  */
  public static <KType> ObjectArrayList<KType> from(KType... elements) {
    final ObjectArrayList<KType> list = new ObjectArrayList<KType>(elements.length);
    list.add(elements);
    return list;
  }
}