ChainedList.java

package org.foo.chainedlist;

import java.util.AbstractList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.RandomAccess;

import org.apache.commons.collections4.IterableUtils;

/** This class makes multiple lists look like one to the caller. */
public class /* NOSONAR */ ChainedList<E> extends AbstractList<E> implements RandomAccess {

    private final List<E>[] elements;

    private final int[] endIndexes;

    @SafeVarargs
    public ChainedList(final List<E>... lists) {
        this(Arrays.asList(lists));
    }

    @SuppressWarnings("unchecked")
    public ChainedList(final Iterable<List<E>> elements) {
        final List<List<E>> tmpElementsList = IterableUtils.toList(elements);
        this.elements = tmpElementsList.toArray(new List[tmpElementsList.size()]);
        endIndexes = new int[this.elements.length];
        int currentSize = 0;
        for (int i = 0; i < this.elements.length; i++) {
            final List<E> curr = this.elements[i];
            final int sz = curr.size();
            endIndexes[i] = currentSize + sz;
            currentSize += sz;
        }
    }

    @Override
    public E get(final int index) {
        final int partitionIndex = getPartitionIndex(index);
        final int subIndex = getSubIndex(partitionIndex, index);

        // throws when index >= size()
        final List<E> subList = elements[partitionIndex];
        // throws when index is negative or last sublist is empty
        return subList.get(subIndex);
    }

    @Override
    public E set(final int index, final E element) {
        final int partitionIndex = getPartitionIndex(index);
        final int subIndex = getSubIndex(partitionIndex, index);

        // throws when index >= size()
        final List<E> subList = elements[partitionIndex];
        if (subIndex < 0 || subIndex >= subList.size()) {
            // a sublist may throw unsupported even when index OOB
            throw new IndexOutOfBoundsException();
        }
        return subList.set(subIndex, element);
    }

    @Override
    public Iterator<E> iterator() {
        // this may perform better with contained LinkedList
        return IterableUtils.chainedIterable(elements).iterator();
    }

    @Override
    public ListIterator<E> listIterator(final int index) {
        // indexOf, lastIndexOf, equals, removeRange, subList
        // call this method and for non-RandomAccess lists
        // the default implementation is slow
        // T O D O: implement LazyListIteratorChain similar to
        // org.apache.commons.collections4.iterators.LazyIteratorChain
        for (final List<E> subList : elements) {
            if (!(subList instanceof RandomAccess)) {
                throw new UnsupportedOperationException(
                    "Not RandomAccess: " + subList.getClass().getName());
            }
        }
        return super.listIterator(index);
    }

    /**
     * @return negative value when {@code index} is negative
     */
    private int getSubIndex(final int partitionIndex, final int index) {
        return index - (partitionIndex == 0 ? 0 : endIndexes[partitionIndex - 1]);
    }

    private int getPartitionIndex(final int index) {
        int location = Arrays.binarySearch(endIndexes, index);
        if (location < 0) {
            location = (~location) - 1;
        }
        return location + 1;
    }

    @Override
    public int size() {
        return endIndexes.length == 0 ? 0 : endIndexes[endIndexes.length - 1];
    }
}

ChainedListTests.java

package org.foo.chainedlist;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.fail;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.collections4.ListUtils;
import org.junit.Test;

public class ChainedListTests {

    private static List<String> emptyList() {
        return Collections.emptyList();
    }

    private final List<String> list1 = Collections.unmodifiableList(Arrays.asList("a", "b"));

    private final List<String> list2 = Collections.unmodifiableList(Arrays.asList("c", "d"));

    @Test
    public void testA() throws Exception {

        check(list1, list2, Arrays.asList("a", "b", "c", "d"));
    }

    @Test
    public void testB() throws Exception {
        final ChainedList<String> combined =
            new ChainedList<String>(
                emptyList(),
                new ArrayList<>(list1),
                emptyList(),
                new ArrayList<>(list2),
                emptyList());

        check(list1, list2, combined);
    }

    @Test
    public void testC() throws Exception {
        final ChainedList<String> combined =
            new ChainedList<>(
                emptyList(),
                new ArrayList<>(list1),
                new ArrayList<>(list2),
                emptyList());

        check(list1, list2, combined);
    }

    @Test
    public void testD() throws Exception {
        final ChainedList<String> combined =
            new ChainedList<>(new ArrayList<>(list1), new ArrayList<>(list2));

        check(list1, list2, combined);
    }

    @Test
    public void testE() throws Exception {
        final ChainedList<String> noSublists = new ChainedList<>();
        assertEquals(0, noSublists.size());
        checkFailsGet(noSublists, 0);
    }

    @Test
    public void testF() throws Exception {
        final ChainedList<String> emptySublist = new ChainedList<>(emptyList());
        assertEquals(0, emptySublist.size());
        checkFailsGet(emptySublist, 0);
    }

    @Test
    public void testG() throws Exception {
        final ChainedList<String> emptySublist = new ChainedList<>(emptyList(), emptyList());
        assertEquals(0, emptySublist.size());
        checkFailsGet(emptySublist, 0);
    }

    private static void check(
            final List<String> list1,
            final List<String> list2,
            final List<String> combined) {
        assertEquals(4, combined.size());

        checkFailsGet(combined, Integer.MIN_VALUE);
        checkFailsGet(combined, -1);
        checkFailsGet(combined, 4);
        checkFailsGet(combined, Integer.MAX_VALUE);

        assertEquals("a", combined.get(0));
        assertEquals("b", combined.get(1));
        assertEquals("c", combined.get(2));
        assertEquals("d", combined.get(3));
        
        assertEquals(1, combined.indexOf("b"));
        assertEquals(2, combined.indexOf("c"));

        final List<String> copy3 = new ArrayList<>();
        CollectionUtils.addAll(copy3, combined.listIterator());

        final List<String> copy1 = ListUtils.union(list1, list2);

        final List<String> copy2 = new ArrayList<>();
        CollectionUtils.addAll(copy2, combined.iterator());

        assertEquals(copy1, copy3);
        assertEquals(copy1, copy2);

        assertEquals(copy1, combined);

        checkFailSet(combined, Integer.MIN_VALUE, "z");
        checkFailSet(combined, -1, "z");
        checkFailSet(combined, 4, "z");
        checkFailSet(combined, Integer.MAX_VALUE, "z");

        assertEquals("a", combined.set(0, "aa"));
        assertEquals("b", combined.set(1, "bb"));
        assertEquals("c", combined.set(2, "cc"));
        assertEquals("d", combined.set(3, "dd"));

    }

    private static void checkFailSet(
            final List<String> combined,
            final int index,
            final String value) {
        try {
            combined.set(index, value);
            fail("should throw");
        } catch (final IndexOutOfBoundsException e) {
            //
        }
    }

    private static void checkFailsGet(final List<String> combined, final int index) {
        try {
            combined.get(index);
            fail("should throw");
        } catch (final IndexOutOfBoundsException e) {
            //
        }
    }

}