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