A Java subclass of ArrayList that supports rotation in constant time - follow-up

Question

(See the previous (and initial) iteration.)

Compared to the previous iteration, I have added more methods that maintain the invariant required for constant time rotations, such as bulk add/remove, iterators, dumping contents to array.

I have more progress on java.util.ArrayList subclass that supports rotations in constant time. See what I have now:

RotableArrayList.java

package net.coderodde.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;
import java.util.Spliterator;

/**
 * This class implements a rotable list. Pushing to the front or the end of this
 * list runs in constant amortized time. Rotation runs in constant time.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Mar 24, 2016)
 */
public class RotableArrayList<E> extends ArrayList<E> {

    private int finger;

    @Override
    public E get(int index) {
        checkAccessIndex(index);
        return super.get((index + finger) % size());
    }

    @Override
    public E set(int index, E element) {
        checkAccessIndex(index);
        E ret = get(index);
        super.set((index + finger) % size(), element);
        return ret;
    }

    @Override
    public void add(int index, E element) {
        checkAdditionIndex(index);
        super.add((index + finger) % (size() + 1), element);
    }

    @Override
    public boolean add(E element) {
        add(size(), element);
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends E> coll) {
        if (coll.isEmpty()) {
            return false;
        }

        super.addAll(finger, coll);
        finger += coll.size();
        return true;
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> coll) {
        if (coll.isEmpty()) {
            return false;
        }

        int actualIndex = finger + index;

        if (actualIndex >= size()) {
            actualIndex %= size();
            finger += coll.size();
        } 

        super.addAll(actualIndex, coll);
        return true;
    }

    @Override
    public E remove(int index) {
        checkRemovalIndex(index);
        E ret = this.get(index);
        super.remove((finger + index) % size());

        if (finger + index > size()) {
            --finger;
        }

        return ret;
    }

    @Override
    public void clear() {
        super.clear();
        finger = 0;
    }

    @Override
    public int indexOf(Object o) {
        int size = size();

        for (int index = 0; index < size; ++index) {
            if (Objects.equals(o, get(index))) {
                return index;
            }
        }

        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        for (int index = size() - 1; index >= 0; --index) {
            if (Objects.equals(o, get(index))) {
                return index;
            }
        }

        return -1;
    }

    @Override
    public void sort(Comparator<? super E> c) {
        super.sort(c);
        finger = 0;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {

            private final ListIterator<E> listIterator = listIterator(0);

            @Override
            public boolean hasNext() {
                return listIterator.hasNext();
            }

            @Override
            public E next() {
                return listIterator.next();
            }

            @Override
            public void remove() {
                listIterator.remove();
            }
        };
    }

