The Iterator
is a second stage provision for API users. As such I will not comment on it.
The package name should not contain capitals. It is only a convention, but for java it is maintained relatively strict in the community, due to the hundreds of libraries.
Using T[]
or rather Object[]
requires some disregard to typing. I solved that by passing the class of T: Integer.class
or such. Alternatively one could use ArrayList<T>
instead of T[]
. Then there is full generic typing.
protected
is a dubious choice for such a container class, but maybe a next task would be to add functionality in the form of a child class.
Now to the critics:
limit
should rather be a parameter in the constructor, made two constructors, one with a default limit. As limit is redundant, equal to array.length
you need not have it as field.
- You can use
final
for unchanging fields.
index
and pointer
are no-names, often unsuited for fields.
- No display of really using circularity, start index and end index running around.
Delete in the middle is atypical for a circular array, should not go from 0 to length, and should actually delete
9
in 3 9 5
.
Here I represented circularity by a size
to distinghuish empty from full, and a start index consumeIndex
and an end index produceIndex
. Modulo array.length
is needed.
findIndex
used ==
but the Object wrappers are hideous: Integer.valueOf(3) == Integer.valueOf(3)
(internal cache upto 128) but Integer.valueOf(300) == Integer.valueOf(300)
. So use equals
.
So (not guaranteeing correctness):
import java.lang.reflect.Array;
public class CircularArray<T> {
public static final int DEFAULT_LIMIT = 5;
private final Class<T> elementType;
private final T[] array;
private int consumeIndex = 0;
private int produceIndex = 0;
private int size = 0;
public CircularArray(Class<T> elementType) {
this(elementType, DEFAULT_LIMIT);
}
public CircularArray(Class<T> elementType, int limit) {
this.elementType = elementType;
array = (T[]) Array.newInstance(elementType, limit);
}
public void add(T data) {
if (size == array.length) {
throw new IllegalStateException("CircularArray is full");
}
array[produceIndex++] = data;
if (produceIndex >= array.length) {
produceIndex = 0;
}
size++;
}
public void delete(T data) {
// 4 5 9 11 1
// delete 9
int deleteIndex = findIndex(data);
if (deleteIndex == -1) {
return;
}
for (int index = deleteIndex; (index + 1) % array.length != produceIndex; ++index) {
array[index] = array[(index + 1) % array.length];
}
produceIndex = (produceIndex - 1 + array.length) % array.length;
--size;
}
private int findIndex(T data) {
for (int i = 0; i < size; i++) {
int index = (consumeIndex + i) % size;
if (array[index].equals(data)) {
return index;
}
}
return -1;
}
}
Some test code (as requested by comment)
CircularArray<Integer> ca = new CircularArray<>(Integer.class);
ca.add(1);
ca.add(2);
ca.add(3);
ca.add(4);
ca.add(5);
try {
ca.add(6);
throw new IndexOutOfBoundsException("Overflow expected");
} catch (IllegalStateException e) {
System.out.println("Expected overflow");
}
int i = ca.delete(3);
if (i != 2) {
throw new IllegalStateException();
}
ca.delete(1);
ca.add(7);
ca.add(8)
int i = ca.findIndex(8);
if (i != 0) {
throw new IllegalStateException();
}
This is not real testing, more demo, and unit tests are a different thing, with many scenarios. Also note that the code can be optimized, for instance for deleting the first element:
public void delete(T data) {
// 4 5 9 11 1
// delete 9
int deleteIndex = findIndex(data);
if (deleteIndex == -1) {
return;
}
// Optimisation:
if (deleteIndex == consumeIndex) {
consumeIndex = (consumeIndex + 1) % array.length;
return;
}