001/*
002 * Java Genetic Algorithm Library (jenetics-8.0.0).
003 * Copyright (c) 2007-2024 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 */
020package io.jenetics.internal.collection;
021
022import static java.lang.String.format;
023import static java.util.Objects.requireNonNull;
024
025import java.io.IOException;
026import java.io.InvalidObjectException;
027import java.io.ObjectInput;
028import java.io.ObjectInputStream;
029import java.io.ObjectOutput;
030import java.io.Serial;
031import java.io.Serializable;
032import java.util.Collection;
033import java.util.Comparator;
034import java.util.Iterator;
035
036import io.jenetics.internal.collection.Array.Store.Ref;
037
038/**
039 * Array implementation class. This class manages the actual array (store) and
040 * the start index and the length.
041 *
042 * @param <T> the array element type
043 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
044 * @version 6.0
045 * @since 3.4
046 */
047public final class Array<T> implements BaseMSeq<T>, Serializable {
048
049        @Serial
050        private static final long serialVersionUID = 2L;
051
052        private final Store.Ref<T> _store;
053        private final int _start;
054        private final int _length;
055
056        /**
057         * Private <i>primary</i> constructor.
058         *
059         * @param store the store used by this array
060         * @param from the start index of the array
061         * @param until the end index of the array
062         */
063        private Array(final Store.Ref<T> store, final int from, final int until) {
064                _store = requireNonNull(store);
065                _start = from;
066                _length = until - from;
067        }
068
069        /**
070         * Create a new array from the given store
071         *
072         * @param store the store used by this array
073         */
074        private Array(final Store<T> store) {
075                this(Store.Ref.of(store), 0, store.length());
076        }
077
078        /**
079         * Get the array value at the given {@code index}. The array index is not
080         * checked.
081         *
082         * @param index the array index
083         * @return the value at the given index
084         */
085        @Override
086        public T get(final int index) {
087                return _store.get(index + _start);
088        }
089
090        /**
091         * Return the array length.
092         *
093         * @return the array length
094         */
095        @Override
096        public int length() {
097                return _length;
098        }
099
100        /**
101         * Set the {@code value} at the given {@code index}. The array index is not
102         * checked.
103         *
104         * @param index the array index
105         * @param value the value to set
106         */
107        public void set(final int index, final T value) {
108                _store.set(index + _start, value);
109        }
110
111        /**
112         * Return the underlying array store.
113         *
114         * @return the underlying array store
115         */
116        public Store<T> store() {
117                return _store._value;
118        }
119
120        public void copyIfSealed() {
121                _store.copyIfSealed();
122        }
123
124        /**
125         * Return a new <i>sealed</i> array instance. The underlying store is sealed
126         * as well, but not copied.
127         *
128         * @return a new sealed array
129         */
130        public Array<T> seal() {
131                return new Array<>(_store.seal(), _start, _length + _start);
132        }
133
134        /**
135         * Return the seal state of the array.
136         *
137         * @return {@code true} is the array is sealed, {@code false} otherwise
138         */
139        public boolean isSealed() {
140                return _store.isSealed();
141        }
142
143        /**
144         * Sort the store.
145         *
146         * @param from the start index where to start sorting (inclusively)
147         * @param until the end index where to stop sorting (exclusively)
148         * @param comparator the {@code Comparator} used to compare sequence
149         *        elements. A {@code null} value indicates that the elements'
150         *        Comparable natural ordering should be used
151         */
152        public void sort(
153                final int from,
154                final int until,
155                final Comparator<? super T> comparator
156        ) {
157                _store.sort(from + _start, until + _start, comparator);
158        }
159
160        /**
161         * Return a <i>new</i> {@code Array} object with the given values appended.
162         *
163         * @since 3.4
164         *
165         * @param array the values to append
166         * @return a <i>new</i> {@code Array} object with the elements of
167         *         {@code this} array and the given {@code array} appended.
168         * @throws NullPointerException if the given {@code array} is {@code null}
169         */
170        public Array<T> append(final Array<T> array) {
171                final Array<T> appended = newInstance(length() + array.length());
172                for (int i = 0; i < _length; ++i) {
173                        appended.set(i, get(i));
174                }
175                for (int i = 0; i < array._length; ++i) {
176                        appended.set(i + _length, array.get(i));
177                }
178
179                return appended;
180        }
181
182        private Array<T> newInstance(final int length) {
183                return of(_store._value.newInstance(length));
184        }
185
186        /**
187         * Return a <i>new</i> {@code Array} with the given {@code values} appended.
188         *
189         * @since 3.4
190         *
191         * @param values the values to append
192         * @return a <i>new</i> {@code Array} with the elements of {@code this}
193         *        array and the given {@code values} appended.
194         * @throws NullPointerException if the given {@code values} iterable is
195         *         {@code null}
196         */
197        public Array<T> append(final Iterable<? extends T> values) {
198                final int size = size(values);
199                final Array<T> array = newInstance(_length + size);
200
201                for (int i = 0; i < _length; ++i) {
202                        array.set(i, get(i));
203                }
204
205                final Iterator<? extends T> it = values.iterator();
206                for (int i = 0; i < size; ++i) {
207                        array.set(_length + i, it.next());
208                }
209
210                return array;
211        }
212
213        /**
214         * Return a <i>new</i> {@code Array} with the given {@code values} prepended.
215         *
216         * @since 3.4
217         *
218         * @param values the values to prepend
219         * @return a <i>new</i> {@code Array} with the elements of {@code this}
220         *        array and the given {@code values} appended.
221         * @throws NullPointerException if the given {@code values} iterable is
222         *         {@code null}
223         */
224        public Array<T> prepend(final Iterable<? extends T> values) {
225                final int size = size(values);
226                final Array<T> array = newInstance(_length + size);
227
228                final Iterator<? extends T> it = values.iterator();
229                for (int i = 0; i < size; ++i) {
230                        array.set(i, it.next());
231                }
232
233                for (int i = 0; i < _length; ++i) {
234                        array.set(size + i, get(i));
235                }
236
237                return array;
238        }
239
240        private static int size(final Iterable<?> values) {
241                int size = 0;
242                if (values instanceof Collection) {
243                        size = ((Collection<?>)values).size();
244                } else {
245                        for (Object value : values) {
246                                ++size;
247                        }
248                }
249
250                return size;
251        }
252
253        /**
254         * Return a copy of this array.
255         *
256         * @return a copy of this array
257         */
258        public Array<T> copy() {
259                return new Array<>(_store.copy(_start, _length + _start));
260        }
261
262        /**
263         * Return a new array slice starting with the {@code from} index.
264         *
265         * @param from the start index
266         * @return a new array slice
267         * @throws ArrayIndexOutOfBoundsException if the index is out of bounds.
268         */
269        public Array<T> slice(final int from) {
270                return slice(from, length());
271        }
272
273        /**
274         * Return a new array slice starting with the {@code from} index and
275         * {@code until} index.
276         *
277         * @param from the start index
278         * @param until the end index
279         * @return a new array slice
280         * @throws ArrayIndexOutOfBoundsException if the indexes are out of bounds.
281         */
282        public Array<T> slice(final int from, final int until) {
283                checkIndex(from, until);
284                return new Array<>(_store, from + _start, until + _start);
285        }
286
287        /**
288         * Check the given array {@code index}
289         *
290         * @param index the index to check
291         * @throws ArrayIndexOutOfBoundsException if the given index is not in the
292         *         valid range.
293         */
294        public void checkIndex(final int index) {
295                if (index < 0 || index >= length()) {
296                        throw new ArrayIndexOutOfBoundsException(format(
297                                "Index %s is out of bounds [0, %s)", index, length()
298                        ));
299                }
300        }
301
302        /**
303         * Check the given {@code from} and {@code until} indices.
304         *
305         * @param from the from index, inclusively.
306         * @param until the until index, exclusively.
307         * @throws ArrayIndexOutOfBoundsException if the given index is not in the
308         *         valid range.
309         */
310        public void checkIndex(final int from, final int until) {
311                checkIndex(from, until, length());
312        }
313
314        /**
315         * Check the given {@code from} and {@code until} indices.
316         *
317         * @param from the from index, inclusively.
318         * @param until the until index, exclusively.
319         * @param size the array size
320         * @throws ArrayIndexOutOfBoundsException if the given index is not in the
321         *         valid range.
322         */
323        public static void checkIndex(final int from, final int until, final int size) {
324                if (from < 0) {
325                        throw new ArrayIndexOutOfBoundsException("fromIndex = " + from);
326                }
327                if (until > size) {
328                        throw new ArrayIndexOutOfBoundsException(format(
329                                "Invalid index range: [%d, %s)", from, until
330                        ));
331                }
332                if (from > until) {
333                        throw new IllegalArgumentException(format(
334                                "fromIndex(%d) > toIndex(%d)", from, until
335                        ));
336                }
337        }
338
339        /**
340         * Create a new {@code Array} from the given object store.
341         *
342         * @param store the object store
343         * @param <T> the array type
344         * @return a new array with the given {@code store}
345         */
346        public static <T> Array<T> of(final Store<T> store) {
347                return new Array<>(store);
348        }
349
350        /**
351         * Create a new {@code Array} with the given length. The array is created
352         * with the <i>default</i> {@code ObjectStore} object.
353         *
354         * @param length the array length
355         * @param <T> the array type
356         * @return a new array with the given {@code length}
357         */
358        public static <T> Array<T> ofLength(final int length) {
359                return new Array<>(ObjectStore.ofLength(length));
360        }
361
362
363        /* *************************************************************************
364         *  Java object serialization
365         * ************************************************************************/
366
367        @Serial
368        private Object writeReplace() {
369                return new SerialProxy(SerialProxy.ARRAY, this);
370        }
371
372        @Serial
373        private void readObject(final ObjectInputStream stream)
374                throws InvalidObjectException
375        {
376                throw new InvalidObjectException("Serialization proxy required.");
377        }
378
379        void write(final ObjectOutput out) throws IOException {
380                final Store<T> store = _start == 0
381                        ? _store._value
382                        : _store._value.copy(_start, _start + _length);
383
384                out.writeBoolean(_store._sealed);
385                out.writeObject(store);
386        }
387
388        @SuppressWarnings({"rawtypes", "unchecked"})
389        static Object read(final ObjectInput in)
390                throws IOException, ClassNotFoundException
391        {
392                final boolean sealed = in.readBoolean();
393                final Store store = (Store)in.readObject();
394                final Store.Ref ref = new Ref(store, sealed);
395
396                return new Array(ref, 0, store.length());
397        }
398
399        /**
400         * Minimal interface for accessing an underlying array structure.
401         *
402         * @param <T> the array element type
403         * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
404         * @version 3.4
405         * @since 3.4
406         */
407        public interface Store<T> {
408
409                /**
410                 * Write the given {@code value} at the given {@code index} to the
411                 * underlying array structure.
412                 *
413                 * @param index the array index
414                 * @param value the value to set
415                 */
416                void set(final int index, final T value);
417
418                /**
419                 * Return the value at the given array {@code index}.
420                 *
421                 * @param index the array index
422                 * @return the value at the given index
423                 */
424                T get(final int index);
425
426                /**
427                 * Sort the store.
428                 *
429                 * @param from the start index where to start sorting (inclusively)
430                 * @param until the end index where to stop sorting (exclusively)
431                 * @param comparator the {@code Comparator} used to compare sequence
432                 *        elements. A {@code null} value indicates that the elements'
433                 *        Comparable natural ordering should be used
434                 */
435                void sort(
436                        final int from,
437                        final int until,
438                        final Comparator<? super T> comparator
439                );
440
441                /**
442                 * Return the length of the array {@code Store}.
443                 *
444                 * @return the array store length
445                 */
446                int length();
447
448                /**
449                 * Return a new array {@code Store} with the copied portion of the
450                 * underlying array.
451                 *
452                 * @param from the start index of the copied array
453                 * @param until the end index of the copied array
454                 * @return a new copy of the given range
455                 */
456                Store<T> copy(final int from, final int until);
457
458                /**
459                 * Return a new array {@code Store} with the copied portion of the
460                 * underlying array.
461                 *
462                 * @param from the start index of the copied array
463                 * @return a new copy of the given range
464                 */
465                default Store<T> copy(final int from) {
466                        return copy(from, length());
467                }
468
469                /**
470                 * Return a new array {@code Store} copy.
471                 *
472                 * @return a new array {@code Store} copy
473                 */
474                default Store<T> copy() {
475                        return copy(0, length());
476                }
477
478                /**
479                 * Return a new {@code Store} of the same type and the given length.
480                 *
481                 * @param length the length of the new store
482                 * @return a new {@code Store} of the same type and the given length.
483                 * @throws NegativeArraySizeException if the length is smaller than zero
484                 */
485                Store<T> newInstance(final int length);
486
487                /**
488                 * Mutable reference of an underlying array {@code Store}.
489                 *
490                 * @param <T> the array element type
491                 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
492                 * @version 3.4
493                 * @since 3.4
494                 */
495                final class Ref<T> implements Store<T> {
496                        private Store<T> _value;
497                        private boolean _sealed;
498
499                        /**
500                         * Private <i>primary</i> constructor.
501                         *
502                         * @param value the array store which is referenced
503                         * @param sealed the sealed flag of the reference
504                         */
505                        private Ref(final Store<T> value, final boolean sealed) {
506                                _value = value;
507                                _sealed = sealed;
508                        }
509
510                        public Ref<T> seal() {
511                                _sealed = true;
512                                return new Ref<>(_value, true);
513                        }
514
515                        public boolean isSealed() {
516                                return _sealed;
517                        }
518
519                        @Override
520                        public void set(final int index, final T value) {
521                                copyIfSealed();
522                                _value.set(index, value);
523                        }
524
525                        public void sort(
526                                final int from,
527                                final int until,
528                                final Comparator<? super T> comparator
529                        ) {
530                                copyIfSealed();
531                                _value.sort(from, until, comparator);
532                        }
533
534                        void copyIfSealed() {
535                                if (_sealed) {
536                                        _value = copy();
537                                        _sealed = false;
538                                }
539                        }
540
541                        @Override
542                        public T get(final int index) {
543                                return _value.get(index);
544                        }
545
546                        @Override
547                        public int length() {
548                                return _value.length();
549                        }
550
551                        @Override
552                        public Store<T> copy(final int from, final int until) {
553                                return _value.copy(from, until);
554                        }
555
556                        @Override
557                        public Store<T> newInstance(final int length) {
558                                return _value.newInstance(length);
559                        }
560
561                        public static <T> Ref<T> of(final Store<T> value) {
562                                return new Ref<>(requireNonNull(value), false);
563                        }
564                }
565
566        }
567
568}