1 /*
2 * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package java.util.stream;
26
27 import java.util.Spliterator;
28 import java.util.function.DoublePredicate;
29 import java.util.function.IntPredicate;
30 import java.util.function.LongPredicate;
31 import java.util.function.Predicate;
32 import java.util.function.Supplier;
33
34 /**
35 * A short-circuiting {@code TerminalOp} that evaluates a predicate on the elements of a stream pipeline
36 * and determines whether all, any, or none of the elements match a given {@code Predicate}.
37 *
38 * @param <T> The output type of the stream pipeline
39 * @since 1.8
40 */
41 class MatchOp<T> implements TerminalOp<T, Boolean> {
42 private final StreamShape inputShape;
43 protected final MatchKind matchKind;
44 protected final Supplier<BooleanTerminalSink<T>> sinkSupplier;
45
46 /**
47 * Construct a {@code MatchOp}
48 * @param shape The output shape of the stream pipeline
49 * @param matchKind The kind of quantified match (all, any, none)
50 * @param sinkSupplier {@code Supplier} for a {@code Sink} of the appropriate shape which implements the
51 * matching operation
52 */
53 private MatchOp(StreamShape shape, MatchKind matchKind, Supplier<BooleanTerminalSink<T>> sinkSupplier) {
54 this.inputShape = shape;
55 this.matchKind = matchKind;
56 this.sinkSupplier = sinkSupplier;
57 }
58
59 // Boolean specific terminal sink to avoid the boxing costs when returning results
60
61 /**
62 * Base class for match sink variants. Subclasses implement the shape-specific functionality and implement
63 * {@code TerminalSink}.
64 * @param <T> The output type of the stream pipeline
65 */
66 private static abstract class BooleanTerminalSink<T> implements Sink<T> {
67 protected boolean stop;
68 protected boolean value;
69
70 protected BooleanTerminalSink(MatchKind matchKind) {
71 value = !matchKind.shortCircuitResult;
72 }
73
74 public boolean getAndClearState() {
75 return value;
76 }
77
78 @Override
79 public boolean cancellationRequested() {
80 return stop;
81 }
82 }
83
84 /**
85 * Construct a {@code MatchOp} for the given predicate and quantified match criteria
86 * @param predicate The {@code Predicate} to apply to stream elements
87 * @param matchKind The kind of quantified match (all, any, none)
88 * @param <T> The type of stream elements
89 * @return A {@code MatchOp} implementing the desired quantified match criteria
90 */
91 public static <T> MatchOp<T> match(Predicate<? super T> predicate, MatchKind matchKind) {
92 class MatchSink extends BooleanTerminalSink<T> {
93
94 private MatchSink() {
95 super(matchKind);
96 }
97
98 @Override
99 public void accept(T t) {
100 // @@@ assert !stop when SortedOp supports short-circuit on Sink.end
101 // for sequential operations
102 if (!stop && predicate.test(t) == matchKind.stopOnPredicateMatches) {
103 stop = true;
104 value = matchKind.shortCircuitResult;
105 }
106 }
107 }
108
109 // @@@ Change to return MatchSink::new when compiler and runtime bugs are fixed
110 Supplier<BooleanTerminalSink<T>> s = new Supplier<BooleanTerminalSink<T>>() {
111 @Override
112 public BooleanTerminalSink<T> get() {return new MatchSink();}
113 };
114 return new MatchOp<>(StreamShape.REFERENCE, matchKind, s);
115 }
116
117 /**
118 * Construct a {@code MatchOp} for the given predicate and quantified match criteria for an {@code IntStream}
119 * @param predicate The {@code Predicate} to apply to stream elements
120 * @param matchKind The kind of quantified match (all, any, none)
121 * @return A {@code MatchOp} implementing the desired quantified match criteria
122 */
123 public static MatchOp<Integer> match(IntPredicate predicate, MatchKind matchKind) {
124 class MatchSink extends BooleanTerminalSink<Integer> implements Sink.OfInt {
125 private MatchSink() {
126 super(matchKind);
127 }
128
129 @Override
130 public void accept(int t) {
131 if (!stop && predicate.test(t) == matchKind.stopOnPredicateMatches) {
132 stop = true;
133 value = matchKind.shortCircuitResult;
134 }
135 }
136 }
137
138 Supplier<BooleanTerminalSink<Integer>> s = new Supplier<BooleanTerminalSink<Integer>>() {
139 @Override
140 public BooleanTerminalSink<Integer> get() {return new MatchSink();}
141 };
142 return new MatchOp<>(StreamShape.INT_VALUE, matchKind, s);
143 }
144
145 /**
146 * Construct a {@code MatchOp} for the given predicate and quantified match criteria for a {@code LongStream}
147 * @param predicate The {@code Predicate} to apply to stream elements
148 * @param matchKind The kind of quantified match (all, any, none)
149 * @return A {@code MatchOp} implementing the desired quantified match criteria
150 */
151 public static MatchOp<Long> match(LongPredicate predicate, MatchKind matchKind) {
152 class MatchSink extends BooleanTerminalSink<Long> implements Sink.OfLong {
153
154 private MatchSink() {
155 super(matchKind);
156 }
157
158 @Override
159 public void accept(long t) {
160 if (!stop && predicate.test(t) == matchKind.stopOnPredicateMatches) {
161 stop = true;
162 value = matchKind.shortCircuitResult;
163 }
164 }
165 }
166
167 Supplier<BooleanTerminalSink<Long>> s = new Supplier<BooleanTerminalSink<Long>>() {
168 @Override
169 public BooleanTerminalSink<Long> get() {return new MatchSink();}
170 };
171 return new MatchOp<>(StreamShape.LONG_VALUE, matchKind, s);
172 }
173
174 /**
175 * Construct a {@code MatchOp} for the given predicate and quantified match criteria for a {@code DoubleStream}
176 * @param predicate The {@code Predicate} to apply to stream elements
177 * @param matchKind The kind of quantified match (all, any, none)
178 * @return A {@code MatchOp} implementing the desired quantified match criteria
179 */
180 public static MatchOp<Double> match(DoublePredicate predicate, MatchKind matchKind) {
181 class MatchSink extends BooleanTerminalSink<Double> implements Sink.OfDouble {
182
183 private MatchSink() {
184 super(matchKind);
185 }
186
187 @Override
188 public void accept(double t) {
189 if (!stop && predicate.test(t) == matchKind.stopOnPredicateMatches) {
190 stop = true;
191 value = matchKind.shortCircuitResult;
192 }
193 }
194 }
195
196 Supplier<BooleanTerminalSink<Double>> s = new Supplier<BooleanTerminalSink<Double>>() {
197 @Override
198 public BooleanTerminalSink<Double> get() {return new MatchSink();}
199 };
200 return new MatchOp<>(StreamShape.DOUBLE_VALUE, matchKind, s);
201 }
202
203 @Override
204 public int getOpFlags() {
205 return StreamOpFlag.IS_SHORT_CIRCUIT | StreamOpFlag.NOT_ORDERED;
206 }
207
208 @Override
209 public StreamShape inputShape() {
210 return inputShape;
211 }
212
213 @Override
214 public <S> Boolean evaluateSequential(PipelineHelper<S, T> helper) {
215 return helper.into(sinkSupplier.get(), helper.sourceSpliterator()).getAndClearState();
216 }
217
218 @Override
219 public <S> Boolean evaluateParallel(PipelineHelper<S, T> helper) {
220 // Approach for parallel implementation:
221 // - Decompose as per usual
222 // - run match on leaf chunks, call result "b"
223 // - if b == matchKind.shortCircuitOn, complete early and return b
224 // - else if we complete normally, return !shortCircuitOn
225
226 return new MatchTask<>(this, helper).invoke();
227 }
228
229 /**
230 * ForkJoinTask implementation to implement a parallel short-circuiting quantified match
231 * @param <S> The type of source elements for the pipeline
232 * @param <T> The type of output elements for the pipeline
233 */
234 private static class MatchTask<S, T> extends AbstractShortCircuitTask<S, T, Boolean, MatchTask<S, T>> {
235 private final MatchOp<T> op;
236
237 private MatchTask(MatchOp<T> op, PipelineHelper<S, T> helper) {
238 super(helper);
239 this.op = op;
240 }
241
242 private MatchTask(MatchTask<S, T> parent, Spliterator<S> spliterator) {
243 super(parent, spliterator);
244 this.op = parent.op;
245 }
246
247 @Override
248 protected MatchTask<S, T> makeChild(Spliterator<S> spliterator) {
249 return new MatchTask<>(this, spliterator);
250 }
251
252 @Override
253 protected Boolean doLeaf() {
254 boolean b = helper.into(op.sinkSupplier.get(), spliterator).getAndClearState();
255 if (b == op.matchKind.shortCircuitResult)
256 shortCircuit(b);
257 return null;
258 }
259
260 @Override
261 protected Boolean getEmptyResult() {
262 return !op.matchKind.shortCircuitResult;
263 }
264 }
265
266 /**
267 * Enum describing quantified match options -- all match, any match, none match
268 */
269 public enum MatchKind {
270 /** Do all elements match the predicate? */
271 ANY(true, true),
272
273 /** Do any elements match the predicate? */
274 ALL(false, false),
275
276 /** Do no elements match the predicate? */
277 NONE(true, false);
278
279 private final boolean stopOnPredicateMatches;
280 private final boolean shortCircuitResult;
281
282 private MatchKind(boolean stopOnPredicateMatches, boolean shortCircuitResult) {
283 this.stopOnPredicateMatches = stopOnPredicateMatches;
284 this.shortCircuitResult = shortCircuitResult;
285 }
286 }
287 }