package cc.util;


import java.io.Serializable;
import java.lang.reflect.Array;
import java.util.AbstractList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;


/**
 *  <P>Optimized thread-safe array-backed dynamic {@link java.util.List}
 *  implementation.
 *  
 *  <P>The list is backed by a dynamic array; the array will
 *  grow automatically as more elements are added.  This is 
 *  just like java.util.ArrayList; unlike ArrayList, however, 
 *  the array can also <I>shrink</I> after a remove operation.  
 *  The internal array is always the same size as the list, 
 *  saving memory.
 *  
 *  <P>Read access to this list is not synchronized, but write
 *  access is.  To pull this trick off, the state of the list
 *  is cloned during a write, the changes are applied to the
 *  clone, and then the clone replaces the list's state.  Read
 *  operations use a local reference to the old state, and are
 *  not adversely affected by a write.  This is similar to 
 *  {@link FastArrayList}.
 *  
 *  <P>However, since the list is backed by a dynamic array, <I>many
 *  of the algorithms that alter the list already require that 
 *  the state be cloned</I>.  For instance, to remove an element, 
 *  a new array must be allocated, and the elements from the old
 *  array (minus the removed object) must be copied to the new 
 *  array.  FastArrayList essentially performed the cloning twice:
 *  It first clones the entire list, and then performs the costly
 *  remove() operation on the copy.  This implementation is 
 *  optimized such that a new array is only allocated once.  
 *  Assuming no monitor contention, this class should perform 
 *  similarly to {@link java.util.ArrayList}, except for the add(Object)
 *  and set(int, Object) methods, which now perform in linear time.
 *
 *  <P>Sublists produced by this class are also thread-safe, and
 *  they are also not synchronized during a read operation.  
 *
 *  <P>The iterators produced by this class are <I>not</I> "fail-fast".
 *  Read operations on an iterator <I>never</I> fail.  A 
 *  ConcurrentModificationExcepiton will only be raised if the
 *  original list is modified in some way and somebody attempts to 
 *  modify it via the iterator.
 *
 *  @author Paul Jack (pjack atsign sfaf period org)
 */
public class OptimizedFastArrayList implements List, Serializable, Cloneable // RandomAccess
{

	// Note:  This class doesn't extend FastArrayList because
	// FastArrayList extends java.util.ArrayList -- but doesn't
	// actually use any of java.util.ArrayList's state, which
	// seems wasteful.  Also, this class doesn't provide "fast"
	// vs. "slow" modes -- it's always in fast mode.  The list
	// can be prepopulated using the Collection constructor or
	// by using the addAll() method, which runs about as fast
	// as an ArrayLists'.

	// FIXME: More efficient serialization
	// FIXME: Needs a clone() method.
	// FIXME: Only implement indexOf,lastIndexOf once (duplicated code in SubList)


	/**
	 *  Defines the state of the list: an array and a size.
	 */
	static class State implements Serializable
	{

		// FIXME:  size is always equal to array.length, so this
		// entire class is unnecessary.  However, if removeAll(Collection)
		// and retainAll(Collection) are rewritten to be more efficient,
		// we'll will occassionally need an array larger than the size...

		Object[] array;
		int size;


		/**
	 	 *  Constructor.
		 *
		 *  @param array  the array to hold list elements
		 *  @param size   the current number of elements in the array
		 */
		public State(Object[] array, int size)
		{
			this.array = array;
			this.size = size;
		}


		/**
	 	 *  Ensures that the given index is in the bounds of the list.
		 *
		 *  @param index  the index to check
		 *  @throws IndexOutOfBoundsException  if the index is out of bounds
		 */
		void checkBounds(int index)
		{
			if ((index < 0) || (index >= size))
			{
				throw new IndexOutOfBoundsException("Size is: " + size + " Index: " + index);
			}
		}