    @Override
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        return new RotableListIterator(index);
    }

    @Override
    public Spliterator<E> spliterator() {
        throw new UnsupportedOperationException();
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        throw new UnsupportedOperationException();
    }

    @Override
    public Object[] toArray() {
        Object[] array = new Object[size()];
        int index = 0;

        for (E element : this) {
            array[index++] = element;
        }

        return array;
    }

    @Override
    public <E> E[] toArray(E[] a) {
        if (a.length < size()) {
            a = Arrays.copyOf(a, size());
        }

        int index = 0;

        for (Object element : this) {
            a[index++] = (E) element;
        }

        if (a.length > size()) {
            a[size()] = null;
        }

        return a;
    }

    @Override
    public boolean remove(Object o) {
        int size = size();

        for (int index = 0; index < size; ++index) {
            if (Objects.equals(o, get(index))) {
                remove(index);
                // size = 10, finger = 7, index = 4
                if (index + finger >= size()) {
                    --finger;
                }

                return true;
            }
        }

        return false;
    }

    @Override
    public boolean removeAll(Collection<?> coll) {
        if (coll.isEmpty()) {
            return false;
        }

        Set<?> set = (coll instanceof HashSet) ? 
                                 (Set<?>) coll : 
                                 new HashSet<>(coll);

        Iterator<E> iterator = this.iterator();

        while (iterator.hasNext()) {
            E current = iterator.next();

            if (set.contains(current)) {
                iterator.remove();
            }
        }

        return true;
    }

    @Override
    public boolean retainAll(Collection<?> coll) {
        if (coll.isEmpty()) {
            return false;
        }

        Set<?> set = (coll instanceof HashSet) ? 
                                 (Set<?>) coll : 
                                 new HashSet<>(coll);

        Iterator<E> iterator = iterator();

        while (iterator.hasNext()) {
            E current = iterator.next();

            if (!set.contains(current)) {
                iterator.remove();
            }
        }

        return true;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        int size = size();

        for (int index = 0; index < size; ++index) {
            sb.append(get(index));

            if (index < size - 1) {
                sb.append(", ");
            }
        }

        return sb.append("]").toString();
    }

    public void rotate(int offset) {
        finger -= offset;
        finger %= size();

        if (finger < 0) {
            finger += size();
        }
    }

    private void checkAccessIndex(int index) {
        if (index < 0) {
            throw new IndexOutOfBoundsException(
                    "The access index is negative: " + index + ".");
        }

        if (index >= size()) {
            throw new IndexOutOfBoundsException(
                    "The access index is too large: " + index + "." + 
                    "The size of the list is " + size() + ".");
        }
    }

    private void checkAdditionIndex(int index) {
        if (index < 0) {
            throw new IndexOutOfBoundsException(
                    "The access index is negative: " + index + ".");
        }

        if (index > size()) {
            throw new IndexOutOfBoundsException(
                    "The addition index is too large: " + index + "." + 
                    "The size of the list is " + size() + ".");
        }
    }

    private void checkRemovalIndex(int index) {
        if (index < 0) {
            throw new IndexOutOfBoundsException(
                    "The removal index is negative: " + index + ".");
        }

        if (index >= size()) {
            throw new IndexOutOfBoundsException(
                    "The removal index is too large: " + index + "." + 
                    "The size of the list is " + size() + ".");
        }
    }

    private final class RotableListIterator implements ListIterator<E> {

        // Index is an arrow that points between two array elements:
        // array[index - 1] and array[index].
        private int expectedModCount = RotableArrayList.super.modCount;
        private int index;
        private int indexOfIteratedElement = -1;
        private boolean lastMoveWasNext;

        public RotableListIterator(int index) {
            this.index = index;
        }

        @Override
        public boolean hasNext() {
            return index < RotableArrayList.this.size();
        }

        @Override
        public E next() {
            checkConcurrentModification();

            if (!hasNext()) {
                throw new NoSuchElementException(
                        "No next element in this iterator.");
            }

            indexOfIteratedElement = index;
            lastMoveWasNext = true;
            return (E) RotableArrayList.this.get(index++);
        }

        @Override
        public boolean hasPrevious() {
            return index > 0;
        }

        @Override
        public E previous() {
            checkConcurrentModification();

            if (!hasPrevious()) {
                throw new NoSuchElementException(
                        "No previous element in this iterator.");
            }

            indexOfIteratedElement = --index;
            lastMoveWasNext = false;
            return (E) RotableArrayList.this.get(index);
        }

        @Override
        public int nextIndex() {
            return index;
        }

        @Override
        public int previousIndex() {
            return index - 1;
        }

        @Override
        public void remove() {
            if (indexOfIteratedElement == -1) {
                throw new IllegalStateException(
                        "There is no element to remove.");
            }

            checkConcurrentModification();
            E ret = RotableArrayList.this.remove(indexOfIteratedElement);
            indexOfIteratedElement = -1;
            expectedModCount = RotableArrayList.super.modCount;

            if (lastMoveWasNext) {
                index--;
            }
        }

        @Override
        public void set(E e) {
            if (indexOfIteratedElement == -1) {
                throw new IllegalStateException("There is no current element.");
            }

            checkConcurrentModification();
            RotableArrayList.this.set(indexOfIteratedElement, e);
            expectedModCount = RotableArrayList.super.modCount;
        }

        @Override
        public void add(E e) {
            checkConcurrentModification(); 
            RotableArrayList.this.add(nextIndex(), e);
            index++;
            indexOfIteratedElement = -1;
            expectedModCount = RotableArrayList.super.modCount;
        }

        private void checkConcurrentModification() {
            if (expectedModCount != RotableArrayList.super.modCount) {
                throw new ConcurrentModificationException(
                        "Expected mod count: " + expectedModCount + ", " + 
                        "actual mod count: " + RotableArrayList.super.modCount);
            }
        }
    }

    public static void main(String[] args) {
        RotableArrayList<Integer> list = new RotableArrayList<>();

        for (int i = 0; i < 5; ++i) {
            list.add(i);
        }

        System.out.println("Rotating to the right:");

        for (int i = 0; i < list.size(); ++i) {
            System.out.println(list);
            list.rotate(1);
        }

        System.out.println("Rotating to the left:");

        for (int i = 0; i < list.size(); ++i) {
            System.out.println(list);
            list.rotate(-1);
        }
    }
}

