/*
* Copyright 2004 (C) TJDO.
* All rights reserved.
*
* This software is distributed under the terms of the TJDO License version 1.0.
* See the terms of the TJDO License in the documentation provided with this software.
*
* $Id: IntArrayList.java,v 1.1 2004/01/18 03:01:07 jackknifebarber Exp $
*/
import java.util.Arrays;
/**
* A variation on the standard ArrayList class that efficiently handles arrays
* of integers.
* Using this class rather than ArrayList avoids the need to "box" each
* element in an instance of java.lang.Integer.
* It is useful where performance is important.
*
* @author Mike Martin
* @version $Revision: 1.1 $
*/
public class IntArrayList implements Cloneable
{
private int[] elements;
private int size = 0;
/**
* Constructs an empty list with an initial capacity of ten.
*/
public IntArrayList()
{
this(10);
}
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity
* The initial capacity of the list.
*
* @exception IllegalArgumentException
* If the specified initial capacity is negative.
*/
public IntArrayList(int initialCapacity)
{
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal capacity: "+ initialCapacity);
elements = new int[initialCapacity];
}
/**
* Constructs a list containing the elements of the specified array.
* The IntArrayList instance has an initial capacity of 110% the
* size of the specified collection.
*
* @param initialContents
* The array whose elements are to be placed into this list.
*/
public IntArrayList(int[] initialContents)
{
size = initialContents.length;
elements = new int[(int)Math.min((size * 11L)/10, Integer.MAX_VALUE)];
System.arraycopy(initialContents, 0, elements, 0, size);
}
/**
* Trims the capacity of this IntArrayList instance to be the
* list's current size.
* An application can use this operation to minimize the storage of an
* IntArrayList instance.
*/
public void trimToSize()
{
if (size < elements.length)
{
int[] newelems = new int[size];
System.arraycopy(elements, 0, newelems, 0, size);
elements = newelems;
}
}
/**
* Increases the capacity of this IntArrayList instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity
* The desired minimum capacity.
*/
public void ensureCapacity(int minCapacity)
{
int oldCapacity = elements.length;
if (minCapacity > oldCapacity)
{
int[] newelems = new int[(int)Math.min((oldCapacity * 3L)/2, Integer.MAX_VALUE)];
System.arraycopy(elements, 0, newelems, 0, size);
elements = newelems;
}
}
/**
* Returns the number of elements in this list.
*
* @return The number of elements in this list.
*/
public int size()
{
return size;
}
/**
* Tests if this list has no elements.
*
* @return true if this list has no elements;
* false otherwise.
*/
public boolean isEmpty()
{
return size == 0;
}
/**
* Returns true if this list contains the specified element.
*
* @param elem element whose presence in this List is to be tested.
*
* @return true if the specified element is present;
* false otherwise.
*/
public boolean contains(int elem)
{
return indexOf(elem) >= 0;
}
/**
* Searches for the first occurence of the given argument.
*
* @param elem
* An integer to search for.
*
* @return The index of the first occurrence of the argument in this
* list; returns -1 if the value is not found.
*/
public int indexOf(int elem)
{
for (int i = 0; i < size; ++i)
{
if (elements[i] == elem)
return i;
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified integer in
* this list.
*
* @param elem
* The desired element.
*
* @return The index of the last occurrence of the specified integer in
* this list; returns -1 if the value is not found.
*/
public int lastIndexOf(int elem)
{
for (int i = size - 1; i >= 0; --i)
{
if (elements[i] == elem)
return i;
}
return -1;
}
/**
* Returns a copy of this IntArrayList instance.
*
* @return A clone of this ArrayList instance.
*/
public Object clone()
{
try
{
IntArrayList l = (IntArrayList)super.clone();
l.elements = new int[size];
System.arraycopy(elements, 0, l.elements, 0, size);
return l;
}
catch (CloneNotSupportedException e)
{
/* Should never happen since we are Cloneable. */
throw new InternalError();
}
}
/**
* Returns an array containing all of the elements in this list.
*
* @return An array containing all of the elements in this list.
*/
public int[] toArray()
{
int[] result = new int[size];
System.arraycopy(elements, 0, result, 0, size);
return result;
}
/**
* Check if the given index is in range.
* If not, throw an appropriate runtime exception.
*/
private void rangeCheck(int index)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
/**
* Returns the element at the specified position in this list.
*
* @param index
* Index of element to return.
*
* @return
* The element at the specified position in this list.
*
* @exception IndexOutOfBoundsException
* If index is out of range (index < 0 || index >= size()).
*/
public int get(int index)
{
rangeCheck(index);
return elements[index];
}
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index
* Index of element to replace.
* @param element
* Element to be stored at the specified position.
*
* @return
* The element previously at the specified position.
*
* @exception IndexOutOfBoundsException
* If index is out of range (index < 0 || index >= size()).
*/
public int set(int index, int element)
{
rangeCheck(index);
int oldValue = elements[index];
elements[index] = element;
return oldValue;
}
/**
* Appends the specified element to the end of this list.
*
* @param element
* Element to be appended to this list.
*/
public void add(int element)
{
ensureCapacity(size + 1);
elements[size++] = element;
}
/**
* Inserts the specified element at the specified position in this
* list.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (adds one to their indices).
*
* @param index
* Index at which the specified element is to be inserted.
* @param element
* Element to be inserted.
*
* @exception IndexOutOfBoundsException
* If index is out of range (index < 0 || index > size()).
*/
public void add(int index, int element)
{
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
ensureCapacity(size + 1);
System.arraycopy(elements, index, elements, index + 1, size - index);
elements[index] = element;
++size;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index
* The index of the element to removed.
*
* @return
* The element that was removed from the list.
*
* @exception IndexOutOfBoundsException
* If index is out of range (index < 0 || index >= size()).
*/
public int remove(int index)
{
rangeCheck(index);
int oldValue = elements[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elements, index + 1, elements, index, numMoved);
--size;
return oldValue;
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear()
{
size = 0;
}
/**
* Appends all of the elements in the specified array to the end of this
* list.
*
* @param ai
* The elements to be added to this list.
*/
public void addAll(int[] ai)
{
int numNew = ai.length;
ensureCapacity(size + numNew);
System.arraycopy(ai, 0, elements, size, numNew);
}
/**
* Inserts all of the elements in the specified array into this list,
* starting at the specified position.
* Shifts the element currently at that position (if any) and any subsequent
* elements to the right (increases their indices).
* The new elements will appear in the list in the order that they exist in
* the array argument.
*
* @param index
* Index at which to insert first element from the specified array.
* @param ai
* Elements to be inserted into this list.
*
* @exception IndexOutOfBoundsException
* If index is out of range (index < 0 || index > size()).
*/
public void addAll(int index, int[] ai)
{
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
int numNew = ai.length;
ensureCapacity(size + numNew);
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elements, index, elements, index + numNew, numMoved);
System.arraycopy(ai, 0, elements, index, numNew);
size += numNew;
}
/**
* Returns true if this list contains all of the elements in the
* specified list.
*
* This implementation iterates over the specified array, checking each
* element in turn to see if it's contained in this list.
* If all elements are so contained true is returned, otherwise
* false.
*
* @param ai
* Array to be checked for containment in this list.
*
* @return
* true if this list contains all of the elements in the
* specified array.
*
* @see #contains
*/
public boolean containsAll(int[] ai)
{
for (int i = 0; i < ai.length; ++i)
{
if (!contains(ai[i]))
return false;
}
return true;
}
/**
* Removes from this list all of its elements that are contained in the
* specified array.
*
* This implementation iterates over this list, checking each element in
* turn to see if it's contained in the specified array.
* If it's so contained, it's removed from this list.
*
* @param ai
* Elements to be removed from this list.
*
* @return
* true if this list changed as a result of the call.
*
* @see #remove
* @see #contains
*/
public boolean removeAll(int[] ai)
{
IntArrayList l = new IntArrayList(ai);
boolean modified = false;
for (int i = 0; i < size; ++i)
{
while (i < size && l.contains(elements[i]))
{
remove(i);
modified = true;
}
}
return modified;
}
/**
* Retains only the elements in this list that are contained in the
* specified array.
* In other words, removes from this list all of its elements that are not
* contained in the specified array.
*
* This implementation iterates over this list, checking each element in
* turn to see if it's contained in the specified array.
* If it's not so contained, it's removed from this list.
*
* @param ai
* Elements to be retained in this list.
*
* @return
* true if this list changed as a result of the call.
*
* @see #remove
* @see #contains
*/
public boolean retainAll(int[] ai)
{
IntArrayList l = new IntArrayList(ai);
boolean modified = false;
for (int i = 0; i < size; ++i)
{
while (i < size && !l.contains(elements[i]))
{
remove(i);
modified = true;
}
}
return modified;
}
/**
* Compares the specified object with this list for equality.
* Returns true if and only if the specified object is also an
* IntArrayList, both lists have the same size, and all corresponding pairs
* of elements in the two lists are equal.
*
* @param o the object to be compared for equality with this list.
*
* @return true if the specified object is equal to this list.
*/
public boolean equals(Object o)
{
if (o == this)
return true;
if (!(o instanceof IntArrayList))
return false;
return Arrays.equals(toArray(), ((IntArrayList)o).toArray());
}
/**
* Returns the hash code value for this list.
*
* @return The hash code value for this list.
*/
public int hashCode()
{
int hashCode = 1;
for (int i = 0; i < size; ++i)
hashCode = 31 * hashCode + elements[i];
return hashCode;
}
/**
* Returns a string representation of this list.
* The string representation consists of a list of the elements, enclosed
* in square brackets ("[]").
* Adjacent elements are separated by the characters ", " (comma
* and space).
* Elements are converted to strings as by String.valueOf(int).
*
* @return
* A string representation of this collection.
*/
public String toString()
{
StringBuffer buf = new StringBuffer();
buf.append('[');
for (int i = 0; i < size; ++i)
{
if (i > 0)
buf.append(", ");
buf.append(elements[i]);
}
buf.append(']');
return buf.toString();
}
}