		/**
		 *  Ensure the given index is in the bounds of the list, or
		 *  is one after the last index.
		 *
	 	 *  @param index the index to check
		 *  @throws IndexOutOfBoundsException if that index is out of bounds
		 */
		void checkBounds2(int index)
		{
			if ((index < 0) || (index > size))
			{
				throw new IndexOutOfBoundsException("Size is: " + size + "Index: " + index);
			}
		}
	}


	/**
	 *  The current state of the list.
	 */
	State state;


	/**
	 *  Constructs a new <Code>OptimizedFastArrayList</Code>.<P>
	 *
	 *  The list will have an initial capacity of 10.
	 */
	public OptimizedFastArrayList()
	{
		this(10);
	}


	/**
	 *  Constructs a new <Code>OptimizedFastArrayList</Code> that will
	 *  be populated from the given collection.
	 *
	 *  @param c  the collection to use to populate this list
	 */
	public OptimizedFastArrayList(Collection c)
	{
		Object[] array = c.toArray();
		this.state = new State(array, array.length);
	}


	/**
	 *  Constructs a new <Code>OptimizedFastArrayList</Code> with the
	 *  specified initial capacity.
	 *
	 *  @param capacity  the initial capacity for the list
	 */ 
	public OptimizedFastArrayList(int capacity)
	{
		this.state = new State(new Object[capacity], 0);
	}


	// javadoc inherited from java.util.List interface
	public int size()
	{
		return state.size;
	}


	// javadoc inherited from java.util.List interface
	public Object get(int index)
	{
		State local = state;
		local.checkBounds(index);
		return local.array[index];
	}


	// javadoc inherited from java.util.List interface
	public synchronized Object set(int index, Object value)
	{
		// Note:  Because the set method doesn't structurally 
		// modify the list, you may be thinking that you can 
		// leave it unsynchronized.  However, since the method
		// returns the previous value, algorithms that depend 
		// on all previous values being returned could fail.
		// If two threads invoke an unsynchronized version of this
		// method, one of them may not get the other's previous
		// value.

		state.checkBounds(index);
		Object[] clone = (Object[])state.array.clone();
		Object result = clone[index];
		clone[index] = value;
		state = new State(clone, state.size);
		return result;
	}


	// javadoc inherited from java.util.List interface
	public synchronized void add(int index, Object value)
	{
		state.checkBounds2(index);
		Object[] clone = new Object[state.size + 1];
		System.arraycopy(state.array, 0, clone, 0, index);
		clone[index] = value;
		System.arraycopy(state.array, index, clone, index + 1, state.size - index);
		state = new State(clone, state.size + 1);
	}


	// javadoc inherited from java.util.List interface
	public synchronized Object remove(int index)
	{
		state.checkBounds(index);
		Object result = state.array[index];
		Object[] clone = new Object[state.size - 1];
		System.arraycopy(state.array, 0, clone, 0, index);
		System.arraycopy(state.array, index + 1, clone, index, state.size - index - 1);
		state = new State(clone, state.size - 1);
		return result;
	}


	// javadoc inherited from java.util.List interface
	public boolean isEmpty()
	{
		return state.size == 0;
	}


	// javadoc inherited from java.util.List interface
	public boolean contains(Object value)
	{
		return indexOf(value) >= 0;
	}


	// javadoc inherited from java.util.List interface
	public Iterator iterator()
	{
		return listIterator();
	}


	// javadoc inherited from java.util.List interface
	public Object[] toArray()
	{
		State local = state;
		Object[] result = new Object[local.size];
		System.arraycopy(local.array, 0, result, 0, local.size);
		return result;
	}


	// javadoc inherited from java.util.List interface
	public Object[] toArray(Object[] target)
	{
		State local = state;
		if (target.length < local.size)
		{
			Class type = target.getClass().getComponentType();
			target = (Object[])Array.newInstance(type, local.size);
		}
		else if (target.length > local.size)
		{
			target[local.size] = null;
		}
		System.arraycopy(local.array, 0, target, 0, state.size);
		return target;
	}


	// javadoc inherited from java.util.List interface
	public synchronized boolean add(Object value)
	{
		Object[] clone;
		clone = new Object[state.size + 1];
		System.arraycopy(state.array, 0, clone, 0, state.size);
		clone[state.size] = value;
		state = new State(clone, state.size + 1);
		return true;
	}


