/*

  Copyright 2004-2008 Paul R. Holser, Jr.  All rights reserved.

  Licensed under the Academic Free License version 3.0

  */

 package jaggregate;

 import java.io.Serializable;

 import java.util.Comparator;

 import static jaggregate.Objects.*;

 import static jaggregate.OrderedCollection.*;

 import static jaggregate.internal.ArgumentChecks.*;

 import jaggregate.internal.ReadOnlySequences;

 import static jaggregate.internal.ReadOnlySequences.*;

 import jaggregate.internal.SequenceIndexOutOfBoundsException;

 /**

  * Represents a variable-sized collection of objects whose elements are ordered based on

  * a sort order.  The sort order is specified by a {@linkplain Comparator comparator}.

  * 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: SortedCollection.java,v 1.9 2008/10/03 19:01:23 pholser Exp $

  */

 public class SortedCollection<E> extends AbstractExtensibleCollection<E>

     implements ContractibleSequence<E>, ReadOnlySequence<E>, Serializable {

     private static final long serialVersionUID = -1L;

     private final OrderedCollection<E> storage;

     private final Comparator<? super E> comparator;

     /**

      * Creates an empty sorted collection whose elements are sorted using the given

      * comparator.

      *

      * @param comparator the comparator with which to compare elements for sorting

      * @throws NullPointerException if {@code comparator} is {@code null}

      */

     public SortedCollection( Comparator<? super E> comparator ) {

         ensureNotNull( comparator, "comparator" );

         this.comparator = comparator;

         storage = emptyOrderedCollection();

     }

     /**

      * Creates a sorted collection whose elements are sorted using the given

      * comparator, and containing the elements of the given collection.

      *

      * @param comparator the comparator with which to compare elements for sorting

      * @param newElements the elements to add to the new collection

      * @throws NullPointerException if either {@code comparator} or {@code newElements}

      * is {@code null}

      */

     public SortedCollection( Comparator<? super E> comparator,

         Collection<? extends E> newElements ) {

         this( comparator );

         addAll( newElements );

     }

     /**

      * Creates a sorted collection whose elements are sorted using the given

      * comparator, and containing the elements of the given array.

      *

      * @param comparator the comparator with which to compare elements for sorting

      * @param newElements the elements to add to the new collection

      * @throws NullPointerException if either {@code comparator} or {@code newElements}

      * is {@code null}

      */

     public SortedCollection( Comparator<? super E> comparator, E... newElements ) {

         this( comparator );

         addAll( newElements );

     }

     /**

      * Creates a sorted collection whose elements are sorted using the given

      * comparator, and containing the elements of the given iterable.

      *

      * @param comparator the comparator with which to compare elements for sorting

      * @param newElements the elements to add to the new collection

      * @throws NullPointerException if either {@code comparator} or {@code newElements}

      * is {@code null}

      */

     public SortedCollection( Comparator<? super E> comparator,

         Iterable<? extends E> newElements ) {

         this( comparator );

         addAll( newElements );

     }

     /**

      * Creates an empty sorted collection whose elements are sorted using the given

      * comparator.

      *

      * @param <T> the type of elements allowed in the new sorted collection

      * @param comparator the comparator with which to compare elements for sorting

      * @return the new sorted collection

      * @throws NullPointerException if {@code comparator} is {@code null}

      */

     public static <T> SortedCollection<T> emptySortedCollection(

         Comparator<? super T> comparator ) {

         return new SortedCollection<T>( comparator );

     }

     /**

      * Creates a sorted collection whose elements are sorted using the given

      * comparator, and containing the elements of the given collection.

      *

      * @param <T> the type of elements allowed in the new sorted collection

      * @param comparator the comparator with which to compare elements for sorting

      * @param newElements the elements to add to the new collection

      * @return the new sorted collection

      * @throws NullPointerException if either {@code comparator} or {@code newElements}

      * is {@code null}

      */

     public static <T> SortedCollection<T> sortedCollectionFrom(

         Comparator<? super T> comparator, Collection<? extends T> newElements ) {

         return new SortedCollection<T>( comparator, newElements );

     }

     /**

      * Creates a sorted collection whose elements are sorted using the given

      * comparator, and containing the elements of the given array.

      *

      * @param <T> the type of elements allowed in the new sorted collection

      * @param comparator the comparator with which to compare elements for sorting

      * @param newElements the elements to add to the new collection

      * @return the new sorted collection

      * @throws NullPointerException if either {@code comparator} or {@code newElements}

      * is {@code null}

      */

     public static <T> SortedCollection<T> sortedCollectionWith(

         Comparator<? super T> comparator, T... newElements ) {

         return new SortedCollection<T>( comparator, newElements );

     }

     /**

      * Creates a sorted collection whose elements are sorted using the given

      * comparator, and containing the elements of the given iterable.

      *

      * @param <T> the type of elements allowed in the new sorted collection

      * @param comparator the comparator with which to compare elements for sorting

      * @param newElements the elements to add to the new collection

      * @return the new sorted collection

      * @throws NullPointerException if either {@code comparator} or {@code newElements}

      * is {@code null}

      */

     public static <T> SortedCollection<T> sortedCollectionFrom(

         Comparator<? super T> comparator, Iterable<? extends T> newElements ) {

         return new SortedCollection<T>( comparator, newElements );

     }

     /**

      * {@inheritDoc}

      * <p/>

      * Answers self.

      */

     @Override

     public SortedCollection<E> toSortedCollection() {

         return this;

     }

     /**

      * {@inheritDoc}

      *

      * @return an ordered collection of the results

      */

     @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 ) {

         storage.forEachDo( operation );

     }

     /**

      * {@inheritDoc}

      *

      * @return a sorted collection of the rejects

      */

     @Override

     public SortedCollection<E> reject( UnaryCondition<? super E> discriminator ) {

         return (SortedCollection<E>) super.reject( discriminator );

     }

     /**

      * {@inheritDoc}

      *

      * @return a sorted collection of the matches

      */

     @Override

     public SortedCollection<E> select( UnaryCondition<? super E> discriminator ) {

         return (SortedCollection<E>) super.select( discriminator );

     }

     /**

      * {@inheritDoc}

      */

     public int size() {

         return storage.size();

     }

     /**

      * {@inheritDoc}

      * <p/>

      * Since this collection sorts its elements, the result will also be sorted

      * as defined by this collection's comparator.

      *

      * @param otherSequence

      * @return a sorted collection that is the concatenation of this collection and

      * {@code otherSequence}

      */

     public SortedCollection<E> concat( ReadOnlySequence<? extends E> otherSequence ) {

         SortedCollection<E> concatenation = sortedCollectionFrom( comparator(), this );

         concatenation.addAll( otherSequence );

         return concatenation;

     }

     /**

      * {@inheritDoc}

      */

     public E after( E target ) {

         return storage.after( target );

     }

     /**

      * {@inheritDoc}

      */

     public E at( int index ) {

         return storage.at( index );

     }

     /**

      * {@inheritDoc}

      */

     public E before( E target ) {

         return storage.before( target );

     }

     /**

      * {@inheritDoc}

      */

     public SortedCollection<E> copyRange( int start, int stop ) {

         if ( start > stop )

             return new SortedCollection<E>( comparator() );

         if ( stop > start ) {

             if ( start < 0 || start >= size() )

                 throw new SequenceIndexOutOfBoundsException( STARTING_INDEX, start );

             if ( stop < 0 || stop >= size() )

                 throw new SequenceIndexOutOfBoundsException( ENDING_INDEX, stop );

         }

         final SortedCollection<E> subsequence = new SortedCollection<E>( comparator() );

         storage.forEachInRangeDo( start, stop, new UnaryFunctor<E, Void>() {

             public Void evaluate( E argument ) {

                 subsequence.add( argument );

                 return null;

             }

         } );

         return subsequence;

     }

     /**

      * {@inheritDoc}

      */

     public SortedCollection<E> copyWith( E newElement ) {

         SortedCollection<E> copy = sortedCollectionFrom( comparator(), this );

         copy.add( newElement );

         return copy;

     }

     /**

      * {@inheritDoc}

      */

     public SortedCollection<E> copyWithout( final E oldElement ) {

         final SortedCollection<E> copy = new SortedCollection<E>( comparator() );

         storage.forEachDo( new UnaryFunctor<E, Void>() {

             public Void evaluate( E argument ) {

                 if ( !areEqual( oldElement, argument ) )

                     copy.add( argument );

                 return null;

             }

         } );

         return copy;

     }

     /**

      * {@inheritDoc}

      */

     public int findFirst( UnaryCondition<? super E> discriminator ) {

         return storage.findFirst( discriminator );

     }

     /**

      * {@inheritDoc}

      */

     public int findLast( UnaryCondition<? super E> discriminator ) {

         return storage.findLast( discriminator );

     }

     /**

      * {@inheritDoc}

      */

     public void forEachInReverseDo( UnaryFunctor<? super E, ?> operation ) {

         storage.forEachInReverseDo( operation );

     }

     /**

      * {@inheritDoc}

      */

     public E first() {

         return storage.first();

     }

     /**

      * {@inheritDoc}

      */

     public void forEachInRangeDo( int start, int stop,

         UnaryFunctor<? super E, ?> operation ) {

         storage.forEachInRangeDo( start, stop, operation );

     }

     /**

      * {@inheritDoc}

      */

     public void forEachInRangeDoWithIndex( int start, int stop,

         BinaryFunctor<? super Integer, ? super E, ?> operation ) {

         storage.forEachInRangeDoWithIndex( start, stop, operation );

     }

     /**

      * {@inheritDoc}

      */

     public int indexOf( E target ) {

         return storage.indexOf( target );

     }

     /**

      * {@inheritDoc}

      */

     public int indexOf( ReadOnlySequence<? extends E> targetSequence, int start ) {

         return storage.indexOf( targetSequence, start );

     }

     /**

      * {@inheritDoc}

      */

     public void doWithIndex( BinaryFunctor<? super Integer, ? super E, ?> operation ) {

         storage.doWithIndex( operation );

     }

     /**

      * {@inheritDoc}

      */

     public E last() {

         return storage.last();

     }

     /**

      * {@inheritDoc}

      */

     public ReadOnlySequence<E> reverse() {

         return storage.reverse();

     }

     /**

      * {@inheritDoc}

      */

     public <T> void doWithOthers( ReadOnlySequence<? extends T> otherSequence,

         BinaryFunctor<? super E, ? super T, ?> operation ) {

         storage.doWithOthers( otherSequence, operation );

     }

     /**

      * {@inheritDoc}

      */

     public void add( E newElement ) {

         storage.addBeforeIndex( newElement, indexBeforeWhichToInsert( newElement ) );

     }

     /**

      * {@inheritDoc}

      */

     public boolean remove( E oldElement ) {

         return storage.remove( oldElement );

     }

     /**

      * {@inheritDoc}

      */

     public E removeAt( int index ) {

         return storage.removeAt( index );

     }

     /**

      * {@inheritDoc}

      */

     public E removeFirst() {

         return storage.removeFirst();

     }

     /**

      * {@inheritDoc}

      */

     public E removeLast() {

         return storage.removeLast();

     }

     /**

      * {@inheritDoc}

      */

     @Override

     public boolean removeIf( UnaryCondition<? super E> discriminator ) {

         return storage.removeIf( discriminator );

     }

     /**

      * {@inheritDoc}

      */

     @Override

     public boolean retainIf( UnaryCondition<? super E> discriminator ) {

         return storage.retainIf( discriminator );

     }

     /**

      * Answers the comparator which is used to order this collection's elements.

      *

      * @return this collection's comparator

      */

     public Comparator<? super E> comparator() {

         return comparator;

     }

     /**

      * {@inheritDoc}

      */

     @Override

     public boolean equals( Object that ) {

         return 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 SortedCollection<E> newEmptyExtensibleCollection() {

         return new SortedCollection<E>( comparator() );

     }

     /**

      * {@inheritDoc}

      */

     @Override

     protected <R> OrderedCollection<R> newEmptyExtensibleResultCollection() {

         return emptyOrderedCollection();

     }

     private int indexBeforeWhichToInsert( E newElement ) {

         int lowerBound = 0;

         int upperBound = size();

         while ( lowerBound < upperBound ) {

             int medianIndex = ( upperBound + lowerBound ) / 2;

             int comparison = comparator().compare( at( medianIndex ), newElement );

             if ( comparison == 0 )

                 return medianIndex;

             else if ( comparison < 0 )

                 ++lowerBound;

             else

                 --upperBound;

         }

         return lowerBound;

     }

 }