TransWikia.com

Circular Array - OOP

Code Review Asked on December 22, 2021

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

}

One Answer

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

Answered by Joop Eggen on December 22, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP