001 /*
002 * Java Genetic Algorithm Library (jenetics-3.0.0).
003 * Copyright (c) 2007-2014 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
024 import java.util.ArrayList;
025 import java.util.Collection;
026 import java.util.Iterator;
027 import java.util.List;
028 import java.util.ListIterator;
029 import java.util.Random;
030 import java.util.function.Function;
031 import java.util.function.Supplier;
032 import java.util.stream.Collector;
033
034 import org.jenetics.internal.collection.ArrayProxyMSeq;
035 import org.jenetics.internal.collection.ObjectArrayProxy;
036
037 /**
038 * Mutable, ordered, fixed sized sequence.
039 *
040 * @see ISeq
041 *
042 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
043 * @since 1.0
044 * @version 3.0 — <em>$Date: 2014-12-28 $</em>
045 */
046 public interface MSeq<T> extends Seq<T>, Copyable<MSeq<T>> {
047
048 /**
049 * Set the {@code value} at the given {@code index}.
050 *
051 * @param index the index of the new value.
052 * @param value the new value.
053 * @throws IndexOutOfBoundsException if the index is out of range
054 * <code>(index < 0 || index >= size())</code>.
055 */
056 public void set(final int index, final T value);
057
058 /**
059 * Fills the sequence with values of the given iterator.
060 *
061 * @param it the iterator of the values to fill this sequence.
062 * @return {@code this} sequence.
063 */
064 public default MSeq<T> setAll(final Iterator<? extends T> it) {
065 for (int i = 0, n = length(); i < n && it.hasNext(); ++i) {
066 set(i, it.next());
067 }
068 return this;
069 }
070
071 /**
072 * Fills the sequence with values of the given iterable.
073 *
074 * @param values the values to fill this sequence.
075 * @return {@code this} sequence.
076 */
077 public default MSeq<T> setAll(final Iterable<? extends T> values) {
078 setAll(values.iterator());
079 return this;
080 }
081
082 /**
083 * Fill the sequence with the given values.
084 *
085 * @param values the first initial values of this sequence
086 * @return {@code this} sequence.
087 */
088 public default MSeq<T> setAll(final T[] values) {
089 for (int i = 0, n = length(); i < n && i < values.length; ++i) {
090 set(i, values[i]);
091 }
092 return this;
093 }
094
095 /**
096 * Fill the sequence with values generated by the given factory.
097 *
098 * @param supplier the value factory.
099 * @return {@code this} sequence.
100 * @throws NullPointerException if the given {@code factory} is {@code null}.
101 */
102 public default MSeq<T> fill(final Supplier<? extends T> supplier) {
103 for (int i = 0, n = length(); i < n; ++i) {
104 set(i, supplier.get());
105 }
106 return this;
107 }
108
109 /**
110 * Swap the elements at the two positions.
111 *
112 * @param i the index of the first element.
113 * @param j the index of the second element.
114 * @throws IndexOutOfBoundsException if {@code i < 0 || j >= length()}.
115 */
116 public default void swap(final int i, final int j) {
117 final T temp = get(i);
118 set(i, get(j));
119 set(j, temp);
120 }
121
122 /**
123 * Swap a given range with a range of the same size with another array.
124 *
125 * <pre>
126 * start end
127 * | |
128 * this: +---+---+---+---+---+---+---+---+---+---+---+---+
129 * +---------------+
130 * +---------------+
131 * other: +---+---+---+---+---+---+---+---+---+---+---+---+
132 * |
133 * otherStart
134 * </pre>
135 *
136 * @param start the start index of {@code this} range, inclusively.
137 * @param end the end index of {@code this} range, exclusively.
138 * @param other the other array to swap the elements with.
139 * @param otherStart the start index of the {@code other} array.
140 * @throws IndexOutOfBoundsException if {@code start > end} or
141 * if {@code start < 0 || end >= this.length() || otherStart < 0 ||
142 * otherStart + (end - start) >= other.length()}
143 */
144 public default void swap(
145 final int start, final int end,
146 final MSeq<T> other, final int otherStart
147 ) {
148 if (otherStart < 0 || (otherStart + (end - start)) > length()) {
149 throw new ArrayIndexOutOfBoundsException(format(
150 "Invalid index range: [%d, %d)",
151 otherStart, (otherStart + (end - start))
152 ));
153 }
154
155 if (start < end) {
156 for (int i = (end - start); --i >= 0;) {
157 final T temp = get(start + i);
158 set(start + i, other.get(otherStart + i));
159 other.set(otherStart + i, temp);
160 }
161 }
162 }
163
164 /**
165 * Randomize the {@code array} using the {@link Random} object currently
166 * registered in the {@link RandomRegistry} class. The used shuffling
167 * algorithm is from D. Knuth TAOCP, Seminumerical Algorithms, Third edition,
168 * page 142, Algorithm S (Selection sampling technique).
169 *
170 * @return this shuffled sequence
171 */
172 public default MSeq<T> shuffle() {
173 return shuffle(RandomRegistry.getRandom());
174 }
175
176 /**
177 * Randomize the {@code array} using the given {@link Random} object. The used
178 * shuffling algorithm is from D. Knuth TAOCP, Seminumerical Algorithms,
179 * Third edition, page 142, Algorithm S (Selection sampling technique).
180 *
181 * @param random the {@link Random} object to use for randomize.
182 * @return this shuffled sequence
183 * @throws NullPointerException if the random object is {@code null}.
184 */
185 public default MSeq<T> shuffle(final Random random) {
186 for (int j = length() - 1; j > 0; --j) {
187 swap(j, random.nextInt(j + 1));
188 }
189 return this;
190 }
191
192 /**
193 * Returns a list iterator over the elements in this sequence (in proper
194 * sequence).
195 *
196 * @return a list iterator over the elements in this list (in proper
197 * sequence)
198 */
199 public ListIterator<T> listIterator();
200
201 @Override
202 public MSeq<T> subSeq(final int start, final int end);
203
204 @Override
205 public MSeq<T> subSeq(final int start);
206
207 @Override
208 public <B> MSeq<B> map(final Function<? super T, ? extends B> mapper);
209
210 /**
211 * Return a read-only projection of this sequence. Changes to the original
212 * sequence will not influence the returned {@code ISeq}.
213 *
214 * @return a read-only projection of this sequence
215 */
216 public ISeq<T> toISeq();
217
218
219 /* *************************************************************************
220 * Some static factory methods.
221 * ************************************************************************/
222
223 /**
224 * Returns a {@code Collector} that accumulates the input elements into a
225 * new {@code MSeq}.
226 *
227 * @param <T> the type of the input elements
228 * @return a {@code Collector} which collects all the input elements into a
229 * {@code MSeq}, in encounter order
230 */
231 public static <T> Collector<T, ?, MSeq<T>> toMSeq() {
232 return Collector.of(
233 (Supplier<List<T>>)ArrayList::new,
234 List::add,
235 (left, right) -> { left.addAll(right); return left; },
236 MSeq::of
237 );
238 }
239
240 /**
241 * Single instance of an empty {@code MSeq}.
242 */
243 public static final MSeq<?> EMPTY = ofLength(0);
244
245 /**
246 * Return an empty {@code MSeq}.
247 *
248 * @param <T> the element type of the new {@code MSeq}.
249 * @return an empty {@code MSeq}.
250 */
251 @SuppressWarnings("unchecked")
252 public static <T> MSeq<T> empty() {
253 return (MSeq<T>)EMPTY;
254 }
255
256 /**
257 * Create a new {@code MSeq} with the given {@code length}.
258 *
259 * @param length the length of the created {@code MSeq}.
260 * @param <T> the element type of the new {@code MSeq}.
261 * @return the new mutable sequence.
262 */
263 public static <T> MSeq<T> ofLength(final int length) {
264 return new ArrayProxyMSeq<>(new ObjectArrayProxy<T>(length));
265 }
266
267 /**
268 * Create a new {@code MSeq} from the given values.
269 *
270 * @param <T> the element type
271 * @param values the array values.
272 * @return a new {@code Meq} with the given values.
273 * @throws NullPointerException if the {@code values} array is {@code null}.
274 */
275 @SafeVarargs
276 public static <T> MSeq<T> of(final T... values) {
277 final ObjectArrayProxy<T> proxy = new ObjectArrayProxy<>(
278 values.clone(), 0, values.length
279 );
280 return new ArrayProxyMSeq<>(proxy);
281 }
282
283 /**
284 * Create a new {@code MSeq} from the given values.
285 *
286 * @param <T> the element type
287 * @param values the array values.
288 * @return a new {@code MSeq} with the given values.
289 * @throws NullPointerException if the {@code values} array is {@code null}.
290 */
291 @SuppressWarnings("unchecked")
292 public static <T> MSeq<T> of(final Iterable<? extends T> values) {
293 MSeq<T> mseq = null;
294 if (values instanceof ISeq<?>) {
295 mseq = ((ISeq<T>)values).copy();
296 } else if (values instanceof MSeq<?>) {
297 mseq = (MSeq<T>)values;
298 } else if (values instanceof Collection<?>) {
299 final Collection<T> collection = (Collection<T>)values;
300 mseq = MSeq.<T>ofLength(collection.size()).setAll(values);
301 } else {
302 int length = 0;
303 for (final T value : values) ++length;
304
305 mseq = MSeq.ofLength(length);
306 int index = 0;
307 for (final T value : values) mseq.set(index++, value);
308 }
309
310 return mseq;
311 }
312
313 /**
314 * Create a new {@code MSeq} from the values of the given {@code Seq}.
315 *
316 * @param <T> the element type
317 * @param values the array values.
318 * @return an new {@code MSeq} with the given values
319 * @throws NullPointerException if the {@code values} array is {@code null}.
320 */
321 public static <T> MSeq<T> of(final Seq<T> values) {
322 return values instanceof ArrayProxyMSeq<?, ?> ?
323 ((ArrayProxyMSeq<T, ?>)values).copy() :
324 MSeq.<T>ofLength(values.length()).setAll(values);
325 }
326
327 }
|