MSeq.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-5.1.0).
003  * Copyright (c) 2007-2019 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 4.2
058  */
059 public interface MSeq<T> extends Seq<T>, Copyable<MSeq<T>> {
060 
061     public 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     public 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     public 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     public 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     public 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     public 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     public 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     public default void swap(
162         final int start, final int end,
163         final MSeq<T> other, final int otherStart
164     ) {
165         if (otherStart < || (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     public 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     public default MSeq<T> shuffle() {
207         return shuffle(RandomRegistry.getRandom());
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     public 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     public 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     public 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     public 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     public 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     public 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     public 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     public 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     public default ListIterator<T> listIterator() {
362         return asList().listIterator();
363     }
364 
365     @Override
366     public MSeq<T> subSeq(final int start, final int end);
367 
368     @Override
369     public MSeq<T> subSeq(final int start);
370 
371     @Override
372     public <B> MSeq<B> map(final Function<? super T, ? extends B> mapper);
373 
374     @SuppressWarnings("unchecked")
375     @Override
376     public default MSeq<T> append(final T... values) {
377         return append(MSeq.of(values));
378     }
379 
380     @Override
381     public MSeq<T> append(final Iterable<? extends T> values);
382 
383     @SuppressWarnings("unchecked")
384     @Override
385     public default MSeq<T> prepend(final T... values) {
386         return prepend(MSeq.of(values));
387     }
388 
389     @Override
390     public 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     public 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     public 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     public 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     public 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     public static final 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     public 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     public 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     public 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     public 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     public 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 {
556             final Stream.Builder<T> builder = Stream.builder();
557             values.forEach(builder::add);
558             final Object[] objects = builder.build().toArray();
559 
560             mseq = objects.length == 0
561                 ? empty()
562                 new ArrayMSeq<>(Array.of(ObjectStore.of(objects)));
563         }
564 
565         return mseq;
566     }
567 
568 //    /**
569 //     * Create a new {@code MSeq} instance from the remaining elements of the
570 //     * given iterator.
571 //     *
572 //     * @since 3.3
573 //     *
574 //     * @param <T> the element type.
575 //     * @return a new {@code MSeq} with the given remaining values.
576 //     * @throws NullPointerException if the {@code values} object is
577 //     *        {@code null}.
578 //     */
579 //    public static <T> MSeq<T> of(final Iterator<? extends T> values) {
580 //        final Stream.Builder<T> builder = Stream.builder();
581 //        values.forEachRemaining(builder::add);
582 //        final Object[] objects = builder.build().toArray();
583 //
584 //        return objects.length == 0
585 //            ? empty()
586 //            : new ArrayProxyMSeq<>(
587 //                new ObjectArrayProxy<>(objects, 0, objects.length));
588 //    }
589 
590     /**
591      * Creates a new sequence, which is filled with objects created be the given
592      * {@code supplier}.
593      *
594      @since 3.3
595      *
596      @param <T> the element type of the sequence
597      @param supplier the {@code Supplier} which creates the elements, the
598      *        returned sequence is filled with
599      @param length the length of the returned sequence
600      @return a new sequence filled with elements given by the {@code supplier}
601      @throws NegativeArraySizeException if the given {@code length} is
602      *         negative
603      @throws NullPointerException if the given {@code supplier} is
604      *         {@code null}
605      */
606     public static <T> MSeq<T> of(
607         final Supplier<? extends T> supplier,
608         final int length
609     ) {
610         requireNonNull(supplier);
611 
612         return length == 0
613             ? empty()
614             : MSeq.<T>ofLength(length).fill(supplier);
615     }
616 
617     /**
618      * Create a new {@code MSeq} from the values of the given {@code Seq}.
619      *
620      @param <T> the element type
621      @param values the array values.
622      @return an new {@code MSeq} with the given values
623      @throws NullPointerException if the {@code values} array is {@code null}.
624      */
625     @SuppressWarnings("unchecked")
626     public static <T> MSeq<T> of(final Seq<? extends T> values) {
627         final MSeq<T> result;
628         if (values instanceof MSeq) {
629             result = ((MSeq<T>)values).copy();
630         else if (values instanceof ISeq) {
631             result = ((ISeq<T>)values).copy();
632         else {
633             result = MSeq.<T>ofLength(values.length()).setAll(values);
634         }
635         return result;
636     }
637 
638 }