3
\$\begingroup\$

I have a solution for a circular array. How can I improve this?

package oopdesign.CircularArrayNes;

import java.util.Iterator;
import java.util.Spliterator;
import java.util.function.Consumer;

public class ArrayIterator<T> implements Iterable<T> {

    @Override
    public Iterator<T> iterator() {
        return null;
    }

    @Override
    public void forEach(Consumer<? super T> action) {

    }

    @Override
    public Spliterator<T> spliterator() {
        return null;
    }
}

package oopdesign.CircularArrayNes;

public class CircularArray<T> {

    protected T[] array;
    protected int limit;
    protected int pointer;
    protected int index;


    protected CircularArray(){
        limit = 5;
        T[] array = (T[])new Object[limit];
        pointer = 0;
        index = 0;
    }

    public void add(T data){
        index = getCurrentIndex() + 1;
        array[index] = data;
        pointer++;
    }

    public int getCurrentIndex()
    {
        return (pointer) % limit;
    }

    public void delete(T data){
        // 4 5 9 11 1
        // delete 9
        int deleteIndex = findIndex(data);
        if (deleteIndex == -1) return;
        for(int i=deleteIndex;i< array.length-1;i++) {
            array[deleteIndex] = array[deleteIndex+1];
        }
        pointer-- ;
    }

    private int findIndex(T data) {
        for(int i=0;i< array.length;i++) {
          if (array[i] == data){
              return i;
          }
        }
        return -1;
    }

}
\$\endgroup\$
3
2
\$\begingroup\$

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;
        }
\$\endgroup\$
8
  • \$\begingroup\$ It seems me there is a typo array in the produceIndex of method delete. I have a question, could you explain me for Integer comparison about internal cache up to 128 ? Thanks in advance for your time. \$\endgroup\$ – dariosicily Apr 19 '20 at 15:56
  • 1
    \$\begingroup\$ The JVM has a (configurable) cache of Integer.valueOf of -128 to 127, also used by auto-boxing. These 256 Integer objects derived from autoboxing are identical (==) objects. An other int value can lead to several Integer objects instances with the same value (!=). Will correct \$\endgroup\$ – Joop Eggen Apr 19 '20 at 20:19
  • \$\begingroup\$ I got it, thank you for your answer. \$\endgroup\$ – dariosicily Apr 20 '20 at 6:33
  • \$\begingroup\$ @JoopEggen could you add a test as well, please? Thanks. \$\endgroup\$ – Neslihan Bozer Jul 24 '20 at 2:43
  • \$\begingroup\$ @NeslihanBozer Was that a hint, that my code is not entirely correct? That could well be. In every case I have added some testing code. Not tested any code in an IDE, as the class as presented is not interesting (missing functionality). \$\endgroup\$ – Joop Eggen Jul 24 '20 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.