001 /*
002 * Java Genetic Algorithm Library (jenetics-4.3.0).
003 * Copyright (c) 2007-2018 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 < 0 || (otherStart + (end - start)) > length()) {
166 throw new ArrayIndexOutOfBoundsException(format(
167 "Invalid index range: [%d, %d)",
168 otherStart, otherStart + (end - start)
169 ));
170 }
171
172 if (start < end) {
173 for (int i = end - start; --i >= 0;) {
174 final T temp = get(start + i);
175 set(start + i, other.get(otherStart + i));
176 other.set(otherStart + i, temp);
177 }
178 }
179 }
180
181 /**
182 * Swap the elements at the same position.
183 *
184 * @since 4.0
185 *
186 * @param index the index of swapped element.
187 * @param other the other array to swap the elements with.
188 * @throws IndexOutOfBoundsException if
189 * {@code index < 0 || index >= this.length() || index >= other.length()}.
190 * @throws NullPointerException if the {@code other} sequence is {@code null}
191 */
192 default void swap(final int index, final MSeq<T> other) {
193 final T temp = get(index);
194 set(index, other.get(index));
195 other.set(index, temp);
196 }
197
198 /**
199 * Randomize the {@code array} using the {@link Random} object currently
200 * registered in the {@link RandomRegistry} class. The used shuffling
201 * algorithm is from D. Knuth TAOCP, Seminumerical Algorithms, Third edition,
202 * page 142, Algorithm S (Selection sampling technique).
203 *
204 * @return this shuffled sequence
205 */
206 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 factory methods.
403 * ************************************************************************/
404
405 /**
406 * Single instance of an empty {@code MSeq}.
407 */
408 public static final MSeq<?> EMPTY = EmptyMSeq.INSTANCE;
409
410 /**
411 * Return an empty {@code MSeq}.
412 *
413 * @param <T> the element type of the returned {@code MSeq}.
414 * @return an empty {@code MSeq}.
415 */
416 public static <T> MSeq<T> empty() {
417 return Empty.mseq();
418 }
419
420 /**
421 * Returns a {@code Collector} that accumulates the input elements into a
422 * new {@code MSeq}.
423 *
424 * @param <T> the type of the input elements
425 * @return a {@code Collector} which collects all the input elements into a
426 * {@code MSeq}, in encounter order
427 */
428 public static <T> Collector<T, ?, MSeq<T>> toMSeq() {
429 return Collector.of(
430 (Supplier<List<T>>)ArrayList::new,
431 List::add,
432 (left, right) -> { left.addAll(right); return left; },
433 MSeq::of
434 );
435 }
436
437 /**
438 * Create a new {@code MSeq} with the given {@code length}.
439 *
440 * @param length the length of the created {@code MSeq}.
441 * @param <T> the element type of the new {@code MSeq}.
442 * @return the new mutable sequence.
443 * @throws NegativeArraySizeException if the given {@code length} is
444 * negative
445 */
446 public static <T> MSeq<T> ofLength(final int length) {
447 return length == 0
448 ? empty()
449 : new ArrayMSeq<>(Array.of(ObjectStore.ofLength(length)));
450 }
451
452 /**
453 * Create a new {@code MSeq} from the given values.
454 *
455 * @param <T> the element type
456 * @param values the array values.
457 * @return a new {@code Meq} with the given values.
458 * @throws NullPointerException if the {@code values} array is {@code null}.
459 */
460 @SafeVarargs
461 public static <T> MSeq<T> of(final T... values) {
462 return values.length == 0
463 ? empty()
464 : new ArrayMSeq<>(Array.of(ObjectStore.of(values.clone())));
465 }
466
467 /**
468 * Create a new {@code MSeq} from the given values.
469 *
470 * @param <T> the element type
471 * @param values the array values.
472 * @return a new {@code MSeq} with the given values.
473 * @throws NullPointerException if the {@code values} object is
474 * {@code null}.
475 */
476 @SuppressWarnings("unchecked")
477 public static <T> MSeq<T> of(final Iterable<? extends T> values) {
478 final MSeq<T> mseq;
479 if (values instanceof ISeq) {
480 final ISeq<T> seq = (ISeq<T>)values;
481 mseq = seq.isEmpty() ? empty() : seq.copy();
482 } else if (values instanceof MSeq) {
483 final MSeq<T> seq = (MSeq<T>)values;
484 mseq = seq.isEmpty() ? empty() : MSeq.of(seq);
485 } else if (values instanceof Collection) {
486 final Collection<T> collection = (Collection<T>)values;
487 mseq = collection.isEmpty()
488 ? empty()
489 : MSeq.<T>ofLength(collection.size()).setAll(values);
490 } else {
491 final Stream.Builder<T> builder = Stream.builder();
492 values.forEach(builder::add);
493 final Object[] objects = builder.build().toArray();
494
495 mseq = objects.length == 0
496 ? empty()
497 : new ArrayMSeq<>(Array.of(ObjectStore.of(objects)));
498 }
499
500 return mseq;
501 }
502
503 // /**
504 // * Create a new {@code MSeq} instance from the remaining elements of the
505 // * given iterator.
506 // *
507 // * @since 3.3
508 // *
509 // * @param <T> the element type.
510 // * @return a new {@code MSeq} with the given remaining values.
511 // * @throws NullPointerException if the {@code values} object is
512 // * {@code null}.
513 // */
514 // public static <T> MSeq<T> of(final Iterator<? extends T> values) {
515 // final Stream.Builder<T> builder = Stream.builder();
516 // values.forEachRemaining(builder::add);
517 // final Object[] objects = builder.build().toArray();
518 //
519 // return objects.length == 0
520 // ? empty()
521 // : new ArrayProxyMSeq<>(
522 // new ObjectArrayProxy<>(objects, 0, objects.length));
523 // }
524
525 /**
526 * Creates a new sequence, which is filled with objects created be the given
527 * {@code supplier}.
528 *
529 * @since 3.3
530 *
531 * @param <T> the element type of the sequence
532 * @param supplier the {@code Supplier} which creates the elements, the
533 * returned sequence is filled with
534 * @param length the length of the returned sequence
535 * @return a new sequence filled with elements given by the {@code supplier}
536 * @throws NegativeArraySizeException if the given {@code length} is
537 * negative
538 * @throws NullPointerException if the given {@code supplier} is
539 * {@code null}
540 */
541 public static <T> MSeq<T> of(
542 final Supplier<? extends T> supplier,
543 final int length
544 ) {
545 requireNonNull(supplier);
546
547 return length == 0
548 ? empty()
549 : MSeq.<T>ofLength(length).fill(supplier);
550 }
551
552 /**
553 * Create a new {@code MSeq} from the values of the given {@code Seq}.
554 *
555 * @param <T> the element type
556 * @param values the array values.
557 * @return an new {@code MSeq} with the given values
558 * @throws NullPointerException if the {@code values} array is {@code null}.
559 */
560 @SuppressWarnings("unchecked")
561 public static <T> MSeq<T> of(final Seq<? extends T> values) {
562 final MSeq<T> result;
563 if (values instanceof MSeq) {
564 result = ((MSeq<T>)values).copy();
565 } else if (values instanceof ISeq) {
566 result = ((ISeq<T>)values).copy();
567 } else {
568 result = MSeq.<T>ofLength(values.length()).setAll(values);
569 }
570 return result;
571 }
572
573 }
|