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 */
017package org.apache.commons.functor.core.algorithm;
018
019import java.io.Serializable;
020import java.util.Stack;
021
022import org.apache.commons.functor.BinaryFunction;
023import org.apache.commons.functor.UnaryFunction;
024import org.apache.commons.functor.UnaryProcedure;
025import 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 *
033 * @param <T> the returned evaluation type.
034 * @version $Revision: 1344796 $ $Date: 2012-05-31 12:12:39 -0400 (Thu, 31 May 2012) $
035 */
036public class FoldRight<T> implements UnaryFunction<Generator<T>, T>, BinaryFunction<Generator<T>, T, T>, Serializable {
037
038    /**
039     * serialVersionUID declaration.
040     */
041    private static final long serialVersionUID = 4671387086700391506L;
042
043    /**
044     * Helper class.
045     *
046     * @param <T> the returned evaluation type.
047     */
048    private static class FoldRightHelper<T> implements UnaryProcedure<T> {
049        /**
050         * The stack where storing the wrapped function evaluations.
051         */
052        private final Stack<T> stk = new Stack<T>();
053        /**
054         * The wrapped function.
055         */
056        private final BinaryFunction<? super T, ? super T, ? extends T> function;
057        /**
058         * The seed object.
059         */
060        private final T seed;
061        /**
062         * Flag to check the helper started or not.
063         */
064        private final boolean hasSeed;
065
066        /**
067         * Create a seedless FoldRightHelper.
068         *
069         * @param function The wrapped function
070         */
071        public FoldRightHelper(BinaryFunction<? super T, ? super T, ? extends T> function) {
072            this(null, function);
073        }
074
075        /**
076         * Create a new FoldRightHelper.
077         *
078         * @param seed initial right-side argument
079         * @param function The wrapped function
080         */
081        FoldRightHelper(T seed, BinaryFunction<? super T, ? super T, ? extends T> function) {
082            this.seed = seed;
083            hasSeed = seed != null ? true : false;
084            this.function = function;
085        }
086
087        /**
088         * {@inheritDoc}
089         */
090        public void run(T obj) {
091            stk.push(obj);
092        }
093
094        /**
095         * Get result after processing.
096         * Get current result.
097         * @return Object
098         */
099        T getResult() {
100            T right = seed;
101            if (!hasSeed) {
102                if (stk.isEmpty()) {
103                    return null;
104                }
105                right = stk.pop();
106            }
107            while (!stk.isEmpty()) {
108                right = function.evaluate(stk.pop(), right);
109            }
110            return right;
111        }
112
113    }
114
115    /**
116     * {@link BinaryFunction} to apply to each (seed, next).
117     */
118    private final BinaryFunction<? super T, ? super T, ? extends T> function;
119
120    /**
121     * Create a new FoldRight.
122     * @param function {@link BinaryFunction} to apply to each (seed, next)
123     */
124    public FoldRight(BinaryFunction<? super T, ? super T, ? extends T> function) {
125        this.function = function;
126    }
127
128    /**
129     * {@inheritDoc}
130     * @param obj {@link Generator} to transform
131     */
132    public final T evaluate(Generator<T> obj) {
133        FoldRightHelper<T> helper = new FoldRightHelper<T>(function);
134        obj.run(helper);
135        return helper.getResult();
136    }
137
138    /**
139     * {@inheritDoc}
140     * @param left {@link Generator} to transform
141     * @param right initial right-side seed object
142     */
143    public final T evaluate(Generator<T> left, T right) {
144        FoldRightHelper<T> helper = new FoldRightHelper<T>(right, function);
145        left.run(helper);
146        return helper.getResult();
147    }
148
149    /**
150     * {@inheritDoc}
151     */
152    @Override
153    public final boolean equals(Object obj) {
154        if (obj == this) {
155            return true;
156        }
157        if (!(obj instanceof FoldRight<?>)) {
158            return false;
159        }
160        return ((FoldRight<?>) obj).function.equals(function);
161    }
162
163    /**
164     * {@inheritDoc}
165     */
166    @Override
167    public int hashCode() {
168        return "FoldRight".hashCode() << 2 ^ function.hashCode();
169    }
170
171    /**
172     * {@inheritDoc}
173     */
174    @Override
175    public String toString() {
176        return "FoldRight<" + function + ">";
177    }
178
179}