	// javadoc inherited from java.util.List interface
	public synchronized boolean remove(Object value)
	{
		Object[] array = state.array;
		if (value == null)
		{
			for (int i = 0; i < state.size; i++)
			{
				if (array[i] == null)
				{
					remove(i);
					return true;
				}
			}
		}
		else
		{
			for (int i = 0; i < state.size; i++)
			{
				if (value.equals(array[i]))
				{
					remove(i);
					return true;
				}
			}
		}
		return false;
	}


	// javadoc inherited from java.util.List interface
	public boolean containsAll(Collection c)
	{
		final State local = state;
		// FIXME: This is hardly "optimized"...
		return new AbstractList()
		{
			public int size()
			{
				return local.size;
			}

			public Object get(int index)
			{
				return local.array[index];
			}
		}.containsAll(c);
	}


	// javadoc inherited from java.util.List interface
	public synchronized boolean addAll(Collection c)
	{
		Object[] clone = new Object[state.size + c.size()];
		System.arraycopy(state.array, 0, clone, 0, state.size);
		Iterator iterator = c.iterator();
		int index = state.size;
		while (iterator.hasNext())
		{
			clone[index] = iterator.next();
			index++;
		}
		state = new State(clone, index);
		return true;
	}


	// javadoc inherited from java.util.List interface
	public synchronized boolean addAll(int index, Collection c)
	{
		state.checkBounds2(index);
		Object[] clone = new Object[state.size + c.size()];
		System.arraycopy(state.array, 0, clone, 0, index);
		System.arraycopy(state.array, index, clone, index + c.size(), state.size - index);
		Iterator iterator = c.iterator();
		while (iterator.hasNext())
		{
			clone[index] = iterator.next();
			index++;
		}
		state = new State(clone, state.size + c.size());
		return true;
	}


	// javadoc inherited from java.util.List interface
	public synchronized boolean removeAll(Collection c)
	{
		return removeAll(0, state.size, c) > 0;
	}


	/**
	 *  Removes every element in the given collection that's
	 *  within the given range from this list.<P>
	 *
	 *  Note that this method expects external synchronization.
	 *
	 *  @param first  the first index in the range, inclusive
	 *  @param last   the last index in the range, exclusive
	 *  @param c      the collection of elements to remove
	 *  @return  the number of elements that were removed
	 */
	int removeAll(int first, int last, Collection c)
	{
		// FIXME:  This implementation isn't the fastest, but it
		// conserves memory.  Ideally instead of looping twice, we'd
		// only loop once.  However, that would mean that we couldn't
		// resize the array (since we wouldn't know how many elements
		// were removed until after the loop).

		int removalCount = 0;
		for (int i = first; i < last; i++)
		{
			if (c.contains(state.array[i]))
			{
				removalCount++;
			}
		}
		if (removalCount == 0)
		{
			return 0;
		}
		Object[] clone = new Object[state.size - removalCount];
		int index = 0;
		for (int i = first; i < last; i++)
		{
			if (!c.contains(state.array[i]))
			{
				clone[index] = state.array[i];
				index++;
			}
		}
		state = new State(clone, state.size - removalCount);
		return removalCount;
	}


	// javadoc inherited from java.util.List interface
	public synchronized boolean retainAll(Collection c)
	{
		return retainAll(0, state.size, c) > 0;
	}



	/**
	 *  Removes every element not found in the given collection
	 *  within the given range from this list.<P>
	 *
	 *  Note that this method expects external synchronization.
	 *
	 *  @param first  the first index in the range, inclusive
	 *  @param last   the last index in the range, exclusive
	 *  @param c      the collection of elements to retain
	 *  @return  the number of elements that were removed
	 */
	int retainAll(int first, int last, Collection c)
	{
		// FIXME:  This implementation isn't the fastest, but it
		// conserves memory.  Ideally instead of looping twice, we'd
		// only loop once.  However, that would mean that we couldn't
		// resize the array (since we wouldn't know how many elements
		// were removed until after the loop).

		int removalCount = 0;
		for (int i = first; i < last; i++)
		{
			if (!c.contains(state.array[i]))
			{
				removalCount++;
			}
		}
		if (removalCount == 0)
		{
			return 0;
		}
		Object[] clone = new Object[state.size - removalCount];
		int index = 0;
		for (int i = first; i < last; i++)
		{
			if (c.contains(state.array[i]))
			{
				clone[index] = state.array[i];
				index++;
			}
		}
		state = new State(clone, state.size - removalCount);
		return removalCount;
	}


	// javadoc inherited from java.util.List interface
	public synchronized void clear()
	{
		Object[] clone = new Object[0];
		state = new State(clone, 0);
	}


	/**
	 *  Removes the given range of elements from this list.
	 *
	 *  @param first  the first index in the range, inclusive
	 *  @param last   the last index  in the range, exclusive
	 */
	void clear(int first, int last)
	{
		int s = last - first;
		Object[] clone = new Object[s];
		System.arraycopy(state.array, 0, clone, 0, first);
		System.arraycopy(state.array, last, clone, first, s);
		state = new State(clone, state.size - s);
	}


	// javadoc inherited from java.util.List interface
	public boolean equals(Object o)
	{
		if (o == this) return true;
		State local = state;
		return equals(local, 0, local.size, o);
	}


	/**
	 *  Returns true if the given object is a list that matches
	 *  the given range of elements.
	 *
	 *  @param local  the state object containing the list to compare
	 *  @param first  the first index of the range, inclusive
	 *  @param last   the last index of the range, exclusive
	 *  @param o   the object to compare
	 *  @return true if the object is a list containing the same
	 *   elements as the sublist; false otherwise
	 */
	boolean equals(State local, int first, int last, Object o)
	{
		if (o == null) return false;
		if (!(o instanceof List)) return false;
		List list = (List)o;
		if (list.size() != local.size) return false;
		Iterator iterator = list.iterator();
		for (int i = first; i < last; i++)
		{
			Object o1 = iterator.next();
			Object o2 = local.array[i];
			if (!(o1 == null) ? (o2 == null) : o1.equals(o2)) return false;
		}
		return true;
	}


	// javadoc inherited from java.util.List interface
	public int hashCode()
	{
		State local = state;
		int code = 0;
		for (int i = 0; i < local.array.length; i++)
		{
			Object v = local.array[i];
			if (v != null) code += v.hashCode();
		}
		return code;
	}


	// javadoc inherited from java.util.List interface
	public int indexOf(Object value)
	{
		State local = state;
		Object[] array = local.array;
		int size = local.size;
		if (value == null)
		{
			for (int i = 0; i < size; i++)
			{
				if (array[i] == null)
				{
					return i;
				}
			}
		}
		else
		{
			for (int i = 0; i < size; i++)
			{
				if (value.equals(array[i]))
				{
					return i;
				}
			}
		}
		return -1;
	}


	// javadoc inherited from java.util.List interface
	public int lastIndexOf(Object value)
	{
		State local = state;
		Object[] array = local.array;
		int size = local.size;
		if (value == null)
		{
			for (int i = size - 1; i >= 0; i++)
			{
				if (array[i] == null)
				{
					return i;
				}
			}
		}
		else
		{
			for (int i = size; i >= 0; i++)
			{
				if (value.equals(array[i]))
				{
					return i;
				}
			}
		}
		return -1;		
	}


	// javadoc inherited from java.util.List interface
	public ListIterator listIterator()
	{
		return listIterator(0);
	}


	// javadoc inherited from java.util.List interface
	public ListIterator listIterator(int index)
	{
		State local = state;
		local.checkBounds2(index);
		return new OptimizedFastArrayListIterator(this, local, index);
	}


