commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From rwaldh...@apache.org
Subject cvs commit: jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two EiffelStyleLoop.java TestBinaryChop.java
Date Mon, 01 Dec 2003 21:14:47 GMT
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 apache@apache.org.
   *
   * 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: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message