RotableArrayListTest.java

package net.coderodde.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Set;
import org.junit.Test;
import static org.junit.Assert.*;
import org.junit.Before;

public class RotableArrayListTest {

    private final RotableArrayList<Integer> list = new RotableArrayList<>();

    @Before
    public void before() {
        list.clear();
    }

    private void load(int n) {
        for (int i = 0; i < n; ++i) {
            list.add(i);
        }
    }

    @Test
    public void testGet() {
        load(5);

        for (int i = 0; i < 5; ++i) {
            assertEquals(Integer.valueOf(i), list.get(i));
        }

        list.rotate(2);

        assertEquals(Integer.valueOf(3), list.get(0));
        assertEquals(Integer.valueOf(4), list.get(1));
        assertEquals(Integer.valueOf(0), list.get(2));
        assertEquals(Integer.valueOf(1), list.get(3));
        assertEquals(Integer.valueOf(2), list.get(4));

        list.rotate(-4);

        assertEquals(Integer.valueOf(2), list.get(0));
        assertEquals(Integer.valueOf(3), list.get(1));
        assertEquals(Integer.valueOf(4), list.get(2));
        assertEquals(Integer.valueOf(0), list.get(3));
        assertEquals(Integer.valueOf(1), list.get(4));

        list.rotate(-8);

        for (int i = 0; i < 5; ++i) {
            assertEquals(Integer.valueOf(i), list.get(i));
        }
    }

    @Test
    public void testSet() {
        load(4);

        list.set(0, 3);
        list.set(1, 2);
        list.set(2, 1);
        list.set(3, 0);

        assertEquals(Integer.valueOf(3), list.get(0));
        assertEquals(Integer.valueOf(2), list.get(1));
        assertEquals(Integer.valueOf(1), list.get(2));
        assertEquals(Integer.valueOf(0), list.get(3));
    }

    @Test
    public void testAdd_int_GenericType() {
        load(2);

        list.add(1, 10);
        list.add(0, 11);
        list.add(4, 12);

        assertEquals(Integer.valueOf(11), list.get(0));
        assertEquals(Integer.valueOf(0), list.get(1));
        assertEquals(Integer.valueOf(10), list.get(2));
        assertEquals(Integer.valueOf(1), list.get(3));
        assertEquals(Integer.valueOf(12), list.get(4));
    }

    @Test
    public void testAdd_GenericType() {
        load(2);

        list.add(10);

        assertEquals(Integer.valueOf(0), list.get(0));
        assertEquals(Integer.valueOf(1), list.get(1));
        assertEquals(Integer.valueOf(10), list.get(2));
    }

