///////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
///////////////////////////////////////////////////////////////////////////////
// THIS FILE IS AUTOGENERATED, PLEASE DO NOT EDIT OR ELSE

package gnu.trove;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Arrays;
import java.util.Random;

/**
 * A resizable, array-backed list of int primitives.
 * <p>
 * Created: Sat Dec 29 14:21:12 2001
 *
 * @author Eric D. Friedman
 */
@Deprecated
public final class TIntArrayList implements Serializable, Cloneable {

  /**
   * the data of the list
   */
  private transient int[] _data; // null means the array list was just created

  /**
   * the index after the last entry in the list
   */
  private transient int _pos;

  /**
   * the default capacity for new lists
   */
  static final int DEFAULT_CAPACITY = 4;

  /**
   * Creates a new <code>TIntArrayList</code> instance with the
   * default capacity.
   */
  public TIntArrayList() {
  }

  /**
   * Creates a new <code>TIntArrayList</code> instance with the
   * specified capacity.
   *
   * @param capacity an <code>int</code> value
   */
  public TIntArrayList(int capacity) {
    _data = new int[capacity];
    _pos = 0;
  }

  /**
   * Creates a new <code>TIntArrayList</code> instance whose
   * capacity is the greater of the length of <tt>values</tt> and
   * DEFAULT_CAPACITY and whose initial contents are the specified
   * values.
   *
   * @param values an <code>int[]</code> value
   */
  public TIntArrayList(int[] values) {
    this(Math.max(values.length, DEFAULT_CAPACITY));
    add(values);
  }

  // sizing

  /**
   * Grow the internal array as needed to accommodate the specified
   * number of elements.  The size of the array doubles on each
   * resize unless <tt>capacity</tt> requires more than twice the
   * current capacity.
   *
   * @param capacity an <code>int</code> value
   */
  public void ensureCapacity(int capacity) {
    if (_data == null) {
      _data = new int[Math.max(DEFAULT_CAPACITY, capacity)];
    }
    if (capacity > _data.length) {
      int newCap = Math.max(_data.length << 1, capacity);
      int[] tmp = new int[newCap];
      System.arraycopy(_data, 0, tmp, 0, _data.length);
      _data = tmp;
    }
  }

  /**
   * Returns the number of values in the list.
   *
   * @return the number of values in the list.
   */
  public int size() {
    return _pos;
  }

  /**
   * Tests whether this list contains any values.
   *
   * @return true if the list is empty.
   */
  public boolean isEmpty() {
    return _pos == 0;
  }

  /**
   * Sheds any excess capacity above and beyond the current size of
   * the list.
   */
  public void trimToSize() {
    if (_data != null && _data.length > size()) {
      int[] tmp = new int[size()];
      toNativeArray(tmp, 0, tmp.length);
      _data = tmp;
    }
  }

  // modifying

  /**
   * Adds <tt>val</tt> to the end of the list, growing as needed.
   *
   * @param val an <code>int</code> value
   */
  public void add(int val) {
    ensureCapacity(_pos + 1);
    _data[_pos++] = val;
  }

  /**
   * Adds the values in the array <tt>vals</tt> to the end of the
   * list, in order.
   *
   * @param vals an <code>int[]</code> value
   */
  public void add(int[] vals) {
    add(vals, 0, vals.length);
  }

  /**
   * Adds a subset of the values in the array <tt>vals</tt> to the
   * end of the list, in order.
   *
   * @param vals   an <code>int[]</code> value
   * @param offset the offset at which to start copying
   * @param length the number of values to copy.
   */
  public void add(int[] vals, int offset, int length) {
    ensureCapacity(_pos + length);
    System.arraycopy(vals, offset, _data, _pos, length);
    _pos += length;
  }

  /**
   * Inserts <tt>value</tt> into the list at <tt>offset</tt>.  All
   * values including and to the right of <tt>offset</tt> are shifted
   * to the right.
   *
   * @param offset an <code>int</code> value
   * @param value  an <code>int</code> value
   */
  public void insert(int offset, int value) {
    if (offset == _pos) {
      add(value);
      return;
    }
    ensureCapacity(_pos + 1);
    // shift right
    System.arraycopy(_data, offset, _data, offset + 1, _pos - offset);
    // insert
    _data[offset] = value;
    _pos++;
  }

  /**
   * Inserts the array of <tt>values</tt> into the list at
   * <tt>offset</tt>.  All values including and to the right of
   * <tt>offset</tt> are shifted to the right.
   *
   * @param offset an <code>int</code> value
   * @param values an <code>int[]</code> value
   */
  public void insert(int offset, int[] values) {
    insert(offset, values, 0, values.length);
  }

