You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by rw...@apache.org on 2003/12/01 21:27:20 UTC
cvs commit: jakarta-commons-sandbox/functor/src/java/org/apache/commons/functor Algorithms.java
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