Coverage Report - com.sun.javafx.runtime.sequence.Sequences
 
Classes in this File Line Coverage Branch Coverage Complexity
Sequences
90%
223/248
87%
164/188
0
 
 1  
 /*
 2  
  * Copyright 2007 Sun Microsystems, Inc.  All Rights Reserved.
 3  
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 4  
  *
 5  
  * This code is free software; you can redistribute it and/or modify it
 6  
  * under the terms of the GNU General Public License version 2 only, as
 7  
  * published by the Free Software Foundation.  Sun designates this
 8  
  * particular file as subject to the "Classpath" exception as provided
 9  
  * by Sun in the LICENSE file that accompanied this code.
 10  
  *
 11  
  * This code is distributed in the hope that it will be useful, but WITHOUT
 12  
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 13  
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 14  
  * version 2 for more details (a copy is included in the LICENSE file that
 15  
  * accompanied this code).
 16  
  *
 17  
  * You should have received a copy of the GNU General Public License version
 18  
  * 2 along with this work; if not, write to the Free Software Foundation,
 19  
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 20  
  *
 21  
  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 22  
  * CA 95054 USA or visit www.sun.com if you need additional information or
 23  
  * have any questions.
 24  
  */
 25  
 
 26  
 package com.sun.javafx.runtime.sequence;
 27  
 
 28  
 import java.lang.reflect.Array;
 29  
 import java.util.*;
 30  
 
 31  
 import com.sun.javafx.runtime.Util;
 32  
 
 33  
 /**
 34  
  * Sequences -- static helper methods for constructing derived sequences. Implements heuristics for reducing time and
 35  
  * space overhead, such as flattening complicated sequence trees where appropriate and ignoring null transformations
 36  
  * (such as appending an empty sequence). These methods are generally preferable to the constructors for
 37  
  * CompositeSequence, FilterSequence, SubSequence, etc, because they implement heuristics for sensible time-space
 38  
  * tradeoffs.
 39  
  *
 40  
  * @author Brian Goetz
 41  
  */
 42  
 public final class Sequences {
 43  
 
 44  253
     public static final Integer INTEGER_ZERO = 0;
 45  253
     public static final Double DOUBLE_ZERO = 0.0;
 46  253
     public static final Boolean BOOLEAN_ZERO = false;
 47  
     public static final int FLATTENING_THRESHOLD = 16;
 48  
 
 49  
     // Inhibit instantiation
 50  0
     private Sequences() { }
 51  
 
 52  
     /** Factory for simple sequence generation */
 53  
     public static<T> Sequence<T> make(Class<T> clazz, T... values) {
 54  1579
         if (values == null || values.length == 0)
 55  294
             return emptySequence(clazz);
 56  
         else
 57  1285
             return new ArraySequence<T>(clazz, values);
 58  
     }
 59  
 
 60  
     /** Factory for simple sequence generation */
 61  
     public static<T> Sequence<T> make(Class<T> clazz, T[] values, int size) {
 62  4630
         if (values == null || size <= 0)
 63  307
             return emptySequence(clazz);
 64  
         else
 65  4323
             return new ArraySequence<T>(clazz, values, size);
 66  
     }
 67  
 
 68  
     /** Factory for simple sequence generation */
 69  
     public static<T> Sequence<T> make(Class<T> clazz, List<? extends T> values) {
 70  0
         if (values == null || values.size() == 0)
 71  0
             return emptySequence(clazz);
 72  
         else
 73  0
             return new ArraySequence<T>(clazz, values);
 74  
     }
 75  
 
 76  
     /** Concatenate two sequences into a new sequence.  */
 77  
     public static<T> Sequence<T> concatenate(Class<T> clazz, Sequence<? extends T> first, Sequence<? extends T> second) {
 78  3280
         int size1 = Sequences.size(first);
 79  3280
         int size2 = Sequences.size(second);
 80  
 
 81  
         // OPT: for small sequences, just copy the elements
 82  3280
         if (size1 == 0)
 83  3
             return Sequences.upcast(clazz, second);
 84  3277
         else if (size2 == 0)
 85  689
             return Sequences.upcast(clazz, first);
 86  2588
         else if (size1 + size2 <= FLATTENING_THRESHOLD)
 87  689
             return new ArraySequence<T>(clazz, first, second);
 88  
         else
 89  1899
             return new CompositeSequence<T>(clazz, first, second);
 90  
     }
 91  
 
 92  
     /** Concatenate zero or more sequences into a new sequence.  */
 93  
     public static<T> Sequence<T> concatenate(Class<T> clazz, Sequence<? extends T>... seqs) {
 94  2080
         int size = 0;
 95  8624
         for (Sequence i : seqs)
 96  6544
             size += Sequences.size(i);
 97  
         // OPT: for small sequences, just copy the elements
 98  2080
         if (size <= FLATTENING_THRESHOLD)
 99  1690
             return new ArraySequence<T>(clazz, seqs);
 100  
         else
 101  390
             return new CompositeSequence<T>(clazz, seqs);
 102  
     }
 103  
 
 104  
     /** Create an Integer range sequence ranging from lower to upper inclusive. */
 105  
     public static Sequence<Integer> range(int lower, int upper) {
 106  2471
         return new IntRangeSequence(lower, upper);
 107  
     }
 108  
 
 109  
     /** Create an Integer range sequence ranging from lower to upper inclusive, incrementing by the specified step. */
 110  
     public static Sequence<Integer> range(int lower, int upper, int step) {
 111  118
         return new IntRangeSequence(lower, upper, step);
 112  
     }
 113  
 
 114  
     /** Create an Integer range sequence ranging from lower to upper exclusive. */
 115  
     public static Sequence<Integer> rangeExclusive(int lower, int upper) {
 116  116
         return new IntRangeSequence(lower, upper, true);
 117  
     }
 118  
 
 119  
     /** Create an Integer range sequence ranging from lower to upper exnclusive, incrementing by the specified step. */
 120  
     public static Sequence<Integer> rangeExclusive(int lower, int upper, int step) {
 121  41
         return new IntRangeSequence(lower, upper, step, true);
 122  
     }
 123  
 
 124  
     /** Create a double range sequence ranging from lower to upper inclusive, incrementing by 1.0 */
 125  
     public static Sequence<Double> range(double lower, double upper) {
 126  1003
         return new NumberRangeSequence(lower, upper, 1.0);
 127  
     }
 128  
 
 129  
     /** Create a double range sequence ranging from lower to upper inclusive, incrementing by the specified step. */
 130  
     public static Sequence<Double> range(double lower, double upper, double step) {
 131  29
         return new NumberRangeSequence(lower, upper, step);
 132  
     }
 133  
 
 134  
     /** Create a double range sequence ranging from lower to upper exnclusive */
 135  
      public static Sequence<Double> rangeExclusive(double lower, double upper) {
 136  0
         return new NumberRangeSequence(lower, upper, 1.0, true);
 137  
     }
 138  
     /** Create a double range sequence ranging from lower to upper exnclusive, incrementing by the specified step. */
 139  
     public static Sequence<Double> rangeExclusive(double lower, double upper, double step) {
 140  23
         return new NumberRangeSequence(lower, upper, step, true);
 141  
     }
 142  
 
 143  
     /** Create a filtered sequence.  A filtered sequence contains some, but not necessarily all, of the elements
 144  
      * of another sequence, in the same order as that sequence.  If bit n is set in the BitSet, then the element
 145  
      * at position n of the original sequence appears in the filtered sequence.  */
 146  
     public static<T> Sequence<T> filter(Sequence<T> seq, BitSet bits) {
 147  
         // OPT: for small sequences, just copy the elements
 148  5462
         if (bits.cardinality() == seq.size() && bits.nextClearBit(0) == seq.size())
 149  3899
             return seq;
 150  1563
         else if (bits.cardinality() == 0)
 151  546
             return EmptySequence.get(seq.getElementType());
 152  
         else
 153  1017
             return new FilterSequence<T>(seq, bits);
 154  
     }
 155  
 
 156  
     /** Extract a subsequence from the specified sequence, starting as the specified start position, and up to but
 157  
      * not including the specified end position.  If the start position is negative it is assumed to be zero; if the
 158  
      * end position is greater than seq.size() it is assumed to be seq.size().  */
 159  
     public static<T> Sequence<T> subsequence(Sequence<T> seq, int start, int end) {
 160  
         // OPT: for small sequences, just copy the elements
 161  4751
         if (start >= end)
 162  3120
             return EmptySequence.get(seq.getElementType());
 163  1631
         else if (start <= 0 && end >= seq.size())
 164  80
             return seq;
 165  
         else
 166  1551
             return new SubSequence<T>(seq, start, end);
 167  
     }
 168  
 
 169  
     /** Create a sequence containing a single element, the specified value */
 170  
     public static<T> Sequence<T> singleton(Class<T> clazz, T t) {
 171  5123
         if (t == null)
 172  34
             return emptySequence(clazz);
 173  
         else
 174  5089
             return new SingletonSequence<T>(clazz, t);
 175  
     }
 176  
 
 177  
     /** Create an empty sequence */
 178  
     public static<T> Sequence<T> emptySequence(Class<T> clazz) {
 179  5573
         return EmptySequence.get(clazz);
 180  
     }
 181  
 
 182  
     /** Reverse an existing sequence */
 183  
     public static<T> Sequence<T> reverse(Sequence<T> sequence) {
 184  927
         return new ReverseSequence<T>(sequence);
 185  
     }
 186  
 
 187  
     /** Create a new sequence that is the result of applying a mapping function to each element */
 188  
     public static<T,U> Sequence<U> map(Class<U> clazz, Sequence<T> sequence, SequenceMapper<T, U> mapper) {
 189  
         // OPT: for small sequences, do the mapping eagerly
 190  1
         return new MapSequence<T,U>(clazz, sequence, mapper);
 191  
     }
 192  
 
 193  
     /** Upcast a sequence of T to a sequence of superclass-of-T */
 194  
     @SuppressWarnings("unchecked")
 195  
     public static<T> Sequence<T> upcast(Class<T> clazz, Sequence<? extends T> sequence) {
 196  2437
         if (clazz == sequence.getElementType())
 197  1991
             return (Sequence<T>) sequence;
 198  446
         else if (!clazz.isAssignableFrom(sequence.getElementType()))
 199  1
             throw new ClassCastException("Cannot upcast Sequence<" + sequence.getElementType().getName()
 200  
                     + "> to Sequence<" + clazz.getName() + ">");
 201  
         else
 202  445
             return new UpcastSequence<T>(clazz, sequence);
 203  
     }
 204  
 
 205  
     /** How large is this sequence?  Can be applied to any object.  */
 206  
     public static int size(Object seq) {
 207  4
         if (seq instanceof Sequence)
 208  0
             return ((Sequence) seq).size();
 209  
         else
 210  4
             return seq == null ? 0 : 1;
 211  
     }
 212  
 
 213  
     /** How large is this sequence?  */
 214  
     public static int size(Sequence seq) {
 215  95384
         return (seq == null) ? 0 : seq.size();
 216  
     }
 217  
 
 218  
     /** Convert a Collection<T> to a Sequence<T> */
 219  
     public static<T> Sequence<T> fromCollection(Class<T> clazz, Collection<T> values) {
 220  0
         if (values == null)
 221  0
             return Sequences.emptySequence(clazz);
 222  0
         return new ArraySequence<T>(clazz, values.toArray(Util.<T>newArray(clazz, values.size())));
 223  
     }
 224  
 
 225  
     /** Convert a T[] to a Sequence<T> */
 226  
     public static<T> Sequence<T> fromArray(Class<T> clazz, T[] values) {
 227  17
         if (values == null)
 228  1
             return Sequences.emptySequence(clazz);
 229  16
         return new ArraySequence<T>(clazz, values);
 230  
     }
 231  
 
 232  
     /** Convert a long[] to a Sequence<Long> */
 233  
     public static Sequence<Long> fromArray(long[] values) {
 234  2
         if (values == null)
 235  0
             return Sequences.emptySequence(Long.class);
 236  2
         Long[] boxed = new Long[values.length];
 237  8
         for (int i=0; i<values.length; i++)
 238  6
             boxed[i] = Long.valueOf(values[i]);
 239  2
         return new ArraySequence<Long>(Long.class, boxed, values.length);
 240  
     }
 241  
 
 242  
     /** Convert an int[] to a Sequence<Integer> */
 243  
     public static Sequence<Integer> fromArray(int[] values) {
 244  1
         if (values == null)
 245  0
             return Sequences.emptySequence(Integer.class);
 246  1
         Integer[] boxed = new Integer[values.length];
 247  4
         for (int i=0; i<values.length; i++)
 248  3
             boxed[i] = Integer.valueOf(values[i]);
 249  1
         return new ArraySequence<Integer>(Integer.class, boxed, values.length);
 250  
     }
 251  
 
 252  
     /** Convert a short[] to a Sequence<Integer> */
 253  
     public static Sequence<Integer> fromArray(short[] values) {
 254  1
         if (values == null)
 255  0
             return Sequences.emptySequence(Integer.class);
 256  1
         Integer[] boxed = new Integer[values.length];
 257  4
         for (int i=0; i<values.length; i++)
 258  3
             boxed[i] = Integer.valueOf(values[i]);
 259  1
         return new ArraySequence<Integer>(Integer.class, boxed, values.length);
 260  
     }
 261  
 
 262  
     /** Convert a char[] to a Sequence<Integer> */
 263  
     public static Sequence<Integer> fromArray(char[] values) {
 264  1
         if (values == null)
 265  0
             return Sequences.emptySequence(Integer.class);
 266  1
         Integer[] boxed = new Integer[values.length];
 267  4
         for (int i=0; i<values.length; i++)
 268  3
             boxed[i] = Integer.valueOf(values[i]);
 269  1
         return new ArraySequence<Integer>(Integer.class, boxed, values.length);
 270  
     }
 271  
 
 272  
     /** Convert a byte[] to a Sequence<Integer> */
 273  
     public static Sequence<Integer> fromArray(byte[] values) {
 274  2
         if (values == null)
 275  0
             return Sequences.emptySequence(Integer.class);
 276  2
         Integer[] boxed = new Integer[values.length];
 277  8
         for (int i=0; i<values.length; i++)
 278  6
             boxed[i] = Integer.valueOf(values[i]);
 279  2
         return new ArraySequence<Integer>(Integer.class, boxed, values.length);
 280  
     }
 281  
 
 282  
     /** Convert a double[] to a Sequence<Double> */
 283  
     public static Sequence<Double> fromArray(double[] values) {
 284  1
         if (values == null)
 285  0
             return Sequences.emptySequence(Double.class);
 286  1
         Double[] boxed = new Double[values.length];
 287  4
         for (int i=0; i<values.length; i++)
 288  3
             boxed[i] = Double.valueOf(values[i]);
 289  1
         return new ArraySequence<Double>(Double.class, boxed, values.length);
 290  
     }
 291  
 
 292  
     /** Convert a float[] to a Sequence<Double> */
 293  
     public static Sequence<Double> fromArray(float[] values) {
 294  1
         if (values == null)
 295  0
             return Sequences.emptySequence(Double.class);
 296  1
         Double[] boxed = new Double[values.length];
 297  4
         for (int i=0; i<values.length; i++)
 298  3
             boxed[i] = Double.valueOf(values[i]);
 299  1
         return new ArraySequence<Double>(Double.class, boxed, values.length);
 300  
     }
 301  
 
 302  
     /** Convert a boolean[] to a Sequence<Boolean> */
 303  
     public static Sequence<Boolean> fromArray(boolean[] values) {
 304  2
         if (values == null)
 305  0
             return Sequences.emptySequence(Boolean.class);
 306  2
         Boolean[] boxed = new Boolean[values.length];
 307  7
         for (int i=0; i<values.length; i++)
 308  5
             boxed[i] = Boolean.valueOf(values[i]);
 309  2
         return new ArraySequence<Boolean>(Boolean.class, boxed, values.length);
 310  
     }
 311  
 
 312  
     /** Convert a Sequence<T> to an array */
 313  
     public static<T> T[] toArray(Sequence<T> seq) {
 314  0
         T[] unboxed = Util.<T>newObjectArray(seq.size());
 315  0
         for (int i=0; i<unboxed.length; i++)
 316  0
             unboxed[i] = seq.get(i);
 317  0
         return unboxed;
 318  
     }
 319  
 
 320  
     /** Convert a Sequence<Long> to an array */
 321  
     public static long[] toArray(Sequence<Long> seq) {
 322  1
         long[] unboxed = new long[seq.size()];
 323  4
         for (int i=0; i<unboxed.length; i++)
 324  3
             unboxed[i] = seq.get(i);
 325  1
         return unboxed;
 326  
     }
 327  
 
 328  
     /** Convert a Sequence<Integer> to an array */
 329  
     public static int[] toArray(Sequence<Integer> seq) {
 330  1
         int[] unboxed = new int[seq.size()];
 331  4
         for (int i=0; i<unboxed.length; i++)
 332  3
             unboxed[i] = seq.get(i);
 333  1
         return unboxed;
 334  
     }
 335  
 
 336  
     /** Convert a Sequence<Double> to a double array */
 337  
     public static double[] toArray(Sequence<? extends java.lang.Number> seq) {
 338  1
         double[] unboxed = new double[seq.size()];
 339  4
         for (int i=0; i<unboxed.length; i++)
 340  3
             unboxed[i] = seq.get(i).doubleValue();
 341  1
         return unboxed;
 342  
     }
 343  
 
 344  
     /** Convert a Sequence<Double> to a float array */
 345  
     public static float[] toFloatArray(Sequence<? extends java.lang.Number> seq) {
 346  0
         float[] unboxed = new float[seq.size()];
 347  0
         for (int i=0; i<unboxed.length; i++)
 348  0
           unboxed[i] = seq.get(i).floatValue();
 349  0
         return unboxed;
 350  
     }
 351  
 
 352  
     /** Convert a Sequence<Boolean> to an array */
 353  
     public static boolean[] toArray(Sequence<Boolean> seq) {
 354  1
         boolean[] unboxed = new boolean[seq.size()];
 355  3
         for (int i=0; i<unboxed.length; i++)
 356  2
             unboxed[i] = seq.get(i);
 357  1
         return unboxed;
 358  
     }
 359  
 
 360  
     public static<T> boolean isEqual(Sequence<?> one, Sequence<?> other) {
 361  23451
         int oneSize = size(one);
 362  23451
         int otherSize = size(other);
 363  23451
         if (oneSize == 0)
 364  10666
             return (otherSize == 0);
 365  12785
         else if (oneSize != otherSize)
 366  4843
             return false;
 367  
         else {
 368  7942
             Iterator<?> it1 = one.iterator();
 369  7942
             Iterator<?> it2 = other.iterator();
 370  328723
             while (it1.hasNext()) {
 371  324718
                 if (! it1.next().equals(it2.next()))
 372  3937
                     return false;
 373  
             }
 374  4005
             return true;
 375  
         }
 376  
     }
 377  
 
 378  
     public static<T> boolean isEqualByContentIdentity(Sequence<? extends T> one, Sequence<? extends T> other) {
 379  14
         int oneSize = size(one);
 380  14
         if (oneSize == 0)
 381  6
             return size(other) == 0;
 382  8
         else if (oneSize != size(other))
 383  4
             return false;
 384  
         else {
 385  4
             Iterator<? extends T> it1 = one.iterator();
 386  4
             Iterator<? extends T> it2 = other.iterator();
 387  12
             while (it1.hasNext()) {
 388  10
                 if (it1.next() != it2.next())
 389  2
                     return false;
 390  
             }
 391  2
             return true;
 392  
         }
 393  
     }
 394  
 
 395  
     public static<T> Sequence<? extends T> forceNonNull(Class<T> clazz, Sequence<? extends T> seq) {
 396  3970
         return seq == null ? emptySequence(clazz) : seq;
 397  
     }
 398  
 
 399  
     /**
 400  
      * Searches the specified sequence for the specified object using the 
 401  
      * binary search algorithm. The sequence must be sorted into ascending 
 402  
      * order according to the natural ordering of its elements (as by 
 403  
      * the sort(Sequence<T>) method) prior to making this call. 
 404  
      * 
 405  
      * If it is not sorted, the results are undefined. If the array contains 
 406  
      * multiple elements equal to the specified object, there is no guarantee 
 407  
      * which one will be found.
 408  
      * 
 409  
      * @param seq The sequence to be searched.
 410  
      * @param key The value to be searched for.
 411  
      * @return Index of the search key, if it is contained in the array; 
 412  
      *         otherwise, (-(insertion point) - 1). The insertion point is 
 413  
      *         defined as the point at which the key would be inserted into the 
 414  
      *         array: the index of the first element greater than the key, or
 415  
      *         a.length if all elements in the array are less than the specified
 416  
      *         key. Note that this guarantees that the return value will be >= 0
 417  
      *         if and only if the key is found.
 418  
      */
 419  
     @SuppressWarnings("unchecked")
 420  
     public static <T extends Comparable> int binarySearch (Sequence<? extends T> seq, T key) {
 421  12
         if (seq.isEmpty())
 422  3
             return -1;
 423  8
         T[] array = (T[])Array.newInstance(seq.getElementType(), seq.size());
 424  8
         seq.toArray(array, 0);
 425  8
         return Arrays.binarySearch(array, key);
 426  
     }
 427  
     
 428  
     /**
 429  
      * Searches the specified array for the specified object using the 
 430  
      * binary search algorithm. The array must be sorted into ascending 
 431  
      * order according to the specified comparator (as by the 
 432  
      * sort(Sequence<T>, Comparator<? super T>)  method) prior to making 
 433  
      * this call. 
 434  
      * 
 435  
      * If it is not sorted, the results are undefined. If the array contains 
 436  
      * multiple elements equal to the specified object, there is no guarantee 
 437  
      * which one will be found.
 438  
      * 
 439  
      * @param seq The sequence to be searched.
 440  
      * @param key The value to be searched for.
 441  
      * @param c The comparator by which the array is ordered. A null value 
 442  
      *          indicates that the elements' natural ordering should be used.
 443  
      * @return Index of the search key, if it is contained in the array; 
 444  
      *         otherwise, (-(insertion point) - 1). The insertion point is 
 445  
      *         defined as the point at which the key would be inserted into the 
 446  
      *         array: the index of the first element greater than the key, or
 447  
      *         a.length if all elements in the array are less than the specified
 448  
      *         key. Note that this guarantees that the return value will be >= 0
 449  
      *         if and only if the key is found.
 450  
      */
 451  
     @SuppressWarnings("unchecked")
 452  
     public static <T> int binarySearch(Sequence<? extends T> seq,  T key,  Comparator<? super T> c) {
 453  16
         if (seq.isEmpty())
 454  3
             return -1;
 455  12
         T[] array = (T[])Array.newInstance(seq.getElementType(), seq.size());
 456  12
         seq.toArray(array, 0);
 457  12
         return Arrays.binarySearch(array, (T)key, c);
 458  
     }
 459  
     
 460  
     /**
 461  
      * Searches the specified sequence for the specified object.
 462  
      * 
 463  
      * If the sequence contains multiple elements equal to the specified object, 
 464  
      * the first occurence in the sequence will be returned.
 465  
      * 
 466  
      * The method nextIndexOf can be used in consecutive calls to iterate
 467  
      * through all occurences of a specified object.
 468  
      * 
 469  
      * @param seq The sequence to be searched.
 470  
      * @param key The value to be searched for.
 471  
      * @return Index of the search key, if it is contained in the array; 
 472  
      *         otherwise -1.
 473  
      */
 474  
     public static<T> int indexByIdentity(Sequence<? extends T> seq, T key) {
 475  22
         return nextIndexByIdentity(seq, key, 0);
 476  
     }
 477  
     
 478  
     /**
 479  
      * Searches the specified sequence for an object with the same value. The
 480  
      * objects are compared using the method equals(). If the sequence is sorted, 
 481  
      * binarySearch should be used instead.
 482  
      * 
 483  
      * If the sequence contains multiple elements equal to the specified object, 
 484  
      * the first occurence in the sequence will be returned.
 485  
      * 
 486  
      * The method nextIndexOf can be used in consecutive calls to iterate
 487  
      * through all occurences of a specified object.
 488  
      * 
 489  
      * @param seq The sequence to be searched.
 490  
      * @param key The value to be searched for.
 491  
      * @return Index of the search key, if it is contained in the array; 
 492  
      *         otherwise -1.
 493  
      */
 494  
     public static<T> int indexOf(Sequence<? extends T> seq, T key) {
 495  20
         return nextIndexOf(seq, key, 0);
 496  
     }
 497  
     
 498  
     /**
 499  
      * Returns the element with the maximum value in the specified sequence, 
 500  
      * according to the natural ordering  of its elements. All elements in the 
 501  
      * sequence must implement the Comparable interface. Furthermore, all 
 502  
      * elements in the sequence must be mutually comparable (that is, 
 503  
      * e1.compareTo(e2) must not throw a ClassCastException  for any elements 
 504  
      * e1 and e2 in the sequence).
 505  
      * 
 506  
      * If the sequence contains multiple elements with the maximum value, 
 507  
      * there is no guarantee which one will be found.
 508  
      * 
 509  
      * @param seq The sequence to be searched.
 510  
      * @return The element with the maximum value.
 511  
      */
 512  
     public static <T extends Comparable> T max (Sequence<T> seq) {
 513  14
         if (seq == null || seq.isEmpty())
 514  4
             throw new IllegalArgumentException("empty sequence passed to Sequences.max");
 515  
         
 516  10
         Iterator<T> it = seq.iterator();
 517  10
         T result = it.next();
 518  
         T current;
 519  26
         while (it.hasNext()) {
 520  16
             if ((current = it.next()).compareTo(result) > 0)
 521  6
                 result = current;
 522  
         }
 523  10
         return result;
 524  
     }
 525  
     
 526  
     /**
 527  
      * Returns the element with the maximum value in the specified sequence, 
 528  
      * according to the specified comparator. All elements in the sequence must 
 529  
      * be mutually comparable by the specified comparator (that is, 
 530  
      * c.compare(e1, e2) must not throw a ClassCastException  for any elements
 531  
      * e1 and e2 in the sequence).
 532  
      * 
 533  
      * If the sequence contains multiple elements with the maximum value, 
 534  
      * there is no guarantee which one will be found.
 535  
      * 
 536  
      * @param seq The sequence to be searched.
 537  
      * @param c The comparator to determine the order of the sequence. 
 538  
      *          A null value indicates that the elements' natural ordering 
 539  
      *          should be used.
 540  
      * @return The element with the maximum value.
 541  
      */
 542  
     public static <T> T max (Sequence<T> seq, Comparator<? super T> c) {
 543  14
         if (seq == null || seq.isEmpty())
 544  4
             throw new IllegalArgumentException("empty sequence passed to Sequences.max");
 545  10
         if (c == null)
 546  2
             return (T)max((Sequence<Comparable>)seq);
 547  
         
 548  8
         Iterator<T> it = seq.iterator();
 549  8
         T result = it.next();
 550  
         T current;
 551  20
         while (it.hasNext()) {
 552  12
             if (c.compare(current = it.next(), result) > 0)
 553  6
                 result = current;
 554  
         }
 555  8
         return result;
 556  
     }
 557  
     
 558  
     /**
 559  
      * Returns the element with the minimum value in the specified sequence, 
 560  
      * according to the natural ordering  of its elements. All elements in the 
 561  
      * sequence must implement the Comparable interface. Furthermore, all 
 562  
      * elements in the sequence must be mutually comparable (that is, 
 563  
      * e1.compareTo(e2) must not throw a ClassCastException  for any elements 
 564  
      * e1 and e2 in the sequence).
 565  
      * 
 566  
      * If the sequence contains multiple elements with the minimum value, 
 567  
      * there is no guarantee which one will be found.
 568  
      * 
 569  
      * @param seq The sequence to be searched.
 570  
      * @return The element with the maximum value.
 571  
      */
 572  
     public static <T extends Comparable> T min (Sequence<T> seq) {
 573  14
         if (seq == null || seq.isEmpty())
 574  4
             throw new IllegalArgumentException("empty sequence passed to Sequences.min");
 575  
         
 576  10
         Iterator<T> it = seq.iterator();
 577  10
         T result = it.next();
 578  
         T current;
 579  26
         while (it.hasNext()) {
 580  16
             if ((current = it.next()).compareTo(result) < 0)
 581  6
                 result = current;
 582  
         }
 583  10
         return result;
 584  
     }
 585  
     
 586  
     /**
 587  
      * Returns the element with the minimum value in the specified sequence, 
 588  
      * according to the specified comparator. All elements in the sequence must 
 589  
      * be mutually comparable by the specified comparator (that is, 
 590  
      * c.compare(e1, e2) must not throw a ClassCastException  for any elements
 591  
      * e1 and e2 in the sequence).
 592  
      * 
 593  
      * If the sequence contains multiple elements with the minimum value, 
 594  
      * there is no guarantee which one will be found.
 595  
      * 
 596  
      * @param seq The sequence to be searched.
 597  
      * @param c The comparator to determine the order of the sequence. 
 598  
      *          A null value indicates that the elements' natural ordering 
 599  
      *          should be used.
 600  
      * @return The element with the minimum value.
 601  
      */
 602  
     public static <T> T min (Sequence<T> seq, Comparator<? super T> c) {
 603  14
         if (seq == null || seq.isEmpty())
 604  4
             throw new IllegalArgumentException("empty sequence passed to Sequences.min");
 605  10
         if (c == null)
 606  2
             return (T)min((Sequence<Comparable>)seq);
 607  
         
 608  8
         Iterator<T> it = seq.iterator();
 609  8
         T result = it.next();
 610  
         T current;
 611  20
         while (it.hasNext()) {
 612  12
             if (c.compare(current = it.next(), result) < 0)
 613  3
                 result = current;
 614  
         }
 615  8
         return result;
 616  
     }
 617  
             
 618  
     /**
 619  
      * Searches the specified sequence for an object with the same value,
 620  
      * starting the search at the specified position. The objects are compared 
 621  
      * using the method equals().
 622  
      * 
 623  
      * If the sequence contains multiple elements equal to the specified object, 
 624  
      * the first occurence in the subsequence will be returned.
 625  
      * 
 626  
      * @param seq The sequence to be searched.
 627  
      * @param key The value to be searched for.
 628  
      * @param pos The position in the sequence to start the search. If pos is
 629  
      *            negative or 0 the whole sequence will be searched.
 630  
      * @return Index of the search key, if it is contained in the array; 
 631  
      *         otherwise -1.
 632  
      */
 633  
     public static<T> int nextIndexByIdentity(Sequence<? extends T> seq, T key, int pos) {
 634  36
         if (seq == null)
 635  1
             return -1;
 636  35
         if (key == null)
 637  2
             throw new NullPointerException();
 638  
         
 639  33
         Iterator<? extends T> it = seq.iterator();
 640  
         int i;
 641  61
         for (i=0; i<pos && it.hasNext(); ++i)
 642  28
             it.next();
 643  101
         for (; it.hasNext(); ++i)
 644  48
             if (it.next() ==  key)
 645  14
                 return i;
 646  19
         return -1;
 647  
     }
 648  
     
 649  
     /**
 650  
      * Searches the specified sequence for the specified object, starting the
 651  
      * search at the specified position. 
 652  
      * 
 653  
      * If the sequence contains multiple elements equal to the specified object, 
 654  
      * the first occurence in the subsequence will be returned.
 655  
      * 
 656  
      * @param seq The sequence to be searched.
 657  
      * @param key The value to be searched for.
 658  
      * @param pos The position in the sequence to start the search. If pos is
 659  
      *            negative or 0 the whole sequence will be searched.
 660  
      * @return Index of the search key, if it is contained in the array; 
 661  
      *         otherwise -1.
 662  
      */
 663  
     public static<T> int nextIndexOf(Sequence<? extends T> seq, T key, int pos) {
 664  32
         if (seq == null)
 665  1
             return -1;
 666  31
         if (key == null)
 667  2
             throw new NullPointerException();
 668  
         
 669  29
         Iterator<? extends T> it = seq.iterator();
 670  
         int i;
 671  55
         for (i=0; i<pos && it.hasNext(); ++i)
 672  26
             it.next();
 673  69
         for (; it.hasNext(); ++i)
 674  34
             if (it.next().equals(key))
 675  14
                 return i;
 676  15
         return -1;
 677  
     }
 678  
     
 679  
     /**
 680  
      * Sorts the specified sequence of objects into ascending order, according 
 681  
      * to the natural ordering  of its elements. All elements in the sequence
 682  
      * must implement the Comparable interface. Furthermore, all elements in 
 683  
      * the sequence must be mutually comparable (that is, e1.compareTo(e2) 
 684  
      * must not throw a ClassCastException  for any elements e1 and e2 in the 
 685  
      * sequence).
 686  
      * 
 687  
      * This method is immutative, the result is returned in a new sequence,
 688  
      * while the original sequence is left untouched.
 689  
      * 
 690  
      * This sort is guaranteed to be stable: equal elements will not be 
 691  
      * reordered as a result of the sort.
 692  
      * 
 693  
      * The sorting algorithm is a modified mergesort (in which the merge is 
 694  
      * omitted if the highest element in the low sublist is less than the 
 695  
      * lowest element in the high sublist). This algorithm offers guaranteed 
 696  
      * n*log(n) performance. 
 697  
      * 
 698  
      * @param seq The sequence to be sorted.
 699  
      * @return The sorted sequence.
 700  
      */
 701  
     @SuppressWarnings("unchecked")
 702  
     public static <T extends Comparable> Sequence<T> sort (Sequence<T> seq) {
 703  16
         if (seq.isEmpty())
 704  4
             return Sequences.emptySequence(seq.getElementType());
 705  10
         T[] array = (T[])Array.newInstance(seq.getElementType(), seq.size());
 706  10
         seq.toArray(array, 0);
 707  10
         Arrays.sort(array);
 708  10
         return Sequences.make(seq.getElementType(), array);
 709  
     }
 710  
     
 711  
     /**
 712  
      * Sorts the specified sequence of objects according to the order induced 
 713  
      * by the specified comparator. All elements in the sequence must be 
 714  
      * mutually comparable by the specified comparator (that is, 
 715  
      * c.compare(e1, e2) must not throw a ClassCastException  for any elements
 716  
      * e1 and e2 in the sequence).
 717  
      * 
 718  
      * This method is immutative, the result is returned in a new sequence,
 719  
      * while the original sequence is left untouched.
 720  
      *
 721  
      * This sort is guaranteed to be stable: equal elements will not be 
 722  
      * reordered as a result of the sort.
 723  
      * 
 724  
      * The sorting algorithm is a modified mergesort (in which the merge is 
 725  
      * omitted if the highest element in the low sublist is less than the 
 726  
      * lowest element in the high sublist). This algorithm offers guaranteed 
 727  
      * n*log(n) performance. 
 728  
      * 
 729  
      * @param seq The sequence to be sorted.
 730  
      * @param c The comparator to determine the order of the sequence. 
 731  
      *          A null value indicates that the elements' natural ordering 
 732  
      *          should be used.
 733  
      * @return The sorted sequence.
 734  
      */
 735  
     @SuppressWarnings("unchecked")
 736  
     public static <T> Sequence<T> sort (Sequence<T> seq, Comparator<? super T> c) {
 737  12
         if (seq.isEmpty())
 738  3
             return Sequences.emptySequence(seq.getElementType());
 739  8
         T[] array = (T[])Array.newInstance(seq.getElementType(), seq.size());
 740  8
         seq.toArray(array, 0);
 741  8
         Arrays.sort(array, c);
 742  6
         return Sequences.make(seq.getElementType(), array);
 743  
     }
 744  
 
 745  
     /**
 746  
      * Return the single value of a sequence.
 747  
      * Return null if the sequence zero zero or more than 1 elements.
 748  
      * Thid is used to implement 'seq instanceof T'.
 749  
      */
 750  
     public static <T> T getSingleValue (Sequence<T> seq) {
 751  2
         if (seq == null || seq.size() != 1)
 752  1
             return null;
 753  1
         return seq.get(0);
 754  
     }
 755  
 }