001package ball.util;
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 java.util.Iterator;
022import java.util.Spliterator;
023import java.util.Spliterators.AbstractSpliterator;
024import java.util.Spliterators;
025import java.util.function.Consumer;
026import java.util.function.Supplier;
027import java.util.stream.LongStream;
028
029/**
030 * {@link Spliterator} abstract base class that dispatches to
031 * {@link Spliterator}s supplied through an {@link Spliterator} of
032 * {@link Spliterator} {@link Supplier}s.
033 *
034 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
035 */
036public abstract class DispatchSpliterator<T> extends AbstractSpliterator<T> {
037    private Iterator<Supplier<Spliterator<T>>> spliterators = null;
038    private Spliterator<T> spliterator = null;
039
040    /**
041     * See {@link AbstractSpliterator} constructor.
042     *
043     * @param   estimate        The estimated size of {@link.this}
044     *                          {@link Spliterator} if known, otherwise
045     *                          {@link Long#MAX_VALUE}.
046     * @param   characteristics Properties of this {@link Spliterator}'s
047     *                          source or elements.  If {@link #SIZED} is
048     *                          reported then {@link.this}
049     *                          {@link Spliterator} will additionally report
050     *                          {@link #SUBSIZED}.
051     */
052    protected DispatchSpliterator(long estimate, int characteristics) {
053        super(estimate, characteristics);
054    }
055
056    /**
057     * Method to provide the {@link Spliterator} {@link Supplier}s.  This
058     * method is called sometime after the first call to
059     * {@link #tryAdvance(Consumer)}.
060     *
061     * @return  The {@link Iterator} of {@link Spliterator}
062     *          {@link Supplier}s.
063     */
064    protected abstract Spliterator<Supplier<Spliterator<T>>> spliterators();
065
066    @Override
067    public Spliterator<T> trySplit() {
068        if (spliterators == null) {
069            spliterators = Spliterators.iterator(spliterators());
070        }
071
072        return spliterators.hasNext() ? spliterators.next().get() : null;
073    }
074
075    @Override
076    public boolean tryAdvance(Consumer<? super T> consumer) {
077        boolean accepted = false;
078
079        while (! accepted) {
080            if (spliterator == null) {
081                spliterator = trySplit();
082            }
083
084            if (spliterator != null) {
085                accepted = spliterator.tryAdvance(consumer);
086
087                if (! accepted) {
088                    spliterator = null;
089                }
090            } else {
091                break;
092            }
093        }
094
095        return accepted;
096    }
097
098    /**
099     * Method to count the number of combinations of {@code [k0,kN]} size
100     * that may be chosen from a set of {@code n}-size (binomial
101     * coefficient).
102     *
103     * @param   n               The size of the set.
104     * @param   k0              The beginning of the interval (inclusive) of
105     *                          size of the subsets to be chosen.
106     * @param   kN              The end of the interval (inclusive) of size
107     *                          of the subsets to be chosen.
108     *
109     * @return  The total number of combinations.
110     */
111    protected static long binomial(long n, long k0, long kN) {
112        long size =
113            LongStream.rangeClosed(Math.min(k0, kN), Math.max(k0, kN))
114            .filter(t -> ! (n < t))
115            .map(t -> binomial(n, t))
116            .sum();
117
118        return size;
119    }
120
121    /**
122     * Method to count the number of combinations of {@code k}-size that may
123     * be chosen from a set of {@code n}-size (binomial coefficient).
124     *
125     * @param   n               The size of the set.
126     * @param   k               The size of the subset to be chosen.
127     *
128     * @return  The total number of {@code k}-combinations.
129     */
130    protected static long binomial(long n, long k) {
131        if (n < 0) {
132            throw new IllegalStateException();
133        }
134
135        long product = 1;
136
137        if (k > 0) {
138            switch ((int) n) {
139            case 1:
140            case 0:
141                break;
142
143            default:
144                product = n * binomial(n - 1, k - 1);
145                break;
146            }
147        }
148
149        return product;
150    }
151}