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