Skip to content

Instantly share code, notes, and snippets.

@basinilya
Last active August 23, 2020 15:25
Show Gist options
  • Save basinilya/d4837a2098b4349d17b9ac4b57e7a95a to your computer and use it in GitHub Desktop.
Save basinilya/d4837a2098b4349d17b9ac4b57e7a95a to your computer and use it in GitHub Desktop.
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];
}
}
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) {
//
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment