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 }