	// javadoc inherited from java.util.List interface
	public List subList(int first, int last)
	{
		if (last < first)
		{
			throw new IllegalArgumentException("subList(" + first + ", " + last + "): Invalid range.");
		}
		State local = state;
		local.checkBounds(first);
		local.checkBounds(last);
		return new OptimizedSubList(this, local, first, last);
	}


	/**
	 *  Returns a string representation of this list.<P>
	 *
	 *  The output is the same as {@link java.util.ArrayList#toString}.
	 *
	 *  @return a string representation of this list.
	 */
	public String toString()
	{
		State local = state;
		return toString(local, 0, local.size);
	}


	/**
	 *  Returns a string representation of the given range of elements
	 *  in this list.
	 *
	 *  @param local  the state object containing the list
	 *  @param first  the first index in the range, inclusive
	 *  @param last   the last index in the range, exclusive
	 *  @return a string representation of the given range of elements
	 */
	String toString(State local, int first, int last)
	{
		StringBuffer result = new StringBuffer(16 * local.size);
		result.append('[');
		if (last - first > 0)
		{
			result.append(local.array[first]);
		}
		for (int i = first + 1; i < last; i++)
		{
			result.append(", ");
			result.append(local.array[i]);
		}
		result.append(']');
		return result.toString();
	}

}


/**
 *  Sublist produced by OptimizedFastArrayList.
 */
class OptimizedSubList implements List
{

	static class SubState
	{
		int first;
		int last;
		OptimizedFastArrayList.State expected;


		public SubState(OptimizedFastArrayList.State expected, int first, int last)
		{
			this.expected = expected;
			this.first = first;
			this.last = last;
		}


		public int checkBounds(int index)
		{
			index += first;
			if ((index < first) || (index >= last))
			{
				throw new IndexOutOfBoundsException();
			}
			return index;
		}

		public int checkBounds2(int index)
		{
			index += first;
			if ((index < first) || (index > last))
			{
				throw new IndexOutOfBoundsException();
			}
			return index;
		}
	}


	OptimizedFastArrayList fast;
	SubState state;


	OptimizedSubList(OptimizedFastArrayList fast, OptimizedFastArrayList.State expected, int first, int last)
	{
		this.fast = fast;
		this.state = new SubState(expected, first, last);
	}


	private void checkMod()
	{
		if (fast.state != state.expected)
		{
			throw new ConcurrentModificationException();
		}
	}


	public int size()
	{
		SubState local = state;
		return local.last - local.first;
	}


	public boolean isEmpty()
	{
		SubState local = state;
		return local.first == local.last;
	}


	public boolean contains(Object v)
	{
		return indexOf(v) >= 0;
	}


	public Iterator iterator()
	{
		return listIterator();
	}


	public Object[] toArray()
	{
		// FIXME: Optimize
		return toArray(new Object[0]);
	}


	public Object[] toArray(Object[] target)
	{
		SubState local = state;
		int size = local.last - local.first;
		if (target.length < size)
		{
			Class type = target.getClass().getComponentType();
			target = (Object[])Array.newInstance(type, size);
		}
		else if (target.length > size)
		{
			target[size] = null;
		}
		System.arraycopy(local.expected.array, 0, target, 0, size);
		return target;
	}


	public boolean add(Object v)
	{
		synchronized (fast)
		{
			checkMod();
			fast.add(state.first, v);
			state = new SubState(fast.state, state.first, state.last + 1);
		}
		return true;
	}


	public boolean remove(Object v)
	{
		synchronized (fast)
		{
			checkMod();
			int i = indexOf(v);
			if (i < 0) return false;
			fast.remove(state.first + i);
			state = new SubState(fast.state, state.first, state.last - 1);
			return true;
		}
	}


	public boolean containsAll(Collection c)
	{
		SubState local = state;
		Object[] array = local.expected.array;
		for (int i = local.first; i < local.last; i++)
		{
			if (!c.contains(array[i])) return false;
		}
		return true;
	}


	public boolean addAll(Collection c)
	{
		return addAll(0, c);
	}


