001 /*
002 * Java Genetic Algorithm Library (jenetics-4.3.0).
003 * Copyright (c) 2007-2018 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 */
020 package io.jenetics.engine;
021
022 import static java.util.Objects.requireNonNull;
023 import static io.jenetics.internal.util.Hashes.hash;
024
025 import java.io.Serializable;
026 import java.util.HashSet;
027 import java.util.Objects;
028 import java.util.Set;
029 import java.util.function.Function;
030 import java.util.function.UnaryOperator;
031 import java.util.stream.Collector;
032 import java.util.stream.Stream;
033
034 import io.jenetics.Gene;
035 import io.jenetics.Genotype;
036 import io.jenetics.Optimize;
037 import io.jenetics.Phenotype;
038 import io.jenetics.internal.util.Lazy;
039 import io.jenetics.stat.MinMax;
040 import io.jenetics.util.Factory;
041 import io.jenetics.util.ISeq;
042 import io.jenetics.util.Seq;
043
044 /**
045 * Represents a state of the GA after an evolution step. It also represents the
046 * final state of an evolution process and can be created with an appropriate
047 * collector:
048 * <pre>{@code
049 * final Problem<ISeq<Point>, EnumGene<Point>, Double> tsm = ...;
050 * final EvolutionResult<EnumGene<Point>, Double> result = Engine.builder(tsm)
051 * .optimize(Optimize.MINIMUM).build()
052 * .stream()
053 * .limit(100)
054 * .collect(EvolutionResult.toBestEvolutionResult());
055 * }</pre>
056 *
057 * @see EvolutionStart
058 * @see Engine
059 *
060 * @param <G> the gene type
061 * @param <C> the fitness type
062 *
063 * @implNote
064 * This class is immutable and thread-safe.
065 *
066 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
067 * @since 3.0
068 * @version 4.0
069 */
070 public final class EvolutionResult<
071 G extends Gene<?, G>,
072 C extends Comparable<? super C>
073 >
074 implements Comparable<EvolutionResult<G, C>>, Serializable
075 {
076 private static final long serialVersionUID = 1L;
077
078 private final Optimize _optimize;
079 private final ISeq<Phenotype<G, C>> _population;
080 private final long _generation;
081 private final long _totalGenerations;
082
083 private final EvolutionDurations _durations;
084 private final int _killCount;
085 private final int _invalidCount;
086 private final int _alterCount;
087
088 private final Lazy<Phenotype<G, C>> _best;
089 private final Lazy<Phenotype<G, C>> _worst;
090
091 private EvolutionResult(
092 final Optimize optimize,
093 final ISeq<Phenotype<G, C>> population,
094 final long generation,
095 final long totalGenerations,
096 final EvolutionDurations durations,
097 final int killCount,
098 final int invalidCount,
099 final int alterCount
100 ) {
101 _optimize = requireNonNull(optimize);
102 _population = requireNonNull(population);
103 _generation = generation;
104 _totalGenerations = totalGenerations;
105 _durations = requireNonNull(durations);
106 _killCount = killCount;
107 _invalidCount = invalidCount;
108 _alterCount = alterCount;
109
110 _best = Lazy.of(() -> _population.stream()
111 .max(_optimize.ascending())
112 .orElse(null)
113 );
114
115 _worst = Lazy.of(() -> _population.stream()
116 .min(_optimize.ascending())
117 .orElse(null)
118 );
119 }
120
121 /**
122 * Return the optimization strategy used.
123 *
124 * @return the optimization strategy used
125 */
126 public Optimize getOptimize() {
127 return _optimize;
128 }
129
130 /**
131 * Return the population after the evolution step.
132 *
133 * @return the population after the evolution step
134 */
135 public ISeq<Phenotype<G, C>> getPopulation() {
136 return _population;
137 }
138
139 /**
140 * Return the current list of genotypes of this evolution result.
141 *
142 * @since 3.9
143 *
144 * @return the list of genotypes of this evolution result.
145 */
146 public ISeq<Genotype<G>> getGenotypes() {
147 return _population.stream()
148 .map(Phenotype::getGenotype)
149 .collect(ISeq.toISeq());
150 }
151
152 /**
153 * The current generation.
154 *
155 * @return the current generation
156 */
157 public long getGeneration() {
158 return _generation;
159 }
160
161 /**
162 * Return the generation count evaluated so far.
163 *
164 * @return the total number of generations evaluated so far
165 */
166 public long getTotalGenerations() {
167 return _totalGenerations;
168 }
169
170 /**
171 * Return the timing (meta) information of the evolution step.
172 *
173 * @return the timing (meta) information of the evolution step
174 */
175 public EvolutionDurations getDurations() {
176 return _durations;
177 }
178
179 /**
180 * Return the number of killed individuals.
181 *
182 * @return the number of killed individuals
183 */
184 public int getKillCount() {
185 return _killCount;
186 }
187
188 /**
189 * Return the number of invalid individuals.
190 *
191 * @return the number of invalid individuals
192 */
193 public int getInvalidCount() {
194 return _invalidCount;
195 }
196
197 /**
198 * The number of altered individuals.
199 *
200 * @return the number of altered individuals
201 */
202 public int getAlterCount() {
203 return _alterCount;
204 }
205
206 /**
207 * Return the best {@code Phenotype} of the result population.
208 *
209 * @return the best {@code Phenotype} of the result population
210 */
211 public Phenotype<G, C> getBestPhenotype() {
212 return _best.get();
213 }
214
215 /**
216 * Return the worst {@code Phenotype} of the result population.
217 *
218 * @return the worst {@code Phenotype} of the result population
219 */
220 public Phenotype<G, C> getWorstPhenotype() {
221 return _worst.get();
222 }
223
224 /**
225 * Return the best population fitness.
226 *
227 * @return The best population fitness.
228 */
229 public C getBestFitness() {
230 return _best.get() != null ? _best.get().getFitness() : null;
231 }
232
233 /**
234 * Return the worst population fitness.
235 *
236 * @return The worst population fitness.
237 */
238 public C getWorstFitness() {
239 return _worst.get() != null ? _worst.get().getFitness() : null;
240 }
241
242 /**
243 * Return the next evolution start object with the current population and
244 * the incremented generation.
245 *
246 * @since 4.1
247 *
248 * @return the next evolution start object
249 */
250 public EvolutionStart<G, C> next() {
251 return EvolutionStart.of(_population, _totalGenerations + 1);
252 }
253
254 /**
255 * Return the current evolution result object as an {@code EvolutionStart}
256 * object with the current population and current total generation.
257 *
258 * @since 4.1
259 *
260 * @return the current result as evolution start
261 */
262 public EvolutionStart<G, C> toEvolutionStart() {
263 return EvolutionStart.of(_population, _totalGenerations);
264 }
265
266 /**
267 * Compare {@code this} evolution result with another one, according the
268 * populations best individual.
269 *
270 * @param other the other evolution result to compare
271 * @return a negative integer, zero, or a positive integer as this result
272 * is less than, equal to, or greater than the specified result.
273 */
274 @Override
275 public int compareTo(final EvolutionResult<G, C> other) {
276 return _optimize.compare(_best.get(), other._best.get());
277 }
278
279 private EvolutionResult<G, C> withTotalGenerations(final long total) {
280 return of(
281 _optimize,
282 _population,
283 _generation,
284 total,
285 _durations,
286 _killCount,
287 _invalidCount,
288 _alterCount
289 );
290 }
291
292 @Override
293 public int hashCode() {
294 return
295 hash(_optimize,
296 hash(_population,
297 hash(_generation,
298 hash(_totalGenerations,
299 hash(_durations,
300 hash(_killCount,
301 hash(_invalidCount,
302 hash(_alterCount,
303 hash(getBestFitness(),
304 hash(EvolutionResult.class))))))))));
305 }
306
307 @Override
308 public boolean equals(final Object obj) {
309 return obj == this ||
310 obj instanceof EvolutionResult &&
311 Objects.equals(_optimize,
312 ((EvolutionResult)obj)._optimize) &&
313 Objects.equals(_population,
314 ((EvolutionResult)obj)._population) &&
315 Objects.equals(_generation,
316 ((EvolutionResult)obj)._generation) &&
317 Objects.equals(_totalGenerations,
318 ((EvolutionResult)obj)._totalGenerations) &&
319 Objects.equals(_durations,
320 ((EvolutionResult)obj)._durations) &&
321 Objects.equals(_killCount,
322 ((EvolutionResult)obj)._killCount) &&
323 Objects.equals(_invalidCount,
324 ((EvolutionResult)obj)._invalidCount) &&
325 Objects.equals(_alterCount,
326 ((EvolutionResult)obj)._alterCount) &&
327 Objects.equals(getBestFitness(),
328 ((EvolutionResult)obj).getBestFitness());
329 }
330
331
332 /* *************************************************************************
333 * Some static collector/factory methods.
334 * ************************************************************************/
335
336 /**
337 * Return a collector which collects the best result of an evolution stream.
338 *
339 * <pre>{@code
340 * final Problem<ISeq<Point>, EnumGene<Point>, Double> tsm = ...;
341 * final EvolutionResult<EnumGene<Point>, Double> result = Engine.builder(tsm)
342 * .optimize(Optimize.MINIMUM).build()
343 * .stream()
344 * .limit(100)
345 * .collect(EvolutionResult.toBestEvolutionResult());
346 * }</pre>
347 *
348 * If the collected {@link EvolutionStream} is empty, the collector returns
349 * <b>{@code null}</b>.
350 *
351 * @param <G> the gene type
352 * @param <C> the fitness type
353 * @return a collector which collects the best result of an evolution stream
354 */
355 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
356 Collector<EvolutionResult<G, C>, ?, EvolutionResult<G, C>>
357 toBestEvolutionResult() {
358 return Collector.of(
359 MinMax::<EvolutionResult<G, C>>of,
360 MinMax::accept,
361 MinMax::combine,
362 mm -> mm.getMax() != null
363 ? mm.getMax().withTotalGenerations(mm.getCount())
364 : null
365 );
366 }
367
368 /**
369 * Return a collector which collects the best phenotype of an evolution
370 * stream.
371 *
372 * <pre>{@code
373 * final Problem<ISeq<Point>, EnumGene<Point>, Double> tsm = ...;
374 * final Phenotype<EnumGene<Point>, Double> result = Engine.builder(tsm)
375 * .optimize(Optimize.MINIMUM).build()
376 * .stream()
377 * .limit(100)
378 * .collect(EvolutionResult.toBestPhenotype());
379 * }</pre>
380 *
381 * If the collected {@link EvolutionStream} is empty, the collector returns
382 * <b>{@code null}</b>.
383 *
384 * @param <G> the gene type
385 * @param <C> the fitness type
386 * @return a collector which collects the best phenotype of an evolution
387 * stream
388 */
389 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
390 Collector<EvolutionResult<G, C>, ?, Phenotype<G, C>>
391 toBestPhenotype() {
392 return Collector.of(
393 MinMax::<EvolutionResult<G, C>>of,
394 MinMax::accept,
395 MinMax::combine,
396 mm -> mm.getMax() != null
397 ? mm.getMax().getBestPhenotype()
398 : null
399 );
400 }
401
402 /**
403 * Return a collector which collects the best genotype of an evolution
404 * stream.
405 *
406 * <pre>{@code
407 * final Problem<ISeq<Point>, EnumGene<Point>, Double> tsm = ...;
408 * final Genotype<EnumGene<Point>> result = Engine.builder(tsm)
409 * .optimize(Optimize.MINIMUM).build()
410 * .stream()
411 * .limit(100)
412 * .collect(EvolutionResult.toBestGenotype());
413 * }</pre>
414 *
415 * If the collected {@link EvolutionStream} is empty, the collector returns
416 * <b>{@code null}</b>.
417 *
418 * @param <G> the gene type
419 * @param <C> the fitness type
420 * @return a collector which collects the best genotype of an evolution
421 * stream
422 */
423 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
424 Collector<EvolutionResult<G, C>, ?, Genotype<G>>
425 toBestGenotype() {
426 return Collector.of(
427 MinMax::<EvolutionResult<G, C>>of,
428 MinMax::accept,
429 MinMax::combine,
430 mm -> mm.getMax() != null
431 ? mm.getMax().getBestPhenotype() != null
432 ? mm.getMax().getBestPhenotype().getGenotype()
433 : null
434 : null
435 );
436 }
437
438 /**
439 * Return a collector which collects the best <em>result</em> (in the native
440 * problem space).
441 *
442 * <pre>{@code
443 * final Problem<ISeq<Point>, EnumGene<Point>, Double> tsm = ...;
444 * final ISeq<Point> route = Engine.builder(tsm)
445 * .optimize(Optimize.MINIMUM).build()
446 * .stream()
447 * .limit(100)
448 * .collect(EvolutionResult.toBestResult(tsm.codec().decoder()));
449 * }</pre>
450 *
451 * If the collected {@link EvolutionStream} is empty, the collector returns
452 * <b>{@code null}</b>.
453 *
454 * @since 3.6
455 *
456 * @param decoder the decoder which converts the {@code Genotype} into the
457 * result of the problem space.
458 * @param <T> the <em>native</em> problem result type
459 * @param <G> the gene type
460 * @param <C> the fitness result type
461 * @return a collector which collects the best result of an evolution stream
462 * @throws NullPointerException if the given {@code decoder} is {@code null}
463 */
464 public static <G extends Gene<?, G>, C extends Comparable<? super C>, T>
465 Collector<EvolutionResult<G, C>, ?, T>
466 toBestResult(final Function<Genotype<G>, T> decoder) {
467 requireNonNull(decoder);
468
469 return Collector.of(
470 MinMax::<EvolutionResult<G, C>>of,
471 MinMax::accept,
472 MinMax::combine,
473 mm -> mm.getMax() != null
474 ? mm.getMax().getBestPhenotype() != null
475 ? decoder.apply(mm.getMax().getBestPhenotype().getGenotype())
476 : null
477 : null
478 );
479 }
480
481 /**
482 * Return a collector which collects the best <em>result</em> (in the native
483 * problem space).
484 *
485 * <pre>{@code
486 * final Problem<ISeq<Point>, EnumGene<Point>, Double> tsm = ...;
487 * final ISeq<Point> route = Engine.builder(tsm)
488 * .optimize(Optimize.MINIMUM).build()
489 * .stream()
490 * .limit(100)
491 * .collect(EvolutionResult.toBestResult(tsm.codec()));
492 * }</pre>
493 *
494 * If the collected {@link EvolutionStream} is empty, the collector returns
495 * <b>{@code null}</b>.
496 *
497 * @since 3.6
498 *
499 * @param codec the problem decoder
500 * @param <T> the <em>native</em> problem result type
501 * @param <G> the gene type
502 * @param <C> the fitness result type
503 * @return a collector which collects the best result of an evolution stream
504 * @throws NullPointerException if the given {@code codec} is {@code null}
505 */
506 public static <G extends Gene<?, G>, C extends Comparable<? super C>, T>
507 Collector<EvolutionResult<G, C>, ?, T>
508 toBestResult(final Codec<T, G> codec) {
509 return toBestResult(codec.decoder());
510 }
511
512 /**
513 * Return a mapping function, which removes duplicate individuals from the
514 * population and replaces it with newly created one by the given genotype
515 * {@code factory}.
516 *
517 * <pre>{@code
518 * final Problem<Double, DoubleGene, Integer> problem = ...;
519 * final Engine<DoubleGene, Integer> engine = Engine.builder(problem)
520 * .mapping(EvolutionResult.toUniquePopulation(problem.codec().encoding(), 100))
521 * .build();
522 * final Genotype<DoubleGene> best = engine.stream()
523 * .limit(100);
524 * .collect(EvolutionResult.toBestGenotype());
525 * }</pre>
526 *
527 * @since 4.0
528 * @see Engine.Builder#mapping(Function)
529 *
530 * @param factory the genotype factory which create new individuals
531 * @param maxRetries the maximal number of genotype creation tries
532 * @param <G> the gene type
533 * @param <C> the fitness function result type
534 * @return a mapping function, which removes duplicate individuals from the
535 * population
536 * @throws NullPointerException if the given genotype {@code factory} is
537 * {@code null}
538 */
539 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
540 UnaryOperator<EvolutionResult<G, C>>
541 toUniquePopulation(final Factory<Genotype<G>> factory, final int maxRetries) {
542 requireNonNull(false);
543
544 return result -> {
545 final Seq<Phenotype<G, C>> population = result.getPopulation();
546 final Seq<Genotype<G>> genotypes = result.getGenotypes();
547 final Set<Genotype<G>> elements = new HashSet<>(genotypes.asList());
548
549 EvolutionResult<G, C> uniques = result;
550 if (elements.size() < population.size()) {
551 int retries = 0;
552 while (elements.size() < population.size() && retries < maxRetries) {
553 if (!elements.add(factory.newInstance())) {
554 ++retries;
555 }
556 }
557
558 uniques = result.with(
559 Stream.concat(elements.stream(), genotypes.stream())
560 .limit(population.size())
561 .map(gt -> population.get(0).newInstance(
562 factory.newInstance(), result.getGeneration()))
563 .collect(ISeq.toISeq())
564 );
565 }
566
567 return uniques;
568 };
569 }
570
571 EvolutionResult<G, C> with(final ISeq<Phenotype<G, C>> population) {
572 return EvolutionResult.of(
573 getOptimize(),
574 population,
575 getGeneration(),
576 getTotalGenerations(),
577 getDurations(),
578 getKillCount(),
579 getInvalidCount(),
580 getAlterCount()
581 );
582 }
583
584 /**
585 * Return a mapping function, which removes duplicate individuals from the
586 * population and replaces it with newly created one by the given genotype
587 * {@code factory}.
588 *
589 * <pre>{@code
590 * final Problem<Double, DoubleGene, Integer> problem = ...;
591 * final Engine<DoubleGene, Integer> engine = Engine.builder(problem)
592 * .mapping(EvolutionResult.toUniquePopulation(problem.codec().encoding()))
593 * .build();
594 * final Genotype<DoubleGene> best = engine.stream()
595 * .limit(100);
596 * .collect(EvolutionResult.toBestGenotype());
597 * }</pre>
598 *
599 * @since 4.0
600 * @see Engine.Builder#mapping(Function)
601 *
602 * @param factory the genotype factory which create new individuals
603 * @param <G> the gene type
604 * @param <C> the fitness function result type
605 * @return a mapping function, which removes duplicate individuals from the
606 * population
607 * @throws NullPointerException if the given genotype {@code factory} is
608 * {@code null}
609 */
610 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
611 UnaryOperator<EvolutionResult<G, C>>
612 toUniquePopulation(final Factory<Genotype<G>> factory) {
613 return toUniquePopulation(factory, 100);
614 }
615
616 /**
617 * Return a mapping function, which removes duplicate individuals from the
618 * population and replaces it with newly created one by the existing
619 * genotype factory.
620 *
621 * <pre>{@code
622 * final Problem<Double, DoubleGene, Integer> problem = ...;
623 * final Engine<DoubleGene, Integer> engine = Engine.builder(problem)
624 * .mapping(EvolutionResult.toUniquePopulation(10))
625 * .build();
626 * final Genotype<DoubleGene> best = engine.stream()
627 * .limit(100);
628 * .collect(EvolutionResult.toBestGenotype(5));
629 * }</pre>
630 *
631 * @since 4.0
632 * @see Engine.Builder#mapping(Function)
633 *
634 * @param maxRetries the maximal number of genotype creation tries
635 * @param <G> the gene type
636 * @param <C> the fitness function result type
637 * @return a mapping function, which removes duplicate individuals from the
638 * population
639 * @throws NullPointerException if the given genotype {@code factory} is
640 * {@code null}
641 */
642 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
643 UnaryOperator<EvolutionResult<G, C>> toUniquePopulation(final int maxRetries) {
644 return result -> {
645 final Factory<Genotype<G>> factory = result
646 .getPopulation().get(0)
647 .getGenotype();
648
649 final UnaryOperator<EvolutionResult<G, C>> unifier =
650 toUniquePopulation(factory, maxRetries);
651
652 return unifier.apply(result);
653 };
654 }
655
656 /**
657 * Return a mapping function, which removes duplicate individuals from the
658 * population and replaces it with newly created one by the existing
659 * genotype factory.
660 *
661 * <pre>{@code
662 * final Problem<Double, DoubleGene, Integer> problem = ...;
663 * final Engine<DoubleGene, Integer> engine = Engine.builder(problem)
664 * .mapping(EvolutionResult.toUniquePopulation())
665 * .build();
666 * final Genotype<DoubleGene> best = engine.stream()
667 * .limit(100);
668 * .collect(EvolutionResult.toBestGenotype());
669 * }</pre>
670 *
671 * @since 4.0
672 * @see Engine.Builder#mapping(Function)
673 *
674 * @param <G> the gene type
675 * @param <C> the fitness function result type
676 * @return a mapping function, which removes duplicate individuals from the
677 * population
678 * @throws NullPointerException if the given genotype {@code factory} is
679 * {@code null}
680 */
681 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
682 UnaryOperator<EvolutionResult<G, C>> toUniquePopulation() {
683 return result -> {
684 final Factory<Genotype<G>> factory = result
685 .getPopulation().get(0)
686 .getGenotype();
687
688 final UnaryOperator<EvolutionResult<G, C>> unifier =
689 toUniquePopulation(factory);
690
691 return unifier.apply(result);
692 };
693 }
694
695 /**
696 * Return an new {@code EvolutionResult} object with the given values.
697 *
698 * @param optimize the optimization strategy used
699 * @param population the population after the evolution step
700 * @param generation the current generation
701 * @param totalGenerations the overall number of generations
702 * @param durations the timing (meta) information
703 * @param killCount the number of individuals which has been killed
704 * @param invalidCount the number of individuals which has been removed as
705 * invalid
706 * @param alterCount the number of individuals which has been altered
707 * @param <G> the gene type
708 * @param <C> the fitness type
709 * @return an new evolution result object
710 * @throws java.lang.NullPointerException if one of the parameters is
711 * {@code null}
712 */
713 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
714 EvolutionResult<G, C> of(
715 final Optimize optimize,
716 final ISeq<Phenotype<G, C>> population,
717 final long generation,
718 final long totalGenerations,
719 final EvolutionDurations durations,
720 final int killCount,
721 final int invalidCount,
722 final int alterCount
723 ) {
724 return new EvolutionResult<>(
725 optimize,
726 population,
727 generation,
728 totalGenerations,
729 durations,
730 killCount,
731 invalidCount,
732 alterCount
733 );
734 }
735
736 /**
737 * Return an new {@code EvolutionResult} object with the given values.
738 *
739 * @param optimize the optimization strategy used
740 * @param population the population after the evolution step
741 * @param generation the current generation
742 * @param durations the timing (meta) information
743 * @param killCount the number of individuals which has been killed
744 * @param invalidCount the number of individuals which has been removed as
745 * invalid
746 * @param alterCount the number of individuals which has been altered
747 * @param <G> the gene type
748 * @param <C> the fitness type
749 * @return an new evolution result object
750 * @throws java.lang.NullPointerException if one of the parameters is
751 * {@code null}
752 */
753 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
754 EvolutionResult<G, C> of(
755 final Optimize optimize,
756 final ISeq<Phenotype<G, C>> population,
757 final long generation,
758 final EvolutionDurations durations,
759 final int killCount,
760 final int invalidCount,
761 final int alterCount
762 ) {
763 return new EvolutionResult<>(
764 optimize,
765 population,
766 generation,
767 generation,
768 durations,
769 killCount,
770 invalidCount,
771 alterCount
772 );
773 }
774
775 }
|