Implementation of a list-like array

Question

This is a follow up question for this question:

Implementation of a dynamic list-like array

---

This is an implementation of an array that behaves like a list, granting me an easy and quick way to:

• quickly add items
• iterate over them without caring for empty spots in the array
• quickly remove iterated items

After following user rolfl answer I revised my class to this

import java.lang.reflect.Array;
import java.util.Iterator;
import java.util.stream.IntStream;

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

    private final T[] mItems;
    private final int[] mSlots;
    private int mSlotsTop = -1;

    public final int size;


    private int mIteratedIndex = -1;

    @SuppressWarnings("unchecked")
    public BucketArray(Class<T> cast, int size) {
        this.size = size;
        mItems = (T[]) Array.newInstance(cast, size);
        mSlots = IntStream.range(0, size).toArray();
        mSlotsTop = size - 1;
    }

    public int add(T item) {
        if (item == null)
            return -1;
        if (mSlotsTop < 0)
            return -1;
        final int slot = popSlot();
        mItems[slot] = item;        
        return slot;
    }

    public void addAll(T... items) {
        for (T item : items)
            add(item);
    }

    public T get(int i) {
        if (i < 0 || i >= size)
            throw new IndexOutOfBoundsException();
        return mItems[i];
    }

    public int getIteratedIndex() {
        return mIteratedIndex;
    }

    public boolean remove(int i) {
        if (i < 0 || i > size)
            return false;
        if (mItems[i] == null)
            return false;
        mItems[i] = null;
        pushSlot(i);
        return true;
    }

    public void remove(T item) {
        remove(indexOf(item));
    }

    public boolean removeIterated() {
        return remove(mIteratedIndex);
    }

    public boolean isFull() {
        return mSlotsTop == -1;
    }

    public boolean isEmpty() {
        return mSlotsTop == size - 1;
    }

    public int numFreeSlots() {
        return mSlotsTop + 1;
    }

    public int indexOf(T item) {
        for (int i = 0; i < size; i++)
            if (item == mItems[i])
                return i;
        return -1;
    }

    private int popSlot() {
        return mSlots[mSlotsTop--];
    }

    private void pushSlot(int s) {
        mSlots[++mSlotsTop] = s;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private int index = -1;
            {
                if (mIteratedIndex != -1)
                    index = mIteratedIndex;
            }

            @Override
            public boolean hasNext() {
                do {
                    index++;
                    if (index >= size) {
                        mIteratedIndex = -1;
                        return false;
                    }
                } while (mItems[index] == null);
                return true;
            }

            @Override
            public T next() {
                mIteratedIndex = index;
                return mItems[index];
            }
        };
    }
}

Major changes:

• add() method now ignores null and returns the index of the inserted item so it can be used with get() and remove().
• After some thought, the remove() method mostly used in the context of an iteration, so I added removeIterated() method that removes the currently iterated item in the scope of an iteration being made.
• Name of the class changed to BucketArray from BagArray because it sounds better.

Usage example in deleting duplicated integer values:

public static void main(String[] args) {
        BucketArray<Integer> mBucket = new BucketArray<Integer>(Integer.class,20);
        mBucket.addAll(10, 20, 30, 20, 20, 30, 10, 40);
        // bucket is: 40, 10, 30, 20, 20, 30, 20, 10
        for (int a : mBucket)
            for (int b : mBucket)
                if (a == b)
                    mBucket.removeIterated();
        // bucket is now: 40, 10, 30, 20
    }

Answer 1

Potential bug #1

The problem of using a class variable mIteratedIndex that is modifiable in every new Iterator instance created is simply, multiple such instances cannot iterate through the contents reliably.

Potential bug #2

This is also related to Iterator in the hasNext() method: calling it twice without a next() effectively skips one element. Usually, the iteration state should not be modified when doing a hasNext(), but you have a index++ inside it.

Potential bug #3

The other problem with having index++ inside the hasNext() is that callers cannot reliably retrieve the next() element without calling hasNext() first.

Illustrating all bugs

public static void main(String[] args) {
    BucketArray<String> instance = new BucketArray<>(String.class, 3);
    instance.addAll("first", "middle", "last");
    Iterator<String> i1 = instance.iterator();
    i1.hasNext();
    i1.hasNext();
    System.out.println(i1.next());
    Iterator<String> i2 = instance.iterator();
    i2.hasNext();
    System.out.println(i2.next());
    System.out.println(i2.next());
    i2.hasNext();
    System.out.println(i2.next());
}

Output:

middle
first
first
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3

i1.hasNext() has to be called before i1.next(), else there will be an ArrayIndexOutOfBoundsException: -1 error. When i1.hasNext() is called twice in succession, "middle" is returned from calling i1.next(), skipping the first element.

When we have a new i2 Iterator, it starts from where i1 left off, which bizarrely returns "first" since that was stored as the final element of the internal array - is this expected? Regardless, calling i2.next() twice returns the same value, when it shouldn't. Finally, calling the pair of hasNext()/next() methods triggers the ArrayIndexOutOfBoundsException: 3 error as i2 would have iterated past the contents of the array.

Answer 2

Try using ArrayList:

import java.util.ArrayList;

It's a dynamic array and has features such as insertion, deletion, etc.