View Javadoc

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 }