001 /*
002 * Java Genetic Algorithm Library (jenetics-3.0.0).
003 * Copyright (c) 2007-2014 Franz Wilhelmstötter
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 *
017 * Author:
018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at)
019 */
020 package org.jenetics.util;
021
022 import static java.util.Objects.requireNonNull;
023 import static java.util.stream.Collectors.joining;
024
025 import java.util.ArrayList;
026 import java.util.Comparator;
027 import java.util.Iterator;
028 import java.util.List;
029 import java.util.Objects;
030 import java.util.RandomAccess;
031 import java.util.Spliterator;
032 import java.util.function.Function;
033 import java.util.function.Predicate;
034 import java.util.function.Supplier;
035 import java.util.stream.Collector;
036 import java.util.stream.Stream;
037 import java.util.stream.StreamSupport;
038
039 import org.jenetics.internal.collection.SeqSpliterator;
040
041 /**
042 * General interface for a ordered, fixed sized, object sequence.
043 * <br>
044 * Use the {@link #asList()} method to work together with the
045 * <a href="http://download.oracle.com/javase/6/docs/technotes/guides/collections/index.html">
046 * Java Collection Framework</a>.
047 *
048 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
049 * @since 1.0
050 * @version 3.0 — <em>$Date: 2014-12-28 $</em>
051 */
052 public interface Seq<T> extends Iterable<T> {
053
054 /**
055 * Return the value at the given {@code index}.
056 *
057 * @param index index of the element to return.
058 * @return the value at the given {@code index}.
059 * @throws IndexOutOfBoundsException if the index is out of range
060 * (index < 0 || index >= size()).
061 */
062 public T get(final int index);
063
064 /**
065 * Return the length of this sequence. Once the sequence is created, the
066 * length can't be changed.
067 *
068 * @return the length of this sequence.
069 */
070 public int length();
071
072 /**
073 * @see #length()
074 * @return the size of this sequence
075 */
076 public default int size() {
077 return length();
078 }
079
080 /**
081 * Tests whether a predicate holds for all elements of this sequence.
082 *
083 * @param predicate the predicate to use to test the elements.
084 * @return {@code true} if the given predicate p holds for all elements of
085 * this sequence, {@code false} otherwise.
086 * @throws NullPointerException if the given {@code predicate} is
087 * {@code null}.
088 */
089 public default boolean forAll(final Predicate<? super T> predicate) {
090 boolean valid = true;
091
092 if (this instanceof RandomAccess) {
093 for (int i = 0, n = length(); i < n && valid; ++i) {
094 valid = predicate.test(get(i));
095 }
096 } else {
097 final Iterator<T> it = iterator();
098 while (it.hasNext() && valid) {
099 valid = predicate.test(it.next());
100 }
101 }
102
103 return valid;
104 }
105
106 /**
107 * Returns a sequential Stream with this sequence as its source.
108 *
109 * @since 3.0
110 *
111 * @return a sequential Stream over the elements in this sequence
112 */
113 public default Stream<T> stream() {
114 return StreamSupport.stream(new SeqSpliterator<>(this), false);
115 }
116
117 /**
118 * Returns a possibly parallel {@code Stream} with this sequence as its
119 * source. It is allowable for this method to return a sequential stream.
120 *
121 * @since 3.0
122 *
123 * @return a possibly parallel {@code Stream} over the elements in this
124 * collection
125 */
126 public default Stream<T> parallelStream() {
127 return StreamSupport.stream(new SeqSpliterator<>(this), true);
128 }
129
130 @Override
131 public default Spliterator<T> spliterator() {
132 return new SeqSpliterator<T>(this);
133 }
134
135 /**
136 * Returns {@code true} if this sequence contains the specified element.
137 *
138 * @param element element whose presence in this sequence is to be tested.
139 * The tested element can be {@code null}.
140 * @return {@code true} if this sequence contains the specified element
141 */
142 public default boolean contains(final Object element) {
143 return indexOf(element) != -1;
144 }
145
146 /**
147 * Returns the index of the first occurrence of the specified element
148 * in this sequence, or -1 if this sequence does not contain the element.
149 *
150 * @param element element to search for, can be {@code null}
151 * @return the index of the first occurrence of the specified element in
152 * this sequence, or -1 if this sequence does not contain the element
153 */
154 public default int indexOf(final Object element) {
155 return indexOf(element, 0, length());
156 }
157
158 /**
159 * Returns the index of the first occurrence of the specified element
160 * in this sequence, or -1 if this sequence does not contain the element.
161 *
162 * @param element element to search for, can be {@code null}
163 * @param start the start index (inclusively) for the element search.
164 * @return the index of the first occurrence of the specified element in
165 * this sequence, or -1 if this sequence does not contain the element
166 * @throws IndexOutOfBoundsException for an illegal end point index value
167 * ({@code start < 0 || start > length()}).
168 */
169 public default int indexOf(final Object element, final int start) {
170 return indexOf(element, start, length());
171 }
172
173 /**
174 * Returns the index of the first occurrence of the specified element
175 * in this sequence, or -1 if this sequence does not contain the element.
176 *
177 * @param element element to search for, can be {@code null}
178 * @param start the start index (inclusively) for the element search.
179 * @param end the end index (exclusively) for the element search.
180 * @return the index of the first occurrence of the specified element in
181 * this sequence, or -1 if this sequence does not contain the element
182 * @throws IndexOutOfBoundsException for an illegal end point index value
183 * ({@code start < 0 || end > length() || start > end}).
184 */
185 public default int indexOf(final Object element, final int start, final int end) {
186 return element != null ?
187 indexWhere(element::equals, start, end) :
188 indexWhere(Objects::isNull, start, end);
189 }
190
191 /**
192 * <p>
193 * Returns the index of the first element on which the given predicate
194 * returns {@code true}, or -1 if the predicate returns false for every
195 * sequence element.
196 * </p>
197 * [code]
198 * // Finding index of first null value.
199 * final int index = seq.indexOf(o -> o == null);
200 *
201 * // Assert of no null values.
202 * assert (sequence.indexOf(o -> o == null) == -1);
203 * [/code]
204 *
205 * @param predicate the search predicate.
206 * @return the index of the first element on which the given predicate
207 * returns {@code true}, or -1 if the predicate returns {@code false}
208 * for every sequence element.
209 * @throws NullPointerException if the given {@code predicate} is {@code null}.
210 */
211 public default int indexWhere(final Predicate<? super T> predicate) {
212 return indexWhere(predicate, 0, length());
213 }
214
215 /**
216 * <p>
217 * Returns the index of the first element on which the given predicate
218 * returns {@code true}, or -1 if the predicate returns false for every
219 * sequence element.
220 * </p>
221 * [code]
222 * // Finding index of first null value.
223 * final int index = seq.indexOf(o -> o == null);
224 *
225 * // Assert of no null values.
226 * assert (sequence.indexOf(o -> o == null) == -1);
227 * [/code]
228 *
229 * @param predicate the search predicate.
230 * @param start the search start index
231 * @return the index of the first element on which the given predicate
232 * returns {@code true}, or -1 if the predicate returns {@code false}
233 * for every sequence element.
234 * @throws NullPointerException if the given {@code predicate} is {@code null}.
235 * @throws IndexOutOfBoundsException for an illegal end point index value
236 * ({@code start < 0 || start > length()}).
237 */
238 public default int indexWhere(
239 final Predicate<? super T> predicate,
240 final int start
241 ) {
242 return indexWhere(predicate, start, length());
243 }
244
245 /**
246 * <p>
247 * Returns the index of the first element on which the given predicate
248 * returns {@code true}, or -1 if the predicate returns false for every
249 * sequence element.
250 * </p>
251 * [code]
252 * // Finding index of first null value.
253 * final int index = seq.indexOf(o -> o == null);
254 *
255 * // Assert of no null values.
256 * assert (sequence.indexOf(o -> o == null) == -1);
257 * [/code]
258 *
259 * @param predicate the search predicate.
260 * @param start the search start index
261 * @param end the search end index
262 * @return the index of the first element on which the given predicate
263 * returns {@code true}, or -1 if the predicate returns {@code false}
264 * for every sequence element.
265 * @throws NullPointerException if the given {@code predicate} is {@code null}.
266 * @throws IndexOutOfBoundsException for an illegal end point index value
267 * ({@code start < 0 || end > length() || start > end}).
268 */
269 public default int indexWhere(
270 final Predicate<? super T> predicate,
271 final int start,
272 final int end
273 ) {
274 requireNonNull(predicate, "Predicate");
275
276 int index = -1;
277 for (int i = 0, n = length(); i < n && index == -1; ++i) {
278 if (predicate.test(get(i))) {
279 index = i;
280 }
281 }
282 return index;
283 }
284
285 /**
286 * Returns the index of the last occurrence of the specified element
287 * in this sequence, or -1 if this sequence does not contain the element.
288 *
289 * @param element element to search for, can be {@code null}
290 * @return the index of the last occurrence of the specified element in
291 * this sequence, or -1 if this sequence does not contain the element
292 */
293 public default int lastIndexOf(final Object element) {
294 return lastIndexOf(element, 0, length());
295 }
296
297 /**
298 * Returns the index of the last occurrence of the specified element
299 * in this sequence, or -1 if this sequence does not contain the element.
300 *
301 * @param element element to search for, can be {@code null}
302 * @param end the search end index
303 * @return the index of the last occurrence of the specified element in
304 * this sequence, or -1 if this sequence does not contain the element
305 * @throws IndexOutOfBoundsException for an illegal end point index value
306 * ({@code end < 0 || end > length()}).
307 */
308 public default int lastIndexOf(final Object element, final int end) {
309 return lastIndexOf(element, 0, end);
310 }
311
312 /**
313 * Returns the index of the last occurrence of the specified element
314 * in this sequence, or -1 if this sequence does not contain the element.
315 *
316 * @param element element to search for, can be {@code null}
317 * @param start the search start index
318 * @param end the search end index
319 * @return the index of the last occurrence of the specified element in
320 * this sequence, or -1 if this sequence does not contain the element
321 * @throws IndexOutOfBoundsException for an illegal end point index value
322 * ({@code start < 0 || end > length() || start > end}).
323 */
324 public default int lastIndexOf(
325 final Object element,
326 final int start,
327 final int end
328 ) {
329 return element != null ?
330 lastIndexWhere(element::equals, start, end) :
331 lastIndexWhere(Objects::isNull, start, end);
332 }
333
334 /**
335 * Returns the index of the last element on which the given predicate
336 * returns {@code true}, or -1 if the predicate returns false for every
337 * sequence element.
338 *
339 * @param predicate the search predicate.
340 * @return the index of the last element on which the given predicate
341 * returns {@code true}, or -1 if the predicate returns false for
342 * every sequence element.
343 * @throws NullPointerException if the given {@code predicate} is {@code null}.
344 */
345 public default int lastIndexWhere(final Predicate<? super T> predicate) {
346 return lastIndexWhere(predicate, 0, length());
347 }
348
349 /**
350 * Returns the index of the last element on which the given predicate
351 * returns {@code true}, or -1 if the predicate returns false for every
352 * sequence element.
353 *
354 * @param predicate the search predicate.
355 * @param end the search end index
356 * @return the index of the last element on which the given predicate
357 * returns {@code true}, or -1 if the predicate returns false for
358 * every sequence element.
359 * @throws NullPointerException if the given {@code predicate} is {@code null}.
360 * @throws IndexOutOfBoundsException for an illegal end point index value
361 * ({@code end < 0 || end > length()}).
362 */
363 public default int lastIndexWhere(
364 final Predicate<? super T> predicate,
365 final int end
366 ) {
367 return lastIndexWhere(predicate, 0, end);
368 }
369
370 /**
371 * Returns the index of the last element on which the given predicate
372 * returns {@code true}, or -1 if the predicate returns false for every
373 * sequence element.
374 *
375 * @param predicate the search predicate.
376 * @param start the search start index
377 * @param end the search end index
378 * @return the index of the last element on which the given predicate
379 * returns {@code true}, or -1 if the predicate returns false for
380 * every sequence element.
381 * @throws NullPointerException if the given {@code predicate} is {@code null}.
382 * @throws IndexOutOfBoundsException for an illegal end point index value
383 * ({@code start < 0 || end > length() || start > end}).
384 */
385 public default int lastIndexWhere(
386 final Predicate<? super T> predicate,
387 final int start,
388 final int end
389 ) {
390 requireNonNull(predicate, "Predicate");
391
392 int index = -1;
393 for (int i = length(); --i >= 0 && index == -1;) {
394 if (predicate.test(get(i))) {
395 index = i;
396 }
397 }
398 return index;
399 }
400
401 /**
402 * Returns a fixed-size list backed by the specified sequence. (Changes to
403 * the returned list "write through" to the array.) The returned list is
404 * fixed size, serializable and implements {@link RandomAccess}.
405 *
406 * @return a list view of this sequence
407 */
408 public List<T> asList();
409
410 /**
411 * Builds a new sequence by applying a function to all elements of this
412 * sequence.
413 *
414 * @param <B> the element type of the returned collection.
415 * @param mapper the function to apply to each element.
416 * @return a new sequence of type That resulting from applying the given
417 * function f to each element of this sequence and collecting the
418 * results.
419 * @throws NullPointerException if the element {@code mapper} is
420 * {@code null}.
421 */
422 public <B> Seq<B> map(final Function<? super T, ? extends B> mapper);
423
424 /**
425 * Return an array containing all of the elements in this sequence in right
426 * order. The returned array will be "safe" in that no references to it
427 * are maintained by this sequence. (In other words, this method must allocate
428 * a new array.) The caller is thus free to modify the returned array.
429 *
430 * @see java.util.Collection#toArray()
431 *
432 * @return an array containing all of the elements in this list in right
433 * order
434 */
435 public default Object[] toArray() {
436 final Object[] array = new Object[size()];
437 for (int i = size(); --i >= 0;) {
438 array[i] = get(i);
439 }
440 return array;
441 }
442
443 /**
444 * Return an array containing all of the elements in this sequence in right
445 * order; the runtime type of the returned array is that of the specified
446 * array. If this sequence fits in the specified array, it is returned
447 * therein. Otherwise, a new array is allocated with the runtime type of the
448 * specified array and the length of this array.
449 * <p>
450 * If this sequence fits in the specified array with room to spare (i.e.,
451 * the array has more elements than this array), the element in the array
452 * immediately following the end of this array is set to null. (This is
453 * useful in determining the length of the array only if the caller knows
454 * that the list does not contain any null elements.)
455 *
456 * @see java.util.Collection#toArray(Object[])
457 *
458 * @param array the array into which the elements of this array are to be
459 * stored, if it is big enough; otherwise, a new array of the same
460 * runtime type is allocated for this purpose.
461 * @return an array containing the elements of this array
462 * @throws ArrayStoreException if the runtime type of the specified array is
463 * not a super type of the runtime type of every element in this
464 * array
465 * @throws NullPointerException if the given array is {@code null}.
466 */
467 @SuppressWarnings("unchecked")
468 public default T[] toArray(final T[] array) {
469 if (array.length < length()) {
470 final T[] copy = (T[])java.lang.reflect.Array.newInstance(
471 array.getClass().getComponentType(), length()
472 );
473 for (int i = length(); --i >= 0;) {
474 copy[i] = get(i);
475 }
476
477 return copy;
478 }
479
480 for (int i = 0, n = length(); i < n; ++i) {
481 array[i] = get(i);
482 }
483 return array;
484 }
485
486 /**
487 * Returns a view of the portion of this sequence between the specified
488 * {@code start}, inclusive, and {@code end}, exclusive. (If {@code start}
489 * and {@code end} are equal, the returned sequence has the length zero.)
490 * The returned sequence is backed by this sequence, so non-structural
491 * changes in the returned sequence are reflected in this sequence, and
492 * vice-versa.
493 * <p>
494 * This method eliminates the need for explicit range operations (of the
495 * populationSort that commonly exist for arrays). Any operation that
496 * expects an sequence can be used as a range operation by passing an sub
497 * sequence view instead of an whole sequence.
498 *
499 * @param start low end point (inclusive) of the sub array.
500 * @return a view of the specified range within this array.
501 * @throws IndexOutOfBoundsException for an illegal end point index value
502 * ({@code start < 0 || start > length()}).
503 */
504 public Seq<T> subSeq(final int start);
505
506 /**
507 * Returns a view of the portion of this sequence between the specified
508 * {@code start}, inclusive, and {@code end}, exclusive. (If {@code start}
509 * and {@code end} are equal, the returned sequence has the length zero.)
510 * The returned sequence is backed by this sequence, so non-structural
511 * changes in the returned sequence are reflected in this array, and
512 * vice-versa.
513 * <p>
514 * This method eliminates the need for explicit range operations (of the
515 * populationSort that commonly exist for arrays). Any operation that
516 * expects an array can be used as a range operation by passing an sub
517 * sequence view instead of an whole sequence.
518 *
519 * @param start low end point (inclusive) of the sub sequence.
520 * @param end high end point (exclusive) of the sub sequence.
521 * @return a view of the specified range within this sequence.
522 * @throws IndexOutOfBoundsException for an illegal end point index value
523 * ({@code start < 0 || end > length() || start > end}).
524 */
525 public Seq<T> subSeq(final int start, final int end);
526
527 /**
528 * Test whether the given array is sorted in ascending order.
529 *
530 * @return {@code true} if the given {@code array} is sorted in ascending
531 * order, {@code false} otherwise.
532 * @throws NullPointerException if the given array or one of it's element is
533 * {@code null}.
534 */
535 @SuppressWarnings("unchecked")
536 public default boolean isSorted() {
537 boolean sorted = true;
538 for (int i = 0, n = length() - 1; i < n && sorted; ++i) {
539 sorted = ((Comparable<T>)get(i)).compareTo(get(i + 1)) <= 0;
540 }
541
542 return sorted;
543 }
544
545 /**
546 * Test whether the given array is sorted in ascending order. The order of
547 * the array elements is defined by the given comparator.
548 *
549 * @param comparator the comparator which defines the order.
550 * @return {@code true} if the given {@code array} is sorted in ascending
551 * order, {@code false} otherwise.
552 * @throws NullPointerException if the given array or one of it's element or
553 * the comparator is {@code null}.
554 */
555 public default boolean isSorted(final Comparator<? super T> comparator) {
556 boolean sorted = true;
557 for (int i = 0, n = length() - 1; i < n && sorted; ++i) {
558 sorted = comparator.compare(get(i), get(i + 1)) <= 0;
559 }
560
561 return sorted;
562 }
563
564 /**
565 * Returns the hash code value for this sequence. The hash code is defined
566 * as followed:
567 *
568 * [code]
569 * int hashCode = 1;
570 * final Iterator<E> it = seq.iterator();
571 * while (it.hasNext()) {
572 * final E obj = it.next();
573 * hashCode = 31*hashCode + (obj == null ? 0 : obj.hashCode());
574 * }
575 * [/code]
576 *
577 * @see List#hashCode()
578 * @see Seq#hashCode(Seq)
579 *
580 * @return the hash code value for this list
581 */
582 @Override
583 public int hashCode();
584
585 /**
586 * Compares the specified object with this sequence for equality. Returns
587 * true if and only if the specified object is also a sequence, both
588 * sequence have the same size, and all corresponding pairs of elements in
589 * the two sequences are equal. (Two elements e1 and e2 are equal if
590 * (e1==null ? e2==null : e1.equals(e2)).) This definition ensures that the
591 * equals method works properly across different implementations of the Seq
592 * interface.
593 *
594 * @see List#equals(Object)
595 * @see Seq#equals(Seq, Object)
596 *
597 * @param object the object to be compared for equality with this sequence.
598 * @return {@code true} if the specified object is equal to this sequence,
599 * {@code false} otherwise.
600 */
601 @Override
602 public boolean equals(final Object object);
603
604 /**
605 * Create a string representation of the given sequence.
606 *
607 * @param prefix the prefix of the string representation; e.g {@code '['}.
608 * @param separator the separator of the array elements; e.g. {@code ','}.
609 * @param suffix the suffix of the string representation; e.g. {@code ']'}.
610 * @return the string representation of this sequence.
611 */
612 public default String toString(
613 final String prefix,
614 final String separator,
615 final String suffix
616 ) {
617 return stream()
618 .map(Object::toString)
619 .collect(joining(separator, prefix, suffix));
620 }
621
622 /**
623 * Create a string representation of the given sequence.
624 *
625 * @param separator the separator of the array elements; e.g. {@code ','}.
626 * @return the string representation of this sequence.
627 */
628 public default String toString(final String separator) {
629 return toString("", separator, "");
630 }
631
632 /**
633 * Unified method for calculating the hash code of every {@link Seq}
634 * implementation. The hash code is defined as followed:
635 *
636 * [code]
637 * int hashCode = 1;
638 * final Iterator<E> it = seq.iterator();
639 * while (it.hasNext()) {
640 * final E obj = it.next();
641 * hashCode = 31*hashCode + (obj == null ? 0 : obj.hashCode());
642 * }
643 * [/code]
644 *
645 * @see Seq#hashCode()
646 * @see List#hashCode()
647 *
648 * @param seq the sequence to calculate the hash code for.
649 * @return the hash code of the given sequence.
650 */
651 public static int hashCode(final Seq<?> seq) {
652 int hash = 1;
653 for (Object element : seq) {
654 hash = 31*hash + (element == null ? 0: element.hashCode());
655 }
656 return hash;
657 }
658
659 /**
660 * Unified method for compare to sequences for equality.
661 *
662 * @see Seq#equals(Object)
663 *
664 * @param seq the sequence to test for equality.
665 * @param obj the object to test for equality with the sequence.
666 * @return {@code true} if the given objects are sequences and contain the
667 * same objects in the same order, {@code false} otherwise.
668 */
669 public static boolean equals(final Seq<?> seq, final Object obj) {
670 if (obj == seq) {
671 return true;
672 }
673 if (!(obj instanceof Seq<?>)) {
674 return false;
675 }
676
677 final Seq<?> other = (Seq<?>)obj;
678 boolean equals = (seq.length() == other.length());
679 for (int i = seq.length(); equals && --i >= 0;) {
680 final Object element = seq.get(i);
681 if (element != null) {
682 equals = element.equals(other.get(i));
683 } else {
684 equals = other.get(i) == null;
685 }
686 }
687 return equals;
688 }
689
690 /* *************************************************************************
691 * Some static factory methods.
692 * ************************************************************************/
693
694 /**
695 * Returns a {@code Collector} that accumulates the input elements into a
696 * new {@code Seq}.
697 *
698 * @param <T> the type of the input elements
699 * @return a {@code Collector} which collects all the input elements into a
700 * {@code Seq}, in encounter order
701 */
702 public static <T> Collector<T, ?, Seq<T>> toSeq() {
703 return Collector.of(
704 (Supplier<List<T>>)ArrayList::new,
705 List::add,
706 (left, right) -> { left.addAll(right); return left; },
707 Seq::of
708 );
709 }
710
711 /**
712 * Create a new {@code Seq} from the given values.
713 *
714 * @param <T> the element type
715 * @param values the array values.
716 * @return a new {@code Seq} with the given values.
717 * @throws NullPointerException if the {@code values} array is {@code null}.
718 */
719 @SafeVarargs
720 public static <T> Seq<T> of(final T... values) {
721 return ISeq.of(values);
722 }
723
724 /**
725 * Create a new {@code Seq} from the given values.
726 *
727 * @param <T> the element type
728 * @param values the array values.
729 * @return a new {@code Seq} with the given values.
730 * @throws NullPointerException if the {@code values} array is {@code null}.
731 */
732 public static <T> Seq<T> of(final Iterable<? extends T> values) {
733 return ISeq.of(values);
734 }
735
736 }
|