Coverage Report

 /*
  Copyright 2004-2008 Paul R. Holser, Jr.  All rights reserved.
  Licensed under the Academic Free License version 3.0
  */
 
 package jaggregate;
 
 import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.Serializable;
 import java.lang.reflect.Array;
 import java.util.NoSuchElementException;
 import static java.lang.Math.*;
 import static java.lang.System.*;
 
 import jaggregate.internal.Casting;
 import jaggregate.internal.ReadOnlySequences;
 import static jaggregate.internal.ArgumentChecks.*;
 import static jaggregate.internal.ReadOnlySequences.*;
 
 /**
  * Represents an ordered, variable-sized collection of objects, where elements may be
  * added, removed, or inserted, and can be accessed using external integer keys.
  *
  * @param <E> a restriction on the types of elements that may be included in the
  * collection
  *
  * @author <a href="mailto:pholser@alumni.rice.edu">Paul Holser</a>
  * @version $Id: OrderedCollection.java,v 1.8 2008/10/03 19:01:23 pholser Exp $
  */
 public class OrderedCollection<E> extends AbstractExtensibleCollection<E>
     implements ContractibleSequence<E>, Sequence<E>, Serializable {
 
     private static final int LEFT_BOUND = -2;
     private static final long serialVersionUID = -1L;
     private static final int DEFAULT_INITIAL_CAPACITY = 10;
 
     private transient Object[] storage;
     private int numberOfElements;
 
     /**
      * Creates an empty ordered collection.
      */
     public OrderedCollection() {
         this( DEFAULT_INITIAL_CAPACITY );
     }
 
     /**
      * Creates an ordered collection containing the elements in the given collection.
      *
      * @param elements elements to add to the new ordered collection
      * @throws NullPointerException if {@code elements} is {@code null}
      */
     public OrderedCollection( Collection<? extends E> elements ) {
         this();
         addAll( elements );
     }
 
     /**
      * Creates an ordered collection containing the elements in the given array.
      *
      * @param elements elements to add to the new ordered collection
      * @throws NullPointerException if {@code elements} is {@code null}
      */
     public OrderedCollection( E... elements ) {
         this();
         addAll( elements );
     }
 
     /**
      * Creates an ordered collection containing the elements in the given iterable
      * object.
      *
      * @param elements elements to add to the new ordered collection
      * @throws NullPointerException if {@code elements} is {@code null}
      */
     public OrderedCollection( Iterable<? extends E> elements ) {
         this();
         addAll( elements );
     }
 
     /**
      * Creates an empty ordered collection with the given initial capacity.
      *
      * @param capacity the initial capacity
      * @throws IllegalArgumentException if {@code capacity <= 0}
      */
     public OrderedCollection( int capacity ) {
         if ( capacity <= 0 )
             throw new IllegalArgumentException( "non-positive capacity: " + capacity );
 
         storage = new Object[ capacity ];
         numberOfElements = 0;
     }
 
     /**
      * Creates an empty ordered collection.
      *
      * @param <T> the type of elements allowed in the new ordered collection
      * @return a new empty ordered collection
      */
     public static <T> OrderedCollection<T> emptyOrderedCollection() {
         return new OrderedCollection<T>();
     }
 
     /**
      * Creates an ordered collection containing the elements in the given collection.
      *
      * @param <T> the type of elements allowed in the new ordered collection
      * @param elements elements to add to the new ordered collection
      * @return the new ordered collection
      * @throws NullPointerException if {@code elements} is {@code null}
      */
     public static <T> OrderedCollection<T> orderedCollectionFrom(
         Collection<? extends T> elements ) {
 
         return new OrderedCollection<T>( elements );
     }
 
     /**
      * Creates an ordered collection containing the elements in the given array.
      *
      * @param <T> the type of elements allowed in the new ordered collection
      * @param elements elements to add to the new ordered collection
      * @return a new ordered collection
      * @throws NullPointerException if {@code elements} is {@code null}
      */
     public static <T> OrderedCollection<T> orderedCollectionFrom( T[] elements ) {
         return new OrderedCollection<T>( elements );
     }
 
     /**
      * Creates an ordered collection containing the given elements.
      *
      * @param <T> the type of elements allowed in the new ordered collection
      * @param newElement first new element to ordered collection
      * @param restOfNewElements remainder of the elements to ordered collection
      * @return a new ordered collection
      * @throws NullPointerException if {@code restOfNewElements} is {@code null}
      * @throws IllegalArgumentException if any of the new elements is found to violate
      * restrictions on the characteristics of valid elements
      * @see #addAll(Collection)
      */
     public static <T> OrderedCollection<T> orderedCollectionWith( T newElement,
         T... restOfNewElements ) {
 
         OrderedCollection<T> ordered = emptyOrderedCollection();
         ordered.add( newElement );
         ordered.addAll( restOfNewElements );
 
         return ordered;
     }
 
     /**
      * Creates an ordered collection containing the elements in the given iterable
      * object.
      *
      * @param <T> the type of elements allowed in the new ordered collection
      * @param elements elements to add to the new ordered collection
      * @return a new ordered collection
      * @throws NullPointerException if {@code elements} is {@code null}
      */
     public static <T> OrderedCollection<T> orderedCollectionFrom(
         Iterable<? extends T> elements ) {
 
         return new OrderedCollection<T>( elements );
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     public Object[] toArray( Class<? super E> componentClass ) {
         Object[] asArray = (Object[]) Array.newInstance( componentClass, size() );
         arraycopy( storage, 0, asArray, 0, size() );
 
         return asArray;
     }
 
     /**
      * {@inheritDoc}
      * <p/>
      * Answers self.
      */
     @Override
     public OrderedCollection<E> toOrderedCollection() {
         return this;
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     public <R> OrderedCollection<R> collect(
         UnaryFunctor<? super E, ? extends R> transformer ) {
 
         return (OrderedCollection<R>) super.collect( transformer );
     }
 
     /**
      * {@inheritDoc}
      */
     public void forEachDo( UnaryFunctor<? super E, ?> operation ) {
         ensureNotNull( operation, OPERATION );
 
         for ( int i = 0; i < size(); ++i )
             operation.evaluate( at( i ) );
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     public OrderedCollection<E> reject( UnaryCondition<? super E> discriminator ) {
         return (OrderedCollection<E>) super.reject( discriminator );
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     public OrderedCollection<E> select( UnaryCondition<? super E> discriminator ) {
         return (OrderedCollection<E>) super.select( discriminator );
     }
 
     /**
      * {@inheritDoc}
      */
     public int size() {
         return numberOfElements;
     }
 
     /**
      * {@inheritDoc}
      */
     public int findFirst( UnaryCondition<? super E> discriminator ) {
         return ReadOnlySequences.findFirst( this, discriminator );
     }
 
     /**
      * {@inheritDoc}
      */
     public int findLast( UnaryCondition<? super E> discriminator ) {
         return ReadOnlySequences.findLast( this, discriminator );
     }
 
     /**
      * {@inheritDoc}
      */
     public void forEachInReverseDo( UnaryFunctor<? super E, ?> operation ) {
         ReadOnlySequences.forEachInReverseDo( this, operation );
     }
 
     /**
      * {@inheritDoc}
      */
     public E first() {
         ensureNotEmpty();
 
         return at( 0 );
     }
 
     /**
      * {@inheritDoc}
      */
     public void forEachInRangeDo( int start, int stop,
         UnaryFunctor<? super E, ?> operation ) {
 
         ReadOnlySequences.forEachInRangeDo( this, start, stop, operation );
     }
 
     /**
      * {@inheritDoc}
      */
     public void forEachInRangeDoWithIndex( int start, int stop,
         BinaryFunctor<? super Integer, ? super E, ?> operation ) {
 
         ReadOnlySequences.forEachInRangeDoWithIndex( this, start, stop, operation );
     }
 
     /**
      * {@inheritDoc}
      */
     public int indexOf( E target ) {
         return ReadOnlySequences.indexOf( this, target );
     }
 
     /**
      * {@inheritDoc}
      */
     public int indexOf( ReadOnlySequence<? extends E> targetSequence, int start ) {
         return ReadOnlySequences.indexOf( this, targetSequence, start );
     }
 
     /**
      * {@inheritDoc}
      */
     public void doWithIndex( BinaryFunctor<? super Integer, ? super E, ?> operation ) {
         ReadOnlySequences.doWithIndex( this, operation );
     }
 
     /**
      * {@inheritDoc}
      */
     public E last() {
         ensureNotEmpty();
 
         return at( size() - 1 );
     }
 
     /**
      * {@inheritDoc}
      * <p/>
      * {@code newElement} is added to the end of this collection's elements so that it
      * becomes the {@linkplain #last() last} element in the traversal order.
      * This message is equivalent to {@link #addLast(Object) addLast} for this
      * collection with {@code newElement} as the parameter.
      */
     public void add( E newElement ) {
         addLast( newElement );
     }
 
     /**
      * {@inheritDoc}
      */
     public boolean remove( E oldElement ) {
         int indexOfOldElement = indexOf( oldElement );
 
         if ( indexOfOldElement == -1 )
             return false;
 
         removeAt( indexOfOldElement );
         return true;
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     public boolean removeIf( UnaryCondition<? super E> discriminator ) {
         ensureNotNull( discriminator, DISCRIMINATOR );
 
         boolean removalOccurred = false;
 
         int i = 0;
         while ( i < size() ) {
             if ( discriminator.matches( at( i ) ) ) {
                 removalOccurred = true;
                 removeAt( i );
             }
             else
                 ++i;
         }
 
         return removalOccurred;
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     public boolean retainIf( UnaryCondition<? super E> discriminator ) {
         ensureNotNull( discriminator, DISCRIMINATOR );
 
         boolean removalOccurred = false;
 
         int i = 0;
         while ( i < size() ) {
             if ( discriminator.matches( at( i ) ) )
                 ++i;
             else {
                 removalOccurred = true;
                 removeAt( i );
             }
         }
 
         return removalOccurred;
     }
 
     /**
      * {@inheritDoc}
      */
     public E removeAt( int index ) {
         ensureIndexIsValid( index, "removal" );
 
         E removedElement = Casting.<E>cast( storage[ index ] );
         --numberOfElements;
         arraycopy( storage, index + 1, storage, index, size() - index );
 
         return removedElement;
     }
 
     /**
      * {@inheritDoc}
      */
     public E removeFirst() {
         ensureNotEmpty();
 
         return removeAt( 0 );
     }
 
     /**
      * {@inheritDoc}
      */
     public E removeLast() {
         ensureNotEmpty();
 
         return removeAt( size() - 1 );
     }
 
     /**
      * {@inheritDoc}
      */
     public OrderedCollection<E> concat( ReadOnlySequence<? extends E> otherSequence ) {
         return ReadOnlySequences.concat( this, otherSequence );
     }
 
     /**
      * {@inheritDoc}
      */
     public E after( E target ) {
         int indexOfTarget = ensureIndexOfElementIsNot( target, size() - 1 );
 
         return at( indexOfTarget + 1 );
     }
 
     /**
      * {@inheritDoc}
      */
     public E at( int index ) {
         ensureIndexIsValid( index, "search" );
 
         return Casting.<E>cast( storage[ index ] );
     }
 
     /**
      * {@inheritDoc}
      */
     public E before( E target ) {
         int indexOfTarget = indexOf( target );
         if ( indexOfTarget <= 0 )
             throw new NoSuchElementException( "no element before " + target );
 
         return at( indexOfTarget - 1 );
     }
 
     /**
      * {@inheritDoc}
      */
     public OrderedCollection<E> copyRange( int start, int stop ) {
         return ReadOnlySequences.copyRange( this, start, stop );
     }
 
     /**
      * {@inheritDoc}
      */
     public OrderedCollection<E> copyWith( E newElement ) {
         return ReadOnlySequences.copyWith( this, newElement );
     }
 
     /**
      * {@inheritDoc}
      */
     public OrderedCollection<E> copyWithout( E oldElement ) {
         return ReadOnlySequences.copyWithout( this, oldElement );
     }
 
     /**
      * {@inheritDoc}
      */
     public OrderedCollection<E> reverse() {
         return ReadOnlySequences.reverse( this );
     }
 
     /**
      * {@inheritDoc}
      */
     public <T> void doWithOthers( ReadOnlySequence<? extends T> otherSequence,
         BinaryFunctor<? super E, ? super T, ?> operation ) {
 
         ReadOnlySequences.doWithOthers( this, otherSequence, operation );
     }
 
     /**
      * {@inheritDoc}
      */
     public E putAt( int index, E newElement ) {
         ensureIndexIsValid( index, "insertion" );
 
         E previousElement = at( index );
         storage[ index ] = newElement;
         return previousElement;
     }
 
     /**
      * {@inheritDoc}
      */
     public void putAtAll( Collection<? extends Integer> indices, final E newElement ) {
         indices.forEachDo( new UnaryFunctor<Integer, Void>() {
             public Void evaluate( Integer argument ) {
                 putAt( argument, newElement );
                 return null;
             }
         } );
     }
 
     /**
      * {@inheritDoc}
      */
     public void putAtAll( int[] indices, E newElement ) {
         for ( int each : indices )
             putAt( each, newElement );
     }
 
     /**
      * {@inheritDoc}
      */
     public void putAtAll( Integer[] indices, E newElement ) {
         for ( int each : indices )
             putAt( each, newElement );
     }
 
     /**
      * {@inheritDoc}
      */
     public void putAtAll( Iterable<? extends Integer> indices, E newElement ) {
         for ( int each : indices )
             putAt( each, newElement );
     }
 
     /**
      * {@inheritDoc}
      */
     public void putAtAll( final E newElement ) {
         doWithIndex( new BinaryFunctor<Integer, E, Void>() {
             public Void evaluate( Integer first, E second ) {
                 putAt( first, newElement );
                 return null;
             }
         } );
     }
 
     /**
      * {@inheritDoc}
      */
     public void replace( int start, int stop, final E replacement ) {
         ensureIndexIsValid( start, STARTING_INDEX );
         ensureIndexIsValid( stop, ENDING_INDEX );
 
         forEachInRangeDoWithIndex( start, stop, new BinaryFunctor<Integer, E, Void>() {
             public Void evaluate( Integer first, E second ) {
                 putAt( first, replacement );
                 return null;
             }
         } );
     }
 
     /**
      * {@inheritDoc}
      */
     public void replaceRange( final int start, int stop,
         ReadOnlySequence<? extends E> replacements ) {
 
         ensureNotNull( replacements, REPLACEMENT_SEQUENCE );
         ensureIndexIsValid( start, STARTING_INDEX );
         ensureIndexIsValid( stop, ENDING_INDEX );
 
         if ( stop >= start ) {
             if ( replacements.size() != stop - start + 1 ) {
                 throw new IllegalArgumentException(
                     EXPECTED_SEQUENCE_SIZE
                         + ( stop - start + 1 )
                         + BUT_WAS
                         + replacements.size() );
             }
 
             replacements.doWithIndex( new BinaryFunctor<Integer, E, Void>() {
                 public Void evaluate( Integer first, E second ) {
                     putAt( first + start, second );
                     return null;
                 }
             } );
         }
     }
 
     /**
      * {@inheritDoc}
      */
     public void replaceRange( int start, int stop,
         final ReadOnlySequence<? extends E> replacements, int replacementStart ) {
 
         ensureNotNull( replacements, REPLACEMENT_SEQUENCE );
         ensureIndexIsValid( start, STARTING_INDEX );
         ensureIndexIsValid( stop, ENDING_INDEX );
         checkIndexIsValidOn( replacements, replacementStart, "replacement starting" );
 
         if ( stop >= start ) {
             if ( replacements.size() != replacementStart + stop - start + 1 ) {
                 throw new IllegalArgumentException(
                     "expecting replacement sequence of size "
                         + ( replacementStart + stop - start + 1 )
                         + BUT_WAS
                         + replacements.size() );
             }
 
             final int[] replacementIndex = { replacementStart };
 
             forEachInRangeDoWithIndex( start, stop,
                 new BinaryFunctor<Integer, E, Void>() {
                     public Void evaluate( Integer first, E second ) {
                         int whereToReplace = replacementIndex[ 0 ];
                         ++replacementIndex[ 0 ];
                         putAt( first, replacements.at( whereToReplace ) );
                         return null;
                     }
                 }
             );
         }
     }
 
     /**
      * Adds a new element to this collection immediately following the first element
      * which is equivalent to a given target.  An element immediately follows another
      * if its index is one greater than that of the other.  The order used to determine
      * which of this collection's elements is the first to equal {@code target} is
      * the traversal order defined by {@link #forEachDo(UnaryFunctor) forEachDo} for
      * this collection.
      *
      * @param newElement the element to add
      * @param target the element after which to add {@code newElement}
      * @throws NoSuchElementException if this collection does not {@linkplain
      * #includes(Object) include} {@code target}
      */
     public void addAfter( E newElement, E target ) {
         int indexOfTarget = ensureElementIsPresent( target );
         addAfterIndex( newElement, indexOfTarget );
     }
 
     /**
      * Adds a new element to this collection immediately following the element at
      * the given index.  {@code newElement} is inserted at position {@code index + 1}.
      * If {@code index == -1}, {@code newElement} becomes the {@linkplain #first() first}
      * element of this collection.
      *
      * @param newElement the element to add
      * @param index the index after which to add {@code newElement}
      * @throws IndexOutOfBoundsException if {@code index < -1} or {@code index >=} this
      * collection's {@linkplain #size() size}.
      */
     public void addAfterIndex( E newElement, int index ) {
         ensureIndexIsGreaterThan( index, LEFT_BOUND, ADDITION_INDEX );
         ensureIndexIsLessThan( index, size(), ADDITION_INDEX );
 
         if ( index == -1 )
             addFirst( newElement );
         else if ( index == size() - 1 )
             addLast( newElement );
         else {
             resizeIfNeeded();
             arraycopy( storage, index + 1, storage, index + 2, size() - index - 1 );
 
             putAt( index + 1, newElement );
             ++numberOfElements;
         }
     }
 
     /**
      * Adds a new element to this collection immediately preceding the first element
      * which is equivalent to a given target.  An element immediately precedes another
      * if its index is one less than that of the other.  The order used to determine
      * which of this collection's elements is the first to equal {@code target} is the
      * traversal order defined by {@link #forEachDo(UnaryFunctor) forEachDo} for this
      * collection.
      *
      * @param newElement the element to add
      * @param target the element before which to add {@code newElement}
      * @throws NoSuchElementException if this collection does not {@linkplain
      * #includes(Object) include} {@code target}
      */
     public void addBefore( E newElement, E target ) {
         int indexOfTarget = ensureElementIsPresent( target );
         addBeforeIndex( newElement, indexOfTarget );
     }
 
     /**
      * Adds a new element to this collection immediately preceding the element at the
      * given index.  If {@code index ==} this collection's {@linkplain #size() size},
      * then {@code newElement} will become the {@linkplain #last() last} element of
      * this collection.
      *
      * @param newElement the element to add
      * @param index the before after which to add {@code newElement}
      * @throws IndexOutOfBoundsException if {@code index < 0} or {@code index >} this
      * collection's {@linkplain #size() size}.
      */
     public void addBeforeIndex( E newElement, int index ) {
         ensureIndexIsGreaterThan( index, -1, ADDITION_INDEX );
         ensureIndexIsLessThan( index, size() + 1, ADDITION_INDEX );
 
         if ( index == 0 )
             addFirst( newElement );
         else if ( index == size() )
             addLast( newElement );
         else {
             resizeIfNeeded();
             arraycopy( storage, index, storage, index + 1, size() - index );
 
             putAt( index, newElement );
             ++numberOfElements;
         }
     }
 
     /**
      * Adds each element of the given collection to this collection immediately after
      * the first element in this collection which is equivalent to a given target.
      * <p/>
      * The elements of {@code newElements} are added to this collection in the traversal
      * order defined by {@link #forEachDo(UnaryFunctor) forEachDo} for {@code
      * newElements}.  An element immediately follows another if its index is one greater
      * than that of the other.  The order used to determine which of this collection's
      * elements is the first to equal {@code target} is the traversal order defined by
      * {@link #forEachDo(UnaryFunctor) forEachDo} for this collection.
      *
      * @param newElements the elements to add
      * @param target the element after which to perform the additions
      * @throws NullPointerException if {@code newElements} is {@code null}
      * @throws NoSuchElementException if this collection does not {@linkplain
      * #includes(Object) include} {@code target}
      */
     public void addAllAfter( Collection<? extends E> newElements, E target ) {
         int indexOfTarget = ensureElementIsPresent( target );
         addAllAfterIndex( newElements, indexOfTarget );
     }
 
     /**
      * @see #addAllAfter(Collection,Object)
      * @param newElements the elements to add
      * @param target the element after which to perform the additions
      * @throws NullPointerException if {@code newElements} is {@code null}
      * @throws NoSuchElementException if this collection does not {@linkplain
      * #includes(Object) include} {@code target}
      */
     public void addAllAfter( E[] newElements, E target ) {
         addAllAfter( orderedCollectionFrom( newElements ), target );
     }
 
     /**
      * @see #addAllAfter(Collection,Object)
      * @param newElements the elements to add
      * @param target the element after which to perform the additions
      * @throws NullPointerException if {@code newElements} is {@code null}
      * @throws NoSuchElementException if this collection does not {@linkplain
      * #includes(Object) include} {@code target}
      */
     public void addAllAfter( Iterable<? extends E> newElements, E target ) {
         addAllAfter( orderedCollectionFrom( newElements ), target );
     }
 
     /**
      * Adds each element of the given collection to this collection immediately
      * following the element at the given index.
      * <p/>
      * The elements of {@code newElements} are added to this collection in the traversal
      * order defined by {@link #forEachDo(UnaryFunctor) forEachDo} for {@code
      * newElements}.  {@code newElements} are inserted immediately after the element in
      * this collection at position {@code index}.  If {@code index == -1},
      * {@code newElements} are inserted at the beginning of this collection.
      *
      * @param newElements the elements to add
      * @param index the index after which to add {@code newElements}
      * @throws NullPointerException if {@code newElements} is {@code null}
      * @throws IndexOutOfBoundsException if {@code index < -1} or {@code index >=} this
      * collection's {@linkplain #size() size}
      */
     public void addAllAfterIndex( Collection<? extends E> newElements, final int index ) {
         ensureIndexIsGreaterThan( index, LEFT_BOUND, ADDITION_INDEX );
         ensureIndexIsLessThan( index, size(), ADDITION_INDEX );
 
         if ( index == -1 )
             addAllFirst( newElements );
         else if ( index == size() - 1 )
             addAllLast( newElements );
         else {
             resizeIfNeeded( size() + newElements.size() );
             arraycopy( storage, index + 1, storage, index + 1 + newElements.size(),
                 size() - index - 1 );
 
             final int[] offset = { 0 };
 
             newElements.forEachDo( new UnaryFunctor<E, Void>() {
                 public Void evaluate( E argument ) {
                     storage[ index + 1 + offset[ 0 ] ] = argument;
                     ++offset[ 0 ];
                     ++numberOfElements;
                     return null;
                 }
             } );
         }
     }
 
     /**
      * @see #addAllAfterIndex(Collection,int)
      * @param newElements the elements to add
      * @param index the index after which to add {@code newElements}
      * @throws NullPointerException if {@code newElements} is {@code null}
      * @throws IndexOutOfBoundsException if {@code index < -1} or {@code index >=} this
      * collection's {@linkplain #size() size}
      */
     public void addAllAfterIndex( E[] newElements, int index ) {
         addAllAfterIndex( orderedCollectionFrom( newElements ), index );
     }
 
     /**
      * @see #addAllAfterIndex(Collection,int)
      * @param newElements the elements to add
      * @param index the index after which to add {@code newElements}
      * @throws NullPointerException if {@code newElements} is {@code null}
      * @throws IndexOutOfBoundsException if {@code index < -1} or {@code index >=} this
      * collection's {@linkplain #size() size}
      */
     public void addAllAfterIndex( Iterable<? extends E> newElements, int index ) {
         addAllAfterIndex( orderedCollectionFrom( newElements ), index );
     }
 
     /**
      * Adds each element of the given collection to this collection immediately before
      * the first element in this collection which is equivalent to a given target.
      * <p/>
      * The elements of {@code newElements} are added to this collection in the traversal
      * order defined by {@link #forEachDo(UnaryFunctor) forEachDo} for {@code
      * newElements}.  An element immediately precedes another if its index is one
      * greater than that of the other.  The order used to determine which of this
      * collection's elements is the first to equal {@code target} is the traversal order
      * defined by {@link #forEachDo(UnaryFunctor) forEachDo} for this collection.
      *
      * @param newElements the elements to add
      * @param target the element before which to perform the additions
      * @throws NullPointerException if {@code newElements} is {@code null}
      * @throws NoSuchElementException if this collection does not {@linkplain
      * #includes(Object) include} {@code target}
      */
     public void addAllBefore( Collection<? extends E> newElements, E target ) {
         int indexOfTarget = ensureElementIsPresent( target );
         addAllBeforeIndex( newElements, indexOfTarget );
     }
 
     /**
      * @see #addAllBefore(Collection,Object)
      * @param newElements the elements to add
      * @param target the element before which to perform the additions
      * @throws NullPointerException if {@code newElements} is {@code null}
      * @throws NoSuchElementException if this collection does not {@linkplain
      * #includes(Object) include} {@code target}
      */
     public void addAllBefore( E[] newElements, E target ) {
         addAllBefore( orderedCollectionFrom( newElements ), target );
     }
 
     /**
      * @see #addAllBefore(Collection,Object)
      * @param newElements the elements to add
      * @param target the element before which to perform the additions
      * @throws NullPointerException if {@code newElements} is {@code null}
      * @throws NoSuchElementException if this collection does not {@linkplain
      * #includes(Object) include} {@code target}
      */
     public void addAllBefore( Iterable<? extends E> newElements, E target ) {
         addAllBefore( orderedCollectionFrom( newElements ), target );
     }
 
     /**
      * Adds each element of the given collection to this collection immediately
      * preceding the element at the given index.
      * <p/>
      * The elements of {@code newElements} are added to this collection in the traversal
      * order defined by {@link #forEachDo(UnaryFunctor) forEachDo} for {@code
      * newElements}.  {@code newElements} are inserted immediately before the element in
      * this collection at position {@code index}.  If {@code index ==} this collection's
      * {@linkplain #size() size}, {@code newElements} are inserted at the end of this
      * collection.
      *
      * @param newElements the elements to add
      * @param index the index after which to add {@code newElements}
      * @throws NullPointerException if {@code newElements} is {@code null}
      * @throws IndexOutOfBoundsException if {@code index < 0} or {@code index >} this
      * collection's {@linkplain #size() size}
      */
     public void addAllBeforeIndex( Collection<? extends E> newElements,
         final int index ) {
 
         ensureIndexIsGreaterThan( index, -1, ADDITION_INDEX );
         ensureIndexIsLessThan( index, size() + 1, ADDITION_INDEX );
 
         if ( index == 0 )
             addAllFirst( newElements );
         else if ( index == size() )
             addAllLast( newElements );
         else {
             resizeIfNeeded( size() + newElements.size() );
             arraycopy( storage, index, storage, index + newElements.size(),
                 size() - index );
 
             final int[] offset = { 0 };
 
             newElements.forEachDo( new UnaryFunctor<E, Void>() {
                 public Void evaluate( E argument ) {
                     storage[ index + offset[ 0 ] ] = argument;
                     ++offset[ 0 ];
                     ++numberOfElements;
                     return null;
                 }
             } );
         }
     }
 
     /**
      * @see #addAllBeforeIndex(Collection,int)
      * @param newElements the elements to add
      * @param index the index after which to add {@code newElements}
      * @throws NullPointerException if {@code newElements} is {@code null}
      * @throws IndexOutOfBoundsException if {@code index < 0} or {@code index >} this
      * collection's {@linkplain #size() size}
      */
     public void addAllBeforeIndex( E[] newElements, int index ) {
         addAllBeforeIndex( orderedCollectionFrom( newElements ), index );
     }
 
     /**
      * @see #addAllBeforeIndex(Collection,int)
      * @param newElements the elements to add
      * @param index the index after which to add {@code newElements}
      * @throws NullPointerException if {@code newElements} is {@code null}
      * @throws IndexOutOfBoundsException if {@code index < 0} or {@code index >} this
      * collection's {@linkplain #size() size}
      */
     public void addAllBeforeIndex( Iterable<? extends E> newElements, int index ) {
         addAllBeforeIndex( orderedCollectionFrom( newElements ), index );
     }
 
     /**
      * Adds each element of the given collection to the beginning of this collection's
      * elements.
      * <p/>
      * This operation is equivalent to adding each successive element of {@code
      * newElements} to this collection using {@link #addFirst(Object) addFirst} with the
      * element as the parameter, where {@code newElements} are traversed in the order
      * specified by {@link #forEachInReverseDo(UnaryFunctor) forEachInReverseDo} for
      * {@code newElements}.
      *
      * @param newElements the elements to add
      * @throws NullPointerException if {@code newElements} is {@code null}
      */
     public void addAllFirst( Collection<? extends E> newElements ) {
         ensureNotNull( newElements, "new elements" );
 
         if ( !newElements.isEmpty() ) {
             resizeIfNeeded( size() + newElements.size() );
             arraycopy( storage, 0, storage, newElements.size(), size() );
         }
 
         final int[] index = { 0 };
         newElements.forEachDo( new UnaryFunctor<E, Void>() {
             public Void evaluate( E argument ) {
                 storage[ index[ 0 ] ] = argument;
                 ++index[ 0 ];
                 numberOfElements++;
                 return null;
             }
         } );
     }
 
     /**
      * @see #addAllFirst(Collection)
      * @param newElements the elements to add
      * @throws NullPointerException if {@code newElements} is {@code null}
      */
     public void addAllFirst( E... newElements ) {
         addAllFirst( orderedCollectionFrom( newElements ) );
     }
 
     /**
      * @see #addAllFirst(Collection)
      * @param newElements the elements to add
      * @throws NullPointerException if {@code newElements} is {@code null}
      */
     public void addAllFirst( Iterable<? extends E> newElements ) {
         addAllFirst( orderedCollectionFrom( newElements ) );
     }
 
     /**
      * Adds each element of the given collection to the end of this collection's
      * elements.
      * <p/>
      * This operation is equivalent to adding each successive element of {@code
      * newElements} to this collection using {@link #addLast(Object) addLast} with the
      * element as the parameter, where {@code newElements} are traversed in the order
      * specified by {@link #forEachDo(UnaryFunctor) forEachDo} for {@code newElements}.
      *
      * @param newElements the elements to add
      * @throws NullPointerException if {@code newElements} is {@code null}
      */
     public void addAllLast( Collection<? extends E> newElements ) {
         addAll( newElements );
     }
 
     /**
      * @see #addAllLast(Collection)
      * @param newElements the elements to add
      * @throws NullPointerException if {@code newElements} is {@code null}
      */
     public void addAllLast( E... newElements ) {
         addAll( newElements );
     }
 
     /**
      * @see #addAllLast(Collection)
      * @param newElements the elements to add
      * @throws NullPointerException if {@code newElements} is {@code null}
      */
     public void addAllLast( Iterable<? extends E> newElements ) {
         addAll( newElements );
     }
 
     /**
      * Adds a new element to the beginning of this collection's elements.
      * {@code newElement} becomes the {@linkplain #first() first} element in the
      * traversal order.
      *
      * @param newElement the element to add
      */
     public void addFirst( E newElement ) {
         resizeIfNeeded();
         arraycopy( storage, 0, storage, 1, size() );
         ++numberOfElements;
         putAt( 0, newElement );
     }
 
     /**
      * Adds a new element to the end of this collection's elements.  {@code newElement}
      * becomes the {@linkplain #last() last} element in the traversal order.
      *
      * @param newElement the element to add
      */
     public void addLast( E newElement ) {
         resizeIfNeeded();
         storage[ numberOfElements ] = newElement;
         ++numberOfElements;
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     public boolean equals( Object that ) {
         return ReadOnlySequences.areSequencesEqual( this, that );
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     public int hashCode() {
         return ReadOnlySequences.hashCode( this );
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     public String toString() {
         return ReadOnlySequences.toString( this );
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     protected <T> Set<T> newEmptySet() {
         return Set.emptySet();
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     protected OrderedCollection<E> newEmptyExtensibleCollection() {
         return newEmptyExtensibleResultCollection();
     }
 
     /**
      * {@inheritDoc}
      */
     @Override
     protected <R> OrderedCollection<R> newEmptyExtensibleResultCollection() {
         return emptyOrderedCollection();
     }
 
     private void ensureNotEmpty() {
         if ( isEmpty() )
             throw new NoSuchElementException( EMPTY_SEQUENCE );
     }
 
     private int ensureIndexOfElementIsNot( E target, int badIndex ) {
         int indexOfTarget = indexOf( target );
 
         if ( indexOfTarget == badIndex )
             throw new NoSuchElementException( String.valueOf( target ) );
 
         return indexOfTarget;
     }
 
     private int ensureElementIsPresent( E target ) {
         return ensureIndexOfElementIsNot( target, -1 );
     }
 
     private void ensureIndexIsValid( int index, String failureMessage ) {
         checkIndexIsValidOn( this, index, failureMessage );
     }
 
     private void resizeIfNeeded() {
         resizeIfNeeded( size() );
     }
 
     private void resizeIfNeeded( int magnitude ) {
         if ( magnitude >= storage.length ) {
             Object[] oldStorage = storage;
             int newCapacity = max( DEFAULT_INITIAL_CAPACITY, magnitude * 2 );
             storage = new Object[ newCapacity ];
             arraycopy( oldStorage, 0, storage, 0, oldStorage.length );
         }
     }
 
     private void writeObject( ObjectOutputStream output ) throws IOException {
         output.defaultWriteObject();
 
         for ( int i = 0; i < numberOfElements; ++i )
             output.writeObject( storage[ i ] );
     }
 
     private void readObject( ObjectInputStream input )
         throws IOException, ClassNotFoundException {
 
         input.defaultReadObject();
 
         storage = new Object[ numberOfElements ];
 
         for ( int i = 0; i < numberOfElements; ++i )
             storage[ i ] = input.readObject();
     }
 }