	public boolean addAll(int index, Collection c)
	{
		synchronized (fast)
		{
			checkMod();
			index = state.checkBounds2(index);
			boolean result = fast.addAll(index, c);
			state = new SubState(fast.state, state.first, state.last + c.size());
			return result;
		}
	}


	public boolean removeAll(Collection c)
	{
		int count;
		synchronized (fast)
		{
			checkMod();
			count = fast.removeAll(state.first, state.last, c);
			state = new SubState(fast.state, state.first, state.last - count);
		}
		return count > 0;
	}


	public boolean retainAll(Collection c)
	{
		int count;
		synchronized (fast)
		{
			checkMod();
			count = fast.retainAll(state.first, state.last, c);
			state = new SubState(fast.state, state.first, state.last - count);
		}
		return count > 0;
	}


	public void clear()
	{
		synchronized (fast)
		{
			checkMod();
			fast.clear(state.first, state.last);
			state = new SubState(fast.state, state.first, state.first);
		}
	}


	public boolean equals(Object v)
	{
		if (v == this) return true;
		SubState local = state;
		return fast.equals(local.expected, local.first, local.last, v);
	}


	public int hashCode()
	{
		SubState local = state;
		Object[] array = local.expected.array;
		int code = 0;
		for (int i = local.first; i < local.last; i++)
		{
			Object v = array[i];
			if (v != null) code += v.hashCode();
		}
		return code;
	}


	public Object get(int index)
	{
		SubState local = state;
		index = local.checkBounds(index);
		return local.expected.array[index];
	}


	public Object set(int index, Object v)
	{
		synchronized (fast)
		{
			checkMod();
			index = state.checkBounds(index);
			Object result = fast.set(index, v);
			state = new SubState(fast.state, state.first, state.last);
			return result;
		}
	}


	public void add(int index, Object v)
	{
		synchronized (fast)
		{
			checkMod();
			index = state.checkBounds2(index);
			fast.add(index, v);
			state = new SubState(fast.state, state.first, state.last + 1);
		}
	}


	public Object remove(int index)
	{
		synchronized (fast)
		{
			checkMod();
			index = state.checkBounds(index);
			Object result = fast.remove(index);
			state = new SubState(fast.state, state.first, state.last - 1);
			return result;
		}
	}


	public int indexOf(Object v)
	{
		SubState local = state;
		Object[] array = local.expected.array;
		if (v == null)
		{
			for (int i = local.first; i < local.last; i++)
			{
				if (array[i] == null) return i - local.first;
			}
		}
		else
		{
			for (int i = local.first; i < local.last; i++)
			{
				if (v.equals(array[i])) return i - local.first;
			}
		}
		return -1;
	}


	public int lastIndexOf(Object v)
	{
		SubState local = state;
		Object[] array = local.expected.array;
		if (v == null)
		{
			for (int i = local.last - 1; i >= local.first; i++)
			{
				if (array[i] == null) return i - local.first;
			}
		}
		else
		{
			for (int i = local.last - 1; i < local.first; i++)
			{
				if (v.equals(array[i])) return i - local.first;
			}
		}
		return -1;
	}


	public ListIterator listIterator()
	{
		return listIterator(0);
	}


	public ListIterator listIterator(int index)
	{
		SubState local = state;
		if (index != local.last - local.first)
		{
			local.checkBounds(index);
		}
		return new OptimizedSubListIterator(this, local, index);
	}


	public List subList(int first, int last)
	{
		if (last < first)
		{
			throw new IllegalArgumentException("subList(" + first + ", " + last + "): Invalid range.");
		}
		SubState local = state;
		first = local.checkBounds2(first);
		last = local.checkBounds2(last);
		return new OptimizedSubList(fast, local.expected, first, last);
	}


	public String toString()
	{
		SubState local = state;
		return fast.toString(local.expected, local.first, local.last);
	}


}



class OptimizedFastArrayListIterator implements ListIterator
{

	OptimizedFastArrayList.State state;
	OptimizedFastArrayList fast;
	int cursor;
	int lastReturnedIndex = -1;



