| Clover coverage report - PLT Utilities Test Coverage (plt-20120304-r5436) |
|
 |
|
|||||||||||||||||||
| Source file | Conditionals | Statements | Methods | TOTAL | |||||||||||||||
| PrecomputedRecursionStack.java | 0% | 0% | 0% | 0% |
|
||||||||||||||
| 1 | /*BEGIN_COPYRIGHT_BLOCK* | |
| 2 | ||
| 3 | PLT Utilities BSD License | |
| 4 | ||
| 5 | Copyright (c) 2007-2010 JavaPLT group at Rice University | |
| 6 | All rights reserved. | |
| 7 | ||
| 8 | Developed by: Java Programming Languages Team | |
| 9 | Rice University | |
| 10 | http://www.cs.rice.edu/~javaplt/ | |
| 11 | ||
| 12 | Redistribution and use in source and binary forms, with or without modification, are permitted | |
| 13 | provided that the following conditions are met: | |
| 14 | ||
| 15 | - Redistributions of source code must retain the above copyright notice, this list of conditions | |
| 16 | and the following disclaimer. | |
| 17 | - Redistributions in binary form must reproduce the above copyright notice, this list of | |
| 18 | conditions and the following disclaimer in the documentation and/or other materials provided | |
| 19 | with the distribution. | |
| 20 | - Neither the name of the JavaPLT group, Rice University, nor the names of the library's | |
| 21 | contributors may be used to endorse or promote products derived from this software without | |
| 22 | specific prior written permission. | |
| 23 | ||
| 24 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR | |
| 25 | IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND | |
| 26 | FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS AND | |
| 27 | CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
| 28 | DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
| 29 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER | |
| 30 | IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT | |
| 31 | OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
| 32 | ||
| 33 | *END_COPYRIGHT_BLOCK*/ | |
| 34 | ||
| 35 | package edu.rice.cs.plt.recur; | |
| 36 | ||
| 37 | import java.util.LinkedList; | |
| 38 | import java.util.Map; | |
| 39 | import java.util.HashMap; | |
| 40 | import edu.rice.cs.plt.tuple.Wrapper; | |
| 41 | import edu.rice.cs.plt.tuple.IdentityWrapper; | |
| 42 | import edu.rice.cs.plt.lambda.Thunk; | |
| 43 | import edu.rice.cs.plt.lambda.Lambda; | |
| 44 | import edu.rice.cs.plt.lambda.LambdaUtil; | |
| 45 | ||
| 46 | /** | |
| 47 | * <p>A stack used to store the arguments of a recursive invocation in order to prevent | |
| 48 | * infinite recursion. By checking that a given argument has not been used previously before | |
| 49 | * recurring, a client can prevent infinite recursion in some circumstances (such as | |
| 50 | * when traversing an infinite, immutable data structure).</p> | |
| 51 | * | |
| 52 | * <p>While {@link RecursionStack} allows arbitrary application result values to be provided | |
| 53 | * for the infinite case, this class follows a stricter discipline: the infinite case result | |
| 54 | * must be provided at the time of the <em>first</em> invocation of an argument; that value | |
| 55 | * will be stored, and a second invocation will return it. In this way, the result of | |
| 56 | * a recursive computation is always precomputed -- that is, it must be determined before | |
| 57 | * the computation takes place. Classes like {@link edu.rice.cs.plt.lambda.DelayedThunk} can be | |
| 58 | * used to create precomputed values, providing an initial "empty box" that can be "filled" when | |
| 59 | * computation is complete. This allows the definition, for example, of data structures that | |
| 60 | * contain themselves. Due to the restricted applicability of this class (in comparison to | |
| 61 | * {@code RecursionStack}), methods that involve invoking {@code Runnable}s or recurring multiple | |
| 62 | * times based on a threshold value are not defined here.</p> | |
| 63 | * | |
| 64 | * <p>The client may either choose to explicity check for containment, {@link #push} the argument, | |
| 65 | * recur, and then {@link #pop}, or invoke one of a variety of lambda-based methods that perform | |
| 66 | * these bookkeeping tasks automatically. In the latter case, when an exception occurs between | |
| 67 | * a {@code push} and a matching {@code pop}, the {@code pop} is guaranteed to execute before | |
| 68 | * the exception propagates upward. Thus, clients who do not directly invoke {@link #push} | |
| 69 | * and {@link #pop} may assume that the stack is always in a consistent state.</p> | |
| 70 | * | |
| 71 | * @see RecursionStack | |
| 72 | * @see PrecomputedRecursionStack2 | |
| 73 | * @see PrecomputedRecursionStack3 | |
| 74 | * @see PrecomputedRecursionStack4 | |
| 75 | */ | |
| 76 | public class PrecomputedRecursionStack<T, R> { | |
| 77 | ||
| 78 | private final Lambda<? super T, ? extends Wrapper<T>> _wrapperFactory; | |
| 79 | private final Map<Wrapper<T>, Lambda<? super T, ? extends R>> _previous; | |
| 80 | private final LinkedList<Wrapper<T>> _stack; | |
| 81 | ||
| 82 | /** Create an empty recursion stack with an {@link IdentityWrapper} factory */ | |
| 83 | 0 | public PrecomputedRecursionStack() { this(IdentityWrapper.<T>factory()); } |
| 84 | ||
| 85 | /** | |
| 86 | * Create an empty recursion stack with the given {@code Wrapper} factory | |
| 87 | * @param wrapperFactory A lambda used to produce a wrapper for values placed on the | |
| 88 | * stack. This provides clients with control over the method used | |
| 89 | * to determine if a value has been seen previously. | |
| 90 | */ | |
| 91 | 0 | public PrecomputedRecursionStack(Lambda<? super T, ? extends Wrapper<T>> wrapperFactory) { |
| 92 | 0 | _wrapperFactory = wrapperFactory; |
| 93 | 0 | _previous = new HashMap<Wrapper<T>, Lambda<? super T, ? extends R>>(); |
| 94 | 0 | _stack = new LinkedList<Wrapper<T>>(); |
| 95 | } | |
| 96 | ||
| 97 | /** | |
| 98 | * @return {@code true} iff a value identical (according to {@code ==}) to {@code arg} | |
| 99 | * is currently on the stack | |
| 100 | */ | |
| 101 | 0 | public boolean contains(T arg) { return _previous.containsKey(_wrapperFactory.value(arg)); } |
| 102 | ||
| 103 | /** | |
| 104 | * @return The infinite-case result provided for {@code arg} | |
| 105 | * @throws IllegalStateException If {@code arg} is not on the stack | |
| 106 | */ | |
| 107 | 0 | public R get(T arg) { |
| 108 | 0 | Lambda<? super T, ? extends R> result = _previous.get(_wrapperFactory.value(arg)); |
| 109 | 0 | if (result == null) { throw new IllegalArgumentException("Value is not on the stack"); } |
| 110 | 0 | return result.value(arg); |
| 111 | } | |
| 112 | ||
| 113 | /** | |
| 114 | * Add {@code arg} to the top of the stack with the given infinite-case result. | |
| 115 | * @throws IllegalArgumentException If {@code arg} is already on the stack | |
| 116 | */ | |
| 117 | 0 | public void push(T arg, R value) { push(arg, (Lambda<Object, R>) LambdaUtil.valueLambda(value)); } |
| 118 | ||
| 119 | /** | |
| 120 | * Add {@code arg} to the top of the stack with the given thunk producing its infinite-case result. | |
| 121 | * @throws IllegalArgumentException If {@code arg} is already on the stack | |
| 122 | */ | |
| 123 | 0 | public void push(T arg, Thunk<? extends R> value) { |
| 124 | 0 | push(arg, (Lambda<Object, ? extends R>) LambdaUtil.promote(value)); |
| 125 | } | |
| 126 | ||
| 127 | /** | |
| 128 | * Add {@code arg} to the top of the stack with the given lambda producing its infinite-case result. | |
| 129 | * @throws IllegalArgumentException If {@code arg} is already on the stack | |
| 130 | */ | |
| 131 | 0 | public void push(T arg, Lambda<? super T, ? extends R> value) { |
| 132 | 0 | Wrapper<T> wrapped = _wrapperFactory.value(arg); |
| 133 | 0 | if (_previous.containsKey(wrapped)) { |
| 134 | 0 | throw new IllegalArgumentException("arg is already on the stack"); |
| 135 | } | |
| 136 | 0 | _stack.addLast(wrapped); |
| 137 | 0 | _previous.put(wrapped, value); |
| 138 | } | |
| 139 | ||
| 140 | /** | |
| 141 | * Remove {@code arg} from the top of the stack | |
| 142 | * @throws IllegalArgumentException If {@code arg} is not at the top of the stack | |
| 143 | */ | |
| 144 | 0 | public void pop(T arg) { |
| 145 | 0 | Wrapper<T> wrapped = _wrapperFactory.value(arg); |
| 146 | 0 | if (_stack.isEmpty() || !_stack.getLast().equals(wrapped)) { |
| 147 | 0 | throw new IllegalArgumentException("arg is not on top of the stack"); |
| 148 | } | |
| 149 | 0 | _stack.removeLast(); |
| 150 | 0 | _previous.remove(wrapped); |
| 151 | } | |
| 152 | ||
| 153 | /** @return The current size (depth) of the stack */ | |
| 154 | 0 | public int size() { return _stack.size(); } |
| 155 | ||
| 156 | /** @return {@code true} iff the stack is currently empty */ | |
| 157 | 0 | public boolean isEmpty() { return _stack.isEmpty(); } |
| 158 | ||
| 159 | /** | |
| 160 | * Evaluate the given thunk, unless {@code arg} is already on the stack; push {@code arg} | |
| 161 | * onto the stack with the given precomputed result during {@code thunk}'s evaluation | |
| 162 | * | |
| 163 | * @return The value of {@code thunk}, or a previously-provided precomputed value | |
| 164 | */ | |
| 165 | 0 | public R apply(Thunk<? extends R> thunk, R precomputed, T arg) { |
| 166 | 0 | if (!contains(arg)) { |
| 167 | 0 | push(arg, precomputed); |
| 168 | 0 | try { return thunk.value(); } |
| 169 | 0 | finally { pop(arg); } |
| 170 | } | |
| 171 | 0 | else { return get(arg); } |
| 172 | } | |
| 173 | ||
| 174 | /** | |
| 175 | * Evaluate the given thunk, unless {@code arg} is already on the stack; push {@code arg} | |
| 176 | * onto the stack with the given precomputed result during {@code thunk}'s evaluation | |
| 177 | * | |
| 178 | * @return The value of {@code thunk}, or a previously-provided precomputed value | |
| 179 | */ | |
| 180 | 0 | public R apply(Thunk<? extends R> thunk, Thunk<? extends R> precomputed, T arg) { |
| 181 | 0 | if (!contains(arg)) { |
| 182 | 0 | push(arg, precomputed); |
| 183 | 0 | try { return thunk.value(); } |
| 184 | 0 | finally { pop(arg); } |
| 185 | } | |
| 186 | 0 | else { return get(arg); } |
| 187 | } | |
| 188 | ||
| 189 | /** | |
| 190 | * Evaluate the given thunk, unless {@code arg} is already on the stack; push {@code arg} | |
| 191 | * onto the stack with the given precomputed result during {@code thunk}'s evaluation | |
| 192 | * | |
| 193 | * @return The value of {@code thunk}, or a previously-provided precomputed value | |
| 194 | */ | |
| 195 | 0 | public R apply(Thunk<? extends R> thunk, Lambda<? super T, ? extends R> precomputed, T arg) { |
| 196 | 0 | if (!contains(arg)) { |
| 197 | 0 | push(arg, precomputed); |
| 198 | 0 | try { return thunk.value(); } |
| 199 | 0 | finally { pop(arg); } |
| 200 | } | |
| 201 | 0 | else { return get(arg); } |
| 202 | } | |
| 203 | ||
| 204 | /** | |
| 205 | * Evaluate the given lambda with argument {@code arg}, unless {@code arg} is already on the | |
| 206 | * stack; push {@code arg} onto the stack with the given precomputed result during | |
| 207 | * {@code lambda}'s evaluation | |
| 208 | * | |
| 209 | * @return The value of {@code lambda}, or a previously-provided precomputed value | |
| 210 | */ | |
| 211 | 0 | public R apply(Lambda<? super T, ? extends R> lambda, R precomputed, T arg) { |
| 212 | 0 | if (!contains(arg)) { |
| 213 | 0 | push(arg, precomputed); |
| 214 | 0 | try { return lambda.value(arg); } |
| 215 | 0 | finally { pop(arg); } |
| 216 | } | |
| 217 | 0 | else { return get(arg); } |
| 218 | } | |
| 219 | ||
| 220 | /** | |
| 221 | * Evaluate the given lambda with argument {@code arg}, unless {@code arg} is already on the | |
| 222 | * stack; push {@code arg} onto the stack with the given precomputed result during | |
| 223 | * {@code lambda}'s evaluation | |
| 224 | * | |
| 225 | * @return The value of {@code lambda}, or a previously-provided precomputed value | |
| 226 | */ | |
| 227 | 0 | public R apply(Lambda<? super T, ? extends R> lambda, Thunk<? extends R> precomputed, T arg) { |
| 228 | 0 | if (!contains(arg)) { |
| 229 | 0 | push(arg, precomputed); |
| 230 | 0 | try { return lambda.value(arg); } |
| 231 | 0 | finally { pop(arg); } |
| 232 | } | |
| 233 | 0 | else { return get(arg); } |
| 234 | } | |
| 235 | ||
| 236 | /** | |
| 237 | * Evaluate the given lambda with argument {@code arg}, unless {@code arg} is already on the | |
| 238 | * stack; push {@code arg} onto the stack with the given precomputed result during | |
| 239 | * {@code lambda}'s evaluation | |
| 240 | * | |
| 241 | * @return The value of {@code lambda}, or a previously-provided precomputed value | |
| 242 | */ | |
| 243 | 0 | public R apply(Lambda<? super T, ? extends R> lambda, Lambda<? super T, ? extends R> precomputed, |
| 244 | T arg) { | |
| 245 | 0 | if (!contains(arg)) { |
| 246 | 0 | push(arg, precomputed); |
| 247 | 0 | try { return lambda.value(arg); } |
| 248 | 0 | finally { pop(arg); } |
| 249 | } | |
| 250 | 0 | else { return get(arg); } |
| 251 | } | |
| 252 | ||
| 253 | /** Call the constructor (allows the type arguments to be inferred) */ | |
| 254 | 0 | public static <T, R> PrecomputedRecursionStack<T, R> make() { |
| 255 | 0 | return new PrecomputedRecursionStack<T, R>(); |
| 256 | } | |
| 257 | ||
| 258 | /** Call the constructor (allows the type arguments to be inferred) */ | |
| 259 | 0 | public static <T, R> PrecomputedRecursionStack<T, R> |
| 260 | make(Lambda<? super T, ? extends Wrapper<T>> wrapperFactory) { | |
| 261 | 0 | return new PrecomputedRecursionStack<T, R>(wrapperFactory); |
| 262 | } | |
| 263 | ||
| 264 | } |
|
||||||||||
