76 lines
2.3 KiB
Java
76 lines
2.3 KiB
Java
package net.datastructures;
|
|
//begin#fragment vector
|
|
/** Realization of an indexed list by means of an array, which is doubled
|
|
* when the size of the indexed list exceeds the capacity of the array.
|
|
//end#fragment vector
|
|
*
|
|
* @author Roberto Tamassia, Michael Goodrich
|
|
//begin#fragment vector
|
|
*/
|
|
public class ArrayIndexList<E> implements IndexList<E> {
|
|
private E[] A; // array storing the elements of the indexed list
|
|
private int capacity = 16; // initial length of array A
|
|
private int size = 0; // number of elements stored in the indexed list
|
|
/** Creates the indexed list with initial capacity 16. */
|
|
public ArrayIndexList() {
|
|
A = (E[]) new Object[capacity]; // the compiler may warn, but this is ok
|
|
}
|
|
//end#fragment vector
|
|
/** Returns the number of elements in the indexed list. */
|
|
public int size() {
|
|
return size;
|
|
}
|
|
/** Returns whether the indexed list is empty. */
|
|
public boolean isEmpty() {
|
|
return size() == 0;
|
|
}
|
|
/** Returns the element stored at the given index. */
|
|
public E get(int r)
|
|
throws IndexOutOfBoundsException {
|
|
checkIndex(r, size());
|
|
return A[r];
|
|
}
|
|
/** Replaces the element stored at the given index. */
|
|
public E set(int r, E e)
|
|
throws IndexOutOfBoundsException {
|
|
checkIndex(r, size());
|
|
E temp = A[r];
|
|
A[r] = e;
|
|
return temp;
|
|
}
|
|
//begin#fragment vector list
|
|
/** Inserts an element at the given index. */
|
|
public void add(int r, E e)
|
|
throws IndexOutOfBoundsException {
|
|
checkIndex(r, size() + 1);
|
|
if (size == capacity) { // an overflow
|
|
capacity *= 2;
|
|
E[] B =(E[]) new Object[capacity];
|
|
for (int i=0; i<size; i++)
|
|
B[i] = A[i];
|
|
A = B;
|
|
}
|
|
for (int i=size-1; i>=r; i--) // shift elements up
|
|
A[i+1] = A[i];
|
|
A[r] = e;
|
|
size++;
|
|
}
|
|
/** Removes the element stored at the given index. */
|
|
public E remove(int r)
|
|
throws IndexOutOfBoundsException {
|
|
checkIndex(r, size());
|
|
E temp = A[r];
|
|
for (int i=r; i<size-1; i++) // shift elements down
|
|
A[i] = A[i+1];
|
|
size--;
|
|
return temp;
|
|
}
|
|
//end#fragment vector
|
|
/** Checks whether the given index is in the range [0, n - 1] */
|
|
protected void checkIndex(int r, int n) //
|
|
throws IndexOutOfBoundsException { //
|
|
if (r < 0 || r >= n)
|
|
throw new IndexOutOfBoundsException("Illegal index: " + r);
|
|
}
|
|
}
|