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 — <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 > to</tt>
263 * @throws IndexOutOfBoundsException if <tt>from < 0</tt> or
264 * <tt>to > 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 < 0 || (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 }
|