From commons-dev-return-41473-apmail-jakarta-commons-dev-archive=jakarta.apache.org@jakarta.apache.org Mon Dec 01 08:28:02 2003 Return-Path: Delivered-To: apmail-jakarta-commons-dev-archive@www.apache.org Received: (qmail 45083 invoked from network); 1 Dec 2003 08:28:02 -0000 Received: from daedalus.apache.org (HELO mail.apache.org) (208.185.179.12) by minotaur-2.apache.org with SMTP; 1 Dec 2003 08:28:02 -0000 Received: (qmail 64028 invoked by uid 500); 1 Dec 2003 08:27:33 -0000 Delivered-To: apmail-jakarta-commons-dev-archive@jakarta.apache.org Received: (qmail 63973 invoked by uid 500); 1 Dec 2003 08:27:33 -0000 Mailing-List: contact commons-dev-help@jakarta.apache.org; run by ezmlm Precedence: bulk List-Unsubscribe: List-Subscribe: List-Help: List-Post: List-Id: "Jakarta Commons Developers List" Reply-To: "Jakarta Commons Developers List" Delivered-To: mailing list commons-dev@jakarta.apache.org Received: (qmail 63929 invoked by uid 500); 1 Dec 2003 08:27:32 -0000 Received: (qmail 63791 invoked from network); 1 Dec 2003 08:27:31 -0000 Received: from unknown (HELO minotaur.apache.org) (209.237.227.194) by daedalus.apache.org with SMTP; 1 Dec 2003 08:27:31 -0000 Received: (qmail 44616 invoked by uid 1304); 1 Dec 2003 08:27:54 -0000 Date: 1 Dec 2003 08:27:54 -0000 Message-ID: <20031201082754.44615.qmail@minotaur.apache.org> From: rwaldhoff@apache.org To: jakarta-commons-sandbox-cvs@apache.org Subject: cvs commit: jakarta-commons-sandbox/functor/src/test/org/apache/commons/functor/example/kata/two TestBinaryChop.java X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N X-Spam-Rating: minotaur-2.apache.org 1.6.2 0/1000/N rwaldhoff 2003/12/01 00:27:54 Modified: functor/src/test/org/apache/commons/functor/example/kata/two TestBinaryChop.java Log: more examples, more tests Revision Changes Path 1.3 +72 -6 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.2 retrieving revision 1.3 diff -u -r1.2 -r1.3 --- TestBinaryChop.java 1 Dec 2003 07:46:13 -0000 1.2 +++ TestBinaryChop.java 1 Dec 2003 08:27:54 -0000 1.3 @@ -62,6 +62,9 @@ import junit.framework.TestCase; import junit.framework.TestSuite; +import org.apache.commons.functor.Algorithms; +import org.apache.commons.functor.Function; +import org.apache.commons.functor.generator.util.IntegerRange; import org.apache.commons.functor.util.BinarySearch; /** @@ -110,6 +113,13 @@ assertEquals(-1, chopper.find(4, new int[] { 1, 3, 5, 7 })); assertEquals(-1, chopper.find(6, new int[] { 1, 3, 5, 7 })); assertEquals(-1, chopper.find(8, new int[] { 1, 3, 5, 7 })); + + List largeList = (List)(new IntegerRange(0,100001).toCollection()); + assertEquals(-1, chopper.find(new Integer(-5),largeList)); + assertEquals(100000, chopper.find(new Integer(100000),largeList)); + assertEquals(0, chopper.find(new Integer(0),largeList)); + assertEquals(50000, chopper.find(new Integer(50000),largeList)); + } public void testIterative() { @@ -124,11 +134,11 @@ int comp = ((Comparable)(list.get(cur))).compareTo(seeking); if(comp == 0) { return cur; - } else if(comp > 0) { - high = cur; - } else { + } else if(comp < 0) { if(low == cur) { cur++; } low = cur; + } else { + high = cur; } } return -1; @@ -158,8 +168,64 @@ } }); } + + public void testRecursive2() { + chopTest( + new BaseBinaryChop() { + public int find(Object seeking, List list) { + return find(seeking,list,0,list.size()); + } + + private int find(Object seeking, List list, int low, int high) { + if(low >= high) { + return -1; + } else { + int cur = (high+low)/2; + int comp = ((Comparable)(list.get(cur))).compareTo(seeking); + if(comp == 0) { + return cur; + } else if(comp < 0) { + if(low == cur) { cur++; } + return find(seeking,list,cur,high); + } else { + return find(seeking,list,low,cur); + } + } + } + }); + } + public void testExplicitTailRecursive() { + chopTest( + new BaseBinaryChop() { + public int find(final Object seeking, final List list) { + return ((Number)Algorithms.recurse( + new Function() { + public Object evaluate() { + if(low < high) { + int mid = (high+low)/2; + int comp = ((Comparable)(list.get(mid))).compareTo(seeking); + if(comp == 0) { + return new Integer(mid); + } else if(comp < 0) { + if(mid == low) { mid++; } + low = mid; + return this; + } else { + high = mid; + return this; + } + } else { + return new Integer(-1); + } + } + int high = list.size(); + int low = 0; + })).intValue(); + } + }); + } - public void testTailRecursion() { + public void testImplicitTailRecursive() { chopTest( new BaseBinaryChop() { public int find(Object seeking, List list) { --------------------------------------------------------------------- To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org For additional commands, e-mail: commons-dev-help@jakarta.apache.org