4
\$\begingroup\$

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
    }
\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

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.

\$\endgroup\$
-5
\$\begingroup\$

Try using ArrayList:

import java.util.ArrayList;

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

\$\endgroup\$
1
  • \$\begingroup\$ 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? \$\endgroup\$
    – SirPython
    Oct 2, 2015 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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