  /**
   * Inserts a slice of the array of <tt>values</tt> into the list
   * at <tt>offset</tt>.  All values including and to the right of
   * <tt>offset</tt> are shifted to the right.
   *
   * @param offset    an <code>int</code> value
   * @param values    an <code>int[]</code> value
   * @param valOffset the offset in the values array at which to
   *                  start copying.
   * @param len       the number of values to copy from the values array
   */
  public void insert(int offset, int[] values, int valOffset, int len) {
    if (offset == _pos) {
      add(values, valOffset, len);
      return;
    }

    ensureCapacity(_pos + len);
    // shift right
    System.arraycopy(_data, offset, _data, offset + len, _pos - offset);
    // insert
    System.arraycopy(values, valOffset, _data, offset, len);
    _pos += len;
  }

  /**
   * Returns the value at the specified offset.
   *
   * @param offset an <code>int</code> value
   * @return an <code>int</code> value
   */
  public int get(int offset) {
    if (offset >= _pos) {
      throw new ArrayIndexOutOfBoundsException(offset);
    }
    return _data[offset];
  }

  /**
   * Returns the value at the specified offset without doing any
   * bounds checking.
   *
   * @param offset an <code>int</code> value
   * @return an <code>int</code> value
   */
  public int getQuick(int offset) {
    return _data[offset];
  }

  /**
   * Sets the value at the specified offset.
   *
   * @param offset an <code>int</code> value
   * @param val    an <code>int</code> value
   */
  public void set(int offset, int val) {
    if (offset < 0 || offset >= _pos) {
      throw new ArrayIndexOutOfBoundsException(offset);
    }
    _data[offset] = val;
  }

  /**
   * Sets the value at the specified offset and returns the
   * previously stored value.
   *
   * @param offset an <code>int</code> value
   * @param val    an <code>int</code> value
   * @return the value previously stored at offset.
   */
  public int getSet(int offset, int val) {
    if (offset < 0 || offset >= _pos) {
      throw new ArrayIndexOutOfBoundsException(offset);
    }
    int old = _data[offset];
    _data[offset] = val;
    return old;
  }

  /**
   * Replace the values in the list starting at <tt>offset</tt> with
   * the contents of the <tt>values</tt> array.
   *
   * @param offset the first offset to replace
   * @param values the source of the new values
   */
  public void set(int offset, int[] values) {
    set(offset, values, 0, values.length);
  }

  /**
   * Replace the values in the list starting at <tt>offset</tt> with
   * <tt>length</tt> values from the <tt>values</tt> array, starting
   * at valOffset.
   *
   * @param offset    the first offset to replace
   * @param values    the source of the new values
   * @param valOffset the first value to copy from the values array
   * @param length    the number of values to copy
   */
  public void set(int offset, int[] values, int valOffset, int length) {
    if (offset < 0 || offset + length > _pos) {
      throw new ArrayIndexOutOfBoundsException(offset);
    }
    System.arraycopy(_data, offset, values, valOffset, length);
  }

  /**
   * Sets the value at the specified offset without doing any bounds
   * checking.
   *
   * @param offset an <code>int</code> value
   * @param val    an <code>int</code> value
   */
  public void setQuick(int offset, int val) {
    _data[offset] = val;
  }

  /**
   * Flushes the internal state of the list, resetting the capacity
   * to the default.
   */
  public void clear() {
    _data = null;
    _pos = 0;
  }

  /**
   * Flushes the internal state of the list, setting the capacity of
   * the empty list to <tt>capacity</tt>.
   *
   * @param capacity an <code>int</code> value
   */
  public void clear(int capacity) {
    _data = new int[capacity];
    _pos = 0;
  }

  /**
   * Sets the size of the list to 0, but does not change its
   * capacity.  This method can be used as an alternative to the
   * {@link #clear clear} method if you want to recycle a list without
   * allocating new backing arrays.
   *
   * @see #clear
   */
  public void reset() {
    fill(0);
    _pos = 0;
  }

  /**
   * Sets the size of the list to 0, but does not change its
   * capacity.  This method can be used as an alternative to the
   * {@link #clear clear} method if you want to recycle a list
   * without allocating new backing arrays.  This method differs
   * from {@link #reset reset} in that it does not clear the old
   * values in the backing array.  Thus, it is possible for {@link
   * #getQuick getQuick} to return stale data if this method is used
   * and the caller is careless about bounds checking.
   *
   * @see #reset
   * @see #clear
   * @see #getQuick
   */
  public void resetQuick() {
    _pos = 0;
  }

