001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.apache.commons.functor.core.algorithm;
018    
019    import java.io.Serializable;
020    import java.util.Stack;
021    
022    import org.apache.commons.functor.BinaryFunction;
023    import org.apache.commons.functor.UnaryFunction;
024    import org.apache.commons.functor.UnaryProcedure;
025    import org.apache.commons.functor.generator.Generator;
026    
027    /**
028     * Functional right-fold algorithm against the elements of a {@link Generator}.
029     * Uses the seed object (if supplied) as the initial right-side argument to the {@link BinaryFunction},
030     * then uses the result of that evaluation as the next right-side argument, until the {@link Generator}'s
031     * elements have been expended.
032     * @version $Revision: 1171154 $ $Date: 2011-09-15 17:58:38 +0200 (Thu, 15 Sep 2011) $
033     */
034    public class FoldRight<T> implements UnaryFunction<Generator<T>, T>, BinaryFunction<Generator<T>, T, T>, Serializable {
035    
036        /**
037         * serialVersionUID declaration.
038         */
039        private static final long serialVersionUID = 4671387086700391506L;
040    
041        /**
042         * Helper class
043         */
044        private static class FoldRightHelper<T> implements UnaryProcedure<T> {
045            private final Stack<T> stk = new Stack<T>();
046            private final BinaryFunction<? super T, ? super T, ? extends T> function;
047            private final T seed;
048            private final boolean hasSeed;
049    
050            /**
051             * Create a seedless FoldRightHelper.
052             */
053            public FoldRightHelper(BinaryFunction<? super T, ? super T, ? extends T> function) {
054                this(null, function);
055            }
056    
057            /**
058             * Create a new FoldRightHelper.
059             * @param seed initial right-side argument
060             */
061            FoldRightHelper(T seed, BinaryFunction<? super T, ? super T, ? extends T> function) {
062                this.seed = seed;
063                hasSeed = seed != null ? true : false;
064                this.function = function;
065            }
066    
067            /**
068             * {@inheritDoc}
069             */
070            public void run(T obj) {
071                stk.push(obj);
072            }
073    
074            /**
075             * Get result after processing.
076             * Get current result.
077             * @return Object
078             */
079            T getResult() {
080                T right = seed;
081                if (!hasSeed) {
082                    if (stk.isEmpty()) {
083                        return null;
084                    }
085                    right = stk.pop();
086                }
087                while (!stk.isEmpty()) {
088                    right = function.evaluate(stk.pop(), right);
089                }
090                return right;
091            }
092    
093        }
094    
095        private final BinaryFunction<? super T, ? super T, ? extends T> function;
096    
097        /**
098         * Create a new FoldRight.
099         * @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    }