001 /*
002 * Java Genetic Algorithm Library (jenetics-3.5.0).
003 * Copyright (c) 2007-2016 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.Iterator;
028 import java.util.List;
029 import java.util.ListIterator;
030 import java.util.Random;
031 import java.util.function.Function;
032 import java.util.function.Supplier;
033 import java.util.stream.Collector;
034 import java.util.stream.Stream;
035
036 import org.jenetics.internal.collection.Array;
037 import org.jenetics.internal.collection.ArrayMSeq;
038 import org.jenetics.internal.collection.Empty;
039 import org.jenetics.internal.collection.ObjectStore;
040
041 /**
042 * Mutable, ordered, fixed sized sequence.
043 *
044 * <p>
045 * <b>Implementation note:</b>
046 * <i>This implementation is not thread safe. All {@link ISeq} and {@link MSeq}
047 * instances created by {@link MSeq#toISeq} and {@link MSeq#subSeq(int)},
048 * respectively, must be protected by the same lock, when they are accessed
049 * (get/set) by different threads.</i>
050 *
051 * @see ISeq
052 *
053 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
054 * @since 1.0
055 * @version 3.4
056 */
057 public interface MSeq<T> extends Seq<T>, Copyable<MSeq<T>> {
058
059 public default List<T> asList() {
060 return new MSeqList<>(this);
061 }
062
063 /**
064 * Set the {@code value} at the given {@code index}.
065 *
066 * @param index the index of the new value.
067 * @param value the new value.
068 * @throws IndexOutOfBoundsException if the index is out of range
069 * {@code (index < 0 || index >= size())}.
070 */
071 public void set(final int index, final T value);
072
073 /**
074 * Fills the sequence with values of the given iterator.
075 *
076 * @param it the iterator of the values to fill this sequence.
077 * @return {@code this} sequence.
078 */
079 public default MSeq<T> setAll(final Iterator<? extends T> it) {
080 for (int i = 0, n = length(); i < n && it.hasNext(); ++i) {
081 set(i, it.next());
082 }
083 return this;
084 }
085
086 /**
087 * Fills the sequence with values of the given iterable.
088 *
089 * @param values the values to fill this sequence.
090 * @return {@code this} sequence.
091 */
092 public default MSeq<T> setAll(final Iterable<? extends T> values) {
093 setAll(values.iterator());
094 return this;
095 }
096
097 /**
098 * Fill the sequence with the given values.
099 *
100 * @param values the first initial values of this sequence
101 * @return {@code this} sequence.
102 */
103 public default MSeq<T> setAll(final T[] values) {
104 for (int i = 0, n = length(); i < n && i < values.length; ++i) {
105 set(i, values[i]);
106 }
107 return this;
108 }
109
110 /**
111 * Fill the sequence with values generated by the given factory.
112 *
113 * @param supplier the value factory.
114 * @return {@code this} sequence.
115 * @throws NullPointerException if the given {@code factory} is {@code null}.
116 */
117 public default MSeq<T> fill(final Supplier<? extends T> supplier) {
118 for (int i = 0, n = length(); i < n; ++i) {
119 set(i, supplier.get());
120 }
121 return this;
122 }
123
124 /**
125 * Swap the elements at the two positions.
126 *
127 * @param i the index of the first element.
128 * @param j the index of the second element.
129 * @throws IndexOutOfBoundsException if {@code i < 0 || j >= length()}.
130 */
131 public default void swap(final int i, final int j) {
132 final T temp = get(i);
133 set(i, get(j));
134 set(j, temp);
135 }
136
137 /**
138 * Swap a given range with a range of the same size with another array.
139 *
140 * <pre>
141 * start end
142 * | |
143 * this: +---+---+---+---+---+---+---+---+---+---+---+---+
144 * +---------------+
145 * +---------------+
146 * other: +---+---+---+---+---+---+---+---+---+---+---+---+
147 * |
148 * otherStart
149 * </pre>
150 *
151 * @param start the start index of {@code this} range, inclusively.
152 * @param end the end index of {@code this} range, exclusively.
153 * @param other the other array to swap the elements with.
154 * @param otherStart the start index of the {@code other} array.
155 * @throws IndexOutOfBoundsException if {@code start > end} or
156 * if {@code start < 0 || end >= this.length() || otherStart < 0 ||
157 * otherStart + (end - start) >= other.length()}
158 */
159 public default void swap(
160 final int start, final int end,
161 final MSeq<T> other, final int otherStart
162 ) {
163 if (otherStart < 0 || (otherStart + (end - start)) > length()) {
164 throw new ArrayIndexOutOfBoundsException(format(
165 "Invalid index range: [%d, %d)",
166 otherStart, otherStart + (end - start)
167 ));
168 }
169
170 if (start < end) {
171 for (int i = end - start; --i >= 0;) {
172 final T temp = get(start + i);
173 set(start + i, other.get(otherStart + i));
174 other.set(otherStart + i, temp);
175 }
176 }
177 }
178
179 /**
180 * Randomize the {@code array} using the {@link Random} object currently
181 * registered in the {@link RandomRegistry} class. The used shuffling
182 * algorithm is from D. Knuth TAOCP, Seminumerical Algorithms, Third edition,
183 * page 142, Algorithm S (Selection sampling technique).
184 *
185 * @return this shuffled sequence
186 */
187 public default MSeq<T> shuffle() {
188 return shuffle(RandomRegistry.getRandom());
189 }
190
191 /**
192 * Randomize the {@code array} using the given {@link Random} object. The used
193 * shuffling algorithm is from D. Knuth TAOCP, Seminumerical Algorithms,
194 * Third edition, page 142, Algorithm S (Selection sampling technique).
195 *
196 * @param random the {@link Random} object to use for randomize.
197 * @return this shuffled sequence
198 * @throws NullPointerException if the random object is {@code null}.
199 */
200 public default MSeq<T> shuffle(final Random random) {
201 for (int j = length() - 1; j > 0; --j) {
202 swap(j, random.nextInt(j + 1));
203 }
204 return this;
205 }
206
207 /**
208 * Returns a list iterator over the elements in this sequence (in proper
209 * sequence).
210 *
211 * @return a list iterator over the elements in this list (in proper
212 * sequence)
213 */
214 public default ListIterator<T> listIterator() {
215 return asList().listIterator();
216 }
217
218 @Override
219 public MSeq<T> subSeq(final int start, final int end);
220
221 @Override
222 public MSeq<T> subSeq(final int start);
223
224 @Override
225 public <B> MSeq<B> map(final Function<? super T, ? extends B> mapper);
226
227 @SuppressWarnings("unchecked")
228 @Override
229 public default MSeq<T> append(final T... values) {
230 return append(MSeq.of(values));
231 }
232
233 @Override
234 public MSeq<T> append(final Iterable<? extends T> values);
235
236 @SuppressWarnings("unchecked")
237 @Override
238 public default MSeq<T> prepend(final T... values) {
239 return prepend(MSeq.of(values));
240 }
241
242 @Override
243 public MSeq<T> prepend(final Iterable<? extends T> values);
244
245 /**
246 * Return a read-only projection of this sequence. Changes to the original
247 * sequence will not influence the returned {@code ISeq}.
248 *
249 * @return a read-only projection of this sequence
250 */
251 public ISeq<T> toISeq();
252
253
254 /* *************************************************************************
255 * Some static factory methods.
256 * ************************************************************************/
257
258 /**
259 * Single instance of an empty {@code MSeq}.
260 */
261 public static final MSeq<?> EMPTY = Empty.MSEQ;
262
263 /**
264 * Return an empty {@code MSeq}.
265 *
266 * @param <T> the element type of the returned {@code MSeq}.
267 * @return an empty {@code MSeq}.
268 */
269 public static <T> MSeq<T> empty() {
270 return Empty.mseq();
271 }
272
273 /**
274 * Returns a {@code Collector} that accumulates the input elements into a
275 * new {@code MSeq}.
276 *
277 * @param <T> the type of the input elements
278 * @return a {@code Collector} which collects all the input elements into a
279 * {@code MSeq}, in encounter order
280 */
281 public static <T> Collector<T, ?, MSeq<T>> toMSeq() {
282 return Collector.of(
283 (Supplier<List<T>>)ArrayList::new,
284 List::add,
285 (left, right) -> { left.addAll(right); return left; },
286 MSeq::of
287 );
288 }
289
290 /**
291 * Create a new {@code MSeq} with the given {@code length}.
292 *
293 * @param length the length of the created {@code MSeq}.
294 * @param <T> the element type of the new {@code MSeq}.
295 * @return the new mutable sequence.
296 * @throws NegativeArraySizeException if the given {@code length} is
297 * negative
298 */
299 public static <T> MSeq<T> ofLength(final int length) {
300 return length == 0
301 ? empty()
302 : new ArrayMSeq<>(Array.of(ObjectStore.ofLength(length)));
303 }
304
305 /**
306 * Create a new {@code MSeq} from the given values.
307 *
308 * @param <T> the element type
309 * @param values the array values.
310 * @return a new {@code Meq} with the given values.
311 * @throws NullPointerException if the {@code values} array is {@code null}.
312 */
313 @SafeVarargs
314 public static <T> MSeq<T> of(final T... values) {
315 return values.length == 0
316 ? empty()
317 : new ArrayMSeq<>(Array.of(ObjectStore.of(values.clone())));
318 }
319
320 /**
321 * Create a new {@code MSeq} from the given values.
322 *
323 * @param <T> the element type
324 * @param values the array values.
325 * @return a new {@code MSeq} with the given values.
326 * @throws NullPointerException if the {@code values} object is
327 * {@code null}.
328 */
329 @SuppressWarnings("unchecked")
330 public static <T> MSeq<T> of(final Iterable<? extends T> values) {
331 final MSeq<T> mseq;
332 if (values instanceof ISeq<?>) {
333 final ISeq<T> seq = (ISeq<T>)values;
334 mseq = seq.isEmpty() ? empty() : seq.copy();
335 } else if (values instanceof MSeq<?>) {
336 final MSeq<T> seq = (MSeq<T>)values;
337 mseq = seq.isEmpty() ? empty() : MSeq.of(seq);
338 } else if (values instanceof Collection<?>) {
339 final Collection<T> collection = (Collection<T>)values;
340 mseq = collection.isEmpty()
341 ? empty()
342 : MSeq.<T>ofLength(collection.size()).setAll(values);
343 } else {
344 final Stream.Builder<T> builder = Stream.builder();
345 values.forEach(builder::add);
346 final Object[] objects = builder.build().toArray();
347
348 mseq = objects.length == 0
349 ? empty()
350 : new ArrayMSeq<>(Array.of(ObjectStore.of(objects)));
351 }
352
353 return mseq;
354 }
355
356 // /**
357 // * Create a new {@code MSeq} instance from the remaining elements of the
358 // * given iterator.
359 // *
360 // * @since 3.3
361 // *
362 // * @param <T> the element type.
363 // * @return a new {@code MSeq} with the given remaining values.
364 // * @throws NullPointerException if the {@code values} object is
365 // * {@code null}.
366 // */
367 // public static <T> MSeq<T> of(final Iterator<? extends T> values) {
368 // final Stream.Builder<T> builder = Stream.builder();
369 // values.forEachRemaining(builder::add);
370 // final Object[] objects = builder.build().toArray();
371 //
372 // return objects.length == 0
373 // ? empty()
374 // : new ArrayProxyMSeq<>(
375 // new ObjectArrayProxy<>(objects, 0, objects.length));
376 // }
377
378 /**
379 * Creates a new sequence, which is filled with objects created be the given
380 * {@code supplier}.
381 *
382 * @since 3.3
383 *
384 * @param <T> the element type of the sequence
385 * @param supplier the {@code Supplier} which creates the elements, the
386 * returned sequence is filled with
387 * @param length the length of the returned sequence
388 * @return a new sequence filled with elements given by the {@code supplier}
389 * @throws NegativeArraySizeException if the given {@code length} is
390 * negative
391 * @throws NullPointerException if the given {@code supplier} is
392 * {@code null}
393 */
394 public static <T> MSeq<T> of(
395 final Supplier<? extends T> supplier,
396 final int length
397 ) {
398 requireNonNull(supplier);
399
400 return length == 0
401 ? empty()
402 : MSeq.<T>ofLength(length).fill(supplier);
403 }
404
405 /**
406 * Create a new {@code MSeq} from the values of the given {@code Seq}.
407 *
408 * @param <T> the element type
409 * @param values the array values.
410 * @return an new {@code MSeq} with the given values
411 * @throws NullPointerException if the {@code values} array is {@code null}.
412 */
413 public static <T> MSeq<T> of(final Seq<T> values) {
414 return values instanceof ArrayMSeq<?>
415 ? ((ArrayMSeq<T>)values).copy()
416 : MSeq.<T>ofLength(values.length()).setAll(values);
417 }
418
419 }
|