1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Simon Forsberg Mar 30 '16 at 5:33
  • \$\begingroup\$ @SimonForsberg Added description of changes compared to the previous iteration. Please, tell me what you think. \$\endgroup\$ – coderodde Mar 30 '16 at 6:50
2
\$\begingroup\$

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.

\$\endgroup\$

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.