001 /*
002 * Java Genetic Algorithm Library (jenetics-6.1.0).
003 * Copyright (c) 2007-2020 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@gmail.com)
019 */
020 package io.jenetics.util;
021
022 import static java.lang.Math.min;
023 import static java.lang.String.format;
024 import static java.util.Objects.requireNonNull;
025
026 import java.util.ArrayList;
027 import java.util.Collection;
028 import java.util.Comparator;
029 import java.util.Iterator;
030 import java.util.List;
031 import java.util.ListIterator;
032 import java.util.Random;
033 import java.util.function.Function;
034 import java.util.function.Supplier;
035 import java.util.stream.Collector;
036 import java.util.stream.Stream;
037
038 import io.jenetics.internal.collection.Array;
039 import io.jenetics.internal.collection.ArrayMSeq;
040 import io.jenetics.internal.collection.Empty;
041 import io.jenetics.internal.collection.Empty.EmptyMSeq;
042 import io.jenetics.internal.collection.ObjectStore;
043
044 /**
045 * Mutable, ordered, fixed sized sequence.
046 *
047 * @implNote
048 * This implementation is not thread safe. All {@link ISeq} and {@link MSeq}
049 * instances created by {@link MSeq#toISeq} and {@link MSeq#subSeq(int)},
050 * respectively, must be protected by the same lock, when they are accessed
051 * (get/set) by different threads.
052 *
053 * @see ISeq
054 *
055 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
056 * @since 1.0
057 * @version 5.2
058 */
059 public interface MSeq<T> extends Seq<T>, Copyable<MSeq<T>> {
060
061 default List<T> asList() {
062 return new MSeqList<>(this);
063 }
064
065 /**
066 * Set the {@code value} at the given {@code index}.
067 *
068 * @param index the index of the new value.
069 * @param value the new value.
070 * @throws IndexOutOfBoundsException if the index is out of range
071 * {@code (index < 0 || index >= size())}.
072 */
073 void set(final int index, final T value);
074
075 /**
076 * Fills the sequence with values of the given iterator.
077 *
078 * @param it the iterator of the values to fill this sequence.
079 * @return {@code this} sequence.
080 */
081 default MSeq<T> setAll(final Iterator<? extends T> it) {
082 for (int i = 0, n = length(); i < n && it.hasNext(); ++i) {
083 set(i, it.next());
084 }
085 return this;
086 }
087
088 /**
089 * Fills the sequence with values of the given iterable.
090 *
091 * @param values the values to fill this sequence.
092 * @return {@code this} sequence.
093 */
094 default MSeq<T> setAll(final Iterable<? extends T> values) {
095 setAll(values.iterator());
096 return this;
097 }
098
099 /**
100 * Fill the sequence with the given values.
101 *
102 * @param values the first initial values of this sequence
103 * @return {@code this} sequence.
104 */
105 default MSeq<T> setAll(final T[] values) {
106 for (int i = 0, n = min(length(), values.length); i < n; ++i) {
107 set(i, values[i]);
108 }
109 return this;
110 }
111
112 /**
113 * Fill the sequence with values generated by the given factory.
114 *
115 * @param supplier the value factory.
116 * @return {@code this} sequence.
117 * @throws NullPointerException if the given {@code factory} is {@code null}.
118 */
119 default MSeq<T> fill(final Supplier<? extends T> supplier) {
120 for (int i = 0, n = length(); i < n; ++i) {
121 set(i, supplier.get());
122 }
123 return this;
124 }
125
126 /**
127 * Swap the elements at the two positions.
128 *
129 * @param i the index of the first element.
130 * @param j the index of the second element.
131 * @throws IndexOutOfBoundsException if {@code i < 0 || j >= length()}.
132 */
133 default void swap(final int i, final int j) {
134 final T temp = get(i);
135 set(i, get(j));
136 set(j, temp);
137 }
138
139 /**
140 * Swap a given range with a range of the same size with another array.
141 *
142 * <pre>
143 * start end
144 * | |
145 * this: +---+---+---+---+---+---+---+---+---+---+---+---+
146 * +---------------+
147 * +---------------+
148 * other: +---+---+---+---+---+---+---+---+---+---+---+---+
149 * |
150 * otherStart
151 * </pre>
152 *
153 * @param start the start index of {@code this} range, inclusively.
154 * @param end the end index of {@code this} range, exclusively.
155 * @param other the other array to swap the elements with.
156 * @param otherStart the start index of the {@code other} array.
157 * @throws IndexOutOfBoundsException if {@code start > end} or
158 * if {@code start < 0 || end >= this.length() || otherStart < 0 ||
159 * otherStart + (end - start) >= other.length()}
160 */
161 default void swap(
162 final int start, final int end,
163 final MSeq<T> other, final int otherStart
164 ) {
165 if (otherStart < 0 || (otherStart + (end - start)) > length()) {
166 throw new ArrayIndexOutOfBoundsException(format(
167 "Invalid index range: [%d, %d)",
168 otherStart, otherStart + (end - start)
169 ));
170 }
171
172 if (start < end) {
173 for (int i = end - start; --i >= 0;) {
174 final T temp = get(start + i);
175 set(start + i, other.get(otherStart + i));
176 other.set(otherStart + i, temp);
177 }
178 }
179 }
180
181 /**
182 * Swap the elements at the same position.
183 *
184 * @since 4.0
185 *
186 * @param index the index of swapped element.
187 * @param other the other array to swap the elements with.
188 * @throws IndexOutOfBoundsException if
189 * {@code index < 0 || index >= this.length() || index >= other.length()}.
190 * @throws NullPointerException if the {@code other} sequence is {@code null}
191 */
192 default void swap(final int index, final MSeq<T> other) {
193 final T temp = get(index);
194 set(index, other.get(index));
195 other.set(index, temp);
196 }
197
198 /**
199 * Randomize the {@code array} using the {@link Random} object currently
200 * registered in the {@link RandomRegistry} class. The used shuffling
201 * algorithm is from D. Knuth TAOCP, Seminumerical Algorithms, Third edition,
202 * page 142, Algorithm S (Selection sampling technique).
203 *
204 * @return this shuffled sequence
205 */
206 default MSeq<T> shuffle() {
207 return shuffle(RandomRegistry.random());
208 }
209
210 /**
211 * Randomize the {@code array} using the given {@link Random} object. The used
212 * shuffling algorithm is from D. Knuth TAOCP, Seminumerical Algorithms,
213 * Third edition, page 142, Algorithm S (Selection sampling technique).
214 *
215 * @param random the {@link Random} object to use for randomize.
216 * @return this shuffled sequence
217 * @throws NullPointerException if the random object is {@code null}.
218 */
219 default MSeq<T> shuffle(final Random random) {
220 for (int j = length() - 1; j > 0; --j) {
221 swap(j, random.nextInt(j + 1));
222 }
223 return this;
224 }
225
226 /**
227 * Sorts this sequence according to the order induced by the specified
228 * {@link Comparator}.
229 *
230 * <p>All elements in this sequence must be <i>mutually comparable</i> using
231 * the specified comparator (that is, {@code c.compare(e1, e2)} must not
232 * throw a {@code ClassCastException} for any elements {@code e1} and
233 * {@code e2} in the sequence).
234 *
235 * <p>If the specified comparator is {@code null} then all elements in this
236 * list must implement the {@link Comparable} interface and the elements'
237 * Comparable natural ordering should be used.
238 *
239 * @param start the start index where to start sorting (inclusively)
240 * @param end the end index where to stop sorting (exclusively)
241 * @param comparator the {@code Comparator} used to compare sequence elements.
242 * A {@code null} value indicates that the elements' Comparable
243 * natural ordering should be used
244 * @throws ClassCastException if the sequence contains elements that are not
245 * <i>mutually comparable</i> using the specified comparator
246 * @return {@code this} sequence
247 */
248 MSeq<T> sort(
249 final int start,
250 final int end,
251 final Comparator<? super T> comparator
252 );
253
254 /**
255 * Sorts this sequence according to the natural order of the elements.
256 *
257 * @param start the start index where to start sorting (inclusively)
258 * @param end the end index where to stop sorting (exclusively)
259 * @throws ClassCastException if the sequence contains elements that are not
260 * <i>mutually comparable</i> using the specified comparator
261 * @return {@code this} sequence
262 */
263 default MSeq<T> sort(final int start, final int end) {
264 return sort(start, end, null);
265 }
266
267 /**
268 * Sorts this sequence according to the order induced by the specified
269 * {@link Comparator}.
270 *
271 * <p>All elements in this sequence must be <i>mutually comparable</i> using
272 * the specified comparator (that is, {@code c.compare(e1, e2)} must not
273 * throw a {@code ClassCastException} for any elements {@code e1} and
274 * {@code e2} in the sequence).
275 *
276 * <p>If the specified comparator is {@code null} then all elements in this
277 * list must implement the {@link Comparable} interface and the elements'
278 * Comparable natural ordering should be used.
279 *
280 * @param start the start index where to start sorting (inclusively)
281 * @param comparator the {@code Comparator} used to compare sequence elements.
282 * A {@code null} value indicates that the elements' Comparable
283 * natural ordering should be used
284 * @throws ClassCastException if the sequence contains elements that are not
285 * <i>mutually comparable</i> using the specified comparator
286 * @return {@code this} sequence
287 */
288 default MSeq<T> sort(
289 final int start,
290 final Comparator<? super T> comparator
291 ) {
292 return sort(start, length(), comparator);
293 }
294
295 /**
296 * Sorts this sequence according to the natural order of the elements.
297 *
298 * @param start the start index where to start sorting (inclusively)
299 * @throws ClassCastException if the sequence contains elements that are not
300 * <i>mutually comparable</i> using the specified comparator
301 * @return {@code this} sequence
302 */
303 default MSeq<T> sort(final int start) {
304 return sort(start, length(), null);
305 }
306
307 /**
308 * Sorts this sequence according to the order induced by the specified
309 * {@link Comparator}.
310 *
311 * <p>All elements in this sequence must be <i>mutually comparable</i> using
312 * the specified comparator (that is, {@code c.compare(e1, e2)} must not
313 * throw a {@code ClassCastException} for any elements {@code e1} and
314 * {@code e2} in the sequence).
315 *
316 * <p>If the specified comparator is {@code null} then all elements in this
317 * list must implement the {@link Comparable} interface and the elements'
318 * Comparable natural ordering should be used.
319 *
320 * @param comparator the {@code Comparator} used to compare sequence elements.
321 * A {@code null} value indicates that the elements' Comparable
322 * natural ordering should be used
323 * @throws ClassCastException if the sequence contains elements that are not
324 * <i>mutually comparable</i> using the specified comparator
325 * @return {@code this} sequence
326 */
327 default MSeq<T> sort(final Comparator<? super T> comparator) {
328 return sort(0, length(), comparator);
329 }
330
331 /**
332 * Sorts this sequence according to the natural order of the elements.
333 *
334 * @throws ClassCastException if the sequence contains elements that are not
335 * <i>mutually comparable</i> using the specified comparator
336 * @return {@code this} sequence
337 */
338 default MSeq<T> sort() {
339 return sort(0, length(), null);
340 }
341
342 /**
343 * Reverses the order of the elements this sequence (in place).
344 *
345 * @return this sequence with reverse order or the elements
346 */
347 default MSeq<T> reverse() {
348 for (int i = 0, j = length() - 1; i < j; ++i, --j) {
349 swap(i, j);
350 }
351 return this;
352 }
353
354 /**
355 * Returns a list iterator over the elements in this sequence (in proper
356 * sequence).
357 *
358 * @return a list iterator over the elements in this list (in proper
359 * sequence)
360 */
361 default ListIterator<T> listIterator() {
362 return asList().listIterator();
363 }
364
365 @Override
366 MSeq<T> subSeq(final int start, final int end);
367
368 @Override
369 MSeq<T> subSeq(final int start);
370
371 @Override
372 <B> MSeq<B> map(final Function<? super T, ? extends B> mapper);
373
374 @SuppressWarnings("unchecked")
375 @Override
376 default MSeq<T> append(final T... values) {
377 return append(MSeq.of(values));
378 }
379
380 @Override
381 MSeq<T> append(final Iterable<? extends T> values);
382
383 @SuppressWarnings("unchecked")
384 @Override
385 default MSeq<T> prepend(final T... values) {
386 return prepend(MSeq.of(values));
387 }
388
389 @Override
390 MSeq<T> prepend(final Iterable<? extends T> values);
391
392 /**
393 * Return a read-only projection of this sequence. Changes to the original
394 * sequence will not influence the returned {@code ISeq}.
395 *
396 * @return a read-only projection of this sequence
397 */
398 ISeq<T> toISeq();
399
400
401 /* *************************************************************************
402 * Some static helper methods.
403 * ************************************************************************/
404
405 /**
406 * Return a sequence whose elements are all the elements of the first
407 * element followed by all the elements of the sequence.
408 *
409 * @since 5.0
410 *
411 * @param a the first element
412 * @param b the appending sequence
413 * @param <T> the type of the sequence elements
414 * @return the concatenation of the two inputs
415 * @throws NullPointerException if one of the second arguments is
416 * {@code null}
417 */
418 @SuppressWarnings("unchecked")
419 static <T> MSeq<T> concat(
420 final T a,
421 final MSeq<? extends T> b
422 ) {
423 return ((MSeq<T>)b).prepend(a);
424 }
425
426 /**
427 * Return a sequence whose elements are all the elements of the first
428 * sequence followed by all the elements of the vararg array.
429 *
430 * @since 5.0
431 *
432 * @param a the first sequence
433 * @param b the vararg elements
434 * @param <T> the type of the sequence elements
435 * @return the concatenation of the two inputs
436 * @throws NullPointerException if one of the arguments is {@code null}
437 */
438 @SuppressWarnings("unchecked")
439 static <T> MSeq<T> concat(
440 final MSeq<? extends T> a,
441 final T... b
442 ) {
443 return ((MSeq<T>)a).append(b);
444 }
445
446 /**
447 * Return a sequence whose elements are all the elements of the first
448 * sequence followed by all the elements of the second sequence.
449 *
450 * @since 5.0
451 *
452 * @param a the first sequence
453 * @param b the second sequence
454 * @param <T> the type of the sequence elements
455 * @return the concatenation of the two input sequences
456 * @throws NullPointerException if one of the arguments is {@code null}
457 */
458 @SuppressWarnings("unchecked")
459 static <T> MSeq<T> concat(
460 final MSeq<? extends T> a,
461 final MSeq<? extends T> b
462 ) {
463 return ((MSeq<T>)a).append(b);
464 }
465
466 /* *************************************************************************
467 * Some static factory methods.
468 * ************************************************************************/
469
470 /**
471 * Single instance of an empty {@code MSeq}.
472 */
473 MSeq<?> EMPTY = EmptyMSeq.INSTANCE;
474
475 /**
476 * Return an empty {@code MSeq}.
477 *
478 * @param <T> the element type of the returned {@code MSeq}.
479 * @return an empty {@code MSeq}.
480 */
481 static <T> MSeq<T> empty() {
482 return Empty.mseq();
483 }
484
485 /**
486 * Returns a {@code Collector} that accumulates the input elements into a
487 * new {@code MSeq}.
488 *
489 * @param <T> the type of the input elements
490 * @return a {@code Collector} which collects all the input elements into a
491 * {@code MSeq}, in encounter order
492 */
493 static <T> Collector<T, ?, MSeq<T>> toMSeq() {
494 return Collector.of(
495 (Supplier<List<T>>)ArrayList::new,
496 List::add,
497 (left, right) -> { left.addAll(right); return left; },
498 MSeq::of
499 );
500 }
501
502 /**
503 * Create a new {@code MSeq} with the given {@code length}.
504 *
505 * @param length the length of the created {@code MSeq}.
506 * @param <T> the element type of the new {@code MSeq}.
507 * @return the new mutable sequence.
508 * @throws NegativeArraySizeException if the given {@code length} is
509 * negative
510 */
511 static <T> MSeq<T> ofLength(final int length) {
512 return length == 0
513 ? empty()
514 : new ArrayMSeq<>(Array.of(ObjectStore.ofLength(length)));
515 }
516
517 /**
518 * Create a new {@code MSeq} from the given values.
519 *
520 * @param <T> the element type
521 * @param values the array values.
522 * @return a new {@code Meq} with the given values.
523 * @throws NullPointerException if the {@code values} array is {@code null}.
524 */
525 @SafeVarargs
526 static <T> MSeq<T> of(final T... values) {
527 return values.length == 0
528 ? empty()
529 : new ArrayMSeq<>(Array.of(ObjectStore.of(values.clone())));
530 }
531
532 /**
533 * Create a new {@code MSeq} from the given values.
534 *
535 * @param <T> the element type
536 * @param values the array values.
537 * @return a new {@code MSeq} with the given values.
538 * @throws NullPointerException if the {@code values} object is
539 * {@code null}.
540 */
541 @SuppressWarnings("unchecked")
542 static <T> MSeq<T> of(final Iterable<? extends T> values) {
543 final MSeq<T> mseq;
544 if (values instanceof ISeq) {
545 final ISeq<T> seq = (ISeq<T>)values;
546 mseq = seq.isEmpty() ? empty() : seq.copy();
547 } else if (values instanceof MSeq) {
548 final MSeq<T> seq = (MSeq<T>)values;
549 mseq = seq.isEmpty() ? empty() : MSeq.of(seq);
550 } else if (values instanceof Collection) {
551 final Collection<T> collection = (Collection<T>)values;
552 mseq = collection.isEmpty()
553 ? empty()
554 : MSeq.<T>ofLength(collection.size()).setAll(values);
555 } else if (values instanceof BaseSeq) {
556 final BaseSeq<T> seq = (BaseSeq<T>)values;
557 mseq = seq.length() == 0
558 ? empty()
559 : MSeq.<T>ofLength(seq.length()).setAll(values);
560 } else {
561 final Stream.Builder<T> builder = Stream.builder();
562 values.forEach(builder::add);
563 final Object[] objects = builder.build().toArray();
564
565 mseq = objects.length == 0
566 ? empty()
567 : new ArrayMSeq<>(Array.of(ObjectStore.of(objects)));
568 }
569
570 return mseq;
571 }
572
573 /**
574 * Creates a new sequence, which is filled with objects created be the given
575 * {@code supplier}.
576 *
577 * @since 3.3
578 *
579 * @param <T> the element type of the sequence
580 * @param supplier the {@code Supplier} which creates the elements, the
581 * returned sequence is filled with
582 * @param length the length of the returned sequence
583 * @return a new sequence filled with elements given by the {@code supplier}
584 * @throws NegativeArraySizeException if the given {@code length} is
585 * negative
586 * @throws NullPointerException if the given {@code supplier} is
587 * {@code null}
588 */
589 static <T> MSeq<T> of(
590 final Supplier<? extends T> supplier,
591 final int length
592 ) {
593 requireNonNull(supplier);
594
595 return length == 0
596 ? empty()
597 : MSeq.<T>ofLength(length).fill(supplier);
598 }
599
600 /**
601 * Create a new {@code MSeq} from the values of the given {@code Seq}.
602 *
603 * @param <T> the element type
604 * @param values the array values.
605 * @return an new {@code MSeq} with the given values
606 * @throws NullPointerException if the {@code values} array is {@code null}.
607 */
608 @SuppressWarnings("unchecked")
609 static <T> MSeq<T> of(final Seq<? extends T> values) {
610 final MSeq<T> result;
611 if (values instanceof MSeq) {
612 result = ((MSeq<T>)values).copy();
613 } else if (values instanceof ISeq) {
614 result = ((ISeq<T>)values).copy();
615 } else {
616 result = MSeq.<T>ofLength(values.length()).setAll(values);
617 }
618 return result;
619 }
620
621 }
|