1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.functor.core.algorithm;
18
19 import java.io.Serializable;
20 import java.util.Stack;
21
22 import org.apache.commons.functor.BinaryFunction;
23 import org.apache.commons.functor.UnaryFunction;
24 import org.apache.commons.functor.UnaryProcedure;
25 import org.apache.commons.functor.generator.Generator;
26
27 /**
28 * Functional right-fold algorithm against the elements of a {@link Generator}.
29 * Uses the seed object (if supplied) as the initial right-side argument to the {@link BinaryFunction},
30 * then uses the result of that evaluation as the next right-side argument, until the {@link Generator}'s
31 * elements have been expended.
32 * @version $Revision: 1171154 $ $Date: 2011-09-15 17:58:38 +0200 (Thu, 15 Sep 2011) $
33 */
34 public class FoldRight<T> implements UnaryFunction<Generator<T>, T>, BinaryFunction<Generator<T>, T, T>, Serializable {
35
36 /**
37 * serialVersionUID declaration.
38 */
39 private static final long serialVersionUID = 4671387086700391506L;
40
41 /**
42 * Helper class
43 */
44 private static class FoldRightHelper<T> implements UnaryProcedure<T> {
45 private final Stack<T> stk = new Stack<T>();
46 private final BinaryFunction<? super T, ? super T, ? extends T> function;
47 private final T seed;
48 private final boolean hasSeed;
49
50 /**
51 * Create a seedless FoldRightHelper.
52 */
53 public FoldRightHelper(BinaryFunction<? super T, ? super T, ? extends T> function) {
54 this(null, function);
55 }
56
57 /**
58 * Create a new FoldRightHelper.
59 * @param seed initial right-side argument
60 */
61 FoldRightHelper(T seed, BinaryFunction<? super T, ? super T, ? extends T> function) {
62 this.seed = seed;
63 hasSeed = seed != null ? true : false;
64 this.function = function;
65 }
66
67 /**
68 * {@inheritDoc}
69 */
70 public void run(T obj) {
71 stk.push(obj);
72 }
73
74 /**
75 * Get result after processing.
76 * Get current result.
77 * @return Object
78 */
79 T getResult() {
80 T right = seed;
81 if (!hasSeed) {
82 if (stk.isEmpty()) {
83 return null;
84 }
85 right = stk.pop();
86 }
87 while (!stk.isEmpty()) {
88 right = function.evaluate(stk.pop(), right);
89 }
90 return right;
91 }
92
93 }
94
95 private final BinaryFunction<? super T, ? super T, ? extends T> function;
96
97 /**
98 * Create a new FoldRight.
99 * @param function {@link BinaryFunction} to apply to each (seed, next)
100 */
101 public FoldRight(BinaryFunction<? super T, ? super T, ? extends T> function) {
102 this.function = function;
103 }
104
105 /**
106 * {@inheritDoc}
107 * @param obj {@link Generator} to transform
108 */
109 public final T evaluate(Generator<T> obj) {
110 FoldRightHelper<T> helper = new FoldRightHelper<T>(function);
111 obj.run(helper);
112 return helper.getResult();
113 }
114
115 /**
116 * {@inheritDoc}
117 * @param left {@link Generator} to transform
118 * @param right initial right-side seed object
119 */
120 public final T evaluate(Generator<T> left, T right) {
121 FoldRightHelper<T> helper = new FoldRightHelper<T>(right, function);
122 left.run(helper);
123 return helper.getResult();
124 }
125
126 /**
127 * {@inheritDoc}
128 */
129 public final boolean equals(Object obj) {
130 if (obj == this) {
131 return true;
132 }
133 if (!(obj instanceof FoldRight<?>)) {
134 return false;
135 }
136 return ((FoldRight<?>) obj).function.equals(function);
137 }
138
139 /**
140 * {@inheritDoc}
141 */
142 public int hashCode() {
143 return "FoldRight".hashCode() << 2 ^ function.hashCode();
144 }
145
146 }