  /**
   * Removes the value at <tt>offset</tt> from the list.
   *
   * @param offset an <code>int</code> value
   * @return the value previously stored at offset.
   */
  public int remove(int offset) {
    int old = get(offset);
    remove(offset, 1);
    return old;
  }

  /**
   * Removes <tt>length</tt> values from the list, starting at
   * <tt>offset</tt>
   *
   * @param offset an <code>int</code> value
   * @param length an <code>int</code> value
   */
  public void remove(int offset, int length) {
    if (offset < 0 || offset >= _pos) {
      throw new ArrayIndexOutOfBoundsException(offset);
    }

    if (offset == 0) {
      // data at the front
      System.arraycopy(_data, length, _data, 0, _pos - length);
    }
    else if (_pos - length == offset) {
      // no copy to make, decrementing pos "deletes" values at
      // the end
    }
    else {
      // data in the middle
      System.arraycopy(_data, offset + length,
                       _data, offset, _pos - (offset + length));
    }
    _pos -= length;
    // no need to clear old values beyond _pos, because this is a
    // primitive collection and 0 takes as much room as any other
    // value
  }

  /**
   * Transform each value in the list using the specified function.
   *
   * @param function a <code>TIntFunction</code> value
   */
  public void transformValues(TIntFunction function) {
    for (int i = _pos; i-- > 0; ) {
      _data[i] = function.execute(_data[i]);
    }
  }

  /**
   * Reverse the order of the elements in the list.
   */
  public void reverse() {
    reverse(0, _pos);
  }

  /**
   * Reverse the order of the elements in the range of the list.
   *
   * @param from the inclusive index at which to start reversing
   * @param to   the exclusive index at which to stop reversing
   */
  public void reverse(int from, int to) {
    if (from == to) {
      return;             // nothing to do
    }
    if (from > to) {
      throw new IllegalArgumentException("from cannot be greater than to");
    }
    for (int i = from, j = to - 1; i < j; i++, j--) {
      swap(i, j);
    }
  }

  /**
   * Shuffle the elements of the list using the specified random
   * number generator.
   *
   * @param rand a <code>Random</code> value
   */
  public void shuffle(Random rand) {
    for (int i = _pos; i-- > 1; ) {
      swap(i, rand.nextInt(i));
    }
  }

  /**
   * Swap the values at offsets <tt>i</tt> and <tt>j</tt>.
   *
   * @param i an offset into the data array
   * @param j an offset into the data array
   */
  private void swap(int i, int j) {
    int tmp = _data[i];
    _data[i] = _data[j];
    _data[j] = tmp;
  }

  // copying

  /**
   * Returns a clone of this list.  Since this is a primitive
   * collection, this will be a deep clone.
   *
   * @return a deep clone of the list.
   */
  @Override
  public Object clone() {
    TIntArrayList clone = null;
    try {
      clone = (TIntArrayList)super.clone();
      clone._data = _data == null ? null : _data.clone();
    }
    catch (CloneNotSupportedException e) {
      // it's supported
    } // end of try-catch
    return clone;
  }

  /**
   * Copies the contents of the list into a native array.
   *
   * @return an <code>int[]</code> value
   */
  public int[] toNativeArray() {
    return toNativeArray(0, _pos);
  }

  /**
   * Copies a slice of the list into a native array.
   *
   * @param offset the offset at which to start copying
   * @param len    the number of values to copy.
   * @return an <code>int[]</code> value
   */
  public int[] toNativeArray(int offset, int len) {
    int[] rv = new int[len];
    toNativeArray(rv, offset, len);
    return rv;
  }

  /**
   * Copies a slice of the list into a native array.
   *
   * @param dest   the array to copy into.
   * @param offset the offset of the first value to copy
   * @param len    the number of values to copy.
   */
  public void toNativeArray(int[] dest, int offset, int len) {
    if (len == 0) {
      return;             // nothing to copy
    }
    if (offset < 0 || offset >= _pos) {
      throw new ArrayIndexOutOfBoundsException(offset);
    }
    System.arraycopy(_data, offset, dest, 0, len);
  }

  // comparing

  /**
   * Compares this list to another list, value by value.
   *
   * @param other the object to compare against
   * @return true if other is a TIntArrayList and has exactly the
   * same values.
   */
  @Override
  public boolean equals(Object other) {
    if (other == this) {
      return true;
    }
    else if (other instanceof TIntArrayList) {
      TIntArrayList that = (TIntArrayList)other;
      if (that.size() != size()) {
        return false;
      }
      else {
        for (int i = _pos; i-- > 0; ) {
          if (_data[i] != that._data[i]) {
            return false;
          }
        }
        return true;
      }
    }
    else {
      return false;
    }
  }

