Source code

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