001 /*
002 * Java Genetic Algorithm Library (jenetics-3.8.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@gmx.at)
019 */
020 package org.jenetics.util;
021
022 import static java.lang.String.format;
023 import static java.util.Objects.requireNonNull;
024
025 import java.util.ArrayList;
026 import java.util.Collection;
027 import java.util.Comparator;
028 import java.util.Iterator;
029 import java.util.List;
030 import java.util.ListIterator;
031 import java.util.Random;
032 import java.util.function.Function;
033 import java.util.function.Supplier;
034 import java.util.stream.Collector;
035 import java.util.stream.Stream;
036
037 import org.jenetics.internal.collection.Array;
038 import org.jenetics.internal.collection.ArrayMSeq;
039 import org.jenetics.internal.collection.Empty;
040 import org.jenetics.internal.collection.ObjectStore;
041
042 /**
043 * Mutable, ordered, fixed sized sequence.
044 *
045 * <p>
046 * <b>Implementation note:</b>
047 * <i>This implementation is not thread safe. All {@link ISeq} and {@link MSeq}
048 * instances created by {@link MSeq#toISeq} and {@link MSeq#subSeq(int)},
049 * respectively, must be protected by the same lock, when they are accessed
050 * (get/set) by different threads.</i>
051 *
052 * @see ISeq
053 *
054 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
055 * @since 1.0
056 * @version 3.4
057 */
058 public interface MSeq<T> extends Seq<T>, Copyable<MSeq<T>> {
059
060 public default List<T> asList() {
061 return new MSeqList<>(this);
062 }
063
064 /**
065 * Set the {@code value} at the given {@code index}.
066 *
067 * @param index the index of the new value.
068 * @param value the new value.
069 * @throws IndexOutOfBoundsException if the index is out of range
070 * {@code (index < 0 || index >= size())}.
071 */
072 public void set(final int index, final T value);
073
074 /**
075 * Fills the sequence with values of the given iterator.
076 *
077 * @param it the iterator of the values to fill this sequence.
078 * @return {@code this} sequence.
079 */
080 public default MSeq<T> setAll(final Iterator<? extends T> it) {
081 for (int i = 0, n = length(); i < n && it.hasNext(); ++i) {
082 set(i, it.next());
083 }
084 return this;
085 }
086
087 /**
088 * Fills the sequence with values of the given iterable.
089 *
090 * @param values the values to fill this sequence.
091 * @return {@code this} sequence.
092 */
093 public default MSeq<T> setAll(final Iterable<? extends T> values) {
094 setAll(values.iterator());
095 return this;
096 }
097
098 /**
099 * Fill the sequence with the given values.
100 *
101 * @param values the first initial values of this sequence
102 * @return {@code this} sequence.
103 */
104 public default MSeq<T> setAll(final T[] values) {
105 for (int i = 0, n = length(); i < n && i < values.length; ++i) {
106 set(i, values[i]);
107 }
108 return this;
109 }
110
111 /**
112 * Fill the sequence with values generated by the given factory.
113 *
114 * @param supplier the value factory.
115 * @return {@code this} sequence.
116 * @throws NullPointerException if the given {@code factory} is {@code null}.
117 */
118 public default MSeq<T> fill(final Supplier<? extends T> supplier) {
119 for (int i = 0, n = length(); i < n; ++i) {
120 set(i, supplier.get());
121 }
122 return this;
123 }
124
125 /**
126 * Swap the elements at the two positions.
127 *
128 * @param i the index of the first element.
129 * @param j the index of the second element.
130 * @throws IndexOutOfBoundsException if {@code i < 0 || j >= length()}.
131 */
132 public default void swap(final int i, final int j) {
133 final T temp = get(i);
134 set(i, get(j));
135 set(j, temp);
136 }
137
138 /**
139 * Swap a given range with a range of the same size with another array.
140 *
141 * <pre>
142 * start end
143 * | |
144 * this: +---+---+---+---+---+---+---+---+---+---+---+---+
145 * +---------------+
146 * +---------------+
147 * other: +---+---+---+---+---+---+---+---+---+---+---+---+
148 * |
149 * otherStart
150 * </pre>
151 *
152 * @param start the start index of {@code this} range, inclusively.
153 * @param end the end index of {@code this} range, exclusively.
154 * @param other the other array to swap the elements with.
155 * @param otherStart the start index of the {@code other} array.
156 * @throws IndexOutOfBoundsException if {@code start > end} or
157 * if {@code start < 0 || end >= this.length() || otherStart < 0 ||
158 * otherStart + (end - start) >= other.length()}
159 */
160 public default void swap(
161 final int start, final int end,
162 final MSeq<T> other, final int otherStart
163 ) {
164 if (otherStart < 0 || (otherStart + (end - start)) > length()) {
165 throw new ArrayIndexOutOfBoundsException(format(
166 "Invalid index range: [%d, %d)",
167 otherStart, otherStart + (end - start)
168 ));
169 }
170
171 if (start < end) {
172 for (int i = end - start; --i >= 0;) {
173 final T temp = get(start + i);
174 set(start + i, other.get(otherStart + i));
175 other.set(otherStart + i, temp);
176 }
177 }
178 }
179
180 /**
181 * Randomize the {@code array} using the {@link Random} object currently
182 * registered in the {@link RandomRegistry} class. The used shuffling
183 * algorithm is from D. Knuth TAOCP, Seminumerical Algorithms, Third edition,
184 * page 142, Algorithm S (Selection sampling technique).
185 *
186 * @return this shuffled sequence
187 */
188 public default MSeq<T> shuffle() {
189 return shuffle(RandomRegistry.getRandom());
190 }
191
192 /**
193 * Randomize the {@code array} using the given {@link Random} object. The used
194 * shuffling algorithm is from D. Knuth TAOCP, Seminumerical Algorithms,
195 * Third edition, page 142, Algorithm S (Selection sampling technique).
196 *
197 * @param random the {@link Random} object to use for randomize.
198 * @return this shuffled sequence
199 * @throws NullPointerException if the random object is {@code null}.
200 */
201 public default MSeq<T> shuffle(final Random random) {
202 for (int j = length() - 1; j > 0; --j) {
203 swap(j, random.nextInt(j + 1));
204 }
205 return this;
206 }
207
208 /**
209 * Sorts this sequence according to the order induced by the specified
210 * {@link Comparator}.
211 *
212 * <p>All elements in this sequence must be <i>mutually comparable</i> using
213 * the specified comparator (that is, {@code c.compare(e1, e2)} must not
214 * throw a {@code ClassCastException} for any elements {@code e1} and
215 * {@code e2} in the sequence).
216 *
217 * <p>If the specified comparator is {@code null} then all elements in this
218 * list must implement the {@link Comparable} interface and the elements'
219 * Comparable natural ordering should be used.
220 *
221 * @param start the start index where to start sorting (inclusively)
222 * @param end the end index where to stop sorting (exclusively)
223 * @param comparator the {@code Comparator} used to compare sequence elements.
224 * A {@code null} value indicates that the elements' Comparable
225 * natural ordering should be used
226 * @throws ClassCastException if the sequence contains elements that are not
227 * <i>mutually comparable</i> using the specified comparator
228 * @return {@code this} sequence
229 */
230 public MSeq<T> sort(
231 final int start,
232 final int end,
233 final Comparator<? super T> comparator
234 );
235
236 /**
237 * Sorts this sequence according to the natural order of the elements.
238 *
239 * @param start the start index where to start sorting (inclusively)
240 * @param end the end index where to stop sorting (exclusively)
241 * @throws ClassCastException if the sequence contains elements that are not
242 * <i>mutually comparable</i> using the specified comparator
243 * @return {@code this} sequence
244 */
245 public default MSeq<T> sort(final int start, final int end) {
246 return sort(start, end, null);
247 }
248
249 /**
250 * Sorts this sequence according to the order induced by the specified
251 * {@link Comparator}.
252 *
253 * <p>All elements in this sequence must be <i>mutually comparable</i> using
254 * the specified comparator (that is, {@code c.compare(e1, e2)} must not
255 * throw a {@code ClassCastException} for any elements {@code e1} and
256 * {@code e2} in the sequence).
257 *
258 * <p>If the specified comparator is {@code null} then all elements in this
259 * list must implement the {@link Comparable} interface and the elements'
260 * Comparable natural ordering should be used.
261 *
262 * @param start the start index where to start sorting (inclusively)
263 * @param comparator the {@code Comparator} used to compare sequence elements.
264 * A {@code null} value indicates that the elements' Comparable
265 * natural ordering should be used
266 * @throws ClassCastException if the sequence contains elements that are not
267 * <i>mutually comparable</i> using the specified comparator
268 * @return {@code this} sequence
269 */
270 public default MSeq<T> sort(
271 final int start,
272 final Comparator<? super T> comparator
273 ) {
274 return sort(start, length(), comparator);
275 }
276
277 /**
278 * Sorts this sequence according to the natural order of the elements.
279 *
280 * @param start the start index where to start sorting (inclusively)
281 * @throws ClassCastException if the sequence contains elements that are not
282 * <i>mutually comparable</i> using the specified comparator
283 * @return {@code this} sequence
284 */
285 public default MSeq<T> sort(final int start) {
286 return sort(start, length(), null);
287 }
288
289 /**
290 * Sorts this sequence according to the order induced by the specified
291 * {@link Comparator}.
292 *
293 * <p>All elements in this sequence must be <i>mutually comparable</i> using
294 * the specified comparator (that is, {@code c.compare(e1, e2)} must not
295 * throw a {@code ClassCastException} for any elements {@code e1} and
296 * {@code e2} in the sequence).
297 *
298 * <p>If the specified comparator is {@code null} then all elements in this
299 * list must implement the {@link Comparable} interface and the elements'
300 * Comparable natural ordering should be used.
301 *
302 * @param comparator the {@code Comparator} used to compare sequence elements.
303 * A {@code null} value indicates that the elements' Comparable
304 * natural ordering should be used
305 * @throws ClassCastException if the sequence contains elements that are not
306 * <i>mutually comparable</i> using the specified comparator
307 * @return {@code this} sequence
308 */
309 public default MSeq<T> sort(final Comparator<? super T> comparator) {
310 return sort(0, length(), comparator);
311 }
312
313 /**
314 * Sorts this sequence according to the natural order of the elements.
315 *
316 * @throws ClassCastException if the sequence contains elements that are not
317 * <i>mutually comparable</i> using the specified comparator
318 * @return {@code this} sequence
319 */
320 public default MSeq<T> sort() {
321 return sort(0, length(), null);
322 }
323
324 /**
325 * Reverses the order of the elements this sequence (in place).
326 *
327 * @return this sequence with reverse order or the elements
328 */
329 public default MSeq<T> reverse() {
330 for (int i = 0, j = length() - 1; i < j; ++i, --j) {
331 swap(i, j);
332 }
333 return this;
334 }
335
336 /**
337 * Returns a list iterator over the elements in this sequence (in proper
338 * sequence).
339 *
340 * @return a list iterator over the elements in this list (in proper
341 * sequence)
342 */
343 public default ListIterator<T> listIterator() {
344 return asList().listIterator();
345 }
346
347 @Override
348 public MSeq<T> subSeq(final int start, final int end);
349
350 @Override
351 public MSeq<T> subSeq(final int start);
352
353 @Override
354 public <B> MSeq<B> map(final Function<? super T, ? extends B> mapper);
355
356 @SuppressWarnings("unchecked")
357 @Override
358 public default MSeq<T> append(final T... values) {
359 return append(MSeq.of(values));
360 }
361
362 @Override
363 public MSeq<T> append(final Iterable<? extends T> values);
364
365 @SuppressWarnings("unchecked")
366 @Override
367 public default MSeq<T> prepend(final T... values) {
368 return prepend(MSeq.of(values));
369 }
370
371 @Override
372 public MSeq<T> prepend(final Iterable<? extends T> values);
373
374 /**
375 * Return a read-only projection of this sequence. Changes to the original
376 * sequence will not influence the returned {@code ISeq}.
377 *
378 * @return a read-only projection of this sequence
379 */
380 public ISeq<T> toISeq();
381
382
383 /* *************************************************************************
384 * Some static factory methods.
385 * ************************************************************************/
386
387 /**
388 * Single instance of an empty {@code MSeq}.
389 */
390 public static final MSeq<?> EMPTY = Empty.MSEQ;
391
392 /**
393 * Return an empty {@code MSeq}.
394 *
395 * @param <T> the element type of the returned {@code MSeq}.
396 * @return an empty {@code MSeq}.
397 */
398 public static <T> MSeq<T> empty() {
399 return Empty.mseq();
400 }
401
402 /**
403 * Returns a {@code Collector} that accumulates the input elements into a
404 * new {@code MSeq}.
405 *
406 * @param <T> the type of the input elements
407 * @return a {@code Collector} which collects all the input elements into a
408 * {@code MSeq}, in encounter order
409 */
410 public static <T> Collector<T, ?, MSeq<T>> toMSeq() {
411 return Collector.of(
412 (Supplier<List<T>>)ArrayList::new,
413 List::add,
414 (left, right) -> { left.addAll(right); return left; },
415 MSeq::of
416 );
417 }
418
419 /**
420 * Create a new {@code MSeq} with the given {@code length}.
421 *
422 * @param length the length of the created {@code MSeq}.
423 * @param <T> the element type of the new {@code MSeq}.
424 * @return the new mutable sequence.
425 * @throws NegativeArraySizeException if the given {@code length} is
426 * negative
427 */
428 public static <T> MSeq<T> ofLength(final int length) {
429 return length == 0
430 ? empty()
431 : new ArrayMSeq<>(Array.of(ObjectStore.ofLength(length)));
432 }
433
434 /**
435 * Create a new {@code MSeq} from the given values.
436 *
437 * @param <T> the element type
438 * @param values the array values.
439 * @return a new {@code Meq} with the given values.
440 * @throws NullPointerException if the {@code values} array is {@code null}.
441 */
442 @SafeVarargs
443 public static <T> MSeq<T> of(final T... values) {
444 return values.length == 0
445 ? empty()
446 : new ArrayMSeq<>(Array.of(ObjectStore.of(values.clone())));
447 }
448
449 /**
450 * Create a new {@code MSeq} from the given values.
451 *
452 * @param <T> the element type
453 * @param values the array values.
454 * @return a new {@code MSeq} with the given values.
455 * @throws NullPointerException if the {@code values} object is
456 * {@code null}.
457 */
458 @SuppressWarnings("unchecked")
459 public static <T> MSeq<T> of(final Iterable<? extends T> values) {
460 final MSeq<T> mseq;
461 if (values instanceof ISeq<?>) {
462 final ISeq<T> seq = (ISeq<T>)values;
463 mseq = seq.isEmpty() ? empty() : seq.copy();
464 } else if (values instanceof MSeq<?>) {
465 final MSeq<T> seq = (MSeq<T>)values;
466 mseq = seq.isEmpty() ? empty() : MSeq.of(seq);
467 } else if (values instanceof Collection<?>) {
468 final Collection<T> collection = (Collection<T>)values;
469 mseq = collection.isEmpty()
470 ? empty()
471 : MSeq.<T>ofLength(collection.size()).setAll(values);
472 } else {
473 final Stream.Builder<T> builder = Stream.builder();
474 values.forEach(builder::add);
475 final Object[] objects = builder.build().toArray();
476
477 mseq = objects.length == 0
478 ? empty()
479 : new ArrayMSeq<>(Array.of(ObjectStore.of(objects)));
480 }
481
482 return mseq;
483 }
484
485 // /**
486 // * Create a new {@code MSeq} instance from the remaining elements of the
487 // * given iterator.
488 // *
489 // * @since 3.3
490 // *
491 // * @param <T> the element type.
492 // * @return a new {@code MSeq} with the given remaining values.
493 // * @throws NullPointerException if the {@code values} object is
494 // * {@code null}.
495 // */
496 // public static <T> MSeq<T> of(final Iterator<? extends T> values) {
497 // final Stream.Builder<T> builder = Stream.builder();
498 // values.forEachRemaining(builder::add);
499 // final Object[] objects = builder.build().toArray();
500 //
501 // return objects.length == 0
502 // ? empty()
503 // : new ArrayProxyMSeq<>(
504 // new ObjectArrayProxy<>(objects, 0, objects.length));
505 // }
506
507 /**
508 * Creates a new sequence, which is filled with objects created be the given
509 * {@code supplier}.
510 *
511 * @since 3.3
512 *
513 * @param <T> the element type of the sequence
514 * @param supplier the {@code Supplier} which creates the elements, the
515 * returned sequence is filled with
516 * @param length the length of the returned sequence
517 * @return a new sequence filled with elements given by the {@code supplier}
518 * @throws NegativeArraySizeException if the given {@code length} is
519 * negative
520 * @throws NullPointerException if the given {@code supplier} is
521 * {@code null}
522 */
523 public static <T> MSeq<T> of(
524 final Supplier<? extends T> supplier,
525 final int length
526 ) {
527 requireNonNull(supplier);
528
529 return length == 0
530 ? empty()
531 : MSeq.<T>ofLength(length).fill(supplier);
532 }
533
534 /**
535 * Create a new {@code MSeq} from the values of the given {@code Seq}.
536 *
537 * @param <T> the element type
538 * @param values the array values.
539 * @return an new {@code MSeq} with the given values
540 * @throws NullPointerException if the {@code values} array is {@code null}.
541 */
542 public static <T> MSeq<T> of(final Seq<T> values) {
543 return values instanceof ArrayMSeq<?>
544 ? ((ArrayMSeq<T>)values).copy()
545 : MSeq.<T>ofLength(values.length()).setAll(values);
546 }
547
548 }
|