Coverage Report - jaggregate.SortedCollection
 
Classes in this File Line Coverage Branch Coverage Complexity
SortedCollection
100%
92/92
100%
7/7
0
SortedCollection$1
100%
3/3
N/A
0
SortedCollection$2
100%
4/4
100%
1/1
0
 
 1  
 /*
 2  
  Copyright 2004-2008 Paul R. Holser, Jr.  All rights reserved.
 3  
  Licensed under the Academic Free License version 3.0
 4  
  */
 5  
 
 6  
 package jaggregate;
 7  
 
 8  
 import java.io.Serializable;
 9  
 import java.util.Comparator;
 10  
 
 11  
 import static jaggregate.Objects.*;
 12  
 import static jaggregate.OrderedCollection.*;
 13  
 import static jaggregate.internal.ArgumentChecks.*;
 14  
 import jaggregate.internal.ReadOnlySequences;
 15  
 import static jaggregate.internal.ReadOnlySequences.*;
 16  
 import jaggregate.internal.SequenceIndexOutOfBoundsException;
 17  
 
 18  
 /**
 19  
  * Represents a variable-sized collection of objects whose elements are ordered based on
 20  
  * a sort order.  The sort order is specified by a {@linkplain Comparator comparator}.
 21  
  * Elements may be added, removed, or inserted, and can be accessed using external
 22  
  * integer keys.
 23  
  *
 24  
  * @param <E> A restriction on the types of elements that may be included in the
 25  
  * collection
 26  
  *
 27  
  * @author <a href="mailto:pholser@alumni.rice.edu">Paul Holser</a>
 28  
  * @version $Id: SortedCollection.java,v 1.9 2008/10/03 19:01:23 pholser Exp $
 29  
  */
 30  44
 public class SortedCollection<E> extends AbstractExtensibleCollection<E>
 31  
     implements ContractibleSequence<E>, ReadOnlySequence<E>, Serializable {
 32  
 
 33  
     private static final long serialVersionUID = -1L;
 34  
 
 35  
     private final OrderedCollection<E> storage;
 36  
     private final Comparator<? super E> comparator;
 37  
 
 38  
     /**
 39  
      * Creates an empty sorted collection whose elements are sorted using the given
 40  
      * comparator.
 41  
      *
 42  
      * @param comparator the comparator with which to compare elements for sorting
 43  
      * @throws NullPointerException if {@code comparator} is {@code null}
 44  
      */
 45  834
     public SortedCollection( Comparator<? super E> comparator ) {
 46  834
         ensureNotNull( comparator, "comparator" );
 47  
 
 48  830
         this.comparator = comparator;
 49  830
         storage = emptyOrderedCollection();
 50  830
     }
 51  
 
 52  
     /**
 53  
      * Creates a sorted collection whose elements are sorted using the given
 54  
      * comparator, and containing the elements of the given collection.
 55  
      *
 56  
      * @param comparator the comparator with which to compare elements for sorting
 57  
      * @param newElements the elements to add to the new collection
 58  
      * @throws NullPointerException if either {@code comparator} or {@code newElements}
 59  
      * is {@code null}
 60  
      */
 61  
     public SortedCollection( Comparator<? super E> comparator,
 62  
         Collection<? extends E> newElements ) {
 63  
 
 64  52
         this( comparator );
 65  51
         addAll( newElements );
 66  49
     }
 67  
 
 68  
     /**
 69  
      * Creates a sorted collection whose elements are sorted using the given
 70  
      * comparator, and containing the elements of the given array.
 71  
      *
 72  
      * @param comparator the comparator with which to compare elements for sorting
 73  
      * @param newElements the elements to add to the new collection
 74  
      * @throws NullPointerException if either {@code comparator} or {@code newElements}
 75  
      * is {@code null}
 76  
      */
 77  
     public SortedCollection( Comparator<? super E> comparator, E... newElements ) {
 78  206
         this( comparator );
 79  205
         addAll( newElements );
 80  203
     }
 81  
 
 82  
     /**
 83  
      * Creates a sorted collection whose elements are sorted using the given
 84  
      * comparator, and containing the elements of the given iterable.
 85  
      *
 86  
      * @param comparator the comparator with which to compare elements for sorting
 87  
      * @param newElements the elements to add to the new collection
 88  
      * @throws NullPointerException if either {@code comparator} or {@code newElements}
 89  
      * is {@code null}
 90  
      */
 91  
     public SortedCollection( Comparator<? super E> comparator,
 92  
         Iterable<? extends E> newElements ) {
 93  
 
 94  5
         this( comparator );
 95  4
         addAll( newElements );
 96  2
     }
 97  
 
 98  
     /**
 99  
      * Creates an empty sorted collection whose elements are sorted using the given
 100  
      * comparator.
 101  
      *
 102  
      * @param <T> the type of elements allowed in the new sorted collection
 103  
      * @param comparator the comparator with which to compare elements for sorting
 104  
      * @return the new sorted collection
 105  
      * @throws NullPointerException if {@code comparator} is {@code null}
 106  
      */
 107  
     public static <T> SortedCollection<T> emptySortedCollection(
 108  
         Comparator<? super T> comparator ) {
 109  
 
 110  59
         return new SortedCollection<T>( comparator );
 111  
     }
 112  
 
 113  
     /**
 114  
      * Creates a sorted collection whose elements are sorted using the given
 115  
      * comparator, and containing the elements of the given collection.
 116  
      *
 117  
      * @param <T> the type of elements allowed in the new sorted collection
 118  
      * @param comparator the comparator with which to compare elements for sorting
 119  
      * @param newElements the elements to add to the new collection
 120  
      * @return the new sorted collection
 121  
      * @throws NullPointerException if either {@code comparator} or {@code newElements}
 122  
      * is {@code null}
 123  
      */
 124  
     public static <T> SortedCollection<T> sortedCollectionFrom(
 125  
         Comparator<? super T> comparator, Collection<? extends T> newElements ) {
 126  
 
 127  18
         return new SortedCollection<T>( comparator, newElements );
 128  
     }
 129  
 
 130  
     /**
 131  
      * Creates a sorted collection whose elements are sorted using the given
 132  
      * comparator, and containing the elements of the given array.
 133  
      *
 134  
      * @param <T> the type of elements allowed in the new sorted collection
 135  
      * @param comparator the comparator with which to compare elements for sorting
 136  
      * @param newElements the elements to add to the new collection
 137  
      * @return the new sorted collection
 138  
      * @throws NullPointerException if either {@code comparator} or {@code newElements}
 139  
      * is {@code null}
 140  
      */
 141  
     public static <T> SortedCollection<T> sortedCollectionWith(
 142  
         Comparator<? super T> comparator, T... newElements ) {
 143  
 
 144  1
         return new SortedCollection<T>( comparator, newElements );
 145  
     }
 146  
 
 147  
     /**
 148  
      * Creates a sorted collection whose elements are sorted using the given
 149  
      * comparator, and containing the elements of the given iterable.
 150  
      *
 151  
      * @param <T> the type of elements allowed in the new sorted collection
 152  
      * @param comparator the comparator with which to compare elements for sorting
 153  
      * @param newElements the elements to add to the new collection
 154  
      * @return the new sorted collection
 155  
      * @throws NullPointerException if either {@code comparator} or {@code newElements}
 156  
      * is {@code null}
 157  
      */
 158  
     public static <T> SortedCollection<T> sortedCollectionFrom(
 159  
         Comparator<? super T> comparator, Iterable<? extends T> newElements ) {
 160  
 
 161  3
         return new SortedCollection<T>( comparator, newElements );
 162  
     }
 163  
 
 164  
     /**
 165  
      * {@inheritDoc}
 166  
      * <p/>
 167  
      * Answers self.
 168  
      */
 169  
     @Override
 170  
     public SortedCollection<E> toSortedCollection() {
 171  1
         return this;
 172  
     }
 173  
 
 174  
     /**
 175  
      * {@inheritDoc}
 176  
      *
 177  
      * @return an ordered collection of the results
 178  
      */
 179  
     @Override
 180  
     public <R> OrderedCollection<R> collect(
 181  
         UnaryFunctor<? super E, ? extends R> transformer ) {
 182  
 
 183  6
         return (OrderedCollection<R>) super.collect( transformer );
 184  
     }
 185  
 
 186  
     /**
 187  
      * {@inheritDoc}
 188  
      */
 189  
     public void forEachDo( UnaryFunctor<? super E, ?> operation ) {
 190  283
         storage.forEachDo( operation );
 191  246
     }
 192  
 
 193  
     /**
 194  
      * {@inheritDoc}
 195  
      *
 196  
      * @return a sorted collection of the rejects
 197  
      */
 198  
     @Override
 199  
     public SortedCollection<E> reject( UnaryCondition<? super E> discriminator ) {
 200  10
         return (SortedCollection<E>) super.reject( discriminator );
 201  
     }
 202  
 
 203  
     /**
 204  
      * {@inheritDoc}
 205  
      *
 206  
      * @return a sorted collection of the matches
 207  
      */
 208  
     @Override
 209  
     public SortedCollection<E> select( UnaryCondition<? super E> discriminator ) {
 210  10
         return (SortedCollection<E>) super.select( discriminator );
 211  
     }
 212  
 
 213  
     /**
 214  
      * {@inheritDoc}
 215  
      */
 216  
     public int size() {
 217  3375
         return storage.size();
 218  
     }
 219  
 
 220  
     /**
 221  
      * {@inheritDoc}
 222  
      * <p/>
 223  
      * Since this collection sorts its elements, the result will also be sorted
 224  
      * as defined by this collection's comparator.
 225  
      *
 226  
      * @param otherSequence
 227  
      * @return a sorted collection that is the concatenation of this collection and
 228  
      * {@code otherSequence}
 229  
      */
 230  
     public SortedCollection<E> concat( ReadOnlySequence<? extends E> otherSequence ) {
 231  5
         SortedCollection<E> concatenation = sortedCollectionFrom( comparator(), this );
 232  5
         concatenation.addAll( otherSequence );
 233  
 
 234  5
         return concatenation;
 235  
     }
 236  
 
 237  
     /**
 238  
      * {@inheritDoc}
 239  
      */
 240  
     public E after( E target ) {
 241  16
         return storage.after( target );
 242  
     }
 243  
 
 244  
     /**
 245  
      * {@inheritDoc}
 246  
      */
 247  
     public E at( int index ) {
 248  5238
         return storage.at( index );
 249  
     }
 250  
 
 251  
     /**
 252  
      * {@inheritDoc}
 253  
      */
 254  
     public E before( E target ) {
 255  16
         return storage.before( target );
 256  
     }
 257  
 
 258  
     /**
 259  
      * {@inheritDoc}
 260  
      */
 261  
     public SortedCollection<E> copyRange( int start, int stop ) {
 262  52
         if ( start > stop )
 263  12
             return new SortedCollection<E>( comparator() );
 264  
 
 265  40
         if ( stop > start ) {
 266  24
             if ( start < 0 || start >= size() )
 267  3
                 throw new SequenceIndexOutOfBoundsException( STARTING_INDEX, start );
 268  
 
 269  21
             if ( stop < 0 || stop >= size() )
 270  3
                 throw new SequenceIndexOutOfBoundsException( ENDING_INDEX, stop );
 271  
         }
 272  
 
 273  34
         final SortedCollection<E> subsequence = new SortedCollection<E>( comparator() );
 274  34
         storage.forEachInRangeDo( start, stop, new UnaryFunctor<E, Void>() {
 275  98
             public Void evaluate( E argument ) {
 276  64
                 subsequence.add( argument );
 277  64
                 return null;
 278  
             }
 279  
         } );
 280  
 
 281  34
         return subsequence;
 282  
     }
 283  
 
 284  
     /**
 285  
      * {@inheritDoc}
 286  
      */
 287  
     public SortedCollection<E> copyWith( E newElement ) {
 288  8
         SortedCollection<E> copy = sortedCollectionFrom( comparator(), this );
 289  8
         copy.add( newElement );
 290  
 
 291  8
         return copy;
 292  
     }
 293  
 
 294  
     /**
 295  
      * {@inheritDoc}
 296  
      */
 297  
     public SortedCollection<E> copyWithout( final E oldElement ) {
 298  25
         final SortedCollection<E> copy = new SortedCollection<E>( comparator() );
 299  
 
 300  25
         storage.forEachDo( new UnaryFunctor<E, Void>() {
 301  97
             public Void evaluate( E argument ) {
 302  72
                 if ( !areEqual( oldElement, argument ) )
 303  54
                     copy.add( argument );
 304  72
                 return null;
 305  
             }
 306  
         } );
 307  
 
 308  25
         return copy;
 309  
     }
 310  
 
 311  
     /**
 312  
      * {@inheritDoc}
 313  
      */
 314  
     public int findFirst( UnaryCondition<? super E> discriminator ) {
 315  7
         return storage.findFirst( discriminator );
 316  
     }
 317  
 
 318  
     /**
 319  
      * {@inheritDoc}
 320  
      */
 321  
     public int findLast( UnaryCondition<? super E> discriminator ) {
 322  7
         return storage.findLast( discriminator );
 323  
     }
 324  
 
 325  
     /**
 326  
      * {@inheritDoc}
 327  
      */
 328  
     public void forEachInReverseDo( UnaryFunctor<? super E, ?> operation ) {
 329  3
         storage.forEachInReverseDo( operation );
 330  3
     }
 331  
 
 332  
     /**
 333  
      * {@inheritDoc}
 334  
      */
 335  
     public E first() {
 336  12
         return storage.first();
 337  
     }
 338  
 
 339  
     /**
 340  
      * {@inheritDoc}
 341  
      */
 342  
     public void forEachInRangeDo( int start, int stop,
 343  
         UnaryFunctor<? super E, ?> operation ) {
 344  
 
 345  49
         storage.forEachInRangeDo( start, stop, operation );
 346  43
     }
 347  
 
 348  
     /**
 349  
      * {@inheritDoc}
 350  
      */
 351  
     public void forEachInRangeDoWithIndex( int start, int stop,
 352  
         BinaryFunctor<? super Integer, ? super E, ?> operation ) {
 353  
 
 354  49
         storage.forEachInRangeDoWithIndex( start, stop, operation );
 355  43
     }
 356  
 
 357  
     /**
 358  
      * {@inheritDoc}
 359  
      */
 360  
     public int indexOf( E target ) {
 361  19
         return storage.indexOf( target );
 362  
     }
 363  
 
 364  
     /**
 365  
      * {@inheritDoc}
 366  
      */
 367  
     public int indexOf( ReadOnlySequence<? extends E> targetSequence, int start ) {
 368  22
         return storage.indexOf( targetSequence, start );
 369  
     }
 370  
 
 371  
     /**
 372  
      * {@inheritDoc}
 373  
      */
 374  
     public void doWithIndex( BinaryFunctor<? super Integer, ? super E, ?> operation ) {
 375  249
         storage.doWithIndex( operation );
 376  248
     }
 377  
 
 378  
     /**
 379  
      * {@inheritDoc}
 380  
      */
 381  
     public E last() {
 382  7
         return storage.last();
 383  
     }
 384  
 
 385  
     /**
 386  
      * {@inheritDoc}
 387  
      */
 388  
     public ReadOnlySequence<E> reverse() {
 389  7
         return storage.reverse();
 390  
     }
 391  
 
 392  
     /**
 393  
      * {@inheritDoc}
 394  
      */
 395  
     public <T> void doWithOthers( ReadOnlySequence<? extends T> otherSequence,
 396  
         BinaryFunctor<? super E, ? super T, ?> operation ) {
 397  
 
 398  7
         storage.doWithOthers( otherSequence, operation );
 399  7
     }
 400  
 
 401  
     /**
 402  
      * {@inheritDoc}
 403  
      */
 404  
     public void add( E newElement ) {
 405  2469
         storage.addBeforeIndex( newElement, indexBeforeWhichToInsert( newElement ) );
 406  2469
     }
 407  
 
 408  
     /**
 409  
      * {@inheritDoc}
 410  
      */
 411  
     public boolean remove( E oldElement ) {
 412  28
         return storage.remove( oldElement );
 413  
     }
 414  
 
 415  
     /**
 416  
      * {@inheritDoc}
 417  
      */
 418  
     public E removeAt( int index ) {
 419  10
         return storage.removeAt( index );
 420  
     }
 421  
 
 422  
     /**
 423  
      * {@inheritDoc}
 424  
      */
 425  
     public E removeFirst() {
 426  3
         return storage.removeFirst();
 427  
     }
 428  
 
 429  
     /**
 430  
      * {@inheritDoc}
 431  
      */
 432  
     public E removeLast() {
 433  3
         return storage.removeLast();
 434  
     }
 435  
 
 436  
     /**
 437  
      * {@inheritDoc}
 438  
      */
 439  
     @Override
 440  
     public boolean removeIf( UnaryCondition<? super E> discriminator ) {
 441  11
         return storage.removeIf( discriminator );
 442  
     }
 443  
 
 444  
     /**
 445  
      * {@inheritDoc}
 446  
      */
 447  
     @Override
 448  
     public boolean retainIf( UnaryCondition<? super E> discriminator ) {
 449  2
         return storage.retainIf( discriminator );
 450  
     }
 451  
 
 452  
     /**
 453  
      * Answers the comparator which is used to order this collection's elements.
 454  
      *
 455  
      * @return this collection's comparator
 456  
      */
 457  
     public Comparator<? super E> comparator() {
 458  3900
         return comparator;
 459  
     }
 460  
 
 461  
     /**
 462  
      * {@inheritDoc}
 463  
      */
 464  
     @Override
 465  
     public boolean equals( Object that ) {
 466  449
         return areSequencesEqual( this, that );
 467  
     }
 468  
 
 469  
     /**
 470  
      * {@inheritDoc}
 471  
      */
 472  
     @Override
 473  
     public int hashCode() {
 474  90
         return ReadOnlySequences.hashCode( this );
 475  
     }
 476  
 
 477  
     /**
 478  
      * {@inheritDoc}
 479  
      */
 480  
     @Override
 481  
     public String toString() {
 482  5
         return ReadOnlySequences.toString( this );
 483  
     }
 484  
 
 485  
     /**
 486  
      * {@inheritDoc}
 487  
      */
 488  
     @Override
 489  
     protected <T> Set<T> newEmptySet() {
 490  9
         return Set.emptySet();
 491  
     }
 492  
 
 493  
     /**
 494  
      * {@inheritDoc}
 495  
      */
 496  
     @Override
 497  
     protected SortedCollection<E> newEmptyExtensibleCollection() {
 498  20
         return new SortedCollection<E>( comparator() );
 499  
     }
 500  
 
 501  
     /**
 502  
      * {@inheritDoc}
 503  
      */
 504  
     @Override
 505  
     protected <R> OrderedCollection<R> newEmptyExtensibleResultCollection() {
 506  6
         return emptyOrderedCollection();
 507  
     }
 508  
 
 509  
     private int indexBeforeWhichToInsert( E newElement ) {
 510  2469
         int lowerBound = 0;
 511  2469
         int upperBound = size();
 512  
 
 513  6086
         while ( lowerBound < upperBound ) {
 514  3796
             int medianIndex = ( upperBound + lowerBound ) / 2;
 515  3796
             int comparison = comparator().compare( at( medianIndex ), newElement );
 516  
 
 517  3796
             if ( comparison == 0 )
 518  179
                 return medianIndex;
 519  3617
             else if ( comparison < 0 )
 520  2875
                 ++lowerBound;
 521  
             else
 522  742
                 --upperBound;
 523  3617
         }
 524  
 
 525  2290
         return lowerBound;
 526  
     }
 527  
 }