001/*
002 * Java Genetic Algorithm Library (jenetics-8.1.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.ext.moea;
021
022import static java.util.Objects.requireNonNull;
023import static io.jenetics.internal.util.Arrays.revert;
024
025import java.util.AbstractSet;
026import java.util.ArrayList;
027import java.util.Collection;
028import java.util.Comparator;
029import java.util.Iterator;
030import java.util.List;
031import java.util.Objects;
032import java.util.Set;
033import java.util.function.BiPredicate;
034import java.util.function.ToIntFunction;
035import java.util.stream.Collector;
036import java.util.stream.IntStream;
037
038import io.jenetics.util.ISeq;
039import io.jenetics.util.ProxySorter;
040import io.jenetics.util.Seq;
041
042/**
043 * This class only contains non-dominate (Pareto-optimal) elements according to
044 * a given <em>dominance</em> measure. Like a {@link Set}, it only contains no
045 * duplicate entries. Unlike the usual set implementation, the iteration order
046 * is deterministic.
047 * <p>
048 * You can create a new {@code ParetoFront} for {@link Vec} objects
049 * {@snippet lang="java":
050 * final ParetoFront<Vec<double[]>> front = new ParetoFront<>(Vec::dominance);
051 * front.add(Vec.of(1.0, 2.0));
052 * front.add(Vec.of(1.1, 2.5));
053 * front.add(Vec.of(0.9, 2.1));
054 * front.add(Vec.of(0.0, 2.9));
055 * }
056 *
057 * or directly for {@code double[]} array objects
058 * {@snippet lang="java":
059 * final ParetoFront<double[]> front = new ParetoFront<>(Pareto::dominance);
060 * front.add(new double[]{1.0, 2.0});
061 * front.add(new double[]{1.1, 2.5});
062 * front.add(new double[]{0.9, 2.1});
063 * front.add(new double[]{0.0, 2.9});
064 * }
065 *
066 * You only have to specify the <a href="https://en.wikipedia.org/wiki/Pareto_efficiency">
067 *     Pareto dominance/efficiency</a> measure.
068 *
069 * @see Pareto
070 *
071 * @apiNote
072 * Inserting a new element has a time complexity of {@code O(n)}.
073 *
074 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
075 * @version 5.1
076 * @since 4.1
077 */
078public final class ParetoFront<T> extends AbstractSet<T> {
079
080        private final List<T> _population = new ArrayList<>();
081
082        private final Comparator<? super T> _dominance;
083        private final BiPredicate<? super T, ? super T> _equals;
084
085        /**
086         * Create a new {@code ParetoSet} with the given {@code dominance} measure.
087         *
088         * @since 5.1
089         *
090         * @param dominance the <em>Pareto</em> dominance measure
091         * @param equals the equals predicate used for keeping the set distinct
092         * @throws NullPointerException if the given {@code dominance} measure is
093         *         {@code null}
094         */
095        public ParetoFront(
096                final Comparator<? super T> dominance,
097                final BiPredicate<? super T, ? super T> equals
098        ) {
099                _dominance = requireNonNull(dominance);
100                _equals = requireNonNull(equals);
101        }
102
103        /**
104         * Create a new {@code ParetoSet} with the given {@code dominance} measure.
105         *
106         * @param dominance the <em>Pareto</em> dominance measure
107         * @throws NullPointerException if the given {@code dominance} measure is
108         *         {@code null}
109         */
110        public ParetoFront(final Comparator<? super T> dominance) {
111                this(dominance, Objects::equals);
112        }
113
114        /**
115         * Inserts an {@code element} to this pareto front.
116         *
117         * @implNote
118         * Inserting a new element has a time complexity of {@code O(this.size())},
119         * where <em>n</em> is the number of elements of {@code this} pareto-front.
120         *
121         * @param element the element to add
122         * @return {@code true} if this set did not already contain the specified
123         *         element
124         */
125        @Override
126        public boolean add(final T element) {
127                requireNonNull(element);
128
129                boolean updated = false;
130                final Iterator<T> iterator = _population.iterator();
131                while (iterator.hasNext()) {
132                        final T existing = iterator.next();
133
134                        int cmp = _dominance.compare(element, existing);
135                        if (cmp > 0) {
136                                iterator.remove();
137                                updated = true;
138                        } else if (cmp < 0 || _equals.test(element, existing)) {
139                                return updated;
140                        }
141                }
142
143                _population.add(element);
144                return true;
145        }
146
147        /**
148         * Adds all elements of the given collection to {@code this} pareto front.
149         *
150         * @implNote
151         * The runtime complexity of this operation is
152         * {@code O(elements.size()*this.size())}.
153         *
154         * @param elements the elements to add to {@code this} pareto front
155         * @return {@code true} if {@code this} pareto front has been changed,
156         *         {@code false} otherwise
157         */
158        @Override
159        public boolean addAll(final Collection<? extends T> elements) {
160                final int sum = elements.stream()
161                        .mapToInt(e -> add(e) ? 1 : 0)
162                        .sum();
163                return sum > 0;
164        }
165
166        /**
167         * Add the all {@code elements} to {@code this} pareto-set.
168         *
169         * @implNote
170         * Merging two pareto fronts has a time complexity of
171         * {@code O(elements.size()*this.size())}.
172         *
173         * @param elements the elements to add
174         * @return {@code this} pareto-set
175         * @throws NullPointerException if the given parameter is {@code null}
176         */
177        public ParetoFront<T> merge(final ParetoFront<? extends T> elements) {
178                addAll(elements);
179                return this;
180        }
181
182        /**
183         * Trims {@code this} pareto front to the given size. The front elements are
184         * sorted according to its crowding distance, and the elements which have
185         * smaller distance to its neighbors are removed first.
186         *
187         * {@snippet lang="java":
188         * final ParetoFront<Vec<double[]>> front = new ParetoFront<>(Vec::dominance);
189         * front.trim(10, Vec::compare, Vec::distance, Vec::length);
190         * }
191         * The example above reduces the given front to 10 elements.
192         *
193         * @param size the number of front elements after the trim. If
194         *        {@code size() <= size}, nothing is trimmed.
195         * @param comparator the element comparator used for calculating the
196         *        crowded distance
197         * @param distance the element distance measure
198         * @param dimension the number of vector elements of {@code T}
199         * @return {@code this} trimmed pareto front
200         * @throws NullPointerException if one of the objects is {@code null}
201         */
202        public ParetoFront<T> trim(
203                final int size,
204                final ElementComparator<? super T> comparator,
205                final ElementDistance<? super T> distance,
206                final ToIntFunction<? super T> dimension
207        ) {
208                requireNonNull(comparator);
209                requireNonNull(distance);
210                requireNonNull(dimension);
211
212                if (size() > size) {
213                        final double[] distances = Pareto.crowdingDistance(
214                                Seq.viewOf(_population),
215                                comparator,
216                                distance,
217                                dimension
218                        );
219                        final int[] indexes = ProxySorter.sort(distances);
220                        revert(indexes);
221
222                        final List<T> list = IntStream.of(indexes)
223                                .limit(size)
224                                .mapToObj(_population::get)
225                                .toList();
226
227                        _population.clear();
228                        _population.addAll(list);
229                }
230
231                return this;
232        }
233
234        @Override
235        public Iterator<T> iterator() {
236                return _population.iterator();
237        }
238
239        @Override
240        public int size() {
241                return _population.size();
242        }
243
244        @Override
245        public boolean isEmpty() {
246                return _population.isEmpty();
247        }
248
249        /**
250         * Return the elements of {@code this} pareto-front as {@link ISeq}.
251         *
252         * @return the elements of {@code this} pareto-front as {@link ISeq}
253         */
254        public ISeq<T> toISeq() {
255                return ISeq.of(_population);
256        }
257
258        /**
259         * Return a pareto-front collector. The natural order of the elements is
260         * used as pareto-dominance order.
261         *
262         * @param <C> the element type
263         * @return a new pareto-front collector
264         */
265        public static <C extends Comparable<? super C>>
266        Collector<C, ?, ParetoFront<C>> toParetoFront() {
267                return toParetoFront(Comparator.naturalOrder());
268        }
269
270        /**
271         * Return a pareto-front collector with the given pareto {@code dominance}
272         * measure.
273         *
274         * @param dominance the pareto dominance comparator
275         * @param <T> the element type
276         * @return a new pareto-front collector
277         * @throws NullPointerException if the given {@code dominance} collector is
278         *         {@code null}
279         */
280        public static <T> Collector<T, ?, ParetoFront<T>>
281        toParetoFront(final Comparator<? super T> dominance) {
282                requireNonNull(dominance);
283
284                return Collector.of(
285                        () -> new ParetoFront<>(dominance),
286                        ParetoFront::add,
287                        ParetoFront::merge
288                );
289        }
290
291}