    @Test
    public void testRemove_int() {
        load(5);

        list.remove(4);
        list.remove(2);
        list.remove(0);

        assertEquals(Integer.valueOf(1), list.get(0));
        assertEquals(Integer.valueOf(3), list.get(1));

        list.clear();

        load(5);

        list.rotate(2);
        list.remove(0);

        assertEquals(Integer.valueOf(4), list.get(0));
        assertEquals(Integer.valueOf(0), list.get(1));
        assertEquals(Integer.valueOf(1), list.get(2));
        assertEquals(Integer.valueOf(2), list.get(3));

        list.clear();
        load(10);
        list.rotate(3);
        list.remove(Integer.valueOf(3));
    }

    @Test
    public void testIndexOf() {
        load(10);

        list.rotate(-3);
        assertEquals(1, list.indexOf(4));
    }

    @Test
    public void testLastIndexOf() {
        load(10);

        list.rotate(-3);
        assertEquals(8, list.lastIndexOf(1));
    }

    @Test
    public void testSort() {
        list.add(5);
        list.add(2);
        list.add(1);
        list.add(4);
        list.rotate(-1);
        list.sort(Integer::compare);
        assertEquals(Integer.valueOf(1), list.get(0));
    }

    @Test
    public void testRemove_Object() {
        load(5);

        list.rotate(-1);
        list.remove(Integer.valueOf(3));
        assertEquals(4, list.size());

        assertEquals(Integer.valueOf(1), list.get(0));
        assertEquals(Integer.valueOf(2), list.get(1));
        assertEquals(Integer.valueOf(4), list.get(2));
        assertEquals(Integer.valueOf(0), list.get(3));
    }

    @Test
    public void testRotate() {
        load(10);

        list.rotate(2);

        assertEquals(Integer.valueOf(8), list.get(0));
        assertEquals(Integer.valueOf(9), list.get(1));
        assertEquals(Integer.valueOf(0), list.get(2));

        list.rotate(-5);

        assertEquals(Integer.valueOf(3), list.get(0));
        assertEquals(Integer.valueOf(4), list.get(1));
        assertEquals(Integer.valueOf(5), list.get(2));
    }

    @Test
    public void testListIteratorNextAndHasNext() {
        load(5);

        ListIterator<Integer> iterator = list.listIterator(2);

        assertTrue(iterator.hasNext());
        assertEquals(Integer.valueOf(2), iterator.next());

        assertTrue(iterator.hasNext());
        assertEquals(Integer.valueOf(3), iterator.next());

        assertTrue(iterator.hasNext());
        assertEquals(Integer.valueOf(4), iterator.next());
        assertFalse(iterator.hasNext());
        assertTrue(iterator.hasPrevious());

        try {
            iterator.next();
            fail();
        } catch (NoSuchElementException ex) {

        }
    }

    @Test
    public void testListIteratorPreviousAndHasPrevious() {
        load(5);

        ListIterator<Integer> iterator = list.listIterator(2);

        assertTrue(iterator.hasPrevious());
        assertEquals(Integer.valueOf(1), iterator.previous());

        assertTrue(iterator.hasPrevious());
        assertEquals(Integer.valueOf(0), iterator.previous());

        assertTrue(iterator.hasNext());
        assertFalse(iterator.hasPrevious());

        try {
            iterator.previous();
            fail();
        } catch (NoSuchElementException ex) {

        }
    }

    @Test
    public void testListIteratorAdd() {
        List<Integer> list2 = new ArrayList<>();
        load(5);

        for (int i = 0; i < 5; ++i) {
            list2.add(i);
        }

        ListIterator<Integer> iter  = list.listIterator();
        ListIterator<Integer> iter2 = list2.listIterator();

        iter.add(10);
        iter.add(11);

        iter2.add(10);
        iter2.add(11);

        assertTrue(listsEqual(list, list2));

        try {
            iter.remove();
            fail("List should have thrown IllegalStateException.");
        } catch (IllegalStateException ex) {

        }

        try {
            iter2.remove();
            fail("List should have thrown IllegalStateException.");
        } catch (IllegalStateException ex) {

        }
    }

