Implementation of a dynamic list-like array

Question

I needed to address an issue that I met with quite a bit, which has sort of a bag of data that I can easily add items and remove them, and iterate over them at any point without an issue.

First thing that came to mind was to use a linked list: easy to add, easy to remove, without having blank spaces in between, but the use of a linked list didn't look optimal to me.

I made a class in Java called BagArray that behaves like a list in terms of adding and removing items, and is easily iterated over with a for-each without having blank spaces.

It is a mix of a normal array to store the data, and a stack that stores indices of the normal array in which it is free to add an item without deleting another one.

import java.util.Iterator;

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

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

    public final int size;

    public BagArray(int size) {
        this.size = size;
        mItems = new Object[size];
        mSlots = new int[size];
        for (int i = 0; i < size; i++)
            mSlots[i] = i;
        mSlotsTop = size - 1;
    }

    public boolean add(T item) {
        if (mSlotsTop < 0)
            return false;
        mItems[popSlot()] = item;
        return true;
    }

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

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

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

    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;

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

            @Override
            @SuppressWarnings("unchecked")
            public T next() {
                return (T) mItems[index];
            }
        };
    }
}

Important thing to notice here is that the time complexity of the add(), get() and remove(index) methods are \$O(1)\$, which are the essential utilities of this class.

It is also Iterable while the for-each will skip blank spaces in the array.

This makes the use of the class very easy when we need to just "throw some items into a bag or replace them" and iterate over them quickly.

What are your opinions? Is this a good implementation, or is there another way?

Answer 1

This is an interesting concept, a size-limited "bucket" of not-guaranteed-order items. You are right that the add and remove are O(1) operations, but there are a number of concerns I have.... some of them are severe.

1. If someone adds a null value, you are broken in the iterator. You need to accommodate null, or throw an exception.
2. The get(int) and remove(int) methods are useless - how does the user know what int to use? The first item added is placed at index size - 1, and so on, so how does that work?

Then, there's a trick with Collections that have a generic type. The general concensus in Java is that you should pass the class definition in to the constructor. The standard Java collections can't do that for backward compatibility reasons, but, consider this:

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

    private final T[] mItems;
    public BagArray(Class<T> tClass, int size) {
        @SuppressWarnings("unchecked")
        mItems = (T[]) Array.newInstance(tClass, size);

Note two things there...

1. In Java, by convention, you declare arrays as T[] mItems, and not T mItems[]
2. The array now has the correct type, and there's only one place you need to cast the values, and that is in the array creation.

One last thing, in Java 8, a nice trick for creating an array populated with sequential numbers is:

int[] values = IntStream.range(startInclusive, endExclusive).toArray();

Answer 2

You should re-read your problem description. You are describing a Set.

On a general note, I think developers should avoid writing low-level stuff since it is nearly always available in the base classes, or maybe in guava. If you were working for me and I was reviewing your code, I would be upset that you spend some time working on something like this. No problem if you are doing this for fun though...