001 /*
002 * Java Genetic Algorithm Library (jenetics-4.0.0).
003 * Copyright (c) 2007-2017 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 * <p>
048 * <b>Implementation note:</b>
049 * <i>This implementation is not thread safe. All {@link ISeq} and {@link MSeq}
050 * instances created by {@link MSeq#toISeq} and {@link MSeq#subSeq(int)},
051 * respectively, must be protected by the same lock, when they are accessed
052 * (get/set) by different threads.</i>
053 *
054 * @see ISeq
055 *
056 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
057 * @since 1.0
058 * @version 3.4
059 */
060 public interface MSeq<T> extends Seq<T>, Copyable<MSeq<T>> {
061
062 public 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 public 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 public 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 public 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 public 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 public 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 public 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 public 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 Random} 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 public default MSeq<T> shuffle() {
208 return shuffle(RandomRegistry.getRandom());
209 }
210
211 /**
212 * Randomize the {@code array} using the given {@link Random} 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 Random} object to use for randomize.
217 * @return this shuffled sequence
218 * @throws NullPointerException if the random object is {@code null}.
219 */
220 public default MSeq<T> shuffle(final Random 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 public 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 public 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 public 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 public 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 public 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 public 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 public 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 public default ListIterator<T> listIterator() {
363 return asList().listIterator();
364 }
365
366 @Override
367 public MSeq<T> subSeq(final int start, final int end);
368
369 @Override
370 public MSeq<T> subSeq(final int start);
371
372 @Override
373 public <B> MSeq<B> map(final Function<? super T, ? extends B> mapper);
374
375 @SuppressWarnings("unchecked")
376 @Override
377 public default MSeq<T> append(final T... values) {
378 return append(MSeq.of(values));
379 }
380
381 @Override
382 public MSeq<T> append(final Iterable<? extends T> values);
383
384 @SuppressWarnings("unchecked")
385 @Override
386 public default MSeq<T> prepend(final T... values) {
387 return prepend(MSeq.of(values));
388 }
389
390 @Override
391 public 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 public ISeq<T> toISeq();
400
401
402 /* *************************************************************************
403 * Some static factory methods.
404 * ************************************************************************/
405
406 /**
407 * Single instance of an empty {@code MSeq}.
408 */
409 public static final MSeq<?> EMPTY = EmptyMSeq.INSTANCE;
410
411 /**
412 * Return an empty {@code MSeq}.
413 *
414 * @param <T> the element type of the returned {@code MSeq}.
415 * @return an empty {@code MSeq}.
416 */
417 public static <T> MSeq<T> empty() {
418 return Empty.mseq();
419 }
420
421 /**
422 * Returns a {@code Collector} that accumulates the input elements into a
423 * new {@code MSeq}.
424 *
425 * @param <T> the type of the input elements
426 * @return a {@code Collector} which collects all the input elements into a
427 * {@code MSeq}, in encounter order
428 */
429 public static <T> Collector<T, ?, MSeq<T>> toMSeq() {
430 return Collector.of(
431 (Supplier<List<T>>)ArrayList::new,
432 List::add,
433 (left, right) -> { left.addAll(right); return left; },
434 MSeq::of
435 );
436 }
437
438 /**
439 * Create a new {@code MSeq} with the given {@code length}.
440 *
441 * @param length the length of the created {@code MSeq}.
442 * @param <T> the element type of the new {@code MSeq}.
443 * @return the new mutable sequence.
444 * @throws NegativeArraySizeException if the given {@code length} is
445 * negative
446 */
447 public static <T> MSeq<T> ofLength(final int length) {
448 return length == 0
449 ? empty()
450 : new ArrayMSeq<>(Array.of(ObjectStore.ofLength(length)));
451 }
452
453 /**
454 * Create a new {@code MSeq} from the given values.
455 *
456 * @param <T> the element type
457 * @param values the array values.
458 * @return a new {@code Meq} with the given values.
459 * @throws NullPointerException if the {@code values} array is {@code null}.
460 */
461 @SafeVarargs
462 public static <T> MSeq<T> of(final T... values) {
463 return values.length == 0
464 ? empty()
465 : new ArrayMSeq<>(Array.of(ObjectStore.of(values.clone())));
466 }
467
468 /**
469 * Create a new {@code MSeq} from the given values.
470 *
471 * @param <T> the element type
472 * @param values the array values.
473 * @return a new {@code MSeq} with the given values.
474 * @throws NullPointerException if the {@code values} object is
475 * {@code null}.
476 */
477 @SuppressWarnings("unchecked")
478 public static <T> MSeq<T> of(final Iterable<? extends T> values) {
479 final MSeq<T> mseq;
480 if (values instanceof ISeq<?>) {
481 final ISeq<T> seq = (ISeq<T>)values;
482 mseq = seq.isEmpty() ? empty() : seq.copy();
483 } else if (values instanceof MSeq<?>) {
484 final MSeq<T> seq = (MSeq<T>)values;
485 mseq = seq.isEmpty() ? empty() : MSeq.of(seq);
486 } else if (values instanceof Collection<?>) {
487 final Collection<T> collection = (Collection<T>)values;
488 mseq = collection.isEmpty()
489 ? empty()
490 : MSeq.<T>ofLength(collection.size()).setAll(values);
491 } else {
492 final Stream.Builder<T> builder = Stream.builder();
493 values.forEach(builder::add);
494 final Object[] objects = builder.build().toArray();
495
496 mseq = objects.length == 0
497 ? empty()
498 : new ArrayMSeq<>(Array.of(ObjectStore.of(objects)));
499 }
500
501 return mseq;
502 }
503
504 // /**
505 // * Create a new {@code MSeq} instance from the remaining elements of the
506 // * given iterator.
507 // *
508 // * @since 3.3
509 // *
510 // * @param <T> the element type.
511 // * @return a new {@code MSeq} with the given remaining values.
512 // * @throws NullPointerException if the {@code values} object is
513 // * {@code null}.
514 // */
515 // public static <T> MSeq<T> of(final Iterator<? extends T> values) {
516 // final Stream.Builder<T> builder = Stream.builder();
517 // values.forEachRemaining(builder::add);
518 // final Object[] objects = builder.build().toArray();
519 //
520 // return objects.length == 0
521 // ? empty()
522 // : new ArrayProxyMSeq<>(
523 // new ObjectArrayProxy<>(objects, 0, objects.length));
524 // }
525
526 /**
527 * Creates a new sequence, which is filled with objects created be the given
528 * {@code supplier}.
529 *
530 * @since 3.3
531 *
532 * @param <T> the element type of the sequence
533 * @param supplier the {@code Supplier} which creates the elements, the
534 * returned sequence is filled with
535 * @param length the length of the returned sequence
536 * @return a new sequence filled with elements given by the {@code supplier}
537 * @throws NegativeArraySizeException if the given {@code length} is
538 * negative
539 * @throws NullPointerException if the given {@code supplier} is
540 * {@code null}
541 */
542 public static <T> MSeq<T> of(
543 final Supplier<? extends T> supplier,
544 final int length
545 ) {
546 requireNonNull(supplier);
547
548 return length == 0
549 ? empty()
550 : MSeq.<T>ofLength(length).fill(supplier);
551 }
552
553 /**
554 * Create a new {@code MSeq} from the values of the given {@code Seq}.
555 *
556 * @param <T> the element type
557 * @param values the array values.
558 * @return an new {@code MSeq} with the given values
559 * @throws NullPointerException if the {@code values} array is {@code null}.
560 */
561 @SuppressWarnings("unchecked")
562 public static <T> MSeq<T> of(final Seq<? extends T> values) {
563 return values instanceof MSeq<?>
564 ? ((MSeq<T>)values).copy()
565 : MSeq.<T>ofLength(values.length()).setAll(values);
566 }
567
568 }
|