Classes in this File | Line Coverage | Branch Coverage | Complexity | ||||
Sequences |
|
| 0.0;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 | } |