Array.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-2.0.2).
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.Math.min;
023 import static java.lang.String.format;
024 import static java.lang.System.arraycopy;
025 import static java.util.Objects.requireNonNull;
026 
027 import java.util.Arrays;
028 import java.util.Collection;
029 import java.util.Comparator;
030 import java.util.Iterator;
031 import java.util.List;
032 import java.util.ListIterator;
033 import java.util.Random;
034 import java.util.RandomAccess;
035 
036 import org.jenetics.internal.util.Stack;
037 
038 /**
039  * Array class which wraps the the java build in array type T[]. Once the array
040  * is created the array length can't be changed (like the build in array).
041  <p>
042  <strong>Note that this implementation is not synchronized.</strong> If
043  * multiple threads access this object concurrently, and at least one of the
044  * threads modifies it, it must be synchronized externally.
045  *
046  @param <T> the element type of the array.
047  *
048  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
049  @since 1.0
050  @version 2.0 &mdash; <em>$Date: 2014-03-31 $</em>
051  */
052 public final class Array<T>
053     extends ArraySeq<T>
054     implements
055         MSeq<T>,
056         RandomAccess
057 {
058     private static final long serialVersionUID = 2L;
059 
060     @SuppressWarnings("rawtypes")
061     private static final Array EMPTY = new Array(0);
062 
063     /**
064      * Return the empty array.
065      *
066      @param <T> the element type.
067      @return empty array.
068      */
069     @SuppressWarnings("unchecked")
070     public static <T> Array<T> empty() {
071         return EMPTY;
072     }
073 
074     Array(final ArrayRef array, final int start, final int end) {
075         super(array, start, end);
076     }
077 
078     /**
079      * Create a new array with the given length.
080      *
081      @param length the array length.
082      @throws NegativeArraySizeException if the specified {@code length}
083      *          is negative
084      */
085     public Array(final int length) {
086         super(length);
087     }
088 
089     /**
090      * Selects all elements of this list which satisfy a predicate.
091      *
092      @param predicate the predicate used to test elements.
093      @return a new array consisting of all elements of this list that satisfy
094      *         the given {@code predicate}. The order of the elements is
095      *         preserved.
096      @throws NullPointerException if the given {@code predicate} is
097      *         {@code null}.
098      */
099     public Array<T> filter(final Function<? super T, Boolean> predicate) {
100         final Stack<T> filtered = new Stack<>();
101         for (int i = 0, n = length(); i < n; ++i) {
102             @SuppressWarnings("unchecked")
103             final T value = (T)_array.data[i + _start];
104 
105             if (predicate.apply(value== Boolean.TRUE) {
106                 filtered.push(value);
107             }
108         }
109 
110         final Array<T> copy = new Array<>(filtered.length);
111         for (int i = filtered.length; --i >= 0;) {
112             copy._array.data[i= filtered.pop();
113         }
114 
115         return copy;
116     }
117 
118     @Override
119     public void set(final int index, final T value) {
120         checkIndex(index);
121 
122         _array.cloneIfSealed();
123         _array.data[index + _start= value;
124     }
125 
126     /**
127      <p>
128      * Sorts the array of objects into ascending order, according to the natural
129      * ordering of its elements. All elements in the array <b>must</b> implement
130      * the Comparable interface. Furthermore, all elements in the array must be
131      * mutually comparable.
132      </p>
133      * The sorting algorithm is the Quicksort.
134      *
135      @see <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Quicksort">
136      *          Wikipedia: Quicksort
137      *      </a>
138      *
139      @throws ClassCastException if the array contains elements that are not
140      *          <i>mutually comparable</i> (for example, strings and integers).
141      */
142     public void sort() {
143         sort(0, length());
144     }
145 
146     /**
147      <p>
148      * Sorts the array of objects into ascending order, according to the natural
149      * ordering of its elements. All elements in the array <b>must</b> implement
150      * the Comparable interface. Furthermore, all elements in the array must be
151      * mutually comparable.
152      </p>
153      * The sorting algorithm is the Quicksort.
154      *
155      @see <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Quicksort">
156      *          Wikipedia: Quicksort
157      *      </a>
158      *
159      @param from the index of the first element (inclusive) to be sorted.
160      @param to the index of the last element (exclusive) to be sorted.
161      @throws IndexOutOfBoundsException if {@code from < 0 or to > length()}
162      @throws IllegalArgumentException if {@code from > to}
163      @throws ClassCastException if the array contains elements that are not
164      *        <i>mutually comparable</i> (for example, strings and integers).
165      */
166     public void sort(final int from, final int to) {
167         sort(from, to, new Comparator<T>() {
168             @SuppressWarnings({ "unchecked""rawtypes" })
169             @Override
170             public int compare(final T o1, final T o2) {
171                 return ((Comparable)o1).compareTo(o2);
172             }
173         });
174     }
175 
176     /**
177      <p>
178      * Sorts the array of objects according to the order induced by the specified
179      * comparator. All elements in the array must be mutually comparable by the
180      * specified comparator.
181      </p>
182      * The sorting algorithm is the Quicksort.
183      *
184      @see <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Quicksort">
185      *          Wikipedia: Quicksort
186      *      </a>
187      *
188      @param comparator the comparator used for sorting
189      @throws NullPointerException if the given {@code comparator} is
190      *          {@code null}.
191      @throws ClassCastException if the array contains elements that are not
192      *          <i>mutually comparable</i> (for example, strings and integers).
193      */
194     public void sort(final Comparator<? super T> comparator) {
195         sort(0, length(), comparator);
196     }
197 
198     /**
199      <p>
200      * Sorts the array of objects according to the order induced by the specified
201      * comparator. All elements in the array must be mutually comparable by the
202      * specified comparator.
203      </p>
204      * The sorting algorithm is the <i>Timsort</i>.
205      *
206      @see <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Timsort">
207      *          Wikipedia: Timsort
208      *      </a>
209      @see Arrays#sort(Object[], int, int, Comparator)
210      *
211      @param from the index of the first element (inclusive) to be sorted.
212      @param to the index of the last element (exclusive) to be sorted.
213      @param comparator the comparator used for sorting
214      @throws NullPointerException if the given {@code comparator} is
215      *          {@code null}.
216      @throws IndexOutOfBoundsException if {@code from < 0 or to > length()}
217      @throws IllegalArgumentException if {@code from > to}
218      @throws ClassCastException if the array contains elements that are not
219      *          <i>mutually comparable</i> (for example, strings and integers).
220      */
221     public void sort(
222         final int from, final int to,
223         final Comparator<? super T> comparator
224     ) {
225         checkIndex(from, to);
226         if (from > to) {
227             throw new IllegalArgumentException(format(
228                     "From index > to index: %d > %d.", from, to
229                 ));
230         }
231         requireNonNull(comparator, "Comparator");
232 
233         _array.cloneIfSealed();
234 
235         @SuppressWarnings("unchecked")
236         final T[] data = (T[])_array.data;
237         Arrays.sort(data, from + _start, to + _start, comparator);
238     }
239 
240     private void uncheckedSwap(final int i, final int j) {
241         final Object temp = _array.data[i + _start];
242         _array.data[i + _start= _array.data[j + _start];
243         _array.data[j + _start= temp;
244     }
245 
246     /**
247      * Reverses the given array in place.
248      *
249      @return this (reversed) array.
250      */
251     public Array<T> reverse() {
252         return reverse(0, length());
253     }
254 
255     /**
256      * Reverses the part of the array determined by the to indexes. The reverse
257      * method is performed in place.
258      *
259      @param from the first index (inclusive)
260      @param to the second index (exclusive)
261      @return this (reversed) array.
262      @throws IllegalArgumentException if <tt>from &gt; to</tt>
263      @throws IndexOutOfBoundsException if <tt>from &lt; 0</tt> or
264      *            <tt>to &gt; a.length</tt>
265      */
266     public Array<T> reverse(final int from, final int to) {
267         checkIndex(from, to);
268         _array.cloneIfSealed();
269 
270         int i = from;
271         int j = to;
272         while (i < j) {
273             uncheckedSwap(i++, --j);
274         }
275 
276         return this;
277     }
278 
279     @Override
280     public void swap(final int i, final int j) {
281         checkIndex(i);
282         checkIndex(j);
283 
284         _array.cloneIfSealed();
285         uncheckedSwap(i, j);
286     }
287 
288     @Override
289     public void swap(
290         final int start, final int end,
291         final MSeq<T> other, final int otherStart
292     ) {
293         if (other instanceof Array<?>) {
294             swap(start, end, (Array<T>)other, otherStart);
295         else {
296             checkIndex(start, end);
297             if (otherStart < || (otherStart + (end - start)) > _length) {
298                 throw new ArrayIndexOutOfBoundsException(format(
299                     "Invalid index range: [%d, %d)",
300                     otherStart, (otherStart + (end - start))
301                 ));
302             }
303 
304             if (start < end) {
305                 _array.cloneIfSealed();
306 
307                 for (int i = (end - start); --i >= 0;) {
308                     @SuppressWarnings("unchecked")
309                     final T temp = (T)_array.data[_start + start + i];
310                     _array.data[_start + start + i= other.get(otherStart + i);
311                     other.set(otherStart + i, temp);
312                 }
313             }
314         }
315     }
316 
317     /**
318      @see MSeq#swap(int, int, MSeq, int)
319      *
320      @param start the start index of the swap
321      @param end the end index of the swap
322      @param other the other array used for swapping
323      @param otherStart the start index of the other array
324      */
325     public void swap(
326         final int start, final int end,
327         final Array<T> other, final int otherStart
328     ) {
329         checkIndex(start, end);
330         other.checkIndex(otherStart, otherStart + (end - start));
331 
332         if (start < end) {
333             _array.cloneIfSealed();
334             other._array.cloneIfSealed();
335 
336             for (int i = (end - start); --i >= 0;) {
337                 final Object temp = _array.data[_start + start + i];
338                 _array.data[_start + start + i(
339                     other._array.data[other._start + otherStart + i]
340                 );
341                 other._array.data[other._start + otherStart + i= temp;
342             }
343         }
344     }
345 
346     /**
347      * Randomize this array using the given {@link Random} object. The used
348      * shuffling algorithm is from D. Knuth TAOCP, Seminumerical Algorithms,
349      * Third edition, page 142, Algorithm S (Selection sampling technique).
350      *
351      @param random the {@link Random} object to use for randomize.
352      @return this array
353      @throws NullPointerException if the give random object is {@code null}.
354      */
355     public Array<T> shuffle(final Random random) {
356         _array.cloneIfSealed();
357 
358         for (int j = length() 1; j > 0; --j) {
359             uncheckedSwap(j, random.nextInt(j + 1));
360         }
361 
362         return this;
363     }
364 
365     /**
366      * Randomize this array using the <i>registered</i> {@link Random} object.
367      * The used shuffling algorithm is from D. Knuth TAOCP, Seminumerical
368      * Algorithms, Third edition, page 142, Algorithm S (Selection sampling
369      * technique).
370      *
371      @return this array
372      */
373     public Array<T> shuffle() {
374         return shuffle(RandomRegistry.getRandom());
375     }
376 
377     @Override
378     public Array<T> setAll(final T value) {
379         _array.cloneIfSealed();
380         for (int i = _start; i < _end; ++i) {
381             _array.data[i= value;
382         }
383         return this;
384     }
385 
386     @Override
387     public Array<T> setAll(final Iterator<? extends T> it) {
388         _array.cloneIfSealed();
389         for (int i = _start; i < _end && it.hasNext(); ++i) {
390             _array.data[i= it.next();
391         }
392         return this;
393     }
394 
395     @Override
396     public Array<T> setAll(final Iterable<? extends T> values) {
397         return setAll(values.iterator());
398     }
399 
400     @Override
401     public Array<T> setAll(final T[] values) {
402         _array.cloneIfSealed();
403         arraycopy(
404             values, 0, _array.data, _start, min(length(), values.length)
405         );
406         return this;
407     }
408 
409     @Override
410     public Array<T> fill(final Factory<? extends T> factory) {
411         requireNonNull(factory);
412 
413         _array.cloneIfSealed();
414         for (int i = _start; i < _end; ++i) {
415             _array.data[i= factory.newInstance();
416         }
417         return this;
418     }
419 
420     @Override
421     public ISeq<T> toISeq() {
422         return new ArrayISeq<>(new ArrayRef(_array.seal().data), _start, _end);
423     }
424 
425     /**
426      * Create a new array which contains the values of {@code this} and the
427      * given {@code value}. The length of the new array is
428      * {@code this.length() + 1}. The returned array is not sealed.
429      *
430      @param value the value to append to this array.
431      @return a new array which contains the values of {@code this} and the
432      *          given {@code value}
433      */
434     public Array<T> add(final T value) {
435         final Array<T> array = new Array<>(length() 1);
436         arraycopy(_array.data, _start, array._array.data, 0, length());
437         array._array.data[array.length() 1= value;
438         return array;
439     }
440 
441     /**
442      * Create a new array which contains the values of {@code this} and the
443      * given {@code array}. The length of the new array is
444      * {@code this.length() + array.length()}. The returned array is not sealed.
445      *
446      @param array the array to append to this array.
447      @return a new array which contains the values of {@code this} and the
448      *          given {@code array}
449      @throws NullPointerException if the {@code arrays} is {@code null}.
450      */
451     public Array<T> add(final Array<? extends T> array) {
452         final Array<T> appended = new Array<>(length() + array.length());
453 
454         arraycopy(
455             _array.data, _start,
456             appended._array.data, 0, length()
457         );
458         arraycopy(
459             array._array.data, array._start,
460             appended._array.data, length(), array.length()
461         );
462 
463         return appended;
464     }
465 
466     /**
467      * Create a new array which contains the values of {@code this} and the
468      * given {@code values}. The length of the new array is
469      * {@code this.length() + values.size()}. The returned array is not sealed.
470      *
471      @param values the array to append to this array.
472      @return a new array which contains the values of {@code this} and the
473      *          given {@code array}
474      @throws NullPointerException if the {@code values} is {@code null}.
475      */
476     public Array<T> add(final Collection<? extends T> values) {
477         requireNonNull(values, "Values");
478         final Array<T> array = new Array<>(length() + values.size());
479 
480         arraycopy(_array.data, _start, array._array.data, 0, length());
481         int index = length();
482         for (Iterator<? extends T>
483             it = values.iterator(); it.hasNext(); ++index)
484         {
485             array._array.data[index= it.next();
486         }
487 
488         return array;
489     }
490 
491     @Override
492     public <B> Array<B> map(final Function<? super T, ? extends B> mapper) {
493         requireNonNull(mapper, "Converter");
494 
495         final int length = length();
496         final Array<B> result = new Array<>(length);
497         assert (result._array.data.length == length);
498 
499         for (int i = length; --i >= 0;) {
500             @SuppressWarnings("unchecked")
501             final T value = (T)_array.data[i + _start];
502             result._array.data[i= mapper.apply(value);
503         }
504         return result;
505     }
506 
507     @Override
508     public Array<T> copy() {
509         return new Array<>(new ArrayRef(toArray())0, length());
510     }
511 
512     @Override
513     public Array<T> subSeq(final int start, final int end) {
514         checkIndex(start, end);
515         return new Array<>(_array, start + _start, _end + end - _length);
516         //return new Array<>(_array, start + _start, end + _start);
517     }
518 
519     @Override
520     public Array<T> subSeq(final int start) {
521         return subSeq(start, length());
522     }
523 
524     @Override
525     public List<T> asList() {
526         return new ArrayMSeqList<>(this);
527     }
528 
529     @Override
530     public ListIterator<T> listIterator() {
531         return new ArrayMSeqIterator<>(this);
532     }
533 
534 
535     /* *************************************************************************
536      * Static factory methods.
537      **************************************************************************/
538 
539     /**
540      * Create a new array from the given values.
541      *
542      @param <T> the element type
543      @param values the array values.
544      @return an new {@code Array} with the given values
545      @throws NullPointerException if the {@code values} array is {@code null}.
546      */
547     @SafeVarargs
548     public static <T> Array<T> of(final T... values) {
549         Array<T> array = empty();
550         if (values.length > 0) {
551             array = new Array<>(values.length);
552             arraycopy(values, 0, array._array.data, 0, values.length);
553         }
554 
555         return array;
556     }
557 
558     /**
559      * Create a new Array from the values of the given {@code Collection}. The
560      * order of the elements are determined by the iterator of the Collection.
561      *
562      @param <T> the element type
563      @param values the array values.
564      @return an new {@code Array} with the given values
565      @throws NullPointerException if the {@code values} array is {@code null}.
566      */
567     public static <T> Array<T> of(final Collection<? extends T> values) {
568         Array<T> array = empty();
569         if (!values.isEmpty()) {
570             array = new Array<>(values.size());
571             int index = 0;
572             for (Iterator<? extends T>
573                 it = values.iterator(); it.hasNext(); ++index)
574             {
575                 array._array.data[index= it.next();
576             }
577         }
578 
579         return array;
580     }
581 
582     /**
583      * Create a new Array from the values of the given {@code Seq}.
584      *
585      @param <T> the element type
586      @param values the array values.
587      @return an new {@code Array} with the given values
588      @throws NullPointerException if the {@code values} array is {@code null}.
589      */
590     public static <T> Array<T> of(final Seq<T> values) {
591         Array<T> array = empty();
592         if (values.length() 0) {
593             if (values instanceof Array<?>) {
594                 array = ((Array<T>)values).copy();
595             else {
596                 array = new Array<>(values.length());
597                 int index = 0;
598                 for (Iterator<? extends T>
599                     it = values.iterator(); it.hasNext(); ++index)
600                 {
601                     array._array.data[index= it.next();
602                 }
603             }
604         }
605 
606         return array;
607     }
608 
609     /**
610      * Boxes the given native array into an {@code Array<Boolean>}.
611      *
612      @param values the native array to box.
613      @return the boxed array.
614      */
615     public static Array<Boolean> box(final boolean... values) {
616         Array<Boolean> array = empty();
617         if (values.length > 0) {
618             array = new Array<>(values.length);
619             for (int i = values.length; --i >= 0;) {
620                 array._array.data[i= values[i];
621             }
622         }
623 
624         return array;
625     }
626 
627 
628     /**
629      * Boxes the given native array into an {@code Array<Char>}.
630      *
631      @param values the native array to box.
632      @return the boxed array.
633      */
634     public static Array<Character> box(final char... values) {
635         Array<Character> array = empty();
636         if (values.length > 0) {
637             array = new Array<>(values.length);
638             for (int i = values.length; --i >= 0;) {
639                 array._array.data[i= values[i];
640             }
641         }
642 
643         return array;
644     }
645 
646     /**
647      * Boxes the given native array into an {@code Array<Short>}.
648      *
649      @param values the native array to box.
650      @return the boxed array.
651      */
652     public static Array<Short> box(final short... values) {
653         Array<Short> array = empty();
654         if (values.length > 0) {
655             array = new Array<>(values.length);
656             for (int i = values.length; --i >= 0;) {
657                 array._array.data[i= values[i];
658             }
659         }
660 
661         return array;
662     }
663 
664     /**
665      * Boxes the given native array into an {@code Array<Integer>}.
666      *
667      @param values the native array to box.
668      @return the boxed array.
669      */
670     public static Array<Integer> box(final int... values) {
671         Array<Integer> array = empty();
672         if (values.length > 0) {
673             array = new Array<>(values.length);
674             for (int i = values.length; --i >= 0;) {
675                 array._array.data[i= values[i];
676             }
677         }
678 
679         return array;
680     }
681 
682     /**
683      * Boxes the given native array into an {@code Array<Long>}.
684      *
685      @param values the native array to box.
686      @return the boxed array.
687      */
688     public static Array<Long> box(final long... values) {
689         Array<Long> array = empty();
690         if (values.length > 0) {
691             array = new Array<>(values.length);
692             for (int i = values.length; --i >= 0;) {
693                 array._array.data[i= values[i];
694             }
695         }
696 
697         return array;
698     }
699 
700     /**
701      * Boxes the given native array into an {@code Array<Float>}.
702      *
703      @param values the native array to box.
704      @return the boxed array.
705      */
706     public static Array<Float> box(final float... values) {
707         Array<Float> array = empty();
708         if (values.length > 0) {
709             array = new Array<>(values.length);
710             for (int i = values.length; --i >= 0;) {
711                 array._array.data[i= values[i];
712             }
713         }
714 
715         return array;
716     }
717 
718     /**
719      * Boxes the given native array into an {@code Array<Double>}.
720      *
721      @param values the native array to box.
722      @return the boxed array.
723      */
724     public static Array<Double> box(final double... values) {
725         Array<Double> array = empty();
726         if (values.length > 0) {
727             array = new Array<>(values.length);
728             for (int i = values.length; --i >= 0;) {
729                 array._array.data[i= values[i];
730             }
731         }
732 
733         return array;
734     }
735 
736     /**
737      * Unboxes the given array to the corresponding native version.
738      *
739      @param values the {@code Array} to unbox.
740      @return the unboxed native array.
741      */
742     public static boolean[] unboxBoolean(final Array<Boolean> values) {
743         final boolean[] array = new boolean[values.length()];
744         for (int i = values._start; i < values._end; ++i) {
745             array[i - values._start(Boolean)values._array.data[i];
746         }
747 
748         return array;
749     }
750 
751     /**
752      * Unboxes the given array to the corresponding native version.
753      *
754      @param values the {@code Array} to unbox.
755      @return the unboxed native array.
756      */
757     public static char[] unboxChar(final Array<Character> values) {
758         final char[] array = new char[values.length()];
759         for (int i = values._start; i < values._end; ++i) {
760             array[i - values._start(Character)values._array.data[i];
761         }
762 
763         return array;
764     }
765 
766     /**
767      * Unboxes the given array to the corresponding native version.
768      *
769      @param values the {@code Array} to unbox.
770      @return the unboxed native array.
771      */
772     public static short[] unboxShort(final Array<Short> values) {
773         final short[] array = new short[values.length()];
774         for (int i = values._start; i < values._end; ++i) {
775             array[i - values._start(Short)values._array.data[i];
776         }
777 
778         return array;
779     }
780 
781     /**
782      * Unboxes the given array to the corresponding native version.
783      *
784      @param values the {@code Array} to unbox.
785      @return the unboxed native array.
786      */
787     public static int[] unboxInt(final Array<Integer> values) {
788         final int[] array = new int[values.length()];
789         for (int i = values._start; i < values._end; ++i) {
790             array[i - values._start(Integer)values._array.data[i];
791         }
792 
793         return array;
794     }
795 
796     /**
797      * Unboxes the given array to the corresponding native version.
798      *
799      @param values the {@code Array} to unbox.
800      @return the unboxed native array.
801      */
802     public static long[] unboxLong(final Array<Long> values) {
803         final long[] array = new long[values.length()];
804         for (int i = values._start; i < values._end; ++i) {
805             array[i - values._start(Long)values._array.data[i];
806         }
807 
808         return array;
809     }
810 
811     /**
812      * Unboxes the given array to the corresponding native version.
813      *
814      @param values the {@code Array} to unbox.
815      @return the unboxed native array.
816      */
817     public static float[] unboxFloat(final Array<Float> values) {
818         final float[] array = new float[values.length()];
819         for (int i = values._start; i < values._end; ++i) {
820             array[i - values._start(Float)values._array.data[i];
821         }
822 
823         return array;
824     }
825 
826     /**
827      * Unboxes the given array to the corresponding native version.
828      *
829      @param values the {@code Array} to unbox.
830      @return the unboxed native array.
831      */
832     public static double[] unboxDouble(final Array<Double> values) {
833         final double[] array = new double[values.length()];
834         for (int i = values._start; i < values._end; ++i) {
835             array[i - values._start(Double)values._array.data[i];
836         }
837 
838         return array;
839     }
840 
841 }