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