    @Test
    public void testListIteratorSet() {
        List<Integer> list2 = new ArrayList<>(Arrays.asList(0, 1, 2, 3, 4));
        load(5);

        ListIterator<Integer> iter = list.listIterator(2);
        ListIterator<Integer> iter2 = list2.listIterator(2);

        try {
            iter2.set(10);
            fail("ListIterator.set should have thrown IllegalStateException.");
        } catch (IllegalStateException ex) {

        }

        try {
            iter.set(10);
            fail("ListIterator.set should have thrown IllegalStateException.");
        } catch (IllegalStateException ex) {

        }

        iter.previous();
        iter2.previous();

        iter.set(10);
        iter2.set(10);

        assertTrue(listsEqual(list, list2));
    }

    @Test
    public void testListIteratorRemove() {
        List<Integer> list2 = new ArrayList<>(Arrays.asList(0, 1, 2, 3, 4));
        load(5);

        ListIterator<Integer> iter = list.listIterator(2);
        ListIterator<Integer> iter2 = list2.listIterator(2);

        try {
            iter2.remove();
            fail("ListIterator.remove should have thrown " + 
                 "IllegalStateException.");
        } catch (IllegalStateException ex) {

        }

        try {
            iter.remove();
            fail("ListIterator.remove should have thrown " +
                 "IllegalStateException.");
        } catch (IllegalStateException ex) {

        }

        iter.next();
        iter2.next();

        iter.remove();
        iter2.remove();

        assertTrue(listsEqual(list, list2));

        try {
            iter2.remove();
            fail("ListIterator.remove should have thrown " + 
                 "IllegalStateException.");
        } catch (IllegalStateException ex) {

        }

        try {
            iter.remove();
            fail("ListIterator.remove should have thrown " +
                 "IllegalStateException.");
        } catch (IllegalStateException ex) {

        }

        iter.next();
        iter2.next();
        iter.remove();
        iter2.remove();

        assertTrue(listsEqual(list, list2));

        iter.previous();
        iter2.previous();
        iter.remove();
        iter2.remove();

        assertTrue(listsEqual(list, list2));
    }

    @Test  
    public void testAddAll() {
        load(4);
        list.rotate(-2); // 2, 3, 0, 1
        list.addAll(Arrays.asList(4, 5, 6));

        assertEquals(Integer.valueOf(2), list.get(0));
        assertEquals(Integer.valueOf(3), list.get(1));
        assertEquals(Integer.valueOf(0), list.get(2));
        assertEquals(Integer.valueOf(1), list.get(3));
        assertEquals(Integer.valueOf(4), list.get(4));
        assertEquals(Integer.valueOf(5), list.get(5));
        assertEquals(Integer.valueOf(6), list.get(6));

        List<Integer> list2 = new ArrayList<>();

        assertFalse(list.addAll(Arrays.asList()));
        assertFalse(list2.addAll(Arrays.asList()));

        assertTrue(list.addAll(Arrays.asList(1)));
        assertTrue(list2.addAll(Arrays.asList(1)));
    }

