code: package edu.berkeley.nlp.util;
  
  import java.util.AbstractList;
  import java.util.List;
  
  /**
   * Concatenates two lists without building a new one. Unmodifiable.
   * 
   * @author adampauls
   * 
   * @param <K>
   */
  public class ConcatenationList<K> extends AbstractList<K> {
  
  	private List<List<K>> lists;
  
  	private int size = 0;
  	private int[] cumulativeSize;
  
  	public ConcatenationList(List<List<K>> lists) {
  		this.lists = lists;
  		cumulativeSize = new int[lists.size()];
  		int i = 0;
  		for (List<K> set : lists) {
  			cumulativeSize[i++] = i == 0 ? 0 : cumulativeSize[i - 1]
  					+ set.size();
  			size += set.size();
  		}
  	}
  
  	@Override
  	public int size() {
  		return size;
  
  	}
  
  	@Override
  	public K get(int arg0) {
  		K k = binarySearch(lists.size() / 2, arg0);
  		return k;
  	}
  
  	private K binarySearch(int listIndex, int i) {
  		if (i >= cumulativeSize[listIndex]
  				&& (listIndex == lists.size() || i < cumulativeSize[listIndex + 1])) {
  			return lists.get(listIndex).get(i - cumulativeSize[listIndex]);
  		}
  		if (i >= cumulativeSize[listIndex + 1])
  			return binarySearch((lists.size() - listIndex) / 2, i);
  		assert i < cumulativeSize[listIndex];
  		return binarySearch(listIndex / 2, i);
  	}
  
  }