Array List
package iteration;
public interface Iterable {
public Iterator iterator();
}
package dataStructures;
import iteration.Iterable;
public interface List extends Iterable {
public void insert(int index, Object value)
throws IndexOutOfBoundsException;
public void add(Object value);
public Object delete(int index) throws IndexOutOfBoundsException;
public boolean delete(Object value);
public void clear();
public Object set(int index, Object value)
throws IndexOutOfBoundsException;
public Object get(int index) throws IndexOutOfBoundsException;
public int indexOf(Object value);
public boolean contains(Object value);
public int size();
public boolean isEmpty();
}
package sorting;
import dataStructures.List;
public interface ListSorter {
public List sort(List list);
}
package iteration;
public interface Iterator {
public void first();
public void last();
public boolean isDone();
public void next();
public void previous();
public Object current() throws IteratorOutOfBoundsException;
}
package iteration;
public class ArrayIterator implements Iterator {
private final Object[] _array;
private final int _first;
private final int _last;
private int _current = -1;
public ArrayIterator(Object[] array, int start, int length) {
assert array != null : "array can’t be null";
assert start >= 0 : "start can’t be < 0";
assert start < array.length : "start can’t be > array.length";
assert length >= 0 : "length can’t be < 0";
_array = array;
_first = start;
_last = start + length - 1;
assert _last < array.length : "start + length can’t be > array.length";
}
public ArrayIterator(Object[] array) {
assert array != null : "array can’t be null";
_array = array;
_first = 0;
_last = array.length - 1;
}
public void first() {
_current = _first;
}
public void last() {
_current = _last;
}
public void next() {
++_current;
}
public void previous() {
--_current;
}
public boolean isDone() {
return _current < _first || _current > _last;
}
public Object current() throws IteratorOutOfBoundsException {
if (isDone()) {
throw new IteratorOutOfBoundsException();
}
return _array[_current];
}
}
package dataStructures;
import iteration.ArrayIterator;
import iteration.Iterator;
public class ArrayList implements List {
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private final int _initialCapacity;
private Object[] _array;
private int _size;
public ArrayList() {
this(DEFAULT_INITIAL_CAPACITY);
}
public ArrayList(int initialCapacity) {
assert initialCapacity > 0 : "initialCapacity must be > 0";
_initialCapacity = initialCapacity;
clear();
}
public void clear() {
_array = new Object[_initialCapacity];
_size = 0;
}
public void insert(int index, Object value)
throws IndexOutOfBoundsException {
assert value != null : "value can’t be null";
if (index < 0 || index > _size) {
throw new IndexOutOfBoundsException();
}
ensureCapacity(_size + 1);
System.arraycopy(_array, index, _array, index + 1, _size - index);
_array[index] = value;
++_size;
}
private void ensureCapacity(int capacity) {
assert capacity > 0 : "capacity must be > 0";
if (_array.length < capacity) {
Object[] copy = new Object[capacity + capacity / 2];
System.arraycopy(_array, 0, copy, 0, _size);
_array = copy;
}
}
public void add(Object value) {
insert(_size, value);
}
public Object get(int index) throws IndexOutOfBoundsException {
checkOutOfBounds(index);
return _array[index];
}
public Object set(int index, Object value)
throws IndexOutOfBoundsException {
assert value != null : "value can’t be null";
checkOutOfBounds(index);
Object oldValue = _array[index];
_array[index] = value;
return oldValue;
}
private void checkOutOfBounds(int index) {
if (isOutOfBounds(index)) {
throw new IndexOutOfBoundsException();
}
}
private boolean isOutOfBounds(int index) {
return index < 0 || index >= _size;
}
public int indexOf(Object value) {
assert value != null : "value can’t be null";
for (int i = 0; i < _size; ++i) {
if (value.equals(_array[i])) {
return i;
}
}
return -1;
}
public boolean contains(Object value) {
return indexOf(value) != -1;
}
public Object delete(int index) throws IndexOutOfBoundsException {
checkOutOfBounds(index);
Object value = _array[index];
int copyFromIndex = index + 1;
if (copyFromIndex < _size) {
System.arraycopy(_array, copyFromIndex,
_array, index,
_size - copyFromIndex);
}
_array[--_size] = null;
return value;
}
public boolean delete(Object value) {
int index = indexOf(value);
if (index != -1) {
delete(index);
return true;
}
return false;
}
public Iterator iterator() {
return new ArrayIterator(_array, 0, _size);
}
public int size() {
return _size;
}
public boolean isEmpty() {
return size() == 0;
}
}