MSeq.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-7.0.0).
003  * Copyright (c) 2007-2022 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 < || (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 proper
357      * sequence).
358      *
359      @return a list iterator over the elements in this list (in 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 
548         final MSeq<T> mseq;
549         if (vals instanceof ISeq<T> seq) {
550             mseq = seq.isEmpty() ? empty() : seq.copy();
551         else if (vals instanceof MSeq<T> seq) {
552             mseq = seq.isEmpty() ? empty() : MSeq.of(seq);
553         else if (vals instanceof Collection<T> collection) {
554             mseq = collection.isEmpty()
555                 ? empty()
556                 : MSeq.<T>ofLength(collection.size()).setAll(values);
557         else if (vals instanceof BaseSeq<T> seq) {
558             mseq = seq.isEmpty()
559                 ? empty()
560                 : MSeq.<T>ofLength(seq.length()).setAll(values);
561         else {
562             final Stream.Builder<T> builder = Stream.builder();
563             values.forEach(builder::add);
564             final Object[] objects = builder.build().toArray();
565 
566             mseq = objects.length == 0
567                 ? empty()
568                 new ArrayMSeq<>(Array.of(ObjectStore.of(objects)));
569         }
570 
571         return mseq;
572     }
573 
574     /**
575      * Creates a new sequence, which is filled with objects created be the given
576      * {@code supplier}.
577      *
578      @since 3.3
579      *
580      @param <T> the element type of the sequence
581      @param supplier the {@code Supplier} which creates the elements, the
582      *        returned sequence is filled with
583      @param length the length of the returned sequence
584      @return a new sequence filled with elements given by the {@code supplier}
585      @throws NegativeArraySizeException if the given {@code length} is
586      *         negative
587      @throws NullPointerException if the given {@code supplier} is
588      *         {@code null}
589      */
590     static <T> MSeq<T> of(
591         final Supplier<? extends T> supplier,
592         final int length
593     ) {
594         requireNonNull(supplier);
595 
596         return length == 0
597             ? empty()
598             : MSeq.<T>ofLength(length).fill(supplier);
599     }
600 
601     /**
602      * Create a new {@code MSeq} from the values of the given {@code Seq}.
603      *
604      @param <T> the element type
605      @param values the array values.
606      @return an new {@code MSeq} with the given values
607      @throws NullPointerException if the {@code values} array is {@code null}.
608      */
609     @SuppressWarnings("unchecked")
610     static <T> MSeq<T> of(final Seq<? extends T> values) {
611         final MSeq<T> result;
612         if (values instanceof MSeq) {
613             result = ((MSeq<T>)values).copy();
614         else if (values instanceof ISeq) {
615             result = ((ISeq<T>)values).copy();
616         else {
617             result = MSeq.<T>ofLength(values.length()).setAll(values);
618         }
619         return result;
620     }
621 
622 }