Clover coverage report - PLT Utilities Test Coverage (plt-20120304-r5436)
Coverage timestamp: Sat Mar 3 2012 22:01:56 CST
Overview   Package   File
    FRAMES   NO FRAMES  
file stats: LOC: 361   Methods: 26
NCLOC: 161   Classes: 1
 
 Source file Conditionals Statements Methods TOTAL
RecursionStack.java 8.8% 17.6% 26.9% 17.3%
coverage coverage
 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 edu.rice.cs.plt.collect.Multiset;
 39    import edu.rice.cs.plt.collect.HashMultiset;
 40    import edu.rice.cs.plt.tuple.Wrapper;
 41    import edu.rice.cs.plt.tuple.IdentityWrapper;
 42    import edu.rice.cs.plt.lambda.Runnable1;
 43    import edu.rice.cs.plt.lambda.Thunk;
 44    import edu.rice.cs.plt.lambda.Lambda;
 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>The client may either choose to explicity check for containment, {@link #push} the
 53    * argument, recur, and then {@link #pop}, or invoke one of a variety of lambda-based
 54    * methods that perform these bookkeeping tasks automatically. In the latter case, when an
 55    * exception occurs between a {@code push} and a matching {@code pop}, the {@code pop} is
 56    * guaranteed to execute before the exception propagates upward. Thus, clients who do not
 57    * directly invoke {@link #push} and {@link #pop} may assume that the stack is always in a
 58    * consistent state.</p>
 59    *
 60    * @see PrecomputedRecursionStack
 61    * @see RecursionStack2
 62    * @see RecursionStack3
 63    * @see RecursionStack4
 64    */
 65    public class RecursionStack<T> {
 66   
 67    private final Lambda<? super T, ? extends Wrapper<T>> _wrapperFactory;
 68    private final Multiset<Wrapper<T>> _previous;
 69    private final LinkedList<Wrapper<T>> _stack;
 70   
 71    /** Create an empty recursion stack with an {@link IdentityWrapper} factory */
 72  181 public RecursionStack() { this(IdentityWrapper.<T>factory()); }
 73   
 74    /**
 75    * Create an empty recursion stack with the given {@code Wrapper} factory
 76    * @param wrapperFactory A lambda used to produce a wrapper for values placed on the
 77    * stack. This provides clients with control over the method used
 78    * to determine if a value has been seen previously.
 79    */
 80  181 public RecursionStack(Lambda<? super T, ? extends Wrapper<T>> wrapperFactory) {
 81  181 _wrapperFactory = wrapperFactory;
 82  181 _previous = new HashMultiset<Wrapper<T>>();
 83  181 _stack = new LinkedList<Wrapper<T>>();
 84    }
 85   
 86    /**
 87    * @return {@code true} iff a value identical (according to {@code ==}) to {@code arg}
 88    * is currently on the stack
 89    */
 90  182 public boolean contains(T arg) { return _previous.contains(_wrapperFactory.value(arg)); }
 91   
 92    /**
 93    * @return {@code true} iff at least {@code threshold} values identical (according to
 94    * {@code ==}) to {@code arg} are currently on the stack
 95    */
 96  0 public boolean contains(T arg, int threshold) {
 97  0 return _previous.count(_wrapperFactory.value(arg)) >= threshold;
 98    }
 99   
 100    /** Add {@code arg} to the top of the stack */
 101  182 public void push(T arg) {
 102  182 Wrapper<T> wrapped = _wrapperFactory.value(arg);
 103  182 _stack.addLast(wrapped);
 104  182 _previous.add(wrapped);
 105    }
 106   
 107    /**
 108    * Remove {@code arg} from the top of the stack
 109    * @throws IllegalArgumentException If {@code arg} is not at the top of the stack
 110    */
 111  182 public void pop(T arg) {
 112  182 Wrapper<T> wrapped = _wrapperFactory.value(arg);
 113  182 if (_stack.isEmpty() || !_stack.getLast().equals(wrapped)) {
 114  0 throw new IllegalArgumentException("arg is not on top of the stack");
 115    }
 116  182 _stack.removeLast();
 117  182 _previous.remove(wrapped);
 118    }
 119   
 120    /** @return The current size (depth) of the stack */
 121  0 public int size() { return _stack.size(); }
 122   
 123    /** @return {@code true} iff the stack is currently empty */
 124  182 public boolean isEmpty() { return _stack.isEmpty(); }
 125   
 126    /**
 127    * Run the given runnable, unless {@code arg} is already on the stack; push {@code arg}
 128    * onto the stack during runnable execution
 129    */
 130  0 public void run(Runnable r, T arg) {
 131  0 if (!contains(arg)) {
 132  0 push(arg);
 133  0 try { r.run(); }
 134  0 finally { pop(arg); }
 135    }
 136    }
 137   
 138    /**
 139    * Run the given runnable, unless {@code threshold} instances of {@code arg} are already
 140    * on the stack; push {@code arg} onto the stack during runnable execution
 141    */
 142  0 public void run(Runnable r, T arg, int threshold) {
 143  0 if (!contains(arg, threshold)) {
 144  0 push(arg);
 145  0 try { r.run(); }
 146  0 finally { pop(arg); }
 147    }
 148    }
 149   
 150    /**
 151    * If {@code arg} is not on the stack, run {@code r}; otherwise, run {@code infiniteCase}.
 152    * In either case, push {@code arg} onto the stack during runnable execution.
 153    */
 154  0 public void run(Runnable r, Runnable infiniteCase, T arg) {
 155  0 Runnable toRun = (contains(arg) ? infiniteCase : r);
 156  0 push(arg);
 157  0 try { toRun.run(); }
 158  0 finally { pop(arg); }
 159    }
 160   
 161    /**
 162    * If less than {@code threshold} instances of {@code arg} are on the stack, run {@code r};
 163    * otherwise, run {@code infiniteCase}. In either case, push {@code arg} onto the stack
 164    * during runnable execution.
 165    */
 166  0 public void run(Runnable r, Runnable infiniteCase, T arg, int threshold) {
 167  0 Runnable toRun = (contains(arg, threshold) ? infiniteCase : r);
 168  0 push(arg);
 169  0 try { toRun.run(); }
 170  0 finally { pop(arg); }
 171    }
 172   
 173    /**
 174    * Run the given runnable with argument {@code arg}, unless {@code arg} is already on the
 175    * stack; push {@code arg} onto the stack during runnable execution
 176    */
 177  0 public <V extends T> void run(Runnable1<? super V> r, V arg) {
 178  0 if (!contains(arg)) {
 179  0 push(arg);
 180  0 try { r.run(arg); }
 181  0 finally { pop(arg); }
 182    }
 183    }
 184   
 185    /**
 186    * Run the given runnable with argument {@code arg}, unless {@code threshold} instances
 187    * of {@code arg} are already on the stack; push {@code arg} onto the stack during
 188    * runnable execution
 189    */
 190  0 public <V extends T> void run(Runnable1<? super V> r, V arg, int threshold) {
 191  0 if (!contains(arg, threshold)) {
 192  0 push(arg);
 193  0 try { r.run(arg); }
 194  0 finally { pop(arg); }
 195    }
 196    }
 197   
 198    /**
 199    * If {@code arg} is not on the stack, run {@code r} with argument {@code arg}; otherwise,
 200    * run {@code infiniteCase}. In either case, push {@code arg} onto the stack during
 201    * runnable execution.
 202    */
 203  0 public <V extends T> void run(Runnable1<? super V> r, Runnable1<? super V> infiniteCase, V arg) {
 204    // The javac type checker is broken here
 205  0 @SuppressWarnings("unchecked") Runnable1<? super V> toRun =
 206  0 (Runnable1<? super V>) (contains(arg) ? infiniteCase : r);
 207  0 push(arg);
 208  0 try { toRun.run(arg); }
 209  0 finally { pop(arg); }
 210    }
 211   
 212    /**
 213    * If less than {@code threshold} instances of {@code arg} are on the stack, run {@code r}
 214    * with argument {@code arg}; otherwise, run {@code infiniteCase}. In either case,
 215    * push {@code arg} onto the stack during runnable execution.
 216    */
 217  0 public <V extends T> void run(Runnable1<? super V> r, Runnable1<? super V> infiniteCase, V arg,
 218    int threshold) {
 219    // The javac type checker is broken here
 220  0 @SuppressWarnings("unchecked") Runnable1<? super V> toRun =
 221  0 (Runnable1<? super V>) (contains(arg, threshold) ? infiniteCase : r);
 222  0 push(arg);
 223  0 try { toRun.run(arg); }
 224  0 finally { pop(arg); }
 225    }
 226   
 227    /**
 228    * Evaluate the given thunk, unless {@code arg} is already on the stack; push {@code arg}
 229    * onto the stack during thunk evaluation
 230    *
 231    * @return The value of {@code thunk}, or {@code infiniteCase}
 232    */
 233  0 public <R> R apply(Thunk<? extends R> thunk, R infiniteCase, T arg) {
 234  0 if (!contains(arg)) {
 235  0 push(arg);
 236  0 try { return thunk.value(); }
 237  0 finally { pop(arg); }
 238    }
 239  0 else { return infiniteCase; }
 240    }
 241   
 242    /**
 243    * Evaluate the given thunk, unless {@code threshold} instances of {@code arg} are already
 244    * on the stack; push {@code arg} onto the stack during thunk evaluation
 245    *
 246    * @return The value of {@code thunk}, or {@code infiniteCase}
 247    */
 248  0 public <R> R apply(Thunk<? extends R> thunk, R infiniteCase, T arg, int threshold) {
 249  0 if (!contains(arg, threshold)) {
 250  0 push(arg);
 251  0 try { return thunk.value(); }
 252  0 finally { pop(arg); }
 253    }
 254  0 else { return infiniteCase; }
 255    }
 256   
 257    /**
 258    * If {@code arg} is not on the stack, evaluate {@code thunk}; otherwise, evaluate
 259    * {@code infiniteCase}. In either case, push {@code arg} onto the stack during
 260    * thunk evaluation.
 261    *
 262    * @return The value of {@code thunk}, or the value of {@code infiniteCase}
 263    */
 264  0 public <R> R apply(Thunk<? extends R> thunk, Thunk<? extends R> infiniteCase, T arg) {
 265  0 Thunk<? extends R> toApply = (contains(arg) ? infiniteCase : thunk);
 266  0 push(arg);
 267  0 try { return toApply.value(); }
 268  0 finally { pop(arg); }
 269    }
 270   
 271    /**
 272    * If less than {@code threshold} instances of {@code arg} are on the stack, evaluate
 273    * {@code thunk}; otherwise, evaluate {@code infiniteCase}. In either case, push
 274    * {@code arg} onto the stack during thunk evaluation.
 275    *
 276    * @return The value of {@code thunk}, or the value of {@code infiniteCase}
 277    */
 278  0 public <R> R apply(Thunk<? extends R> thunk, Thunk<? extends R> infiniteCase, T arg,
 279    int threshold) {
 280  0 Thunk<? extends R> toApply = (contains(arg, threshold) ? infiniteCase : thunk);
 281  0 push(arg);
 282  0 try { return toApply.value(); }
 283  0 finally { pop(arg); }
 284    }
 285   
 286    /**
 287    * Evaluate the given lambda with argument {@code arg}, unless {@code arg} is already on
 288    * the stack; push {@code arg} onto the stack during lambda evaluation
 289    *
 290    * @return The value of {@code lambda}, or {@code infiniteCase}
 291    */
 292  0 public <V extends T, R> R apply(Lambda<? super V, ? extends R> lambda, R infiniteCase, V arg) {
 293  0 if (!contains(arg)) {
 294  0 push(arg);
 295  0 try { return lambda.value(arg); }
 296  0 finally { pop(arg); }
 297    }
 298  0 else { return infiniteCase; }
 299    }
 300   
 301    /**
 302    * Evaluate the given lambda with argument {@code arg}, unless {@code threshold} instances
 303    * of {@code arg} are already on the stack; push {@code arg} onto the stack during
 304    * lambda evaluation
 305    *
 306    * @return The value of {@code lambda}, or {@code infiniteCase}
 307    */
 308  0 public <V extends T, R> R apply(Lambda<? super V, ? extends R> lambda, R infiniteCase, V arg,
 309    int threshold) {
 310  0 if (!contains(arg, threshold)) {
 311  0 push(arg);
 312  0 try { return lambda.value(arg); }
 313  0 finally { pop(arg); }
 314    }
 315  0 else { return infiniteCase; }
 316    }
 317   
 318    /**
 319    * If {@code arg} is not on the stack, evaluate {@code lambda} with argument {@code arg};
 320    * otherwise, evaluate {@code infiniteCase}. In either case, push {@code arg} onto the
 321    * stack during lambda evaluation.
 322    *
 323    * @return The value of {@code lambda}, or the value of {@code infiniteCase}
 324    */
 325  182 public <V extends T, R> R apply(Lambda<? super V, ? extends R> lambda,
 326    Lambda<? super V, ? extends R> infiniteCase, V arg) {
 327    // The javac type checker is broken here
 328  182 @SuppressWarnings("unchecked") Lambda<? super V, ? extends R> toApply =
 329  182 (Lambda<? super V, ? extends R>) (contains(arg) ? infiniteCase : lambda);
 330  182 push(arg);
 331  182 try { return toApply.value(arg); }
 332  182 finally { pop(arg); }
 333    }
 334   
 335    /**
 336    * If less than {@code threshold} instances of {@code arg} are on the stack, evaluate
 337    * {@code lambda} with argument {@code arg}; otherwise, evaluate {@code infiniteCase}.
 338    * In either case, push {@code arg} onto the stack during lambda evaluation.
 339    *
 340    * @return The value of {@code lambda}, or the value of {@code infiniteCase}
 341    */
 342  0 public <V extends T, R> R apply(Lambda<? super V, ? extends R> lambda,
 343    Lambda<? super V, ? extends R> infiniteCase, V arg,
 344    int threshold) {
 345    // The javac type checker is broken here
 346  0 @SuppressWarnings("unchecked") Lambda<? super V, ? extends R> toApply =
 347  0 (Lambda<? super V, ? extends R>) (contains(arg, threshold) ? infiniteCase : lambda);
 348  0 push(arg);
 349  0 try { return toApply.value(arg); }
 350  0 finally { pop(arg); }
 351    }
 352   
 353    /** Call the constructor (allows {@code T} to be inferred) */
 354  0 public static <T> RecursionStack<T> make() { return new RecursionStack<T>(); }
 355   
 356    /** Call the constructor (allows {@code T} to be inferred) */
 357  0 public static <T> RecursionStack<T> make(Lambda<? super T, ? extends Wrapper<T>> wrapperFactory) {
 358  0 return new RecursionStack<T>(wrapperFactory);
 359    }
 360   
 361    }
 
CloverReport generated by Clover Code Coverage v1.3.14
Sat Mar 3 2012 22:01:57 CST.		   Open Source License registered to the DrJava Project. This license of Clover is provided to support the development of DrJava only.