  @Override
  public int hashCode() {
    int h = 0;
    for (int i = _pos; i-- > 0; ) {
      h += HashFunctions.hash(_data[i]);
    }
    return h;
  }

  // procedures

  /**
   * Applies the procedure to each value in the list in ascending
   * (front to back) order.
   *
   * @param procedure a <code>TIntProcedure</code> value
   * @return true if the procedure did not terminate prematurely.
   */
  public boolean forEach(TIntProcedure procedure) {
    for (int i = 0; i < _pos; i++) {
      if (!procedure.execute(_data[i])) {
        return false;
      }
    }
    return true;
  }

  /**
   * Applies the procedure to each value in the list in descending
   * (back to front) order.
   *
   * @param procedure a <code>TIntProcedure</code> value
   * @return true if the procedure did not terminate prematurely.
   */
  public boolean forEachDescending(TIntProcedure procedure) {
    for (int i = _pos; i-- > 0; ) {
      if (!procedure.execute(_data[i])) {
        return false;
      }
    }
    return true;
  }

  // sorting

  /**
   * Sort the values in the list (ascending) using the Sun quicksort
   * implementation.
   *
   * @see Arrays#sort
   */
  public void sort() {
    if (!isEmpty()) Arrays.sort(_data, 0, _pos);
  }

  /**
   * Sort a slice of the list (ascending) using the Sun quicksort
   * implementation.
   *
   * @param fromIndex the index at which to start sorting (inclusive)
   * @param toIndex   the index at which to stop sorting (exclusive)
   * @see Arrays#sort
   */
  public void sort(int fromIndex, int toIndex) {
    if (!isEmpty()) Arrays.sort(_data, fromIndex, toIndex);
  }

  // filling

  /**
   * Fills every slot in the list with the specified value.
   *
   * @param val the value to use when filling
   */
  public void fill(int val) {
    if (!isEmpty()) Arrays.fill(_data, 0, _pos, val);
  }

  /**
   * Fills a range in the list with the specified value.
   *
   * @param fromIndex the offset at which to start filling (inclusive)
   * @param toIndex   the offset at which to stop filling (exclusive)
   * @param val       the value to use when filling
   */
  public void fill(int fromIndex, int toIndex, int val) {
    if (toIndex > _pos) {
      ensureCapacity(toIndex);
      _pos = toIndex;
    }
    if (!isEmpty()) Arrays.fill(_data, fromIndex, toIndex, val);
  }

  // searching

  /**
   * Performs a binary search for <tt>value</tt> in the entire list.
   * Note that you <b>must</b> {@link #sort sort} the list before
   * doing a search.
   *
   * @param value the value to search for
   * @return the absolute offset in the list of the value, or its
   * negative insertion point into the sorted list.
   */
  public int binarySearch(int value) {
    return binarySearch(value, 0, _pos);
  }

