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;
    }

}