rwaldhoff 2003/12/01 13:14:47 Modified: functor/src/test/org/apache/commons/functor/example/kata/two TestBinaryChop.java Added: functor/src/test/org/apache/commons/functor/example/kata/two EiffelStyleLoop.java Log: more kata two examples Revision Changes Path 1.7 +94 -11 jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two/TestBinaryChop.java Index: TestBinaryChop.java =================================================================== RCS file: /home/cvs/jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two/TestBinaryChop.java,v retrieving revision 1.6 retrieving revision 1.7 diff -u -r1.6 -r1.7 --- TestBinaryChop.java 1 Dec 2003 20:27:20 -0000 1.6 +++ TestBinaryChop.java 1 Dec 2003 21:14:46 -0000 1.7 @@ -240,7 +240,7 @@ * assert(INV.test()); * is valid, then so is: * assert(INV.test()); - * do { BODY.run(); } while(! TERM.test() ); + * while(! TERM.test() ) { BODY.run(); } * assert(INV.test()); * assert(TERM.test()); * @@ -316,7 +316,7 @@ * Now we can use the Algorithms.dountil method to * execute that loop: */ - public void testIterative2() { + public void testIterativeWithInvariants() { chopTest(new BaseBinaryChop() { public int find(final Object seeking, final List list) { @@ -331,13 +331,11 @@ /** Our loop body. */ public void run() { - { - int mid = (high + low) / 2; - if(greaterThan(list,mid,seeking)) { - high = mid; - } else { - low = mid; - } + int mid = (high + low) / 2; + if(greaterThan(list,mid,seeking)) { + high = mid; + } else { + low = mid; } } @@ -359,6 +357,91 @@ }); } + /* + * Jim Weirich notes how Eiffel is very explict about loop invariants: + * + * from + * low := list.lower + * high := list.upper + 1 + * invariant + * lower_limit: -- low <= result (this is just a comment) + * upper_limit: -- high < result (this is just a comment) + * variant + * high - low + * until + * (high - low) <= 1 + * loop + * mid := (high + low) // 2 + * if list.at(mid) > seeking then + * high := mid + * else + * low := mid + * end + * end + * + * We can do that too, see EiffelStyleLoop. + */ + class BinarySearchLoop extends EiffelStyleLoop { + BinarySearchLoop(Object aSeeking, List aList) { + seeking = aSeeking; + list = aList; + + from(new Procedure() { + public void run() { + low = 0; + high = list.size(); + } + }); + + invariant(new Predicate() { + public boolean test() { + return high == 0 || low < high; + } + }); + + variant(new Function() { + public Object evaluate() { + return new Integer(high - low); + } + }); + + until(new Predicate() { + public boolean test() { + return high - low <= 1; + } + }); + + loop(new Procedure() { + public void run() { + int mid = (high + low) / 2; + if(BaseBinaryChop.greaterThan(list,mid,seeking)) { + high = mid; + } else { + low = mid; + } + } + }); + } + + int getResult() { + return list.isEmpty() ? -1 : BaseBinaryChop.equals(list,low,seeking) ? low : -1; + } + + private int high; + private int low; + private final Object seeking; + private final List list; + } + + public void testIterativeWithInvariantsAndAssertions() { + chopTest(new BaseBinaryChop() { + public int find(Object seeking, List list) { + BinarySearchLoop loop = new BinarySearchLoop(seeking,list); + loop.run(); + return loop.getResult(); + }}); + } + /** * A recursive version of that implementation uses * method parameters to track the upper and 1.1 jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two/EiffelStyleLoop.java Index: EiffelStyleLoop.java =================================================================== /* * $Header: /home/cvs/jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two/EiffelStyleLoop.java,v 1.1 2003/12/01 21:14:47 rwaldhoff Exp $ * ==================================================================== * The Apache Software License, Version 1.1 * * Copyright (c) 2003 The Apache Software Foundation. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. The end-user documentation included with the redistribution, * if any, must include the following acknowledgment: * "This product includes software developed by the * Apache Software Foundation (http://www.apache.org/)." * Alternately, this acknowledgment may appear in the software itself, * if and wherever such third-party acknowledgments normally appear. * * 4. The names "The Jakarta Project", "Commons", and "Apache Software * Foundation" must not be used to endorse or promote products derived * from this software without prior written permission. For written * permission, please contact [EMAIL PROTECTED] * * 5. Products derived from this software may not be called "Apache", * nor may "Apache" appear in their name, without prior written * permission of the Apache Software Foundation. * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * ==================================================================== * * This software consists of voluntary contributions made by many * individuals on behalf of the Apache Software Foundation. For more * information on the Apache Software Foundation, please see * <http://www.apache.org/>. * */ package org.apache.commons.functor.example.kata.two; import org.apache.commons.functor.Function; import org.apache.commons.functor.Predicate; import org.apache.commons.functor.Procedure; import org.apache.commons.functor.core.ConstantPredicate; import org.apache.commons.functor.core.NoOp; /** * Supports an Eiffel style loop construct. * <pre> * new EiffelStyleLoop() * .from(new Procedure() { public void run() {} }) // init code * .invariant(new Predicate() { public boolean test() {} }) // invariants * .variant(new Procedure() { public Object evaluate() {} }) // diminishing comparable value * // or * // .variant(new Predicate() { public boolean test() {} }) // more invariants * .until(new Predicate() { public boolean test() {} }) // terminating condition * .loop(new Procedure() { public void run() {} }) // the acutal loop * .run(); * </pre> * * Note that <tt>new EiffelStyleLoop().run()</tt> executes just fine. * You only need to set the parts of the loop you want to use. * * @version $Revision: 1.1 $ $Date: 2003/12/01 21:14:47 $ * @author Rodney Waldhoff */ public class EiffelStyleLoop implements Procedure { public EiffelStyleLoop from(Procedure procedure) { from = procedure; return this; } public EiffelStyleLoop invariant(Predicate predicate) { invariant = predicate; return this; } public EiffelStyleLoop variant(Predicate predicate) { variant = predicate; return this; } public EiffelStyleLoop variant(final Function function) { return variant(new Predicate() { public boolean test() { boolean result = true; Comparable next = (Comparable)(function.evaluate()); if(null != last) { result = last.compareTo(next) > 0; } last = next; return result; } private Comparable last = null; }); } public EiffelStyleLoop until(Predicate predicate) { until = predicate; return this; } public EiffelStyleLoop loop(Procedure procedure) { loop = procedure; return this; } public void run() { from.run(); assertTrue(invariant.test()); while(! until.test() ) { loop.run(); assertTrue(variant.test()); assertTrue(invariant.test()); } // Note that: // assertTrue(until.test()); // holds here, but isn't necessary since that's // the only way we could get out of the loop // Also note that: // assertTrue(invariant.test()); // holds here, but was the last thing called // before until.test() } private void assertTrue(boolean value) { if(!value) { throw new IllegalStateException("Assertion failed"); } } private Procedure from = NoOp.instance(); private Predicate invariant = ConstantPredicate.trueInstance(); private Predicate variant = ConstantPredicate.trueInstance(); private Predicate until = ConstantPredicate.falseInstance(); private Procedure loop = NoOp.instance(); }
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]