  /**
   * Performs a binary search for <tt>value</tt> in the specified
   * range.  Note that you <b>must</b> {@link #sort sort} the list
   * or the range before doing a search.
   *
   * @param value     the value to search for
   * @param fromIndex the lower boundary of the range (inclusive)
   * @param toIndex   the upper boundary of the range (exclusive)
   * @return the absolute offset in the list of the value, or its
   * negative insertion point into the sorted list.
   */
  public int binarySearch(int value, int fromIndex, int toIndex) {
    if (fromIndex < 0) {
      throw new ArrayIndexOutOfBoundsException(fromIndex);
    }
    if (toIndex > _pos) {
      throw new ArrayIndexOutOfBoundsException(toIndex);
    }

    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
      int mid = (low + high) >> 1;
      int midVal = _data[mid];

      if (midVal < value) {
        low = mid + 1;
      }
      else if (midVal > value) {
        high = mid - 1;
      }
      else {
        return mid; // value found
      }
    }
    return -(low + 1);  // value not found.
  }

  /**
   * Searches the list front to back for the index of
   * <tt>value</tt>.
   *
   * @param value an <code>int</code> value
   * @return the first offset of the value, or -1 if it is not in
   * the list.
   * @see #binarySearch for faster searches on sorted lists
   */
  public int indexOf(int value) {
    return indexOf(0, value);
  }

  /**
   * Searches the list front to back for the index of
   * <tt>value</tt>, starting at <tt>offset</tt>.
   *
   * @param offset the offset at which to start the linear search
   *               (inclusive)
   * @param value  an <code>int</code> value
   * @return the first offset of the value, or -1 if it is not in
   * the list.
   * @see #binarySearch for faster searches on sorted lists
   */
  public int indexOf(int offset, int value) {
    for (int i = offset; i < _pos; i++) {
      if (_data[i] == value) {
        return i;
      }
    }
    return -1;
  }

  /**
   * Searches the list back to front for the last index of
   * <tt>value</tt>.
   *
   * @param value an <code>int</code> value
   * @return the last offset of the value, or -1 if it is not in
   * the list.
   * @see #binarySearch for faster searches on sorted lists
   */
  public int lastIndexOf(int value) {
    return lastIndexOf(_pos, value);
  }

  /**
   * Searches the list back to front for the last index of
   * <tt>value</tt>, starting at <tt>offset</tt>.
   *
   * @param offset the offset at which to start the linear search
   *               (exclusive)
   * @param value  an <code>int</code> value
   * @return the last offset of the value, or -1 if it is not in
   * the list.
   * @see #binarySearch for faster searches on sorted lists
   */
  public int lastIndexOf(int offset, int value) {
    for (int i = offset; i-- > 0; ) {
      if (_data[i] == value) {
        return i;
      }
    }
    return -1;
  }

  /**
   * Searches the list for <tt>value</tt>
   *
   * @param value an <code>int</code> value
   * @return true if value is in the list.
   */
  public boolean contains(int value) {
    return lastIndexOf(value) >= 0;
  }

  /**
   * Searches the list for values satisfying <tt>condition</tt> in
   * the manner of the *nix <tt>grep</tt> utility.
   *
   * @param condition a condition to apply to each element in the list
   * @return a list of values which match the condition.
   */
  public TIntArrayList grep(TIntProcedure condition) {
    TIntArrayList list = new TIntArrayList();
    for (int i = 0; i < _pos; i++) {
      if (condition.execute(_data[i])) {
        list.add(_data[i]);
      }
    }
    return list;
  }

  /**
   * Searches the list for values which do <b>not</b> satisfy
   * <tt>condition</tt>.  This is akin to *nix <code>grep -v</code>.
   *
   * @param condition a condition to apply to each element in the list
   * @return a list of values which do not match the condition.
   */
  public TIntArrayList inverseGrep(TIntProcedure condition) {
    TIntArrayList list = new TIntArrayList();
    for (int i = 0; i < _pos; i++) {
      if (!condition.execute(_data[i])) {
        list.add(_data[i]);
      }
    }
    return list;
  }

  /**
   * Finds the maximum value in the list.
   *
   * @return the largest value in the list.
   * @throws IllegalStateException if the list is empty
   */
  public int max() {
    if (size() == 0) {
      throw new IllegalStateException("cannot find maximum of an empty list");
    }
    int max = _data[_pos - 1];
    for (int i = _pos - 1; i-- > 0; ) {
      max = Math.max(max, _data[_pos]);
    }
    return max;
  }

  /**
   * Finds the minimum value in the list.
   *
   * @return the smallest value in the list.
   * @throws IllegalStateException if the list is empty
   */
  public int min() {
    if (size() == 0) {
      throw new IllegalStateException("cannot find minimum of an empty list");
    }
    int min = _data[_pos - 1];
    for (int i = _pos - 1; i-- > 0; ) {
      min = Math.min(min, _data[_pos]);
    }
    return min;
  }

  // stringification

  /**
   * Returns a String representation of the list, front to back.
   *
   * @return a <code>String</code> value
   */
  @Override
  public String toString() {
    final StringBuffer buf = new StringBuffer("{");
    forEach(new TIntProcedure() {
      @Override
      public boolean execute(int val) {
        buf.append(val);
        buf.append(", ");
        return true;
      }
    });
    buf.append("}");
    return buf.toString();
  }

  private void writeObject(ObjectOutputStream stream)
    throws IOException {
    stream.defaultWriteObject();

    // number of entries
    stream.writeInt(size());

    SerializationProcedure writeProcedure = new SerializationProcedure(stream);
    if (!forEach(writeProcedure)) {
      throw writeProcedure.exception;
    }
  }

  private void readObject(ObjectInputStream stream)
    throws IOException, ClassNotFoundException {
    stream.defaultReadObject();

    int size = stream.readInt();
    _data = new int[size];
    while (size-- > 0) {
      int val = stream.readInt();
      add(val);
    }
  }
} // TIntArrayList
