5
\$\begingroup\$

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?

\$\endgroup\$
1

2 Answers 2

6
\$\begingroup\$

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();
\$\endgroup\$
2
0
\$\begingroup\$

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...

\$\endgroup\$
3
  • \$\begingroup\$ I do not completely agree with you that what I am describing is Set, firstly, it can contain duplicates, and secodnly, the idea is that the add and remove methods are O(1), and yes I am doing it for fun, just a utility class for my private use, please see my follow up question for this one: codereview.stackexchange.com/questions/106360/… \$\endgroup\$ Oct 2, 2015 at 17:28
  • \$\begingroup\$ If you want duplicates, see guava's MultiSet. \$\endgroup\$
    – toto2
    Oct 2, 2015 at 17:45
  • \$\begingroup\$ The duplicates are not the issue, my goal was to make an easy to use array that supports adding elements until the array is full, even if some of them are randomly removed, with O(1) complexity. And removing elements at O(1) complexity, this revision of the code is outdated, see the new revision in the link above \$\endgroup\$ Oct 2, 2015 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.