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