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/java/org/apache/commons/functor Algorithms.java
Date Mon, 01 Dec 2003 20:27:20 GMT
rwaldhoff    2003/12/01 12:27:20

  Modified:    functor/src/test/org/apache/commons/functor/example/kata/two
                        TestBinaryChop.java
               functor/src/java/org/apache/commons/functor Algorithms.java
  Log:
  more kata two examples
  
  Revision  Changes    Path
  1.6       +152 -2    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.5
  retrieving revision 1.6
  diff -u -r1.5 -r1.6
  --- TestBinaryChop.java	1 Dec 2003 19:22:41 -0000	1.5
  +++ TestBinaryChop.java	1 Dec 2003 20:27:20 -0000	1.6
  @@ -65,6 +65,8 @@
   
   import org.apache.commons.functor.Algorithms;
   import org.apache.commons.functor.Function;
  +import org.apache.commons.functor.Predicate;
  +import org.apache.commons.functor.Procedure;
   import org.apache.commons.functor.generator.util.IntegerRange;
   
   /**
  @@ -205,6 +207,154 @@
                       }
                   }
                   return list.isEmpty() ? -1 : (equals(list,low,seeking) ? low : -1);
  +            }
  +        });
  +    }
  +
  +    /*
  +     * At http://onestepback.org/index.cgi/Tech/Programming/Kata/KataTwoVariation1.rdoc,
  +     * Jim Weirich discusses Kata Two from the perspective of loop invariants.
  +     * 
  +     * Loop invariants provide a way of deductive reasoning about loops.
  +     *   
  +     * Let P, Q. and R be predicates and A and B be
  +     * procedures.  Note that if:
  +     *   assert(P.test()); 
  +     *   A.run(); 
  +     *   assert(Q.test());
  +     * and 
  +     *   assert(Q.test()); 
  +     *   B.run(); 
  +     *   assert(R.test());
  +     * are both valid, then:
  +     *   assert(P.test()); 
  +     *   A.run(); 
  +     *   B.run(); 
  +     *   assert(R.test());
  +     * is valid as well.
  +     * 
  +     * Similiarly, if INV and TERM are predicates and BODY is a procedure,
  +     * then if:
  +     *   assert(INV.test()); 
  +     *   BODY.run(); 
  +     *   assert(INV.test());
  +     * is valid, then so is:
  +     *   assert(INV.test()); 
  +     *   do { BODY.run(); } while(! TERM.test() ); 
  +     *   assert(INV.test());
  +     *   assert(TERM.test());
  +     * 
  +     * Here INV is an "loop invariant", a statement that is true for every
  +     * single iteration through the loop.  TERM is a terminating condition,
  +     * a statement that is true (by construction) when the loop exits.
  +     * 
  +     * We can use loop invariants to reason about our iterative binary 
  +     * search loop.  In particular, note that:
  +     * 
  +     * // assert that the list is empty, or 
  +     * // the result index is between 
  +     * // low (inclusive) and high (exclusive),
  +     * // or high is 0 (the list is empty)
  +     * Predicate INV = new Predicate() {
  +     *   public boolean test() {
  +     *    return high == 0 || 
  +     *          (low <= result && result < high);
  +     *   }
  +     * };
  +     * 
  +     * is a valid invariant in our binary search, and that:
  +     *
  +     * Predicate TERM = new Predicate() {
  +     *   public boolean test() {
  +     *    return (high - low) <= 1;
  +     *   }
  +     * };
  +     * 
  +     * is a valid terminating condition.
  +     * 
  +     * The BODY in our case simply moves the endpoints 
  +     * closer together, without violating  
  +     * our invariant:
  +     * 
  +     * Procedure BODY = new Procedure() {
  +     *   public void run() {
  +     *     int mid = (high + low) / 2;
  +     *     if(greaterThan(list,mid,seeking)) {
  +     *       high = mid;
  +     *     } else {
  +     *       low = mid;
  +     *     }
  +     *   }
  +     * };
  +     * 
  +     * One could assert our invariant before and after
  +     * the execution of BODY, and the terminating condition
  +     * at the end of the loop, but we can tell by construction
  +     * that these assertions will hold.
  +     * 
  +     * Using the functor framework, we can make these notions
  +     * explict.  Specifically, the construction above is:
  +     * 
  +     *   Algorithms.dountil(BODY,TERM); 
  +     * 
  +     * Since we'll want to share state among the TERM and BODY,
  +     * let's declare a single interface for the TERM Predicate and
  +     * the BODY Procedure.  We'll be calculating a result within
  +     * the loop, so let's add a Function implementation as well,
  +     * as a way of retrieving that result: 
  +     */
  +    interface Loop extends Predicate, Procedure, Function {
  +        /** The terminating condition. */
  +        boolean test();
  +        /** The loop body. */
  +        void run();
  +        /** The result of executing the loop. */
  +        Object evaluate();
  +    };
  +
  +    /*
  +     * Now we can use the Algorithms.dountil method to 
  +     * execute that loop: 
  +     */
  +    public void testIterative2() {
  +        chopTest(new BaseBinaryChop() {
  +            
  +            public int find(final Object seeking, final List list) {
  +                Loop loop = new Loop() {
  +                    int high = list.size();
  +                    int low = 0;
  +
  +                    /** Our terminating condition. */
  +                    public boolean test() {
  +                        return (high - low) <= 1;                    
  +                    }
  +                    
  +                    /** Our loop body. */
  +                    public void run() {
  +                        {
  +                            int mid = (high + low) / 2;
  +                            if(greaterThan(list,mid,seeking)) {
  +                                high = mid;
  +                            } else {
  +                                low = mid;
  +                            }
  +                        }
  +                    }
  +                    
  +                    /** 
  +                     * A way of returning the result 
  +                     * at the end of the loop. 
  +                     */
  +                    public Object evaluate() {
  +                        return new Integer(
  +                            list.isEmpty() ? 
  +                            -1 : 
  +                            (BaseBinaryChop.equals(list,low,seeking) ? low : -1));    
                   
  +                    }
  +                    
  +                };
  +                Algorithms.untildo(loop,loop);
  +                return ((Number)loop.evaluate()).intValue();
               }
           });
       }
  
  
  
  1.16      +19 -2     jakarta-commons-sandbox/functor/src/java/org/apache/commons/functor/Algorithms.java
  
  Index: Algorithms.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/functor/src/java/org/apache/commons/functor/Algorithms.java,v
  retrieving revision 1.15
  retrieving revision 1.16
  diff -u -r1.15 -r1.16
  --- Algorithms.java	25 Nov 2003 21:16:15 -0000	1.15
  +++ Algorithms.java	1 Dec 2003 20:27:20 -0000	1.16
  @@ -67,6 +67,7 @@
   import org.apache.commons.functor.core.collection.FilteredIterator;
   import org.apache.commons.functor.core.collection.TransformedIterator;
   import org.apache.commons.functor.core.composite.ConditionalUnaryProcedure;
  +import org.apache.commons.functor.core.composite.Not;
   import org.apache.commons.functor.core.composite.UnaryNot;
   import org.apache.commons.functor.generator.BaseGenerator;
   import org.apache.commons.functor.generator.Generator;
  @@ -345,6 +346,22 @@
                   gen.run(new ConditionalUnaryProcedure(pred,proc,NoOp.instance()));
               }
           };
  +    }
  +
  +    public static final void dountil(Procedure proc, Predicate pred) {
  +        dowhile(proc,Not.not(pred));
  +    }
  +
  +    public static final void dowhile(Procedure proc, Predicate pred) {
  +        do { proc.run(); } while(pred.test());
  +    }
  +
  +    public static final void untildo(Predicate pred, Procedure proc) {
  +        whiledo(Not.not(pred),proc);
  +    }
  +
  +    public static final void whiledo(Predicate pred, Procedure proc) {
  +        while(pred.test()) { proc.run(); }
       }
   
       /**
  
  
  

---------------------------------------------------------------------
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