001/*
002 * Java Genetic Algorithm Library (jenetics-8.1.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 */
020package io.jenetics.util;
021
022import static java.lang.Math.min;
023import static java.lang.String.format;
024import static java.util.Objects.requireNonNull;
025
026import java.util.ArrayList;
027import java.util.Collection;
028import java.util.Comparator;
029import java.util.Iterator;
030import java.util.List;
031import java.util.ListIterator;
032import java.util.function.Function;
033import java.util.function.Supplier;
034import java.util.random.RandomGenerator;
035import java.util.stream.Collector;
036import java.util.stream.Stream;
037
038import io.jenetics.internal.collection.Array;
039import io.jenetics.internal.collection.ArrayMSeq;
040import io.jenetics.internal.collection.Empty;
041import io.jenetics.internal.collection.Empty.EmptyMSeq;
042import 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 */
059public 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}