A Java subclass of ArrayList that supports rotation in constant time

Question

(See the next iteration.)

I have subclassed java.util.ArrayList in order to be able to "rotate" it in constant time simply by moving a finger index. See what I have:

RotableList.java

package net.coderodde.util;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Objects;
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 RotableList<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 E remove(int index) {
        checkRemovalIndex(index);
        E ret = get(index);
        super.remove((index + finger) % size());
        return ret;
    }

    @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() {
        throw new UnsupportedOperationException();
    }

    @Override
    public ListIterator<E> listIterator() {
        throw new UnsupportedOperationException();
    }

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

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

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

    @Override
    public Object[] toArray() {
        throw new UnsupportedOperationException();
    }

    @Override
    public <E> E[] toArray(E[] a) {
        throw new UnsupportedOperationException();
    }

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

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

        return false;
    }

    @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() + ".");
        }
    }

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

        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);
        }
    }
}

RotableListTest.java

package net.coderodde.util;

import org.junit.Test;
import static org.junit.Assert.*;
import org.junit.Before;

public class RotableListTest {

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

    @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));
    }

    @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));
    }
}

Please, tell me anything that comes to mind.

Answer 1

Your code does not throw UnsupportedOperationException for addAll, when you don't guarantee the index of the ordering. The contract of ArrayList.addAll is as such:

Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's Iterator.

Your code violates this contract, as the elements are inserted at the wrong position.

Test case:

RotableList<Integer> list = new RotableList<>();
list.add(5);
list.add(1);
list.add(2);
list.add(3);
list.add(4);

ArrayList<Integer> list2 = new ArrayList<>();
list2.add(6);
list2.add(7);
list2.add(8);

list.rotate(-1);
System.out.println(list);

list.addAll(list2);
System.out.println(list);

RotableList<Integer> list3 = new RotableList<>();
list3.add(1);
list3.add(2);
list3.add(3);
list3.add(4);
list3.add(5);

ArrayList<Integer> list4 = new ArrayList<>();
list4.add(6);
list4.add(7);
list4.add(8);

list3.addAll(list4);
System.out.println(list3);

Result:

[1, 2, 3, 4, 5]
[1, 2, 3, 4, 6, 7, 8, 5]
[1, 2, 3, 4, 5, 6, 7, 8]

You also don't reset the finger in clear, leading to funky business with other operations such as retainAll and removeAll.

Answer 2

I would go totally in a different direction. Look, what if you need to rotate not ArrayList but 'LinkedList' or even unknown java.util.List implementation?

So the better approach is to use decorator pattern:

1. create own implementation of java.util.List<E> (or extend java.util.AbstractList<E>)
2. take some java.util.List<E> as a constructor parameter as a source
3. redirect some methods to source directly (like e.g. add(E e)) and change calls of others with your offset (e.g. set(int index, E element))
4. think about sending offset as the constructor parameter too making your list decorator immutable

Answer 3

From JavaDoc:

indexOf() - Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.

so if your list is rotated (finger != 0) then you can't iterate in indexOf / lastIndexOf / remove methods from 0 to size()-1. You should use this rotated iteration, because this "first occurrence" might be somwhere else in the list if duplicated elements occurs.

Example:

if initial list is:

3, 2, 1, 3

indexOf(3) returs 0

but if you rotate list (by 1?)

2, 1, 3, 3

then your indexOf(3) still returns 0, but it should 2.

To avoid this error in future, prepare better test cases - at least one with duplicated values.