There is a small bug: In the method add(int, int)
, it should probably be
if (index > length || index < 0)
throw new ArrayIndexOutOfBoundsException(index);
instead of
if (index >= length || index < 0)
throw new ArrayIndexOutOfBoundsException(index);
Inserting at the index length
would just mean appending an element to the end of the iVector, so an index of length
wouldn't be invalid.
Also, data.length + data.length/2
might overflow for very large values of length
. You could prepare for this by checking whether Integer.MAX_VALUE - data.length/2 >= data.length
.
In the method ensureCapacity(int)
, it would suffice to copy length
elements instead of data.length
elements, since the values of all elements in data
with an index equal to or greater than length
are irrelevant.
You could simply call add(length, value)
from add(int value)
, because right now, the code of add(int)
is effectively duplicated in add(int, int)
. If the reason for this is performance due to the unnecessity of argument validation, this would probably only be relevant for a very large number of successive additions, and for this, you could make a separate bulk method like addAll
(which could also employ other optimizations like calling System.arraycopy
instead of manually copying each element via iteration).
public void remove(){
if(length == 0) return;
--length;
}
Can be written more concisely as:
public void remove(){
if(length != 0) --length;
}
remove()
returns void
whereas remove(int index)
returns the value previously at index
. This is inconsistent. I suggest you make remove()
also return the previously last element.
It occurred to me that, if the internal array can contain "vacant lots" at the end, it could also contain vacant lots at the beginning. For example, consider this array with a capacity of 10, containing 6 elements:
abcfgh----
Now, if you want to delete a
from the array, your code would do this:
bcfgh-----
I.e. delete the first element and shift all subsequent elements to the left by one position. But it would be much more efficient to do this:
-bcfgh----
This would also require a pointer to the first element in addition to a field that stores the number of elements in the iVector. And if you want to insert or delete an element, you could calculate for each direction how many elements would have to be shifted, and then perform the cheaper of the two variants and update the respective pointer accordingly. For example, if you now want to insert e
between c
and f
, a "left-push" would require two elements to be moved (bc
), whereas a "right-push" would require three elements to be moved (fgh
), so the left-push variant would be cheaper:
bcefgh----
In fact, the array could even wrap around. If you now want to insert d
before e
, you could do this:
cdefgh---b
While this would make simple get
or set
operations a tiny bit more expensive, because you would have to calculate the index for the internal array from the public index for the iVector
, I guess that this can save quite a bit of performance for add
or remove
operations on the lower half of the iVector.
Update
So I've tried to implement the wraparound suggestion myself, and the code now seems to be about twice as fast as your version when removing and inserting from/to random positions in the vector. When only operating on the upper half, it is, of course, a little bit slower, because the overhead is never compensated for by shifting fewer elements than your original code. Here is my implementation:
public class IntArrayList {
private int[] data;
private int size;
private int indexOfFirstElement;
public IntArrayList() {
this(10);
}
public IntArrayList(int initialCapacity) {
data = new int[Math.max(initialCapacity, 10)];
size = 0;
indexOfFirstElement = 0;
}
public int size() {
return size;
}
/**
* Returns the index of the element in the internal array that is
* {@code offset} positions away from the element at the index
* {@code index}, wrapping around the array if necessary.
* {@code offset} can be negative, in which case the distance will be
* traveled to the left of the original element rather than to the right.
* This method assumes that the passed index is valid and that the
* absolute value of {@code offset} is not greater
* than the length of the internal array. If these conditions are not
* met, the returned index might not be valid.
*
* @param index a valid index for the internal array
* @param offset the distance from the element at index {@code index}; may be negative
* @return the index of the array element at the specified distance
*/
private int indexForOffset(int index, int offset) {
int offsetIndex = index + offset; //might overflow
if (data.length - index <= offset) { //includes cases where the previous line overflows
offsetIndex -= data.length;
} else if (offsetIndex < 0) { //cannot be the result of an overflow
offsetIndex += data.length;
}
return offsetIndex;
}
public void ensureCapacity(final int capacity) {
if (capacity > data.length) {
int[] newData = new int[capacity];
if (size != 0) {
if (indexOfFirstElement <= indexForOffset(indexOfFirstElement, size - 1)) {
System.arraycopy(data, indexOfFirstElement, newData, 0, size);
} else {
System.arraycopy(data, indexOfFirstElement, newData, 0, data.length - indexOfFirstElement);
System.arraycopy(data, 0, newData, data.length - indexOfFirstElement, indexOfFirstElement + size - data.length);
}
}
data = newData;
indexOfFirstElement = 0;
}
}
/**
* Converts an index for this {@code IntArrayList} to the
* corresponding index for the internal array. This method
* assumes that the passed index is valid. If it is not,
* the returned index might not be valid as well.
*
* @param publicIndex A valid index for this {@code IntArrayList}
* @return the index pointing to the corresponding element in the internal array
*/
private int internalArrayIndex(int publicIndex) {
int internalArrayIndex = publicIndex + indexOfFirstElement;
if (internalArrayIndex < 0 || internalArrayIndex >= data.length) {
internalArrayIndex -= data.length;
}
return internalArrayIndex;
}
public void add(final int value) {
add(size, value);
}
public void add(final int index, final int value) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException(index);
}
if (size == data.length) {
if (data.length == Integer.MAX_VALUE) {
throw new OutOfMemoryError();
} else {
int newCapacity = data.length + data.length / 2; // Grow by approx. 1.5x
if (newCapacity < 0) { //overflow
newCapacity = Integer.MAX_VALUE;
}
ensureCapacity(newCapacity);
}
}
int internalInsertionIndex = internalArrayIndex(index);
if (index >= (size + 1) >>> 1) { //right-push
moveRangeWrapping(data, internalInsertionIndex, 1, size - index);
} else { //left-push
internalInsertionIndex = indexForOffset(internalInsertionIndex, -1);
moveRangeWrapping(data, indexOfFirstElement, -1, index);
indexOfFirstElement = indexForOffset(indexOfFirstElement, -1);
}
data[internalInsertionIndex] = value;
size++;
}
public void set(final int index, final int value) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException(index);
}
data[internalArrayIndex(index)] = value;
}
public int get(final int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException(index);
}
return data[internalArrayIndex(index)];
}
public int remove() {
return remove(size - 1);
}
public int remove(int index) {
final int result = get(index);
int internalDeletionIndex = internalArrayIndex(index);
if (index >= size / 2) { //right-side-pull
moveRangeWrapping(data, indexForOffset(internalDeletionIndex, 1), -1, size - index - 1);
} else { //left-side-pull
moveRangeWrapping(data, indexOfFirstElement, 1, index);
indexOfFirstElement = indexForOffset(indexOfFirstElement, 1);
}
size--;
return result;
}
public void clear() {
size = 0;
indexOfFirstElement = 0;
}
@Override
public int hashCode() {
int hashCode = 1;
for (int i = 0; i < size; i++) {
hashCode = 31 * hashCode + get(i);
}
return hashCode;
}
//moves a range without wrapping around
private static void moveRange(int[] array, int sourceStartPosition, int destinationStartPosition, int length) {
if (sourceStartPosition < 0 || destinationStartPosition < 0 || length < 0
|| sourceStartPosition > array.length - length
|| destinationStartPosition > array.length - length) {
throw new IndexOutOfBoundsException();
}
int offset = destinationStartPosition - sourceStartPosition;
if (offset > 0) {
for (int i = destinationStartPosition + length - 1; i >= destinationStartPosition; i--) {
array[i] = array[i - offset];
}
} else if (offset < 0) {
for (int i = destinationStartPosition; i < destinationStartPosition + length; i++) {
array[i] = array[i - offset];
}
}
}
//moves a range, wrapping around if necessary; requires that the foremost element
//in the direction to be moved would not overwrite another element from the range to be moved
private static void moveRangeWrapping(int[] array, int sourceStartPosition, int offset, int length) {
if (length < 0 || length > array.length - Math.abs(offset)
|| sourceStartPosition < 0 || sourceStartPosition >= array.length) {
throw new IndexOutOfBoundsException();
}
if (offset > 0) {
if (sourceStartPosition > array.length - length - offset) {
if (sourceStartPosition > array.length - length) {
moveRange(array, 0, offset, sourceStartPosition + length - array.length);
}
int tempStartPosition = Math.max(array.length - offset, sourceStartPosition);
moveRange(array, tempStartPosition, tempStartPosition + offset - array.length, (sourceStartPosition < array.length - length ? sourceStartPosition + length : array.length) - tempStartPosition);
}
if (array.length - offset > sourceStartPosition) {
moveRange(array, sourceStartPosition, sourceStartPosition + offset, Math.min(length, array.length - offset - sourceStartPosition));
}
} else if (offset < 0) {
//sourceEndPosition is from 1 to array.length, inclusive
int sourceEndPosition = sourceStartPosition + length;
if (sourceEndPosition > array.length || sourceEndPosition < 0) {
sourceEndPosition -= array.length;
}
if (sourceEndPosition + offset < length) {
if (sourceEndPosition < length) {
moveRange(array, sourceStartPosition, sourceStartPosition + offset, array.length - sourceStartPosition);
}
int tempStartPosition = Math.max(0, sourceEndPosition - length);
moveRange(array, tempStartPosition, tempStartPosition + offset + array.length, Math.min(-offset, sourceEndPosition) - tempStartPosition);
}
if (sourceEndPosition + offset > 0) {
int tempStartPosition = Math.max(-offset, sourceEndPosition - length);
moveRange(array, tempStartPosition, tempStartPosition + offset, sourceEndPosition - tempStartPosition);
}
}
}
}
I've renamed length
to size
because I found length
just too confusing with data.length
always coming up somewhere. I've also replaced some of your ArrayIndexOutOfBoundsException
s with IndexOutOfBoundsException
s, since an ArrayIndexOutOfBoundsException
is only meant for arrays, and not for any index-based data structure.
Unfortunately, the method moveRangeWrapping
is an eyesore. Maybe this can be mitigated by introducing more local variables, but the problem is the constant threat of overflows, which often requires the comparison statements in a way that they don't lend themselves to use local variables (e.g. if (sourceStartPosition > array.length - length)
instead of if (sourceStartPosition + length > array.length)
), so I'm not sure how much can be done about this.
In addition, I've implemented hashCode()
so that it produces a hash equivalent to the hash code of an analogous List<Integer>
, which can be used both for testing purposes and to prevent clever compiler optimizations (hopefully).