001package ball.util.stream;
002/*-
003 * ##########################################################################
004 * Utilities
005 * $Id: Combinations.html 6133 2020-06-07 21:34:40Z ball $
006 * $HeadURL: svn+ssh://svn.hcf.dev/var/spool/scm/repository.svn/hcf-dev/blog/2019-03-28-java-streams-and-spliterators/src/main/resources/javadoc/src-html/ball/util/stream/Combinations.html $
007 * %%
008 * Copyright (C) 2008 - 2020 Allen D. Ball
009 * %%
010 * Licensed under the Apache License, Version 2.0 (the "License");
011 * you may not use this file except in compliance with the License.
012 * You may obtain a copy of the License at
013 *
014 *      http://www.apache.org/licenses/LICENSE-2.0
015 *
016 * Unless required by applicable law or agreed to in writing, software
017 * distributed under the License is distributed on an "AS IS" BASIS,
018 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
019 * See the License for the specific language governing permissions and
020 * limitations under the License.
021 * ##########################################################################
022 */
023import ball.util.DispatchSpliterator;
024import java.util.Arrays;
025import java.util.Collection;
026import java.util.Collections;
027import java.util.LinkedList;
028import java.util.List;
029import java.util.Spliterator;
030import java.util.function.Consumer;
031import java.util.function.Predicate;
032import java.util.function.Supplier;
033import java.util.stream.IntStream;
034import java.util.stream.Stream;
035import java.util.stream.StreamSupport;
036import lombok.Getter;
037import lombok.NoArgsConstructor;
038import lombok.Setter;
039import lombok.ToString;
040import lombok.experimental.Accessors;
041
042import static java.util.Objects.requireNonNull;
043import static lombok.AccessLevel.PRIVATE;
044
045/**
046 * {@link Stream} implementaion that provides all combinations of a
047 * {@link List}.
048 *
049 * @param       <T>             The {@link List} element type.
050 *
051 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
052 * @version $Revision: 6133 $
053 */
054public interface Combinations<T> extends Stream<List<T>> {
055
056    /**
057     * Method to get the {@link Stream} of combinations.  Combinations will
058     * be streamed largest to smallest or smallest to largest depending on
059     * the relative magnitude of {@code size0} and {@code sizeN}.  E.g., to
060     * stream largest to smallest specify {@code sizeN} that is greater than
061     * {@code size0}.
062     *
063     * @param   size0           The combination size range start
064     *                          (inclusive).
065     * @param   sizeN           The combination size range end (inclusive).
066     * @param   predicate       The optional {@link Predicate} (may be
067     *                          {@code null}) specifying prerequisite
068     *                          requirement(s) for the combinations.  Any
069     *                          path that does not match will be pruned.
070     * @param   collection      The {@link Collection} of elements to
071     *                          permute.
072     * @param   <T>             The {@link Collection} element type.
073     *
074     * @return  The {@link Stream} of combinations.
075     */
076    public static <T> Stream<List<T>> of(int size0, int sizeN,
077                                         Predicate<List<T>> predicate,
078                                         Collection<T> collection) {
079        SpliteratorSupplier<T> supplier =
080            new SpliteratorSupplier<T>()
081            .collection(collection)
082            .size0(size0).sizeN(sizeN)
083            .predicate(predicate);
084
085        return supplier.stream();
086    }
087
088    /**
089     * Method to get the {@link Stream} of combinations.
090     *
091     * @param   size            The combination size.
092     * @param   collection      The {@link Collection} of elements to
093     *                          permute.
094     * @param   <T>             The {@link Collection} element type.
095     *
096     * @return  The {@link Stream} of combinations.
097     */
098    public static <T> Stream<List<T>> of(int size, Collection<T> collection) {
099        return of(size, size, null, collection);
100    }
101
102    /**
103     * {@link Combinations} {@link Spliterator} {@link Supplier}.
104     */
105    @NoArgsConstructor(access = PRIVATE) @ToString
106    public static class SpliteratorSupplier<T>
107                        implements Supplier<Spliterator<List<T>>> {
108        @Getter @Setter @Accessors(chain = true, fluent = true)
109        private int characteristics =
110            Spliterator.IMMUTABLE
111            | Spliterator.NONNULL
112            | Spliterator.SIZED
113            | Spliterator.SUBSIZED;
114        @Getter @Setter @Accessors(chain = true, fluent = true)
115        private Collection<? extends T> collection = null;
116        @Getter @Setter @Accessors(chain = true, fluent = true)
117        private int size0 = -1;
118        @Getter @Setter @Accessors(chain = true, fluent = true)
119        private int sizeN = -1;
120        @Getter @Setter @Accessors(chain = true, fluent = true)
121        private Predicate<List<T>> predicate = null;
122
123        public SpliteratorSupplier<T> size(int size) {
124            return size0(size).sizeN(size);
125        }
126
127        public Stream<List<T>> stream() {
128            return StreamSupport.<List<T>>stream(get(), false);
129        }
130
131        @Override
132        public Spliterator<List<T>> get() {
133            if (size0() == -1 && sizeN() == -1) {
134                size(collection.size());
135            } else if (size0() == -1) {
136                size0(sizeN());
137            } else if (sizeN() == -1) {
138                sizeN(size0());
139            }
140
141            return new Start();
142        }
143
144        private class Start extends DispatchSpliterator<List<T>> {
145            public Start() {
146                super(binomial(collection().size(), size0(), sizeN()),
147                      SpliteratorSupplier.this.characteristics());
148            }
149
150            @Override
151            protected Spliterator<Supplier<Spliterator<List<T>>>> spliterators() {
152                List<Supplier<Spliterator<List<T>>>> list = new LinkedList<>();
153
154                IntStream.rangeClosed(Math.min(size0(), sizeN()),
155                                      Math.max(size0(), sizeN()))
156                    .filter(t -> ! (collection.size() < t))
157                    .forEach(t -> list.add(() -> new ForSize(t)));
158
159                if (size0() > sizeN()) {
160                    Collections.reverse(list);
161                }
162
163                return list.spliterator();
164            }
165
166            @Override
167            public long estimateSize() {
168                return binomial(collection().size(), size0(), sizeN());
169            }
170
171            @Override
172            public String toString() {
173                return collection() + "/" + Arrays.asList(size0(), sizeN());
174            }
175        }
176
177        private class ForSize extends DispatchSpliterator<List<T>> {
178            private final int size;
179
180            public ForSize(int size) {
181                super(binomial(collection().size(), size),
182                      SpliteratorSupplier.this.characteristics());
183
184                this.size = size;
185            }
186
187            @Override
188            protected Spliterator<Supplier<Spliterator<List<T>>>> spliterators() {
189                Supplier<Spliterator<List<T>>> supplier =
190                    () -> new ForPrefix(size,
191                                        new LinkedList<>(),
192                                        new LinkedList<>(collection()));
193
194                return Stream.of(supplier).spliterator();
195            }
196
197            @Override
198            public long estimateSize() {
199                return binomial(collection().size(), size);
200            }
201
202            @Override
203            public String toString() {
204                return collection() + "/" + Arrays.asList(size);
205            }
206        }
207
208        private class ForPrefix extends DispatchSpliterator<List<T>> {
209            private final int size;
210            private final List<T> prefix;
211            private final List<T> remaining;
212
213            public ForPrefix(int size, List<T> prefix, List<T> remaining) {
214                super(binomial(remaining.size(), size),
215                      SpliteratorSupplier.this.characteristics());
216
217                this.size = size;
218                this.prefix = requireNonNull(prefix);
219                this.remaining = requireNonNull(remaining);
220            }
221
222            @Override
223            protected Spliterator<Supplier<Spliterator<List<T>>>> spliterators() {
224                List<Supplier<Spliterator<List<T>>>> list = new LinkedList<>();
225
226                if (prefix.size() < size) {
227                    for (int i = 0, n = remaining.size(); i < n; i += 1) {
228                        List<T> prefix = new LinkedList<>(this.prefix);
229                        List<T> remaining = new LinkedList<>(this.remaining);
230
231                        prefix.add(remaining.remove(i));
232
233                        list.add(() -> new ForPrefix(size, prefix, remaining));
234                    }
235                } else if (prefix.size() == size) {
236                    list.add(() -> new ForCombination(prefix));
237                } else {
238                    throw new IllegalStateException();
239                }
240
241                return list.spliterator();
242            }
243
244            @Override
245            public boolean tryAdvance(Consumer<? super List<T>> consumer) {
246                Predicate<List<T>> predicate =
247                    SpliteratorSupplier.this.predicate();
248
249                return ((prefix.isEmpty()
250                         || (predicate == null || predicate.test(prefix)))
251                        && super.tryAdvance(consumer));
252            }
253
254            @Override
255            public long estimateSize() {
256                return binomial(remaining.size(), size);
257            }
258
259            @Override
260            public String toString() {
261                return prefix + ":" + remaining + "/" + Arrays.asList(size);
262            }
263        }
264
265        private class ForCombination extends DispatchSpliterator<List<T>> {
266            private final List<T> combination;
267
268            public ForCombination(List<T> combination) {
269                super(1, SpliteratorSupplier.this.characteristics());
270
271                this.combination = requireNonNull(combination);
272            }
273
274            @Override
275            protected Spliterator<Supplier<Spliterator<List<T>>>> spliterators() {
276                Supplier<Spliterator<List<T>>> supplier =
277                    () -> Stream.of(combination).spliterator();
278
279                return Stream.of(supplier).spliterator();
280            }
281
282            @Override
283            public boolean tryAdvance(Consumer<? super List<T>> consumer) {
284                Predicate<List<T>> predicate =
285                    SpliteratorSupplier.this.predicate();
286
287                return ((combination.isEmpty()
288                         || (predicate == null || predicate.test(combination)))
289                        && super.tryAdvance(consumer));
290            }
291
292            @Override
293            public String toString() { return String.valueOf(combination); }
294        }
295    }
296}