Making this arraycopy more efficient

I'd like to find out how I can make my function more efficient:

public boolean addAll(int i, Collection c) {
    for (T x : c)
        add(i++, x);
    return true;
}

public void add(int i, T x) {
    if (n + 1 > a.length) resize();
    System.arraycopy(a, i, a, i+1, n-i);
    a[i] = x;
    n++;
}

protected void resize() {
    T[] b = f.newArray(Math.max(2 * n,1));
    System.arraycopy(a, 0, b, 0, n);
    a = b;
}

I'm not sure what else I can do to implement a more efficient way to use my addAll() function.

As @Brythan suggested, you should rename your variables. I propose:

• arr instead of a

• size instead of n

• index instead of i

• copy instead of b

• items or elements or collection instead of c

I suppose that addAll returns a boolean to mimic the behavior of Collections.addAll. That is all well, except you're not actually implementing that behavior, only the method signature. The JavaDoc says:


Returns:


true if the collection changed as a result of the call

So you should change your implementation accordingly. Perhaps something like this:

public boolean addAll(int index, Collection items) {
    if (items.isEmpty()) {
        return false;
    }
    if (size + items.size() > arr.length) {
        resize(2 * (size + items.size()));
    }
    System.arraycopy(arr, index, arr, index + items.size(), size - index);
    for (T item : items) {
        arr[index++] = item;
    }
    size += items.size();
    return true;
}

This also includes my naming suggestions, as well as Brythan's advice to avoid calling add one by one for each element. For the resizing, I added a helper method and refactored the existing one like this:

private void resize() {
    resize(Math.max(2 * size, 1));
}

private void resize(int targetSize) {
    T[] copy = newArray(targetSize);
    System.arraycopy(arr, 0, copy, 0, size);
    arr = copy;
}

(Since I don't know what was "f" in your original f.newArray, I wrote my own newArray.)

Notice that I changed the visibility of resize to private.
This is an internal operation that shouldn't be accessible by any other class by default.

Finally, by the same logic of addAll (following existing examples), add should also return boolean: true if the collection was modified. (In your case always.)

StackExchange Code Review Q#67268, answer score: 4