    @Test
    public void testAddAllInt() {
        load(4);
        list.rotate(-2); // 2, 3, 0, 1
        list.addAll(1, Arrays.asList(4, 5, 6));

        assertEquals(Integer.valueOf(2), list.get(0));
        assertEquals(Integer.valueOf(4), list.get(1));
        assertEquals(Integer.valueOf(5), list.get(2));
        assertEquals(Integer.valueOf(6), list.get(3));
        assertEquals(Integer.valueOf(3), list.get(4));
        assertEquals(Integer.valueOf(0), list.get(5));
        assertEquals(Integer.valueOf(1), list.get(6));

        List<Integer> list2 = new ArrayList<>(list);

        assertFalse(list.addAll(1, Arrays.asList()));
        assertFalse(list2.addAll(1, Arrays.asList()));

        assertTrue(list.addAll(1, Arrays.asList(1)));
        assertTrue(list2.addAll(1, Arrays.asList(1)));

        list.clear();

        load(5);
        list.rotate(2); // 3, 4, 0, 1, 2
        list.addAll(3, Arrays.asList(10, 11));

        assertEquals(Integer.valueOf(3),  list.get(0));
        assertEquals(Integer.valueOf(4),  list.get(1));
        assertEquals(Integer.valueOf(0),  list.get(2));
        assertEquals(Integer.valueOf(10), list.get(3));
        assertEquals(Integer.valueOf(11), list.get(4));
        assertEquals(Integer.valueOf(1),  list.get(5));
        assertEquals(Integer.valueOf(2),  list.get(6));

        list.clear();
        load(5);
        list.rotate(2); // 3, 4, 0, 1, 2
        list.addAll(1, Arrays.asList(10, 11)); // 3, 10, 11, 4, 0, 1, 2

        assertEquals(Integer.valueOf(3),  list.get(0));
        assertEquals(Integer.valueOf(10),  list.get(1));
        assertEquals(Integer.valueOf(11),  list.get(2));
        assertEquals(Integer.valueOf(4), list.get(3));
        assertEquals(Integer.valueOf(0), list.get(4));
        assertEquals(Integer.valueOf(1),  list.get(5));
        assertEquals(Integer.valueOf(2),  list.get(6));
    }

    @Test
    public void testToArray() {
        load(5);

        list.rotate(3); // 2, 3, 4, 0, 1

        Object[] array = list.toArray();

        assertEquals(2, array[0]);
        assertEquals(3, array[1]);
        assertEquals(4, array[2]);
        assertEquals(0, array[3]);
        assertEquals(1, array[4]);
    }

    @Test
    public void testGenericToArray() {
        load(5);
        list.rotate(-2); // 2, 3, 4, 0, 1

        Integer[] array = new Integer[4];
        Integer[] result = list.toArray(array);

        assertTrue(array != result);
        assertEquals(5, result.length);

        assertEquals(Integer.valueOf(2), result[0]);
        assertEquals(Integer.valueOf(3), result[1]);
        assertEquals(Integer.valueOf(4), result[2]);
        assertEquals(Integer.valueOf(0), result[3]);
        assertEquals(Integer.valueOf(1), result[4]);

        array = new Integer[5];
        result = list.toArray(array);

        assertTrue(array == result);

        assertEquals(5, result.length);

        assertEquals(Integer.valueOf(2), result[0]);
        assertEquals(Integer.valueOf(3), result[1]);
        assertEquals(Integer.valueOf(4), result[2]);
        assertEquals(Integer.valueOf(0), result[3]);
        assertEquals(Integer.valueOf(1), result[4]);

        array = new Integer[6];
        result = list.toArray(array);

        assertTrue(array == result);
        assertEquals(6, array.length);

        assertEquals(Integer.valueOf(2), result[0]);
        assertEquals(Integer.valueOf(3), result[1]);
        assertEquals(Integer.valueOf(4), result[2]);
        assertEquals(Integer.valueOf(0), result[3]);
        assertEquals(Integer.valueOf(1), result[4]);
        assertNull(result[5]); // Cut off value.
    }

    @Test
    public void testRemoveAll() {
        load(5);
        list.rotate(3);
        Set<Integer> set = new HashSet<>(Arrays.asList(2, 3, 1));

        list.removeAll(set);

        assertEquals(Integer.valueOf(4), list.get(0));
        assertEquals(Integer.valueOf(0), list.get(1));

        list.clear();
        load(10);
        list.rotate(3); // 7, 8, 9, 0, 1, 2, 3, 4, 5, 6
        set.clear();
        set.addAll(Arrays.asList(0, 2, 3, 6, 9));
        list.removeAll(set);

        assertEquals(Integer.valueOf(7), list.get(0));
        assertEquals(Integer.valueOf(8), list.get(1));
        assertEquals(Integer.valueOf(1), list.get(2));
        assertEquals(Integer.valueOf(4), list.get(3));
        assertEquals(Integer.valueOf(5), list.get(4));
    }

