How works ArrayList's removeRange method?

Question

ArrayList's removeRange works weirdly. Check the below sample code, I give to input reversely. I thought that the list has been removed reversely.

Ex: 3 to 1 means, the three elements are removed (3rd, 2nd, and 1st).

But, the output is totally confused me. Curious to know, how it works?

From the JavaDoc, I found the below statement. If toIndex < fromIndex, the system will throw IndexOutOfBoundException, But it doesn't. Is this bug?

IndexOutOfBoundsException - if fromIndex or toIndex is out of range (fromIndex < 0 || fromIndex >= size() || toIndex > size() || toIndex < fromIndex)

import java.util.*;
public class TestRemoveRange extends ArrayList {

  public static void main(String arg[]){

    TestRemoveRange list = new TestRemoveRange();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("d");
    list.add("e");

    System.out.println("before remove : " + list);

    list.removeRange(3, 1);

    System.out.println("after remove (3, 1) : " + list); //[a, b, c, b, c, d, e]


  }     
}

Answer 1

Looking at the actual source code might help to clarify your problem:

In Java 8 the ArrayList.removeRange() looks like this:

protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    size = newSize;
}

In Java 9 the ArrayList.removeRange() changed to this:

protected void removeRange(int fromIndex, int toIndex) {
    if (fromIndex > toIndex) {
        throw new IndexOutOfBoundsException(
                outOfBoundsMsg(fromIndex, toIndex));
    }
    modCount++;
    shiftTailOverGap(elementData, fromIndex, toIndex);
}

private void shiftTailOverGap(Object[] es, int lo, int hi) {
    System.arraycopy(es, hi, es, lo, size - hi);
    for (int to = size, i = (size -= hi - lo); i < to; i++)
        es[i] = null;
}

As you can see in the snippets above both implementations use System.arraycopy() to remove the items of the list. But only since Java 9 there is the check which throws the IndexOutOfBoundsException if fromIndex > toIndex.

Since System.arraycopy() is implemented native the source code might be different on different platforms. According to the javadoc it should behave this way:

Copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array. [...]

If the src and dest arguments refer to the same array object, then the copying is performed as if the components at positions srcPos through srcPos+length-1 were first copied to a temporary array with length components and then the contents of the temporary array were copied into positions destPos through destPos+length-1 of the destination array.

For IndexOutOfBoundException it says:

If any of the following is true, an IndexOutOfBoundsException is thrown and the destination is not modified:

• The srcPos argument is negative.
• The destPos argument is negative.
• The length argument is negative.
• srcPos+length is greater than src.length, the length of the source array.
• destPos+length is greater than dest.length, the length of the destination array.

So if you are running your example with Java 8 or below you might get this result:

before remove : [a, b, c, d, e]
after remove (3, 1) : [a, b, c, b, c, d, e]

If you run your example with Java 9 or above you will get this exception:

before remove : [a, b, c, d, e]
Exception in thread "main" java.lang.IndexOutOfBoundsException: From Index: 3 > To Index: 1
    at java.base/java.util.ArrayList.removeRange(ArrayList.java:769)
    at TestRemoveRange.main(TestRemoveRange.java:16)