import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
/*
 * Created on Aug 1, 2004
 */

/** Problem #18 on the Summer 2004 CSE143 Midterm #2.
 *  This is not a full implementation of a List -- just the methods needed
 * for that problem.

 */
public class SegmentedList implements List {
	
	/** Number of objects currently stored in the list. */
	private int size = 0;
	
	/** Holds references to the sublists. 
	 *Each sublist is a java.util.LinkedList.
	 The sublists are in order by their creation, which is also the order
	 of element indices within the overall list.  
	 See comments on "get" method for details of object locations.
	 */
	private List master = new ArrayList();
	
	/** Maximum desired number of elements of any sublist. */
	public static final int MAX_SUBLIST_SIZE = 5; //use a small number for testing
	
	/** Not needed, really. */
	public SegmentedList() {		
	}
	
	/* Add a new object, to the end of the (entire) list.
	 * The end of the entire list will be the end of the last list in the
	 * master list.
	 * @see java.util.Collection#add(java.lang.Object)
	 */
	public boolean add(Object o) {
		//Special case if the list is completely empty
		//Checking this.master.size() is more correct than checking this.size.
		//It is possible the list was formerly not empty, in which case there
		//might exist empty sublists even if this.size == 0.
		if (this.master.size() == 0) {
			this.master.add(new LinkedList());
		}
		assert this.master.size() != 0;
		List lastList = (List) this.master.get(this.master.size() - 1);
		//Will add to lastList now unless it is full (at the stated maximum).
		if (lastList.size() >= MAX_SUBLIST_SIZE) {
			lastList = new LinkedList();
			this.master.add(lastList);
		}
		assert lastList.size() < MAX_SUBLIST_SIZE;
		lastList.add(o);
		this.size ++;
		return true;
	}

	/* Let's call Sublist #0 as s0, and its size as size0, etc.
	 * s0 contains indices 0..size0-1.
	 * s1 contains indices size0..(size0+size1-1).
	 * s2 contains indices (size0+size1)..(size0+size1+size2-1).
	 * s3 contains indices (size0+size1+size2)..(size0+size1+size2+size3-1).
	 * etc.
	 * "position" is in s0 if position <= size0-1, i.e., position < size0;
	 * else position is in s1 if position < size0+size1;
	 * else position is in s2 if position < size0+size1+size2;
	 * else position is in s3 if position < size0+size1+size2+size3; 
	 * etc.
	 * In the following, "passedOver" will be 0, then size0, then size0+size1, then
	 * size0+size1+size2, etc.
	 */
	public Object get(int position) {
		if (position < 0 || position >= this.size) {
			throw new IndexOutOfBoundsException("list position " + position + 
					" out of bounds " + this.size);
		}
		int passedOver = 0; //count how many elements have been passed
		for (int currListIndex = 0; currListIndex < this.master.size(); currListIndex++) {
			List currList = (List) this.master.get(currListIndex);
			int currentListSize = currList.size();
			if (position < passedOver + currentListSize) {
				//We have found the right list!
				assert position >= passedOver;
				int posInList = position - (passedOver);
				assert posInList >= 0 && posInList < currList.size();
				return currList.get(posInList);
			}
			passedOver += currentListSize;
		}
		assert false: position + " " + this.size; //can't happen!
		return null;
		
	}

	/** Following solution is from Michael Dunlap 8/4/2004. */
	public Object get2(int pos) {
		if (pos < 0 || pos >= size)
			throw new IndexOutOfBoundsException();
		int leftToFind = pos;
		List temp;
		for (int i = 0; i < master.size(); i++) {
			temp = (List)master.get(i);
			if (temp.size() > leftToFind)
				return temp.get(leftToFind);
			else
				leftToFind -= temp.size();
			}
		return null;
	}

	/*
	 *  Methods below here exist only to satisfy "implements List".
	 They were not allowed to be used in the problem solution.
	 The first of these, size(), is implemented only to make
	 testing easier.  Tests should NOT rely on any of the others,
	 as they are only stubs.
	 */ 
	
	public int size() {
		return this.size;
	}
	
	/* 
	 * @see java.util.Collection#clear()
	 */
	public void clear() {
	}
	
	/* 
	 * @see java.util.Collection#isEmpty()
	 */
	public boolean isEmpty() {
		return false;
	}

	/* 
	 * @see java.util.Collection#toArray()
	 */
	public Object[] toArray() {
		return null;
	}

	/* 
	 * @see java.util.List#add(int, java.lang.Object)
	 */
	public void add(int index, Object element) {
	}

	/* 
	 * @see java.util.List#remove(int)
	 */
	public Object remove(int index) {
		return null;
	}

	/* 
	 * @see java.util.List#indexOf(java.lang.Object)
	 */
	public int indexOf(Object o) {
		return 0;
	}

	/* 
	 * @see java.util.List#lastIndexOf(java.lang.Object)
	 */
	public int lastIndexOf(Object o) {
		return 0;
	}

	/* 
	 * @see java.util.Collection#contains(java.lang.Object)
	 */
	public boolean contains(Object o) {
		return false;
	}

	/* 
	 * @see java.util.Collection#remove(java.lang.Object)
	 */
	public boolean remove(Object o) {
		return false;
	}

	/* 
	 * @see java.util.List#addAll(int, java.util.Collection)
	 */
	public boolean addAll(int index, Collection c) {
		return false;
	}

	/* 
	 * @see java.util.Collection#addAll(java.util.Collection)
	 */
	public boolean addAll(Collection c) {
		return false;
	}

	/* 
	 * @see java.util.Collection#containsAll(java.util.Collection)
	 */
	public boolean containsAll(Collection c) {
		return false;
	}

	/* 
	 * @see java.util.Collection#removeAll(java.util.Collection)
	 */
	public boolean removeAll(Collection c) {
		return false;
	}

	/* 
	 * @see java.util.Collection#retainAll(java.util.Collection)
	 */
	public boolean retainAll(Collection c) {
		return false;
	}

	/* 
	 * @see java.util.Collection#iterator()
	 */
	public Iterator iterator() {
		return null;
	}

	/* 
	 * @see java.util.List#subList(int, int)
	 */
	public List subList(int fromIndex, int toIndex) {
		return null;
	}

	/* 
	 * @see java.util.List#listIterator()
	 */
	public ListIterator listIterator() {
		return null;
	}

	/* 
	 * @see java.util.List#listIterator(int)
	 */
	public ListIterator listIterator(int index) {
		return null;
	}

	/* 
	 * @see java.util.List#set(int, java.lang.Object)
	 */
	public Object set(int index, Object element) {
		return null;
	}

	/* 
	 * @see java.util.Collection#toArray(java.lang.Object[])
	 */
	public Object[] toArray(Object[] a) {
		return null;
	}

}