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.

• SirPython: Welcome to Code Review! Please add more context to you question: how could the OP use this? What is this replacing? Why should the use this? Why is this better than what the OP already has?