	OptimizedFastArrayListIterator(OptimizedFastArrayList fast, OptimizedFastArrayList.State state, int index)
	{
		this.fast = fast;
		this.state = state;
		this.cursor = index;
	}


	private void checkMod()
	{
		checkNull();
		if (state != fast.state)
		{
			state = null;
			throw new ConcurrentModificationException();
		}
		if (lastReturnedIndex == -1)
		{
			throw new IllegalStateException();
		}
	}


	private void checkNull()
	{
		if (state == null)
		{
			throw new ConcurrentModificationException();
		}
	}


	public boolean hasNext()
	{
		checkNull();
		return cursor != state.size;
	}


	public Object next()
	{
		checkNull();
		Object r = state.array[cursor];
		lastReturnedIndex = cursor;
		cursor++;
		return r;
	}


	public boolean hasPrevious()
	{
		checkNull();
		return cursor != 0;
	}


	public Object previous()
	{
		checkNull();
		cursor--;
		Object r = state.array[cursor];
		lastReturnedIndex = cursor;
		return r;
	}


	public int nextIndex()
	{
		return cursor;
	}


	public int previousIndex()
	{
		return cursor - 1;
	}


	public void remove()
	{
		synchronized (fast)
		{
			checkMod();
			fast.remove(lastReturnedIndex);
			if (lastReturnedIndex < cursor)
			{
				cursor--;
			}
			lastReturnedIndex = -1;
			state = fast.state;
		}
	}


	public void set(Object v)
	{
		synchronized (fast)
		{
			checkMod();
			fast.set(lastReturnedIndex, v);
			lastReturnedIndex = -1;
			state = fast.state;
		}
	}


	public void add(Object v)
	{
		synchronized (fast)
		{
			checkMod();
			fast.add(cursor, v);
			cursor++;
			lastReturnedIndex = -1;
			state = fast.state;
		}
	}


}


class OptimizedSubListIterator implements ListIterator
{

	OptimizedSubList.SubState state;
	OptimizedSubList sub;
	int cursor;
	int lastReturnedIndex = -1;


	OptimizedSubListIterator(OptimizedSubList sub, OptimizedSubList.SubState state, int index)
	{
		this.sub = sub;
		this.state = state;
		this.cursor = index + state.first;
	}


	private void checkMod()
	{
		checkNull();
		if ((state != sub.state) || (state.expected != sub.fast.state))
		{
			state = null;
			throw new ConcurrentModificationException();
		}
		if (lastReturnedIndex == -1)
		{
			throw new IllegalStateException();
		}
	}


	private void checkNull()
	{
		if (state == null)
		{
			throw new ConcurrentModificationException();
		}
	}


	public boolean hasNext()
	{
		checkNull();
		return cursor != state.last;
	}


	public Object next()
	{
		checkNull();
		Object r = state.expected.array[cursor];
		lastReturnedIndex = cursor;
		cursor++;
		return r;
	}


	public boolean hasPrevious()
	{
		checkNull();
		return cursor != state.first;
	}


	public Object previous()
	{
		checkNull();
		cursor--;
		Object r = state.expected.array[cursor];
		lastReturnedIndex = cursor;
		return r;
	}


	public int nextIndex()
	{
		return cursor - state.first;
	}


	public int previousIndex()
	{
		return cursor - 1 - state.first;
	}


	public void remove()
	{
		synchronized (sub.fast)
		{
			checkMod();
			sub.remove(lastReturnedIndex - state.first);
			if (lastReturnedIndex < cursor)
			{
				cursor--;
			}
			lastReturnedIndex = -1;
			state = sub.state;
		}
	}


	public void set(Object v)
	{
		synchronized (sub.fast)
		{
			checkMod();
			sub.set(lastReturnedIndex - state.first, v);
			lastReturnedIndex = -1;
			state = sub.state;
		}
	}


	public void add(Object v)
	{
		synchronized (sub.fast)
		{
			checkMod();
			sub.add(cursor - state.first, v);
			cursor++;
			lastReturnedIndex = -1;
			state = sub.state;
		}
	}


}