package resourceCode.util;


public abstract class AbstractCollectionMe<E> implements CollectionMe<E> {
	/**
	 * Sole constructor. (For invocation by subclass constructors, typically
	 * implicit.)
	 */
	protected AbstractCollectionMe() {
	}

	// Query Operations
	/**
	 * Returns an iterator over the elements contained in this collection.
	 * 
	 * @return an iterator over the elements contained in this collection
	 */
	public abstract IteratorMe<E> iterator();

	public abstract int size();

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * This implementation returns <tt>size() == 0</tt>.
	 */
	public boolean isEmpty() {
		return size() == 0;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * This implementation iterates over the elements in the collection,
	 * checking each element in turn for equality with the specified element.
	 * 
	 * @throws ClassCastException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 */
	public boolean contains(Object o) {
		IteratorMe<E> e = iterator();
		if (o == null) {
			while (e.hasNext())
				if (e.next() == null)
					return true;
		} else {
			while (e.hasNext())
				if (o.equals(e.next()))
					return true;
		}
		return false;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * This implementation returns an array containing all the elements returned
	 * by this collection's iterator, in the same order, stored in consecutive
	 * elements of the array, starting with index {@code 0}. The length of the
	 * returned array is equal to the number of elements returned by the
	 * iterator, even if the size of this collection changes during iteration,
	 * as might happen if the collection permits concurrent modification during
	 * iteration. The {@code size} method is called only as an optimization
	 * hint; the correct result is returned even if the iterator returns a
	 * different number of elements.
	 * 
	 * <p>
	 * This method is equivalent to:
	 * 
	 * <pre>
	 * @code
	 * List<E> list = new ArrayList<E>(size());
	 * for (E e : this)
	 *     list.add(e);
	 * return list.toArray();
	 * }
	 * </pre>
	 */
	public Object[] toArray() {
		// Estimate size of array; be prepared to see more or fewer elements
		Object[] r = new Object[size()];
		IteratorMe<E> it = iterator();
		for (int i = 0; i < r.length; i++) {
			if (!it.hasNext()) // fewer elements than expected
				return ArraysMe.copyOf(r, i);
			r[i] = it.next();
		}
		return it.hasNext() ? finishToArray(r, it) : r;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * This implementation returns an array containing all the elements returned
	 * by this collection's iterator in the same order, stored in consecutive
	 * elements of the array, starting with index {@code 0}. If the number of
	 * elements returned by the iterator is too large to fit into the specified
	 * array, then the elements are returned in a newly allocated array with
	 * length equal to the number of elements returned by the iterator, even if
	 * the size of this collection changes during iteration, as might happen if
	 * the collection permits concurrent modification during iteration. The
	 * {@code size} method is called only as an optimization hint; the correct
	 * result is returned even if the iterator returns a different number of
	 * elements.
	 * 
	 * <p>
	 * This method is equivalent to:
	 * 
	 * <pre>
	 * @code
	 * List<E> list = new ArrayList<E>(size());
	 * for (E e : this)
	 *     list.add(e);
	 * return list.toArray(a);
	 * }
	 * </pre>
	 * 
	 * @throws ArrayStoreException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 */
	public <T> T[] toArray(T[] a) {
		// Estimate size of array; be prepared to see more or fewer elements
		int size = size();
		T[] r = a.length >= size ? a : (T[]) java.lang.reflect.Array
				.newInstance(a.getClass().getComponentType(), size);
		
		IteratorMe<E> it = iterator();
		for (int i = 0; i < r.length; i++) {
			if (!it.hasNext()) { // fewer elements than expected
				if (a != r)
					return ArraysMe.copyOf(r, i);
				r[i] = null; // null-terminate
				return r;
			}
			r[i] = (T) it.next();
		}
		return it.hasNext() ? finishToArray(r, it) : r;
	}

	/**
	 * Reallocates the array being used within toArray when the iterator
	 * returned more elements than expected, and finishes filling it from the
	 * iterator.
	 * 
	 * @param r
	 *            the array, replete with previously stored elements
	 * @param it
	 *            the in-progress iterator over this collection
	 * @return array containing the elements in the given array, plus any
	 *         further elements returned by the iterator, trimmed to size
	 */
	private static <T> T[] finishToArray(T[] r, IteratorMe<?> it) {
		int i = r.length;
		while (it.hasNext()) {
			int cap = r.length;
			if (i == cap) {
				int newCap = ((cap / 2) + 1) * 3;
				if (newCap <= cap) { // integer overflow
					if (cap == Integer.MAX_VALUE)
						throw new OutOfMemoryError(
								"Required array size too large");
					newCap = Integer.MAX_VALUE;
				}
				r = ArraysMe.copyOf(r, newCap);
			}
			r[i++] = (T) it.next();
		}
		// trim if overallocated
		return (i == r.length) ? r : ArraysMe.copyOf(r, i);
	}

	// Modification Operations

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * This implementation always throws an
	 * <tt>UnsupportedOperationException</tt>.
	 * 
	 * @throws UnsupportedOperationException
	 *             {@inheritDoc}
	 * @throws ClassCastException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 * @throws IllegalArgumentException
	 *             {@inheritDoc}
	 * @throws IllegalStateException
	 *             {@inheritDoc}
	 */
	public boolean add(E e) {
		throw new UnsupportedOperationException();
	}

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * This implementation iterates over the collection looking for the
	 * specified element. If it finds the element, it removes the element from
	 * the collection using the iterator's remove method.
	 * 
	 * <p>
	 * Note that this implementation throws an
	 * <tt>UnsupportedOperationException</tt> if the iterator returned by this
	 * collection's iterator method does not implement the <tt>remove</tt>
	 * method and this collection contains the specified object.
	 * 
	 * @throws UnsupportedOperationException
	 *             {@inheritDoc}
	 * @throws ClassCastException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 */
	public boolean remove(Object o) {
		IteratorMe<E> e = iterator();
		if (o == null) {
			while (e.hasNext()) {
				if (e.next() == null) {
					e.remove();
					return true;
				}
			}
		} else {
			while (e.hasNext()) {
				if (o.equals(e.next())) {
					e.remove();
					return true;
				}
			}
		}
		return false;
	}

	// Bulk Operations

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * This implementation iterates over the specified collection, checking each
	 * element returned by the iterator in turn to see if it's contained in this
	 * collection. If all elements are so contained <tt>true</tt> is returned,
	 * otherwise <tt>false</tt>.
	 * 
	 * @throws ClassCastException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 * @see #contains(Object)
	 */
	public boolean containsAll(CollectionMe<?> c) {
		IteratorMe<?> e = c.iterator();
		while (e.hasNext())
			if (!contains(e.next()))
				return false;
		return true;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * This implementation iterates over the specified collection, and adds each
	 * object returned by the iterator to this collection, in turn.
	 * 
	 * <p>
	 * Note that this implementation will throw an
	 * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is overridden
	 * (assuming the specified collection is non-empty).
	 * 
	 * @throws UnsupportedOperationException
	 *             {@inheritDoc}
	 * @throws ClassCastException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 * @throws IllegalArgumentException
	 *             {@inheritDoc}
	 * @throws IllegalStateException
	 *             {@inheritDoc}
	 * 
	 * @see #add(Object)
	 */
	public boolean addAll(CollectionMe<? extends E> c) {
		boolean modified = false;
		IteratorMe<? extends E> e = c.iterator();
		while (e.hasNext()) {
			if (add(e.next()))
				modified = true;
		}
		return modified;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * This implementation iterates over this collection, checking each element
	 * returned by the iterator in turn to see if it's contained in the
	 * specified collection. If it's so contained, it's removed from this
	 * collection with the iterator's <tt>remove</tt> method.
	 * 
	 * <p>
	 * Note that this implementation will throw an
	 * <tt>UnsupportedOperationException</tt> if the iterator returned by the
	 * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
	 * and this collection contains one or more elements in common with the
	 * specified collection.
	 * 
	 * @throws UnsupportedOperationException
	 *             {@inheritDoc}
	 * @throws ClassCastException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 * 
	 * @see #remove(Object)
	 * @see #contains(Object)
	 */
	public boolean removeAll(CollectionMe<?> c) {
		boolean modified = false;
		IteratorMe<?> e = iterator();
		while (e.hasNext()) {
			if (c.contains(e.next())) {
				e.remove();
				modified = true;
			}
		}
		return modified;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * This implementation iterates over this collection, checking each element
	 * returned by the iterator in turn to see if it's contained in the
	 * specified collection. If it's not so contained, it's removed from this
	 * collection with the iterator's <tt>remove</tt> method.
	 * 
	 * <p>
	 * Note that this implementation will throw an
	 * <tt>UnsupportedOperationException</tt> if the iterator returned by the
	 * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
	 * and this collection contains one or more elements not present in the
	 * specified collection.
	 * 
	 * @throws UnsupportedOperationException
	 *             {@inheritDoc}
	 * @throws ClassCastException
	 *             {@inheritDoc}
	 * @throws NullPointerException
	 *             {@inheritDoc}
	 * 
	 * @see #remove(Object)
	 * @see #contains(Object)
	 */
	public boolean retainAll(CollectionMe<?> c) {
		boolean modified = false;
		IteratorMe<E> e = iterator();
		while (e.hasNext()) {
			if (!c.contains(e.next())) {
				e.remove();
				modified = true;
			}
		}
		return modified;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * <p>
	 * This implementation iterates over this collection, removing each element
	 * using the <tt>Iterator.remove</tt> operation. Most implementations will
	 * probably choose to override this method for efficiency.
	 * 
	 * <p>
	 * Note that this implementation will throw an
	 * <tt>UnsupportedOperationException</tt> if the iterator returned by this
	 * collection's <tt>iterator</tt> method does not implement the
	 * <tt>remove</tt> method and this collection is non-empty.
	 * 
	 * @throws UnsupportedOperationException
	 *             {@inheritDoc}
	 */
	public void clear() {
		IteratorMe<E> e = iterator();
		while (e.hasNext()) {
			e.next();
			e.remove();
		}
	}

	// String conversion

	/**
	 * Returns a string representation of this collection. The string
	 * representation consists of a list of the collection's elements in the
	 * order they are returned by its iterator, enclosed in square brackets (
	 * <tt>"[]"</tt>). Adjacent elements are separated by the characters
	 * <tt>", "</tt> (comma and space). Elements are converted to strings as by
	 * {@link String#valueOf(Object)}.
	 * 
	 * @return a string representation of this collection
	 */
	public String toString() {
		IteratorMe<E> i = iterator();
		if (!i.hasNext())
			return "[]";

		StringBuilder sb = new StringBuilder();
		sb.append('[');
		for (;;) {
			E e = i.next();
			sb.append(e == this ? "(this Collection)" : e);
			if (!i.hasNext())
				return sb.append(']').toString();
			sb.append(", ");
		}
	}
}