1 | /* |
2 | * $Id: StepFunctions.java 562 2010-11-11 00:28:13Z PSpeed $ |
3 | * |
4 | * The Filament BSD license. |
5 | * |
6 | * Copyright (c) 2009-2010, the original author or authors |
7 | * |
8 | * Redistribution and use in source and binary forms, with or without |
9 | * modification, are permitted provided that the following conditions |
10 | * are met: |
11 | * |
12 | * 1) Redistributions of source code must retain the above copyright notice, |
13 | * this list of conditions and the following disclaimer. |
14 | * 2) Redistributions in binary form must reproduce the above copyright |
15 | * notice, this list of conditions and the following disclaimer in the |
16 | * documentation and/or other materials provided with the distribution. |
17 | * 3) Neither the names "Filament", "fgraph.org", "filamentgraph.org", nor the |
18 | * names of its contributors may be used to endorse or promote products |
19 | * derived from this software without specific prior written permission. |
20 | * |
21 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
22 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
23 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
24 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
25 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
26 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
27 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
28 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
29 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
30 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
31 | * POSSIBILITY OF SUCH DAMAGE. |
32 | */ |
33 | |
34 | package org.fgraph.steps; |
35 | |
36 | import java.io.Serializable; |
37 | import java.util.*; |
38 | |
39 | import com.google.common.base.Function; |
40 | import com.google.common.base.Predicate; |
41 | import com.google.common.base.Predicates; |
42 | import com.google.common.collect.Iterables; |
43 | |
44 | |
45 | /** |
46 | * Set of utility functions that takes a starting step |
47 | * and produces zero to many result child steps. |
48 | * |
49 | * <p>Unless otherwise specified, all methods return serializable |
50 | * functions as long as they're given serializable parameters.</p> |
51 | * |
52 | * @version $Revision: 562 $ |
53 | * @author Paul Speed |
54 | */ |
55 | public class StepFunctions |
56 | { |
57 | /** |
58 | * Chains two functions together such the the individual element |
59 | * results from the first function are passed one at a time to the |
60 | * second function. All of the result Iterables are aggregated. |
61 | * Note: The argument ordering here is the opposite of of Functions.compose(). |
62 | */ |
63 | public static <A, B, C> StepFunction<A,C> chain( StepFunction<A,? extends B> f1, |
64 | StepFunction<B,C> f2 ) |
65 | { |
66 | return new ChainFunction<A,B,C>( f1, f2 ); |
67 | } |
68 | |
69 | /** |
70 | * Creates a function that concatenates the output of two other |
71 | * functions provided the common apply() input value. |
72 | */ |
73 | public static <S,T> StepFunction<S,T> concat( StepFunction<S,T> f1, StepFunction<S,T> f2 ) |
74 | { |
75 | return new ConcatFunction<S,T>( f1, f2 ); |
76 | } |
77 | |
78 | /** |
79 | * Creates a function that returns a fixed set of results no matter |
80 | * the input. |
81 | */ |
82 | public static <S,T> StepFunction<S,T> constant( T... values ) |
83 | { |
84 | List<T> list; |
85 | if( values == null ) |
86 | list = Collections.singletonList(null); |
87 | else |
88 | list = Arrays.asList(values); |
89 | return new ConstantFunction<S,T>(list); |
90 | } |
91 | |
92 | /** |
93 | * Creates a StepFunction adapter that transforms its input to a |
94 | * singleton Collection wrapped output using the supplied transform function. |
95 | * In other words, the actual processing is basically: |
96 | * Collections.singleton( transform.apply(value) ) |
97 | * |
98 | * <p>For the typical use-case, it is better to call the two-arg |
99 | * transform method that takes a delegate step function. This function |
100 | * is for composing chains where an input function may not be known |
101 | * or available at creation. There is additional overhead to create |
102 | * the one-per result singleton Iterables that is avoided in the two-arg |
103 | * version.</p> |
104 | */ |
105 | public static <S,T> StepFunction<S,T> transform( Function<S,T> transform ) |
106 | { |
107 | return new TransformDecorator<S,T>( transform ); |
108 | } |
109 | |
110 | /** |
111 | * Creates a StepFunction adapter that filters its input |
112 | * by passing it through the specified predicate. If the source |
113 | * passes the filter then it is wrapped in a Collection.sinleton() |
114 | * for return, otherwise an empty Iterable is returned. |
115 | * |
116 | * <p>For the typical use-case, it is better to call the two-arg |
117 | * filter() method that takes a delegate function. This function is |
118 | * for composing chains where an input function may not be known or |
119 | * or available at creation. There is additional overhead to create |
120 | * the one-per result singleton Iterables that is avoided in the two-arg |
121 | * version.</p> |
122 | */ |
123 | public static <T> StepFunction<T,T> filter( Predicate<T> filter ) |
124 | { |
125 | return new FilterDecorator<T>( filter ); |
126 | } |
127 | |
128 | /** |
129 | * Creates a function that adapts non-Step based results into |
130 | * root-level Step results. |
131 | */ |
132 | public static <T> StepFunction<T,Step<T>> wrapSteps() |
133 | { |
134 | return wrapSteps( (Step)null ); |
135 | } |
136 | |
137 | /** |
138 | * Creates a function that adapts non-Step based results into |
139 | * Step results with the supplied constant parent. |
140 | */ |
141 | public static <T> StepFunction<T,Step<T>> wrapSteps( Step parent ) |
142 | { |
143 | return transform( new WrapStep<T>( parent ) ); |
144 | } |
145 | |
146 | /** |
147 | * Creates a function that adapts the results of the specified |
148 | * delegate function into Steps using the specific constant |
149 | * parent. This is the preferred method of wrapping if another |
150 | * function is producing the non-step results, versus the single-arg |
151 | * wrapSteps which is useful at the head of a chain. |
152 | */ |
153 | public static <S,T> StepFunction<S,Step<T>> wrapSteps( StepFunction<S,T> delegate, Step parent ) |
154 | { |
155 | if( delegate == null ) |
156 | throw new IllegalArgumentException( "delegate cannot be null." ); |
157 | return transform( delegate, new WrapStep<T>( parent ) ); |
158 | } |
159 | |
160 | /** |
161 | * Creates a function that adapts the results of the specified |
162 | * delegate function into Steps using the Step supplied to apply() |
163 | * as the parent and its value as the value passed to the delegate |
164 | * function. This is useful for adapting non-step based functions |
165 | * into step-based chains where the full path is maintained. |
166 | */ |
167 | public static <S,T> StepFunction<Step<S>,Step<T>> adaptToSteps( StepFunction<S,T> delegate ) |
168 | { |
169 | return new StepAdapter<S,T>( delegate ); |
170 | } |
171 | |
172 | /** |
173 | * Creates a function that adapts a Step-based function for non-step |
174 | * usage by wrapping any applied objects in a DefaultStep and unwrapping |
175 | * any returned results. In other words, a function that takes a Step<S> and produces |
176 | * Step<T>'s can be adapted into a function that taks <S> and produces |
177 | * <T>. This effectively equivalent to unwrapSteps( chain( wrapSteps, delegate ) ) |
178 | */ |
179 | public static <S,T> StepFunction<S,T> adaptFromSteps( StepFunction<Step<S>,Step<T>> delegate ) |
180 | { |
181 | // Would be more efficient as a custom function. |
182 | return unwrapSteps( chain( StepFunctions.<S>wrapSteps(), delegate ) ); |
183 | } |
184 | |
185 | /** |
186 | * Creates a function that unwraps Step-based results into |
187 | * their component values. |
188 | */ |
189 | public static <T> StepFunction<Step<T>,T> unwrapSteps() |
190 | { |
191 | return transform( new UnwrapStep<T>() ); |
192 | } |
193 | |
194 | /** |
195 | * Creates a function that unwraps the results of the |
196 | * specified delegate function into the Step component values. |
197 | */ |
198 | public static <S,T> StepFunction<S,T> unwrapSteps( StepFunction<S,? extends Step<T>> delegate ) |
199 | { |
200 | return transform( delegate, new UnwrapStep<T>() ); |
201 | } |
202 | |
203 | /** |
204 | * Creates a StepFunction that filters the results of a delegate |
205 | * StepFunction using the supplied predicate filter. |
206 | */ |
207 | public static <S,T> StepFunction<S,T> filter( StepFunction<S,T> delegate, Predicate<? super T> filter ) |
208 | { |
209 | return new FilterFunction<S,T>( delegate, filter ); |
210 | } |
211 | |
212 | /** |
213 | * Creates a StepFunction that transforms the results of a delegate |
214 | * StepFunction using the supplied transform function. |
215 | */ |
216 | public static <A,B,C> StepFunction<A,C> transform( StepFunction<A,B> delegate, |
217 | Function<? super B,C> transform ) |
218 | { |
219 | // Note: in case you are wondering why: |
220 | // StepFunction<A,B> delegate, Function<? super B,C> transform |
221 | // instead of: |
222 | // StepFunction<A,? extends B> delegate, Function<B,C> transform |
223 | // |
224 | // It's because (I think) type resolution is not as smart |
225 | // as a human and is evaluating left to right. So once B |
226 | // is locked in with the first parameter, it doesn't matter if |
227 | // it could slide to support the second. |
228 | // |
229 | // This came up in StepDemo's all() method where we were calling |
230 | // transform with Stepfunction<Class,Method> and Function<Object,String>. |
231 | // Once <B> has been chosen as Method, there is no way to resolve |
232 | // things. In Google's Functions.compose() the ? extends B works |
233 | // because the parameters are in the reverse order. |
234 | return new TransformFunction<A,B,C>( delegate, transform ); |
235 | } |
236 | |
237 | /** |
238 | * Executes one of two delegate functions depending on the result |
239 | * of a predicate applied to the source object. |
240 | */ |
241 | public static <S,T> StepFunction<S,T> branch( Predicate<? super S> condition, |
242 | StepFunction<S,T> doTrue, |
243 | StepFunction<S,T> doFalse ) |
244 | { |
245 | return new ConditionalDelegator<S,T>( condition, doTrue, doFalse ); |
246 | } |
247 | |
248 | /** |
249 | * Convenience method that returns empty results for any source matching |
250 | * the supplied predicate and leaves those results out of any other |
251 | * adjacency sets. This is useful for pruning traversal hierarchies. |
252 | * This is the equivalent of branch( condition, null, delegate ) with a |
253 | * filter( branch, not condition ) |
254 | */ |
255 | public static <S,T extends S> StepFunction<S,T> prune( StepFunction<S,T> delegate, |
256 | Predicate<? super S> condition ) |
257 | { |
258 | StepFunction<S,T> b = branch( condition, null, delegate ); |
259 | return filter( b, Predicates.not(condition) ); |
260 | } |
261 | |
262 | /** |
263 | * Wraps the non-step elements of the specified Iterable |
264 | * in the DefaultStep with the supplied Step as a parent. |
265 | * This is used by other function implementations to adapt non-step |
266 | * based access into steps. |
267 | */ |
268 | public static <T> Iterable<Step<T>> doWrapSteps( Step parent, Iterable<T> children ) |
269 | { |
270 | return Iterables.transform( children, new WrapStep<T>(parent) ); |
271 | } |
272 | |
273 | /** |
274 | * Returns a raw function that can accept a single Step<T> and return |
275 | * a unwrapped single T value. |
276 | */ |
277 | public static <T> Function<Step<T>,T> unwrapStep() |
278 | { |
279 | return new UnwrapStep<T>(); |
280 | } |
281 | |
282 | /** |
283 | * Returns a raw function that can accept a single T and return |
284 | * a wrapped root Step<T> value. |
285 | */ |
286 | public static <T> Function<T,Step<T>> wrapStep() |
287 | { |
288 | return new WrapStep<T>(null); |
289 | } |
290 | |
291 | /** |
292 | * Returns a raw function that can accept a single T and return |
293 | * a wrapped Step<T> value with the specified parent. |
294 | */ |
295 | public static <T> Function<T,Step<T>> wrapStep( Step parent ) |
296 | { |
297 | return new WrapStep<T>(parent); |
298 | } |
299 | |
300 | private static class WrapStep<T> implements Function<T, Step<T>>, Serializable |
301 | { |
302 | static final long serialVersionUID = 1L; |
303 | |
304 | private Step parent; |
305 | |
306 | public WrapStep( Step parent ) |
307 | { |
308 | this.parent = parent; |
309 | } |
310 | |
311 | public Step<T> apply( T value ) |
312 | { |
313 | return new DefaultStep<T>( parent, value ); |
314 | } |
315 | |
316 | public String toString() |
317 | { |
318 | if( parent == null ) |
319 | return "WrapStep[]"; |
320 | return "WrapStep[parent=" + parent + "]"; |
321 | } |
322 | } |
323 | |
324 | private static class UnwrapStep<T> implements Function<Step<T>, T>, Serializable |
325 | { |
326 | static final long serialVersionUID = 1L; |
327 | |
328 | public UnwrapStep() |
329 | { |
330 | } |
331 | |
332 | public T apply( Step<T> step ) |
333 | { |
334 | return step.getValue(); |
335 | } |
336 | |
337 | public String toString() |
338 | { |
339 | return "UnwrapStep[]"; |
340 | } |
341 | } |
342 | |
343 | /** |
344 | * Wraps a delegate function to adapt it into a |
345 | * step-based StepFunction. |
346 | */ |
347 | private static class StepAdapter<S,T> implements StepFunction<Step<S>,Step<T>>, Serializable |
348 | { |
349 | static final long serialVersionUID = 1L; |
350 | |
351 | private Function<S,? extends Iterable<T>> delegate; |
352 | |
353 | public StepAdapter( Function<S,? extends Iterable<T>> delegate ) |
354 | { |
355 | if( delegate == null ) |
356 | throw new IllegalArgumentException( "delegate cannot be null." ); |
357 | this.delegate = delegate; |
358 | } |
359 | |
360 | public Iterable<Step<T>> apply( Step<S> step ) |
361 | { |
362 | // Wrap all of the results in steps with |
363 | // the passed step as parent |
364 | return Iterables.transform( delegate.apply(step.getValue()), |
365 | new WrapStep<T>(step) ); |
366 | } |
367 | |
368 | public String toString() |
369 | { |
370 | return "StepAdapter[" + delegate + "]"; |
371 | } |
372 | } |
373 | |
374 | private static class ConstantFunction<S,T> implements StepFunction<S,T>, Serializable |
375 | { |
376 | static final long serialVersionUID = 1L; |
377 | |
378 | private List<T> values; |
379 | |
380 | public ConstantFunction( List<T> values ) |
381 | { |
382 | this.values = values; |
383 | } |
384 | |
385 | public Iterable<T> apply( S object ) |
386 | { |
387 | return values; |
388 | } |
389 | |
390 | public String toString() |
391 | { |
392 | return "Constant[" + values + "]"; |
393 | } |
394 | } |
395 | |
396 | /** |
397 | * Executes a delegate function based on the result of a Predicate. |
398 | * Either the true function or the false function is executed. |
399 | * If no function exists for a particular branch then an empty |
400 | * Iterable is returned. |
401 | */ |
402 | private static class ConditionalDelegator<S,T> implements StepFunction<S,T>, Serializable |
403 | { |
404 | static final long serialVersionUID = 1L; |
405 | |
406 | private Predicate<? super S> condition; |
407 | private Function<S,? extends Iterable<T>> trueDelegate; |
408 | private Function<S,? extends Iterable<T>> falseDelegate; |
409 | |
410 | public ConditionalDelegator( Predicate<? super S> condition, |
411 | Function<S,? extends Iterable<T>> trueDelegate, |
412 | Function<S,? extends Iterable<T>> falseDelegate ) |
413 | { |
414 | this.condition = condition; |
415 | this.trueDelegate = trueDelegate; |
416 | this.falseDelegate = falseDelegate; |
417 | } |
418 | |
419 | public Iterable<T> apply( S object ) |
420 | { |
421 | if( condition == null || condition.apply(object) ) |
422 | { |
423 | if( trueDelegate != null ) |
424 | return trueDelegate.apply(object); |
425 | } |
426 | else |
427 | { |
428 | if( falseDelegate != null ) |
429 | return falseDelegate.apply(object); |
430 | } |
431 | return Collections.emptySet(); |
432 | } |
433 | |
434 | public String toString() |
435 | { |
436 | return "Branch[condition=" + condition |
437 | + ", true:" + trueDelegate |
438 | + ", false:" + falseDelegate + "]"; |
439 | } |
440 | } |
441 | |
442 | /** |
443 | * Step function that delegates to another function but |
444 | * wraps its result in a singleton collection to meet the |
445 | * StepFunction contract. |
446 | */ |
447 | private static class TransformDecorator<S,T> implements StepFunction<S,T>, Serializable |
448 | { |
449 | static final long serialVersionUID = 1L; |
450 | |
451 | private Function<S,T> transform; |
452 | |
453 | public TransformDecorator( Function<S,T> transform ) |
454 | { |
455 | if( transform == null ) |
456 | throw new IllegalArgumentException( "transform cannot be null." ); |
457 | this.transform = transform; |
458 | } |
459 | |
460 | public Iterable<T> apply( S object ) |
461 | { |
462 | T result = transform.apply( object ); |
463 | return Collections.singleton( result ); |
464 | } |
465 | |
466 | public String toString() |
467 | { |
468 | return "Transform[" + transform + "]"; |
469 | } |
470 | } |
471 | |
472 | private static class FilterDecorator<T> implements StepFunction<T,T>, Serializable |
473 | { |
474 | static final long serialVersionUID = 1L; |
475 | |
476 | private Predicate<T> filter; |
477 | |
478 | public FilterDecorator( Predicate<T> filter ) |
479 | { |
480 | if( filter == null ) |
481 | throw new IllegalArgumentException( "filter cannot be null." ); |
482 | this.filter = filter; |
483 | } |
484 | |
485 | public Iterable<T> apply( T object ) |
486 | { |
487 | if( !filter.apply(object) ) |
488 | return Collections.emptySet(); |
489 | return Collections.singleton( object ); |
490 | } |
491 | |
492 | public String toString() |
493 | { |
494 | return "Filter[" + filter + "]"; |
495 | } |
496 | } |
497 | |
498 | // Note to self: if you ever think you need a prefilter function, |
499 | // take a deep breath and go back and look at branch()/ConditionalDelegator. |
500 | // It's the uber-prefilter function. |
501 | private static class FilterFunction<S,T> implements StepFunction<S,T>, Serializable |
502 | { |
503 | static final long serialVersionUID = 1L; |
504 | |
505 | private Function<S,? extends Iterable<T>> delegate; |
506 | private Predicate<? super T> filter; |
507 | |
508 | public FilterFunction( Function<S,? extends Iterable<T>> delegate, Predicate<? super T> filter ) |
509 | { |
510 | if( delegate == null ) |
511 | throw new IllegalArgumentException( "delegate cannot be null." ); |
512 | if( filter == null ) |
513 | throw new IllegalArgumentException( "filter cannot be null." ); |
514 | this.delegate = delegate; |
515 | this.filter = filter; |
516 | } |
517 | |
518 | public Iterable<T> apply( S object ) |
519 | { |
520 | Iterable<T> results = delegate.apply(object); |
521 | return Iterables.filter( results, filter ); |
522 | } |
523 | |
524 | public String toString() |
525 | { |
526 | return "Filter[" + delegate + " : " + filter + "]"; |
527 | } |
528 | } |
529 | |
530 | private static class TransformFunction<A,B,C> implements StepFunction<A,C>, Serializable |
531 | { |
532 | static final long serialVersionUID = 1L; |
533 | |
534 | private Function<A,? extends Iterable<B>> delegate; |
535 | private Function<? super B,C> transform; |
536 | |
537 | public TransformFunction( Function<A,? extends Iterable<B>> delegate, |
538 | Function<? super B,C> transform ) |
539 | { |
540 | if( delegate == null ) |
541 | throw new IllegalArgumentException( "delegate cannot be null." ); |
542 | if( transform == null ) |
543 | throw new IllegalArgumentException( "transform cannot be null." ); |
544 | this.delegate = delegate; |
545 | this.transform = transform; |
546 | } |
547 | |
548 | public Iterable<C> apply( A object ) |
549 | { |
550 | Iterable<B> results = delegate.apply(object); |
551 | return Iterables.transform( results, transform ); |
552 | } |
553 | |
554 | public String toString() |
555 | { |
556 | return "Transform[" + delegate + " : " + transform + "]"; |
557 | } |
558 | } |
559 | |
560 | private static class ConcatFunction<S,T> implements StepFunction<S,T>, Serializable |
561 | { |
562 | static final long serialVersionUID = 1L; |
563 | |
564 | private Function<S,? extends Iterable<T>> f1; |
565 | private Function<S,? extends Iterable<T>> f2; |
566 | |
567 | public ConcatFunction( Function<S,? extends Iterable<T>> f1, |
568 | Function<S,? extends Iterable<T>> f2 ) |
569 | { |
570 | if( f1 == null || f2 == null ) |
571 | throw new IllegalArgumentException( "Supplied functions cannot be null." ); |
572 | this.f1 = f1; |
573 | this.f2 = f2; |
574 | } |
575 | |
576 | public Iterable<T> apply( S object ) |
577 | { |
578 | Iterable<T> r1 = f1.apply(object); |
579 | Iterable<T> r2 = f2.apply(object); |
580 | return Iterables.concat( r1, r2 ); |
581 | } |
582 | |
583 | public String toString() |
584 | { |
585 | return "Concat[" + f1 + " + " + f2 + "]"; |
586 | } |
587 | } |
588 | |
589 | } |