    @Test
    public void testRetainAll() {
        load(5);
        list.rotate(3); // 2, 3, 4, 0, 1
        Set<Integer> set = new HashSet<>(Arrays.asList(2, 3, 1));

        list.retainAll(set); // 2, 3, 1

        assertEquals(Integer.valueOf(2), list.get(0));
        assertEquals(Integer.valueOf(3), list.get(1));
        assertEquals(Integer.valueOf(1), list.get(2));

        list.clear();
        load(10);
        list.rotate(3); // 7, 8, 9, 0, 1, 2, 3, 4, 5, 6
        set.clear();
        set.addAll(Arrays.asList(0, 2, 3, 6, 9));
        list.retainAll(set);

        assertEquals(Integer.valueOf(9), list.get(0));
        assertEquals(Integer.valueOf(0), list.get(1));
        assertEquals(Integer.valueOf(2), list.get(2));
        assertEquals(Integer.valueOf(3), list.get(3));
        assertEquals(Integer.valueOf(6), list.get(4));
    }

    private boolean listsEqual(List<Integer> list, List<Integer> list2) {
        if (list.size() != list2.size()) {
            return false;
        }

        for (int i = 0; i < list.size(); ++i) {
            if (!list.get(i).equals(list2.get(i))) {
                return false;
            }
        }

        return true;
    }
}

Please, tell me anything that comes to mind.

I am downvoting this because you don't specify what you have changed since the previous iteration, or why you are looking for another review. And additionally, on its own, I consider it a poor question - lots of code and very little description. — Simon Forsberg, Commented Mar 30, 2016 at 5:33
@SimonForsberg Added description of changes compared to the previous iteration. Please, tell me what you think. — coderodde, Commented Mar 30, 2016 at 6:50

Pimgd · Accepted Answer · 2016-03-25 18:08:27Z

Remove checks index twice:

@Override
public E remove(int index) {
    checkRemovalIndex(index);
    E ret = this.get(index);
    super.remove((finger + index) % size());

    if (finger + index > size()) {
        --finger;
    }

    return ret;
}

Here's what get looks like:

@Override
public E get(int index) {
    checkAccessIndex(index);
    return super.get((index + finger) % size());
}

Here's remove with the get call inlined:

@Override
public E remove(int index) {
    checkRemovalIndex(index);
    checkAccessIndex(index);
    E ret = super.get((index + finger) % size());
    super.remove((finger + index) % size());

    if (finger + index > size()) {
        --finger;
    }

    return ret;
}

It checks the index twice!

I think you could do better by directly using the return value of super.remove:

@Override
public E remove(int index) {
    checkRemovalIndex(index);
    E ret = super.remove((finger + index) % size());

    if (finger + index > size()) {
        --finger;
    }

    return ret;
}

addAll with index greater than list size corrupts finger:

@Override
public boolean addAll(int index, Collection<? extends E> coll) {
    if (coll.isEmpty()) {
        return false;
    }

    int actualIndex = finger + index;

    if (actualIndex >= size()) {
        actualIndex %= size();
        finger += coll.size();
    } 

    super.addAll(actualIndex, coll);
    return true;
}

It will throw an exception, but after that you'll be in a dirty state. If you then call addAll again, but without an index, (addAll(Collection)) then you'll get more exceptions for going out of bounds.

Stack Exchange Network

A Java subclass of ArrayList that supports rotation in constant time - follow-up

1 Answer 1

Your Answer

Not the answer you're looking for? Browse other questions tagged
java
array
unit-testing
collections
or ask your own question.

Linked

Hot Network Questions

A Java subclass of ArrayList that supports rotation in constant time - follow-up

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
java
array
unit-testing
collections
or ask your own question.