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}