Implementation of a list-like array 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&lt;T&gt; implements Iterable&lt;T&gt; {

    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&lt;T&gt; 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 &lt; 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 &lt; 0 || i &gt;= size)
            throw new IndexOutOfBoundsException();
        return mItems[i];
    }

    public int getIteratedIndex() {
        return mIteratedIndex;
    }

    public boolean remove(int i) {
        if (i &lt; 0 || i &gt; 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 &lt; 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&lt;T&gt; iterator() {
        return new Iterator&lt;T&gt;() {
            private int index = -1;
            {
                if (mIteratedIndex != -1)
                    index = mIteratedIndex;
            }

            @Override
            public boolean hasNext() {
                do {
                    index++;
                    if (index &gt;= 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&lt;Integer&gt; mBucket = new BucketArray&lt;Integer&gt;(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
    }
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&lt;String&gt; instance = new BucketArray&lt;&gt;(String.class, 3);
    instance.addAll("first", "middle", "last");
    Iterator&lt;String&gt; i1 = instance.iterator();
    i1.hasNext();
    i1.hasNext();
    System.out.println(i1.next());
    Iterator&lt;String&gt; 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.